More changes. Still embryonic.

[u/mdw/catacomb] / mpbarrett.c

diff --git a/mpbarrett.c b/mpbarrett.c
index e438d02..711b7ab 100644 (file)
--- a/mpbarrett.c
+++ b/mpbarrett.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mpbarrett.c,v 1.1 1999/12/10 23:21:59 mdw Exp $
+ * $Id: mpbarrett.c,v 1.3 1999/12/12 15:08:52 mdw Exp $
  *
  * Barrett modular reduction
  *
@@ -30,6 +30,13 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: mpbarrett.c,v $
+ * Revision 1.3  1999/12/12 15:08:52  mdw
+ * Don't bother shifting %$q$% in @mpbarrett_reduce@, just skip the least
+ * significant digits.
+ *
+ * Revision 1.2  1999/12/11 01:50:56  mdw
+ * Improve initialization slightly.
+ *
  * Revision 1.1  1999/12/10 23:21:59  mdw
  * Barrett reduction support: works with even moduli.
  *
@@ -66,7 +73,9 @@ void mpbarrett_create(mpbarrett *mb, mp *m)
   mp_shrink(m);
   mb->k = MP_LEN(m);
   mb->m = MP_COPY(m);
-  b = mp_lsl(MP_NEW, MP_ONE, 2 * MPW_BITS * mb->k);
+  b = mp_create(2 * mb->k + 1);
+  MPX_ZERO(b->v, b->vl - 1);
+  b->vl[-1] = 1;
   mp_div(&b, 0, b, m);
   mb->mu = b;
 }
@@ -119,7 +128,11 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m)
     mp qq;
     mp_build(&qq, m->v + (k - 1), m->vl);
     q = mp_mul(MP_NEW, &qq, mb->mu);
-    q = mp_lsr(q, q, MPW_BITS * (k + 1));
+    if (MP_LEN(q) <= k) {
+      m = MP_COPY(m);
+      MP_DROP(d);
+      return (m);
+    }
   }
 
   /* --- Second stage --- */
@@ -134,7 +147,7 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m)
     else
       mvl = m->v + k + 1;
     r = mp_create(k + 1);
-    mpx_umul(r->v, r->vl, q->v, q->vl, mb->m->v, mb->m->vl);
+    mpx_umul(r->v, r->vl, q->v + k + 1, q->vl, mb->m->v, mb->m->vl);
     r->f = (q->f | mb->m->f) & MP_BURN;
     MP_MODIFY(d, k + 1);
     mpx_usub(d->v, d->vl, m->v, mvl, r->v, r->vl);