Changeset 3829

Timestamp:

07/31/08 03:43:58 (4 months ago)

Author:

Don Clugston

Message:

Added higher-level sub and integer division. Made asm functions private.

Files:

• trunk/tango/math/impl/BiguintCore.d (modified) (3 diffs)

trunk/tango/math/impl/BiguintCore.d

@@ -10 +10 @@
-version(GNU) {
-    // GDC lies about its X86 support
-ublic
+rivate
-} else version(D_InlineAsm_X86) { 
-ublic
+rivate
-} else {
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-}
-
-public:
-    
-// Returns the highest value of i for which left[i]!=right[i],
-// or 0 if left[]==right[]
-int lastDifferentDigit(uint [] left, uint [] right)
-{
-    assert(left.length == right.length);
-    for (int i=left.length; i>0; --i) {
-        if (left[i]!=right[i]) return i;
-    }
-    return 0;
-}
-
-// Converts a big uint to a hexadecimal string.
-//
@@ -185 +155 @@
-}
-
-private:
-// classic 'schoolbook' multiplication.
-void mulSimple(uint[] result, uint [] left, uint[] right)
-in {    
-    assert(result.length == left.length + right.length);
-    assert(right.length>1);
-}
-body {
-    result[left.length] = multibyteMul(result[0..left.length], left, right[0], 0);
-    if (right.length>1)
-        multibyteMultiplyAccumulate(result[1..$], left, right[1..$]);
-}
-
-// add two uints of possibly different lengths. Result must be as long
-// as the larger length.
-uint addSimple(uint [] result, uint [] left, uint [] right)
-in {
-    assert(result.length == left.length);
-    assert(left.length >= right.length);
-    assert(right.length>0);
-}
-body {
-    uint carry = multibyteAddSub!('+')(result[0..right.length],
-            left[0..right.length], right, 0);
-    if (right.length < left.length) {
-        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;
-}
-
-/*  result must be larger than right.
-*/
-void simpleSubAssign(uint [] result, uint [] right)
-{
-    assert(result.length > right.length);
-    uint c = multibyteAddSub!('-')(result[0..right.length], result[0..right.length], right, 0); 
-    if (c) c = multibyteIncrementAssign!('-')(result[right.length .. $], c);
-    assert(c==0);
-}
-
-void simpleAddAssign(uint [] result, uint [] right)
-{
-   assert(result.length > right.length);
-   uint c = multibyteAddSub!('+')(result[0..right.length], result[0..right.length], right, 0);
-   if (c) c = multibyteIncrementAssign!('+')(result[right.length .. $], c);
-   assert(c==0);
-}
-
-// Limits for when to switch between multiplication algorithms.
-const int CACHELIMIT = 8000;   // Half the size of the data cache.
-
-/* Determine how much space is required for the temporaries
- * when performing a Karatsuba multiplication. 
- */
-uint karatsubaRequiredBuffSize(uint xlen)
-{
-    return xlen <= KARATSUBALIMIT ? 0 : xlen * 2;
-}
-
-/* Sets result = x*y, using Karatsuba multiplication.
-* Valid only for balanced multiplies, and x must be longer than y.
-* ie 2*y.length > x.length >= y.length.
-* Params:
-* scratchbuff      An array long enough to store all the temporaries. Will be destroyed.
-*/
-void mulKaratsuba(uint [] result, uint [] x, uint[] y, uint [] scratchbuff)
-{
-    assert(result.length == x.length + y.length);
-    assert(x.length >= y.length);
-    if (x.length <= KARATSUBALIMIT) {
-        return mulSimple(result, x, y);
-    }    
-    // Karatsuba multiply uses the following result:
-    // (Nx1 + x0)*(Ny1 + y0) = (N*N) x1y1 + x0y0 + N * mid
-    // where mid = (x1+x0)*(y1+y0) - x1y1 - x0y0
-    // requiring 3 multiplies of length N, instead of 4.
-
-    // half length, round up.
-    uint half = (x.length >> 1) + (x.length & 1);
-    assert(y.length>half, "Asymmetric Karatsuba");
-    
-    uint [] x0 = x[0 .. half];
-    uint [] x1 = x[half .. $];    
-    uint [] y0 = y[0 .. half];
-    uint [] y1 = y[half .. $];
-    uint [] xsum = result[0 .. half]; // initially use result to store temporaries
-    uint [] ysum = result[half .. half*2];
-    uint [] mid = scratchbuff[0 .. half*2+1];
-    uint [] newscratchbuff = scratchbuff[half*2+2 .. $];
-    uint [] resultLow = result[0 .. x0.length + y0.length];
-    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.
-    uint carry_x = addSimple(xsum, x0, x1);
-    uint carry_y = addSimple(ysum, y0, y1);
-    
-    mulKaratsuba(mid[0..half*2], xsum, ysum, newscratchbuff);
-    mid[half*2] = carry_x & carry_y;
-    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
-   
-    mulKaratsuba(resultLow, x0, y0, newscratchbuff);
-    mid.simpleSubAssign(resultLow);
-    mulKaratsuba(resultHigh, x1, y1, newscratchbuff);
-    mid.simpleSubAssign(resultHigh);
-    
-    // result += MID
-    result[half..$].simpleAddAssign(mid);
-}
-
-public:
+
+/** 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)
+{
+    if (x.length == y.length) {
+        // There's a possibility of cancellation, if x and y are almost equal.
+        int last = lastDifferentDigit(x, y);
+        uint [] result = new uint[last+1];
+        if (x[last] < y[last]) { // we know result is negative
+            multibyteAddSub!('-')(result[0..last+1], y[0..last+1], x[0..last+1], 0);
+            *negative = true;
+        } else { // positive or zero result
+            multibyteAddSub!('-')(result[0..last+1], x[0..last+1], y[0..last+1], 0);
+            *negative = false;
+        }
+        return result;
+    }
+    // Lengths are different
+    uint [] large, small;
+    if (x.length < y.length) {
+        *negative = true;
+        large = y; small = x;
+//        return biguintSubDifferentLength(y, x);
+    } else {
+        *negative = false;
+        large = x; small = y;
+  //      return biguintSubDifferentLength(x, y);
+    }
+    // result.length will be equal to larger length, or could decrease by 1.
+    
+    uint [] result = new uint[large.length];
+    uint carry = multibyteAddSub!('-')(result[0..small.length], large[0..small.length], small, 0);
+    result[small.length..$-1] = large[small.length..$];
+    if (carry) {
+        multibyteIncrementAssign!('-')(result[small.length..$-1], carry);
+        if (result[$-1]==0) return result[0..$-1];
+    }
+    return result;
+}
+
+// return a+b
+uint [] biguintAdd(uint[] a, uint [] b) {
+    uint [] x, y;
+    if (a.length<b.length) { x = b; y = a; } else {x = a; y = b; }
+    // now we know x.length > y.length
+    // create result. add 1 in case it overflows
+    uint [] result = new uint[x.length + 1];
+    
+    uint carry = multibyteAddSub!('+')(result[0..y.length], x[0..y.length], y, 0);
+    if (x.length != y.length){
+        result[y.length..$-1]= x[y.length..$];
+        carry  = multibyteIncrementAssign!('+')(result[y.length..$-1], carry);
+    }
+    if (carry) {
+        result[$-1] = carry;
+        return result;
+    } else return result[0..$-1];
+}
+
+
+/** return x+y
+ */
+uint [] biguintAddInt(uint[] x, ulong y)
+{
+    uint hi = cast(uint)(y >>> 32);
+    uint lo = cast(uint)(y& 0xFFFF_FFFF);
+    uint len = x.length;
+    if (x.length < 2 && hi!=0) ++len;
+    uint [] result = new uint[len+1];
+    result[0..x.length] = x[]; 
+    if (x.length < 2 && hi!=0) { result[1]=hi; hi=0; }
+    uint carry = multibyteIncrementAssign!('+')(result[0..$-1], lo);
+    if (hi!=0) carry += multibyteIncrementAssign!('+')(result[1..$-1], hi);
+    if (carry) {
+        result[$-1] = carry;
+        return result;
+    } else return result[0..$-1];
+}
-    
-/** General unsigned multiply routine for bigints.
@@ -373 +311 @@
-            done += y.length;
-        }
-//
+ 
-    } else {
-        // Balanced. Use Karatsuba directly.
-        uint [] scratchbuff = new uint[karatsubaRequiredBuffSize(x.length)];
-        mulKaratsuba(result, x, y, scratchbuff);
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+