/* -*-c-*-
*
- * $Id: mpx.h,v 1.5 1999/11/20 22:23:27 mdw Exp $
+ * $Id: mpx.h,v 1.6 1999/12/10 23:23:51 mdw Exp $
*
* Low level multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx.h,v $
+ * 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.
*
*
*/
-#ifndef MPX_H
-#define MPX_H
+#ifndef CATACOMB_MPX_H
+#define CATACOMB_MPX_H
#ifdef __cplusplus
extern "C" {
#include <string.h>
-#ifndef MPW_H
+#ifndef CATACOMB_MPW_H
# include "mpw.h"
#endif
extern void mpx_usqr(mpw */*dv*/, mpw */*dvl*/,
const mpw */*av*/, const mpw */*avl*/);
+/* --- @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.
+ */
+
+#define KARATSUBA_CUTOFF 16
+#define KARATSUBA_SLOP 32
+
+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_udiv@ --- *
*
* Arguments: @mpw *qv, *qvl@ = quotient vector base and limit