/* -*-c-*-
*
- * $Id: mp-arith.c,v 1.8 2000/10/08 12:02:21 mdw Exp $
+ * $Id: mp-arith.c,v 1.9 2000/10/08 15:48:35 mdw Exp $
*
* Basic arithmetic on multiprecision integers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-arith.c,v $
+ * Revision 1.9 2000/10/08 15:48:35 mdw
+ * Rename Karatsuba constants now that we have @gfx_kmul@ too.
+ *
* Revision 1.8 2000/10/08 12:02:21 mdw
* Use @MP_EQ@ instead of @MP_CMP@.
*
a = MP_COPY(a);
b = MP_COPY(b);
- if (MP_LEN(a) <= KARATSUBA_CUTOFF || MP_LEN(b) <= KARATSUBA_CUTOFF) {
+ if (MP_LEN(a) <= MPK_THRESH || MP_LEN(b) <= MPK_THRESH) {
MP_DEST(d, MP_LEN(a) + MP_LEN(b), a->f | b->f | MP_UNDEF);
mpx_umul(d->v, d->vl, a->v, a->vl, b->v, b->vl);
} else {
size_t m = 2 * MAX(MP_LEN(a), MP_LEN(b)) + 2;
mpw *s;
MP_DEST(d, m, a->f | b->f | MP_UNDEF);
- m += KARATSUBA_SLOP;
+ m += MPK_SLOP;
s = mpalloc(d->a, m);
mpx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + m);
mpfree(d->a, s);
a = MP_COPY(a);
MP_DEST(d, 2 * m + 2, a->f | MP_UNDEF);
- if (m > KARATSUBA_CUTOFF) {
+ if (m > MPK_THRESH) {
mpw *s;
- m = 2 * (m + 1) + KARATSUBA_SLOP;
+ m = 2 * (m + 1) + MPK_SLOP;
s = mpalloc(d->a, m);
mpx_ksqr(d->v, d->vl, a->v, a->vl, s, s + m);
mpfree(d->a, s);
/* -*-c-*-
*
- * $Id: mpmont.c,v 1.11 2000/10/08 12:04:27 mdw Exp $
+ * $Id: mpmont.c,v 1.12 2000/10/08 15:48:35 mdw Exp $
*
* Montgomery reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpmont.c,v $
+ * Revision 1.12 2000/10/08 15:48:35 mdw
+ * Rename Karatsuba constants now that we have @gfx_kmul@ too.
+ *
* Revision 1.11 2000/10/08 12:04:27 mdw
* (mpmont_reduce, mpmont_mul): Cope with negative numbers.
*
/* --- Check for serious Karatsuba reduction --- */
- if (n > KARATSUBA_CUTOFF * 3) {
+ if (n > MPK_THRESH * 3) {
mp al;
mpw *vl;
mp *u;
mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b)
{
- if (mm->n > KARATSUBA_CUTOFF * 3) {
+ if (mm->n > MPK_THRESH * 3) {
d = mp_mul(d, a, b);
d = mpmont_reduce(mm, d, d);
} else {
/* -*-c-*-
*
- * $Id: mpx-kmul.c,v 1.6 2000/10/08 12:11:01 mdw Exp $
+ * $Id: mpx-kmul.c,v 1.7 2000/10/08 15:48:35 mdw Exp $
*
* Karatsuba's multiplication algorithm
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx-kmul.c,v $
+ * Revision 1.7 2000/10/08 15:48:35 mdw
+ * Rename Karatsuba constants now that we have @gfx_kmul@ too.
+ *
* Revision 1.6 2000/10/08 12:11:01 mdw
* Use @mpx_ueq@ instead of @MPX_UCMP@.
*
#include <stdio.h>
#include "mpx.h"
-#include "mpx-kmac.h"
+#include "karatsuba.h"
/*----- Tweakables --------------------------------------------------------*/
#ifdef TEST_RIG
-# undef KARATSUBA_CUTOFF
-# define KARATSUBA_CUTOFF 2
+# undef MPK_THRESH
+# define MPK_THRESH 2
#endif
/*----- Main code ---------------------------------------------------------*/
*
* The destination must be twice as large as the larger
* argument. The scratch space must be twice as large as the
- * larger argument, plus the magic number @KARATSUBA_SLOP@.
+ * larger argument, plus the magic number @MPK_SLOP@.
*/
void mpx_kmul(mpw *dv, mpw *dvl,
MPX_SHRINK(av, avl);
MPX_SHRINK(bv, bvl);
- if (avl - av <= KARATSUBA_CUTOFF || bvl - bv <= KARATSUBA_CUTOFF) {
+ if (avl - av <= MPK_THRESH || bvl - bv <= MPK_THRESH) {
mpx_umul(dv, dvl, av, avl, bv, bvl);
return;
}
/* --- First things --- *
*
* Sort out where to break the factors in half. I'll choose the midpoint
- * of the largest one, since this minimizes the amount of work I have to do
+ * of the larger one, since this minimizes the amount of work I have to do
* most effectively.
*/
UADD2(sv, bsv, av, avm, avm, avl);
UADD2(bsv, ssv, bv, bvm, bvm, bvl);
- if (m > KARATSUBA_CUTOFF)
+ if (m > MPK_THRESH)
mpx_kmul(rdv, rdvl, sv, bsv, bsv, ssv, ssv, svl);
else
mpx_umul(rdv, rdvl, sv, bsv, bsv, ssv);
if (avl == avm || bvl == bvm)
MPX_ZERO(rdv + m + 1, dvl);
else {
- if (m > KARATSUBA_CUTOFF)
+ if (m > MPK_THRESH)
mpx_kmul(sv, ssv, avm, avl, bvm, bvl, ssv, svl);
else
mpx_umul(sv, ssv, avm, avl, bvm, bvl);
USUB(tdv, sv, svn);
}
- if (m > KARATSUBA_CUTOFF)
+ if (m > MPK_THRESH)
mpx_kmul(sv, ssv, av, avm, bv, bvm, ssv, svl);
else
mpx_umul(sv, ssv, av, avm, bv, bvm);
/* -*-c-*-
*
- * $Id: mpx-ksqr.c,v 1.5 2000/10/08 12:11:01 mdw Exp $
+ * $Id: mpx-ksqr.c,v 1.6 2000/10/08 15:48:35 mdw Exp $
*
* Karatsuba-based squaring algorithm
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx-ksqr.c,v $
+ * Revision 1.6 2000/10/08 15:48:35 mdw
+ * Rename Karatsuba constants now that we have @gfx_kmul@ too.
+ *
* Revision 1.5 2000/10/08 12:11:01 mdw
* Use @mpx_ueq@ instead of @MPX_UCMP@.
*
#include <stdio.h>
#include "mpx.h"
-#include "mpx-kmac.h"
+#include "karatsuba.h"
/*----- Tweakables --------------------------------------------------------*/
#ifdef TEST_RIG
-# undef KARATSUBA_CUTOFF
-# define KARATSUBA_CUTOFF 2
+# undef MPK_THRESH
+# define MPK_THRESH 2
#endif
/*----- Main code ---------------------------------------------------------*/
*
* The destination must be twice as large as the argument. The
* scratch space must be twice as large as the argument, plus
- * the magic number @KARATSUBA_SLOP@.
+ * the magic number @MPK_SLOP@.
*/
void mpx_ksqr(mpw *dv, mpw *dvl,
MPX_SHRINK(av, avl);
- if (avl - av <= KARATSUBA_CUTOFF) {
+ if (avl - av <= MPK_THRESH) {
mpx_usqr(dv, dvl, av, avl);
return;
}
mpw *rdv = tdv + m;
UADD2(sv, svm, av, avm, avm, avl);
- if (m > KARATSUBA_CUTOFF)
+ if (m > MPK_THRESH)
mpx_ksqr(tdv, rdv + m + 4, sv, svm + 1, ssv, svl);
else
mpx_usqr(tdv, rdv + m + 4, sv, svm + 1);
- if (m > KARATSUBA_CUTOFF)
+ if (m > MPK_THRESH)
mpx_ksqr(sv, ssv, avm, avl, ssv, svl);
else
mpx_usqr(sv, ssv, avm, avl);
UADD(rdv, sv, svm + 1);
USUB(tdv, sv, svn);
- if (m > KARATSUBA_CUTOFF)
+ if (m > MPK_THRESH)
mpx_ksqr(sv, ssv, av, avm, ssv, svl);
else
mpx_usqr(sv, ssv, av, avm);
/* -*-c-*-
*
- * $Id: mpx.h,v 1.10 2000/10/08 12:06:12 mdw Exp $
+ * $Id: mpx.h,v 1.11 2000/10/08 15:48:35 mdw Exp $
*
* Low level multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx.h,v $
+ * Revision 1.11 2000/10/08 15:48:35 mdw
+ * Rename Karatsuba constants now that we have @gfx_kmul@ too.
+ *
* Revision 1.10 2000/10/08 12:06:12 mdw
* Provide @mpx_ueq@ for rapidly testing equality of two integers.
*
/*----- Karatsuba multiplication algorithms -------------------------------*/
-/* --- @KARATSUBA_CUTOFF@ --- *
+/* --- @MPK_THRESH@ --- *
*
* This is the limiting length for using Karatsuba algorithms. It's best to
* use the simpler classical multiplication method on numbers smaller than
* this.
*/
-#define KARATSUBA_CUTOFF 16
+#define MPK_THRESH 16
-/* --- @KARATSUBA_SLOP@ --- *
+/* --- @MPK_SLOP@ --- *
*
* The extra number of words required as scratch space by the Karatsuba
* routines. This is a (generous) guess, since the actual amount of space
* required is proportional to the recursion depth.
*/
-#define KARATSUBA_SLOP 64
+#define MPK_SLOP 64
/* --- @mpx_kmul@ --- *
*
* The destination and scratch buffers must be twice as large as
* the larger argument. The scratch space must be twice as
* large as the larger argument, plus the magic number
- * @KARATSUBA_SLOP@.
+ * @MPK_SLOP@.
*/
extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/,
*
* The destination must be twice as large as the argument. The
* scratch space must be twice as large as the argument, plus
- * the magic number @KARATSUBA_SLOP@.
+ * the magic number @MPK_SLOP@.
*/
extern void mpx_ksqr(mpw */*dv*/, mpw */*dvl*/,
projects / u / mdw / catacomb / commitdiff