Changeset 3877

Timestamp:

08/14/08 02:58:10 (3 months ago)

Author:

Don Clugston

Message:

Added biguintMulInt. Improved comments.

Files:

• trunk/tango/math/internal/BignumX86.d (modified) (2 diffs)
• trunk/tango/math/internal/BiguintCore.d (modified) (9 diffs)

trunk/tango/math/internal/BignumX86.d

@@ -84 +84 @@
-// Limits for when to switch between multiplication algorithms.
-enum : int { KARATSUBALIMIT = 18 }; // Minimum value for which Karatsuba is worthwhile.
-
-    
-/** Multi-byte addition or subtraction
@@ -828 +827 @@
-        dec     EAX;
-        ror     EAX, CL ; //ecx bits at msb
-
-
+
-        
-        // Then divide 2^(32+cx) by divisor (edx already ok)

trunk/tango/math/internal/BiguintCore.d

@@ -162 +162 @@
- *  Sets result = x - y. If the result is negative, negative will be true.
- */
-tract
+
-{
-    if (x.length == y.length) {
@@ -252 +252 @@
-}
-
+/** return x*y.
+ *  y must not be zero.
+ */
+uint [] biguintMulInt(uint [] x, ulong y)
+{
+    uint hi = cast(uint)(y >>> 32);
+    uint lo = cast(uint)(y & 0xFFFF_FFFF);
+    uint [] result = new uint[x.length+1+(hi!=0)];
+    result[x.length] = multibyteMul(result[0..x.length], x, lo, 0);
+    if (hi!=0) {
+        result[x.length+1] = multibyteMulAdd(result[1..x.length+1], x, hi, 0);
+    }
+    return result;
+}
+
-/** General unsigned multiply routine for bigints.
- *  Sets result = x*y.
@@ -270 +285 @@
-            return;
-        }
-*
++
-        
-        // If x is so big that it won't fit into the cache, we divide it into chunks            
@@ -472 +487 @@
-* x must be longer or equal to y.
-* Valid only for balanced multiplies, where x is not shorter than y.
-
+
+
-* Params:
-* scratchbuff      An array long enough to store all the temporaries. Will be destroyed.
@@ -491 +507 @@
-    // requiring 3 multiplies of length N, instead of 4.
-    
-    // TODO: Knuth's variant is superior:
-    // (Nx1 + x0)*(Ny1 + y0) = (N*N) x1y1 + x0y0 - N * mid
-    // where mid = (x0-x1)*(y0-y1) - x1y1 - x0y0
-    // since then the lengths cannot exceed length N.
-
-    // half length, round up.
@@ -510 +522 @@
-    uint [] resultHigh = result[x0.length + y0.length .. $];
-        
+    
-    // Add the high and low parts of x and y.
-    // This will generate carries of either 0 or 1.
+    // TODO: Knuth's variant would save the extra two additions:
+    // (Nx1 + x0)*(Ny1 + y0) = (N*N) x1y1 + x0y0 - N * mid
+    // where mid = (x0-x1)*(y0-y1) - x1y1 - x0y0
+    // since then the lengths cannot exceed length N.
-    uint carry_x = addSimple(xsum, x0, x1);
-    uint carry_y = addSimple(ysum, y0, y1);
@@ -519 +536 @@
-    if (carry_x)  simpleAddAssign(mid[half..$], ysum);
-    if (carry_y)  simpleAddAssign(mid[half..$], xsum);
-
+    
-    // Low half of result gets x0 * y0. High half gets x1 * y1
-   
@@ -533 +550 @@
-        } else {
-            // divide x1 in two, then use schoolbook multiply on the two pieces.
-            // Note that this will be smaller than y1, except when x1 = 2*y1 + 1.
-            uint quarter = (x1.length >> 1) + (x1.length & 1);
-            bool ysmaller = (quarter >= y1.length);
@@ -582 +598 @@
-    return 0;
-}
-