X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/7c13f46198399dcb9c837b802833f821eda8f052..3471ebd194145da52d419c6315459237b076e18d:/mpx.h

diff --git a/mpx.h b/mpx.h
index 88f547c..7d8a2cd 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.6 1999/12/10 23:23:51 mdw Exp $
  *
  * Low level multiprecision arithmetic
  *
@@ -30,6 +30,12 @@
 /*----- 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.
+ *
  * Revision 1.4  1999/11/17 18:04:43  mdw
  * Add two's complement support.  Fix a bug in MPX_UMLAN.
  *
@@ -44,8 +50,8 @@
  *
  */
 
-#ifndef MPX_H
-#define MPX_H
+#ifndef CATACOMB_MPX_H
+#define CATACOMB_MPX_H
 
 #ifdef __cplusplus
   extern "C" {
@@ -68,7 +74,7 @@
 
 #include <string.h>
 
-#ifndef MPW_H
+#ifndef CATACOMB_MPW_H
 #  include "mpw.h"
 #endif
 
@@ -336,10 +342,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:	@dv, dvl@ = source and destination vector base and limit
- *		@n@ = other addend
+ * Arguments:	@mpw *dv, *dvl@ = source and destination base and limit
+ *		@mpw n@ = other addend
+ *
+ * Returns:	---
  *
  * Use:		Adds a small integer to a multiprecision number.
  */
@@ -355,6 +363,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 +386,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:	@mpw *dv, *dvl@ = source and destination base and limit
+ *		@n@ = subtrahend
  *
- * Arguments:	@@dv, dvl@ = destination vector base and limit
- *		@n@ = other addend
+ * Returns:	---
  *
  * Use:		Subtracts a small integer from a multiprecision number.
  */
@@ -398,6 +410,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 +430,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 +463,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:	@dv, dvl@ = destination/accumulator vector base and limit
- *		@av, avl@ = multiplicand vector base and limit
- *		@m@ = multiplier
+ * Arguments:	@mpw *dv, *dvl@ = destination/accumulator 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
  *		and adds the result to an accumulator.
@@ -474,6 +495,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
@@ -488,6 +512,32 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/,
 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