Changeset 3876

Timestamp:

08/12/08 03:54:09 (4 months ago)

Author:

Don Clugston

Message:

Better memory efficiency in the asymmetric multiply case

Files:

• trunk/tango/math/internal/BiguintCore.d (modified) (12 diffs)

trunk/tango/math/internal/BiguintCore.d

@@ -5 +5 @@
- * Authors:   Don Clugston
- */
-
+
-module tango.math.internal.BiguintCore;
-
@@ -161 +161 @@
-/** General unsigned subtraction routine for bigints.
- *  Sets result = x - y. If the result is negative, negative will be true.
- *
- *  The length of y must not be larger than the length of x.
- */
-uint [] biguintSubtract(uint[] x, uint[] y, bool *negative)
@@ -203 +201 @@
-uint [] biguintAdd(uint[] a, uint [] b) {
-    uint [] x, y;
-
+ 
-    // now we know x.length > y.length
-    // create result. add 1 in case it overflows
@@ -239 +237 @@
-}
-
+/** Return x-y..
+ *  x must be greater than y.
+ */  
+uint [] biguintSubInt(uint[] x, ulong y)
+{
+    uint hi = cast(uint)(y >>> 32);
+    uint lo = cast(uint)(y& 0xFFFF_FFFF);
+    uint [] result = new uint[x.length];
+    result[] = x[];
+    multibyteIncrementAssign!('-')(result[], lo);
+    if (hi) multibyteIncrementAssign!('-')(result[1..$], hi);
+    if (result[$-1]==0) return result[0..$-1];
+    else return result; 
+}
+
-/** General unsigned multiply routine for bigints.
- *  Sets result = x*y.
@@ -291 +304 @@
-        // For maximum performance, we want the ratio to be as close to 
-        // 1:1 as possible. To achieve this, we can either pad x or y.
-
-
+
-        uint numchunks = x.length / y.length;
-        uint chunksize = y.length;
@@ -298 +310 @@
-        uint maxchunk = chunksize + extra;
-        bool paddingY; // true = we're padding Y, false = we're padding X.
-
-
+
-            // The leftover bit is small enough that it should be incorporated
-            // in the existing chunks.            
@@ -320 +331 @@
-        }
-        // We make the buffer a bit bigger so we have space for the partial sums.
-
-
-
+
+
-        uint done; // how much of X have we done so far?
-        double residual = 0;
-        if (paddingY) {
-            // If the first chunk is bigger, do it first. We're padding y. 
-
-
+
+
+
-          if (extra) --extra;
-        } else { // Begin with the extra bit.
@@ -337 +348 @@
-        auto basechunksize = chunksize;
-        while (done < x.length) {
->0? 1:
+ > 0 ? 1 : 
-            if (extra) --extra;
-
+
+
-                       x[done .. done+chunksize], y, scratchbuff);
-
-
-
+
-            done += chunksize;
-        }
@@ -384 +394 @@
-in {    
-    assert(result.length == left.length + right.length);
-//
+
-}
-body {
-    result[left.length] = multibyteMul(result[0..left.length], left, right[0], 0);
-
-
+
-}
-
@@ -407 +416 @@
-        result[right.length..left.length] = left[right.length .. $];            
-        carry = multibyteIncrementAssign!('+')(result[right.length..$], carry);
- //else if (result.length==left.length+1) { result[$-1] = carry; carry=0; }
+
-    return carry;
-}
@@ -457 +466 @@
-uint karatsubaRequiredBuffSize(uint xlen)
-{
-
-
+
-}
-
@@ -537 +545 @@
-        }
-    } else mulKaratsuba(resultHigh, x1, y1, newscratchbuff);
+    
-    mid.simpleSubAssign(resultHigh);
-