From 52cdaca9b7b8e15871a3de8b5b571c18dcc580f8 Mon Sep 17 00:00:00 2001 From: mdw Date: Sun, 8 Oct 2000 15:48:35 +0000 Subject: [PATCH] Rename Karatsuba constants now that we have @gfx_kmul@ too. --- mp-arith.c | 13 ++++++++----- mpmont.c | 9 ++++++--- mpx-kmul.c | 23 +++++++++++++---------- mpx-ksqr.c | 21 ++++++++++++--------- mpx.h | 17 ++++++++++------- 5 files changed, 49 insertions(+), 34 deletions(-) diff --git a/mp-arith.c b/mp-arith.c index 96fdeb8..82fda15 100644 --- a/mp-arith.c +++ b/mp-arith.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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@. * @@ -236,14 +239,14 @@ mp *mp_mul(mp *d, mp *a, mp *b) 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); @@ -270,9 +273,9 @@ mp *mp_sqr(mp *d, mp *a) 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); diff --git a/mpmont.c b/mpmont.c index 4868bff..d000f8d 100644 --- a/mpmont.c +++ b/mpmont.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -198,7 +201,7 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) /* --- Check for serious Karatsuba reduction --- */ - if (n > KARATSUBA_CUTOFF * 3) { + if (n > MPK_THRESH * 3) { mp al; mpw *vl; mp *u; @@ -283,7 +286,7 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) 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 { diff --git a/mpx-kmul.c b/mpx-kmul.c index eaa0848..f6b0b4f 100644 --- a/mpx-kmul.c +++ b/mpx-kmul.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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@. * @@ -57,13 +60,13 @@ #include #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 ---------------------------------------------------------*/ @@ -84,7 +87,7 @@ * * 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, @@ -106,7 +109,7 @@ 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; } @@ -126,7 +129,7 @@ void mpx_kmul(mpw *dv, mpw *dvl, /* --- 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. */ @@ -159,7 +162,7 @@ void mpx_kmul(mpw *dv, mpw *dvl, 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); @@ -175,7 +178,7 @@ void mpx_kmul(mpw *dv, mpw *dvl, 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); @@ -184,7 +187,7 @@ void mpx_kmul(mpw *dv, mpw *dvl, 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); diff --git a/mpx-ksqr.c b/mpx-ksqr.c index 4aa84dd..25dbb70 100644 --- a/mpx-ksqr.c +++ b/mpx-ksqr.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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@. * @@ -55,13 +58,13 @@ #include #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 ---------------------------------------------------------*/ @@ -82,7 +85,7 @@ * * 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, @@ -102,7 +105,7 @@ 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; } @@ -136,12 +139,12 @@ void mpx_ksqr(mpw *dv, mpw *dvl, 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); @@ -149,7 +152,7 @@ void mpx_ksqr(mpw *dv, mpw *dvl, 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); diff --git a/mpx.h b/mpx.h index cb49bd4..dc86cc9 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -575,23 +578,23 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, /*----- 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@ --- * * @@ -610,7 +613,7 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, * 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*/, @@ -634,7 +637,7 @@ 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*/, -- 2.11.0