TODO for 5.2 v3

[bodrato at mail.dm.unipi.it]

Ciao,

Il Lun, 13 Gennaio 2014 11:57 am, Niels ha scritto:
> bodrato at mail.dm.unipi.it writes:
>> What about _itch functions when the .asm source is used?
>
> They're supposed to exist, and return zero. E.g.,
>
> +PROLOGUE(mpn_cnd_neg_itch)

Oops, I didn't see it :-/

> Nice, but won't make any difference until we have mpn_sec_add_1
> assembly, right?

...well it was wrong too, I wrote MIN instead of MAX... :-/

The following should address your observations.

diff -r 639a0512bdd9 mpn/generic/sec_minvert.c
--- a/mpn/generic/sec_minvert.c	Sun Jan 12 20:27:20 2014 +0100
+++ b/mpn/generic/sec_minvert.c	Mon Jan 13 23:52:10 2014 +0100
@@ -85,7 +85,7 @@
 mp_size_t
 mpn_sec_minvert_itch (mp_size_t n)
 {
-  return 4*n;
+  return n + MAX (mpn_sec_add_1_itch (n), 2*n + mpn_cnd_neg_itch (n));
 }

 /* Compute V <-- A^{-1} (mod M), in data-independent time. M must be
@@ -106,7 +106,9 @@
   ASSERT (! MPN_OVERLAP_P (ap, n, vp, n));
 #define bp (scratch + n)
 #define up (scratch + 2*n)
-#define m1hp (scratch + 3*n)
+#define m1hp (scratch)
+#define neg_scratch (scratch + 3*n)
+#define add_scratch (scratch + n)

   /* Maintain

@@ -119,15 +121,14 @@
        b = m,      v = 0
      */

+  ASSERT_CARRY (mpn_rshift (m1hp, mp, n, 1));
+  ASSERT_NOCARRY (mpn_sec_add_1 (m1hp, m1hp, n, 1, add_scratch));

   up[0] = 1;
   mpn_zero (up+1, n - 1);
   mpn_copyi (bp, mp, n);
   mpn_zero (vp, n);

-  ASSERT_CARRY (mpn_rshift (m1hp, mp, n, 1));
-  ASSERT_NOCARRY (mpn_sec_add_1 (m1hp, m1hp, n, 1, scratch));
-
   while (bit_size-- > 0)
     {
       mp_limb_t odd, swap, cy;
@@ -171,7 +172,7 @@

       swap = mpn_cnd_sub_n (odd, ap, ap, bp, n);
       mpn_cnd_add_n (swap, bp, bp, ap, n);
-      mpn_cnd_neg (swap, ap, ap, n, scratch);
+      mpn_cnd_neg (swap, ap, ap, n, neg_scratch);

       mpn_cnd_swap (swap, up, vp, n);
       cy = mpn_cnd_sub_n (odd, up, up, vp, n);

Best regards,
m

-- 
http://bodrato.it/papers/