mini-gcd

[Marco Bodrato]

Ciao,

While we are looking at gcd, I propose a shorter version for gcd_11 in
mini-gmp.

Meanwhile, we can also define a gcd_1 function... even if this is not
really useful. It would not make sense to give public access to mpn_gcd_1,
because we don't have any division function for the mpn level in mini-gmp
:-)


*** /tmp/extdiff.qIjJF7/gmp.643c931da9bd/mini-gmp/mini-gmp.c	2019-08-22
15:14:09.000000000 +0200
--- /home/bodrato/gmp/mini-gmp/mini-gmp.c	2019-08-22 21:40:30.144348034 +0200
***************
*** 2652,2680 ****
    while ( (v & 1) == 0)
      v >>= 1;

    while (u != v)
      {
        if (u > v)
! 	{
! 	  u -= v;
! 	  do
! 	    u >>= 1;
! 	  while ( (u & 1) == 0);
! 	}
!       else
! 	{
! 	  v -= u;
! 	  do
! 	    v >>= 1;
! 	  while ( (v & 1) == 0);
! 	}
      }
    return u << shift;
  }

  unsigned long
  mpz_gcd_ui (mpz_t g, const mpz_t u, unsigned long v)
  {
    mpz_t t;
    mpz_init_set_ui(t, v);
    mpz_gcd (t, u, t);
--- 2652,2679 ----
    while ( (v & 1) == 0)
      v >>= 1;

    while (u != v)
      {
        if (u > v)
! 	  MP_LIMB_T_SWAP (u, v);
!       v -= u;
!       do
! 	v >>= 1;
!         while ( (v & 1) == 0);
      }
    return u << shift;
  }

+ static mp_limb_t
+ mpn_gcd_1 (mp_srcptr up, mp_size_t un, mp_limb_t v)
+ {
+   mpz_t t;
+   return mpn_gcd_11 (mpz_tdiv_ui (mpz_roinit_n (t, up, un), v), v);
+ }
+
  unsigned long
  mpz_gcd_ui (mpz_t g, const mpz_t u, unsigned long v)
  {
    mpz_t t;
    mpz_init_set_ui(t, v);
    mpz_gcd (t, u, t);
***************
*** 2750,2764 ****
  	  }
  	if (c < 0)
  	  mpz_swap (tu, tv);

  	if (tv->_mp_size == 1)
  	  {
! 	    mp_limb_t vl = tv->_mp_d[0];
! 	    mp_limb_t ul = mpz_tdiv_ui (tu, vl);
! 	    mpz_set_ui (g, mpn_gcd_11 (ul, vl));
  	    break;
  	  }
  	mpz_sub (tu, tu, tv);
        }
    mpz_clear (tu);
    mpz_clear (tv);
--- 2749,2761 ----
  	  }
  	if (c < 0)
  	  mpz_swap (tu, tv);

  	if (tv->_mp_size == 1)
  	  {
! 	    mpz_set_ui (g, mpn_gcd_1 (tu->_mp_d, tu->_mp_size, tv->_mp_d[0]));
  	    break;
  	  }
  	mpz_sub (tu, tu, tv);
        }
    mpz_clear (tu);
    mpz_clear (tv);


Ĝis,
m