X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/7c13f46198399dcb9c837b802833f821eda8f052..f41f820e4b3e230d9314cc4323abf59babdd4e67:/mpx.h diff --git a/mpx.h b/mpx.h index 88f547c..076f14a 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.4 1999/11/17 18:04:43 mdw Exp $ + * $Id: mpx.h,v 1.9 1999/12/22 15:49:07 mdw Exp $ * * Low level multiprecision arithmetic * @@ -30,6 +30,21 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.h,v $ + * Revision 1.9 1999/12/22 15:49:07 mdw + * New function for division by a small integer. + * + * Revision 1.8 1999/12/11 10:57:43 mdw + * Karatsuba squaring algorithm. + * + * Revision 1.7 1999/12/11 01:51:28 mdw + * Change Karatsuba parameters slightly. + * + * Revision 1.6 1999/12/10 23:23:51 mdw + * Karatsuba-Ofman multiplication algorithm. + * + * Revision 1.5 1999/11/20 22:23:27 mdw + * Add function versions of some low-level macros with wider use. + * * Revision 1.4 1999/11/17 18:04:43 mdw * Add two's complement support. Fix a bug in MPX_UMLAN. * @@ -44,8 +59,8 @@ * */ -#ifndef MPX_H -#define MPX_H +#ifndef CATACOMB_MPX_H +#define CATACOMB_MPX_H #ifdef __cplusplus extern "C" { @@ -68,7 +83,7 @@ #include -#ifndef MPW_H +#ifndef CATACOMB_MPW_H # include "mpw.h" #endif @@ -336,10 +351,12 @@ extern void mpx_uadd(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, const mpw */*bv*/, const mpw */*bvl*/); -/* --- @MPX_UADDN@ --- * +/* --- @mpx_uaddn@ --- * + * + * Arguments: @mpw *dv, *dvl@ = source and destination base and limit + * @mpw n@ = other addend * - * Arguments: @dv, dvl@ = source and destination vector base and limit - * @n@ = other addend + * Returns: --- * * Use: Adds a small integer to a multiprecision number. */ @@ -355,6 +372,8 @@ extern void mpx_uadd(mpw */*dv*/, mpw */*dvl*/, } \ } while (0) +extern void mpx_uaddn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/); + /* --- @mpx_usub@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -376,10 +395,12 @@ extern void mpx_usub(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, const mpw */*bv*/, const mpw */*bvl*/); -/* --- @MPX_USUBN@ --- * +/* --- @mpx_usubn@ --- * * - * Arguments: @@dv, dvl@ = destination vector base and limit - * @n@ = other addend + * Arguments: @mpw *dv, *dvl@ = source and destination base and limit + * @n@ = subtrahend + * + * Returns: --- * * Use: Subtracts a small integer from a multiprecision number. */ @@ -398,6 +419,8 @@ extern void mpx_usub(mpw */*dv*/, mpw */*dvl*/, } \ } while (0) +extern void mpx_usubn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/); + /* --- @mpx_umul@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -416,11 +439,13 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, const mpw */*bv*/, const mpw */*bvl*/); -/* --- @MPX_UMULN@ --- * +/* --- @mpx_umuln@ --- * * - * Arguments: @dv, dvl@ = destination vector base and limit - * @av, avl@ = multiplicand vector base and limit - * @m@ = multiplier + * Arguments: @mpw *dv, *dvl@ = destination vector base and limit + * @const mpw *av, *avl@ = multiplicand vector base and limit + * @mpw m@ = multiplier + * + * Returns: --- * * Use: Multiplies a multiprecision integer by a single-word value. * The destination and source may be equal. The destination @@ -447,11 +472,16 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, } \ } while (0) -/* --- @MPX_UMLAN@ --- * +extern void mpx_umuln(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, mpw m); + +/* --- @mpx_umlan@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination/accumulator base and limit + * @const mpw *av, *avl@ = multiplicand vector base and limit + * @mpw m@ = multiplier * - * Arguments: @dv, dvl@ = destination/accumulator vector base and limit - * @av, avl@ = multiplicand vector base and limit - * @m@ = multiplier + * Returns: --- * * Use: Multiplies a multiprecision integer by a single-word value * and adds the result to an accumulator. @@ -463,10 +493,8 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, mpw _cc = 0; \ mpd _m = (m); \ \ - while (_av < _avl) { \ + while (_dv < _dvl && _av < _avl) { \ mpd _x; \ - if (_dv >= _dvl) \ - break; \ _x = (mpd)*_dv + (mpd)_m * (mpd)*_av++ + _cc; \ *_dv++ = MPW(_x); \ _cc = _x >> MPW_BITS; \ @@ -474,6 +502,9 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, MPX_UADDN(_dv, _dvl, _cc); \ } while (0) +extern void mpx_umlan(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, mpw m); + /* --- @mpx_usqr@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -511,6 +542,89 @@ extern void mpx_udiv(mpw */*qv*/, mpw */*qvl*/, mpw */*rv*/, mpw */*rvl*/, const mpw */*dv*/, const mpw */*dvl*/, mpw */*sv*/, mpw */*svl*/); +/* --- @mpx_udivn@ --- * + * + * Arguments: @mpw *qv, *qvl@ = storage for the quotient (may overlap + * dividend) + * @const mpw *rv, *rvl@ = dividend + * @mpw d@ = single-precision divisor + * + * Returns: Remainder after divison. + * + * Use: Performs a single-precision division operation. + */ + +extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, + const mpw */*rv*/, const mpw */*rvl*/, mpw /*d*/); + +/*----- Karatsuba multiplication algorithms -------------------------------*/ + +/* --- @KARATSUBA_CUTOFF@ --- * + * + * 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 + +/* --- @KARATSUBA_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 + +/* --- @mpx_kmul@ --- * + * + * Arguments: @mpw *dv, *dvl@ = pointer to destination buffer + * @const mpw *av, *avl@ = pointer to first argument + * @const mpw *bv, *bvl@ = pointer to second argument + * @mpw *sv, *svl@ = pointer to scratch workspace + * + * Returns: --- + * + * Use: Multiplies two multiprecision integers using Karatsuba's + * algorithm. This is rather faster than traditional long + * multiplication (e.g., @mpx_umul@) on large numbers, although + * more expensive on small ones. + * + * 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@. + */ + +extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, + const mpw */*bv*/, const mpw */*bvl*/, + mpw */*sv*/, mpw */*svl*/); + +/* --- @mpx_ksqr@ --- * + * + * Arguments: @mpw *dv, *dvl@ = pointer to destination buffer + * @const mpw *av, *avl@ = pointer to first argument + * @mpw *sv, *svl@ = pointer to scratch workspace + * + * Returns: --- + * + * Use: Squares a multiprecision integers using something similar to + * Karatsuba's multiplication algorithm. This is rather faster + * than traditional long multiplication (e.g., @mpx_umul@) on + * large numbers, although more expensive on small ones, and + * rather simpler than full-blown Karatsuba multiplication. + * + * 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@. + */ + +extern void mpx_ksqr(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, + mpw */*sv*/, mpw */*svl*/); + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus