fast inversion

[bodrato at mail.dm.unipi.it]

Ciao,

Il Lun, 27 Aprile 2015 4:45 pm, tg at gmplib.org ha scritto:
>   @shell ~/gmp-repo$ tune/speed -s 1-1030 -f 2 -c mpn_neg mpn_com
>   mpn_add_1_inplace.1
>   overhead 6.78 cycles, precision 10000 units of 2.86e-10 secs, CPU freq
>   3500.08 MHz
>                 mpn_neg       mpn_com mpn_add_1_inplace.1
>   1               #5.68         12.54          6.80
>   2                9.40         13.65         #8.19
>   4               16.25         11.40         #8.22
>   8               31.56         16.01         #6.84

>   1024          3689.67       1472.14         #8.29

> Perhaps mpn_neg should use a native mpn_com...

mpn_neg id defined in gmp.h, where we can not check for HAVE_NATIVE, but I
suspect that also the C version of mpn_com is faster than mpn_neg (in the
former, limbs do not depend on one another, no "carry" propagation).
Should we apply a patch like this?

 diff -r 6e11cd70e19e gmp-h.in
--- a/gmp-h.in	Mon Apr 27 22:46:53 2015 +0200
+++ b/gmp-h.in	Tue Apr 28 22:41:52 2015 +0200
@@ -2191,13 +2191,10 @@
 mp_limb_t
 mpn_neg (mp_ptr __gmp_rp, mp_srcptr __gmp_up, mp_size_t __gmp_n)
 {
-  mp_limb_t __gmp_ul, __gmp_cy;
-  __gmp_cy = 0;
-  do {
-      __gmp_ul = *__gmp_up++;
-      *__gmp_rp++ = -__gmp_ul - __gmp_cy;
-      __gmp_cy |= __gmp_ul != 0;
-  } while (--__gmp_n != 0);
+  mp_limb_t __gmp_cy;
+  mpn_com (__gmp_rp, __gmp_up, __gmp_n);
+  __gmp_cy = 1;
+  __gmp_cy -= mpn_add_1 (__gmp_rp, __gmp_rp, __gmp_n, __gmp_cy);
   return __gmp_cy;
 }
 #endif

It would slow down mpn_neg for small values of n...

Regards,
m

-- 
http://bodrato.it/