Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Changeset 4146

Show
Ignore:
Timestamp:
12/02/08 07:40:10 (1 hour ago)
Author:
Don Clugston
Message:

BigInt? now uses BigDigit? internally, a stepping stone to using ulongs internally on 64-bit platforms.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/tango/math/internal/BignumNoAsm.d

    • Property svn:eol-style set to native
    r3900 r4146  
    1717 
    1818public: 
     19alias uint BigDigit; // A Bignum is an array of BigDigits.  
     20     
    1921    // Limits for when to switch between multiplication algorithms. 
    2022enum : int { KARATSUBALIMIT = 10 }; // Minimum value for which Karatsuba is worthwhile. 

  • trunk/tango/math/internal/BignumX86.d

    • Property svn:eol-style set to native
    r4032 r4146  
    5555*/ 
    5656 
    57 private: 
    5857version(GNU) { 
    5958    // GDC is a filthy liar. It can't actually do inline asm. 
    6059} else version(D_InlineAsm_X86) { 
     60 
     61private: 
     62 
    6163/* Duplicate string s, with n times, substituting index for '@'. 
    6264 * 
    …… 
    8890 
    8991public: 
     92     
     93alias uint BigDigit; // A Bignum is an array of BigDigits. Usually the machine word size. 
    9094     
    9195// Limits for when to switch between multiplication algorithms. 

  • trunk/tango/math/internal/BiguintCore.d

    r4140 r4146  
    4040const int FASTDIVLIMIT; // crossover to recursive division 
    4141 
    42 const uint [] ZERO = [0]; 
    43 const uint [] ONE = [1]; 
    44 const uint [] TWO = [2]; 
    45 const uint [] TEN = [10]; 
     42const BigDigit [] ZERO = [0]; 
     43const BigDigit [] ONE = [1]; 
     44const BigDigit [] TWO = [2]; 
     45const BigDigit [] TEN = [10]; 
    4646public:        
    4747 
    …… 
    5050private: 
    5151    invariant() { assert(data.length==1 || data[$-1]!=0); } 
    52     uint [] data = ZERO;  
    53 public: 
    54     static BigUint opCall(uint []x) { 
     52    BigDigit [] data = ZERO;  
     53    static BigUint opCall(BigDigit []x) { 
    5554       BigUint a; 
    5655       a.data=x; 
    5756       return a; 
    5857    } 
     58public: 
    5959    void opAssign(uint u) { 
    6060        if (u == 0) data = ZERO; 
    …… 
    6363        else if (u == 10) data = TEN; 
    6464        else { 
    65             data = new uint[1]; 
     65            data = new BigDigit[1]; 
    6666            data[0] = u; 
    6767        } 
    …… 
    7878 
    7979//return 1 if x>y, -1 if x<y, 0 if equal 
    80 static int compare(BigUint x, uint y) 
    81 { 
    82     if (x.data.length!=1) return 1; 
    83     if (x.data[0]==y) return 0; 
    84     return x.data[0] > y ? 1: -1; 
     80static int compare(BigUint x, ulong y) 
     81{ 
     82    if (x.data.length>2) return 1; 
     83    uint ylo = cast(uint)(y & 0xFFFF_FFFF); 
     84    uint yhi = y>>32; 
     85    if (x.data.length==2 && x.data[1]!=yhi) return x.data[1]>yhi ? 1: -1; 
     86    if (x.data[0]==ylo) return 0; 
     87    return x.data[0] > ylo ? 1: -1; 
    8588} 
    8689 
    …… 
    9295 
    9396int numBytes() { 
    94     return data.length * uint.sizeof; 
     97    return data.length * BigDigit.sizeof; 
    9598} 
    9699 
    …… 
    125128    }     
    126129    int len = (s.length - firstNonZero + 15)>>4; 
    127     data = new uint[len+1]; 
     130    data = new BigDigit[len+1]; 
    128131    uint part = 0; 
    129132    uint sofar = 0; 
    …… 
    167170    }     
    168171    uint predictlength = (18*2 + 2* (s.length-firstNonZero))/19; 
    169     data = new uint[predictlength]; 
     172    data = new BigDigit[predictlength]; 
    170173    uint hi = biguintFromDecimal(data, s[firstNonZero..$]); 
    171174    data.length = hi; 
    …… 
    187190        return BigUint(x.data[words..$]); 
    188191    } else { 
    189         uint [] result = new uint[x.data.length - words]; 
     192        uint [] result = new BigDigit[x.data.length - words]; 
    190193        multibyteShr(result, x.data[words..$], bits); 
    191194        if (result.length>1 && result[$-1]==0) return BigUint(result[0..$-1]); 
    …… 
    202205    assert ((y>>5) < cast(ulong)(uint.max)); 
    203206    uint words = cast(uint)(y >> 5); 
    204     uint [] result = new uint[x.data.length + words+1]; 
     207    BigDigit [] result = new BigDigit[x.data.length + words+1]; 
    205208    result[0..words] = 0; 
    206209    if (bits==0) { 
    …… 
    236239                return r; 
    237240            } 
    238             r.data = new uint[ d > uint.max ? 2: 1]; 
     241            r.data = new BigDigit[ d > uint.max ? 2: 1]; 
    239242            r.data[0] = cast(uint)(d & 0xFFFF_FFFF); 
    240243            if (d > uint.max) r.data[1] = cast(uint)(d>>32); 
    …… 
    269272    uint hi = cast(uint)(y >>> 32); 
    270273    uint lo = cast(uint)(y & 0xFFFF_FFFF); 
    271     uint [] result = new uint[x.data.length+1+(hi!=0)]; 
     274    uint [] result = new BigDigit[x.data.length+1+(hi!=0)]; 
    272275    result[x.data.length] = multibyteMul(result[0..x.data.length], x.data, lo, 0); 
    273276    if (hi!=0) { 
    …… 
    287290    uint len = x.data.length + y.data.length; 
    288291    BigUint r; 
    289     r.data = new uint[len]; 
     292    r.data = new BigDigit[len]; 
    290293    if (y.data.length > x.data.length) { 
    291294        mulInternal(r.data, y.data, x.data); 
    …… 
    303306// return x/y 
    304307static BigUint divInt(BigUint x, uint y) { 
    305     uint [] result = new uint[x.data.length]; 
     308    uint [] result = new BigDigit[x.data.length]; 
    306309    if ((y&(-y))==y) { 
    307310        assert(y!=0); 
    …… 
    328331    } else { 
    329332        // horribly inefficient - malloc, copy, & store are unnecessary. 
    330         uint [] wasteful = new uint[x.data.length]; 
     333        uint [] wasteful = new BigDigit[x.data.length]; 
    331334        wasteful[] = x.data[]; 
    332335        uint rem = multibyteDivAssign(wasteful, y, 0); 
    …… 
    341344    if (y.data.length > x.data.length) return BigUint(ZERO); 
    342345    if (y.data.length == 1) return divInt(x, y.data[0]); 
    343     uint [] result = new uint[x.data.length - y.data.length + 1]; 
     346    BigDigit [] result = new BigDigit[x.data.length - y.data.length + 1]; 
    344347    divModInternal(result, null, x.data, y.data); 
    345348    if (result.length>1 && result[$-1]==0) result=result[0..$-1]; 
    …… 
    352355    if (y.data.length > x.data.length) return x; 
    353356    if (y.data.length == 1) return divInt(x, y.data[0]); 
    354     uint [] result = new uint[x.data.length - y.data.length + 1]; 
    355     uint [] rem = new uint[y.data.length]; 
     357    BigDigit [] result = new BigDigit[x.data.length - y.data.length + 1]; 
     358    BigDigit [] rem = new BigDigit[y.data.length]; 
    356359    divModInternal(result, rem, x.data, y.data); 
    357360    while (rem.length>1 && rem[$-1]==0) rem = rem[0..$-1]; 
    …… 
    367370 *  Sets result = x - y. If the result is negative, negative will be true. 
    368371 */ 
    369 uint [] sub(uint[] x, uint[] y, bool *negative) 
     372BigDigit [] sub(BigDigit[] x, BigDigit[] y, bool *negative) 
    370373{ 
    371374    if (x.length == y.length) { 
    372375        // There's a possibility of cancellation, if x and y are almost equal. 
    373376        int last = highestDifferentDigit(x, y); 
    374         uint [] result = new uint[last+1]; 
     377        BigDigit [] result = new BigDigit[last+1]; 
    375378        if (x[last] < y[last]) { // we know result is negative 
    376379            multibyteAddSub!('-')(result[0..last+1], y[0..last+1], x[0..last+1], 0); 
    …… 
    384387    } 
    385388    // Lengths are different 
    386     uint [] large, small; 
     389    BigDigit [] large, small; 
    387390    if (x.length < y.length) { 
    388391        *negative = true; 
    …… 
    394397    // result.length will be equal to larger length, or could decrease by 1. 
    395398     
    396     uint [] result = new uint[large.length]; 
    397     uint carry = multibyteAddSub!('-')(result[0..small.length], large[0..small.length], small, 0); 
     399    BigDigit [] result = new BigDigit[large.length]; 
     400    BigDigit carry = multibyteAddSub!('-')(result[0..small.length], large[0..small.length], small, 0); 
    398401    result[small.length..$] = large[small.length..$]; 
    399402    if (carry) { 
    …… 
    405408 
    406409// return a + b 
    407 uint [] add(uint[] a, uint [] b) { 
    408     uint [] x, y; 
     410BigDigit [] add(BigDigit[] a, BigDigit [] b) { 
     411    BigDigit [] x, y; 
    409412    if (a.length<b.length) { x = b; y = a; } else { x = a; y = b; } 
    410413    // now we know x.length > y.length 
    411414    // create result. add 1 in case it overflows 
    412     uint [] result = new uint[x.length + 1]; 
    413      
    414     uint carry = multibyteAddSub!('+')(result[0..y.length], x[0..y.length], y, 0); 
     415    BigDigit [] result = new BigDigit[x.length + 1]; 
     416     
     417    BigDigit carry = multibyteAddSub!('+')(result[0..y.length], x[0..y.length], y, 0); 
    415418    if (x.length != y.length){ 
    416419        result[y.length..$-1]= x[y.length..$]; 
    …… 
    425428/**  return x + y 
    426429 */ 
    427 uint [] addInt(uint[] x, ulong y) 
     430BigDigit [] addInt(BigDigit[] x, ulong y) 
    428431{ 
    429432    uint hi = cast(uint)(y >>> 32); 
    …… 
    431434    uint len = x.length; 
    432435    if (x.length < 2 && hi!=0) ++len; 
    433     uint [] result = new uint[len+1]; 
     436    BigDigit [] result = new BigDigit[len+1]; 
    434437    result[0..x.length] = x[];  
    435438    if (x.length < 2 && hi!=0) { result[1]=hi; hi=0; }   
    …… 
    445448 *  x must be greater than y. 
    446449 */   
    447 uint [] subInt(uint[] x, ulong y) 
     450BigDigit [] subInt(BigDigit[] x, ulong y) 
    448451{ 
    449452    uint hi = cast(uint)(y >>> 32); 
    450453    uint lo = cast(uint)(y& 0xFFFF_FFFF); 
    451     uint [] result = new uint[x.length]; 
     454    BigDigit [] result = new BigDigit[x.length]; 
    452455    result[] = x[]; 
    453456    multibyteIncrementAssign!('-')(result[], lo); 
    …… 
    464467 *  
    465468 */ 
    466 void mulInternal(uint[] result, uint[] x, uint[] y) 
     469void mulInternal(BigDigit[] result, BigDigit[] x, BigDigit[] y) 
    467470{ 
    468471    assert( result.length == x.length + y.length ); 
    …… 
    491494            // result[done .. done+ylength] already has a value. 
    492495            chunksize = (done + (CACHELIMIT/y.length) < x.length) ? (CACHELIMIT/y.length) :  x.length - done; 
    493             uint [KARATSUBALIMIT] partial; 
     496            BigDigit [KARATSUBALIMIT] partial; 
    494497            partial[0..y.length] = result[done..done+y.length]; 
    495498            mulSimple(result[done..done+chunksize+y.length], x[done..done+chunksize], y); 
    …… 
    536539        } 
    537540        // We make the buffer a bit bigger so we have space for the partial sums. 
    538         uint [] scratchbuff = new uint[karatsubaRequiredBuffSize(maxchunk) + y.length]; 
    539         uint [] partial = scratchbuff[$ - y.length .. $]; 
     541        BigDigit [] scratchbuff = new BigDigit[karatsubaRequiredBuffSize(maxchunk) + y.length]; 
     542        BigDigit [] partial = scratchbuff[$ - y.length .. $]; 
    540543        uint done; // how much of X have we done so far? 
    541544        double residual = 0; 
    …… 
    564567    } else { 
    565568        // Balanced. Use Karatsuba directly. 
    566         uint [] scratchbuff = new uint[karatsubaRequiredBuffSize(x.length)]; 
     569        BigDigit [] scratchbuff = new BigDigit[karatsubaRequiredBuffSize(x.length)]; 
    567570        mulKaratsuba(result, x, y, scratchbuff); 
    568571        delete scratchbuff; 
    …… 
    573576import tango.core.BitManip : bsr; 
    574577 
    575 void divModInternal(uint [] quotient, uint[] remainder, uint [] u, uint [] v) 
     578void divModInternal(BigDigit [] quotient, BigDigit[] remainder, BigDigit [] u, BigDigit [] v) 
    576579{ 
    577580    assert(quotient.length == u.length - v.length + 1); 
    …… 
    584587    // same amount. 
    585588    
    586     uint [] vn = new uint[v.length]; 
    587     uint [] un = new uint[u.length + 1]; 
     589    BigDigit [] vn = new BigDigit[v.length]; 
     590    BigDigit [] un = new BigDigit[u.length + 1]; 
    588591    // How much to left shift v, so that its MSB is set. 
    589592    uint s = 31 - bsr(v[$-1]); 
    …… 
    631634// buff.length must be data.length*8 if separator is zero, 
    632635// or data.length*9 if separator is non-zero. It will be completely filled. 
    633 char [] biguintToHex(char [] buff, uint [] data, char separator=0) 
     636char [] biguintToHex(char [] buff, BigDigit [] data, char separator=0) 
    634637{ 
    635638    int x=0; 
    …… 
    657660 *    the lowest index of buff which was used. 
    658661 */ 
    659 int biguintToDecimal(char [] buff, uint [] data){ 
     662int biguintToDecimal(char [] buff, BigDigit [] data){ 
    660663    int sofar = buff.length; 
    661664    // Might be better to divide by (10^38/2^32) since that gives 38 digits for 
    …… 
    690693 *    the highest index of data which was used. 
    691694 */ 
    692 int biguintFromDecimal(uint [] data, char [] s) { 
     695int biguintFromDecimal(BigDigit [] data, char [] s) { 
    693696    // Convert to base 1e19 = 10_000_000_000_000_000_000. 
    694697    // (this is the largest power of 10 that will fit into a long). 
    …… 
    775778 
    776779// Classic 'schoolbook' multiplication. 
    777 void mulSimple(uint[] result, uint [] left, uint[] right) 
     780void mulSimple(BigDigit[] result, BigDigit [] left, BigDigit[] right) 
    778781in {     
    779782    assert(result.length == left.length + right.length); 
    …… 
    788791// add two uints of possibly different lengths. Result must be as long 
    789792// as the larger length. 
    790 uint addSimple(uint [] result, uint [] left, uint [] right) 
     793// Returns carry (0 or 1). 
     794uint addSimple(BigDigit [] result, BigDigit [] left, BigDigit [] right) 
    791795in { 
    792796    assert(result.length == left.length); 
    …… 
    804808} 
    805809 
    806 uint subSimple(uint [] result, uint [] left, uint [] right) 
     810//  result = left - right 
     811// returns carry (0 or 1) 
     812uint subSimple(BigDigit [] result, BigDigit [] left, BigDigit [] right) 
    807813in { 
    808814    assert(result.length == left.length); 
    …… 
    821827 
    822828 
    823 /*  Returns carry if result was less than right. 
     829/* result = result - right  
     830 * Returns carry = 1 if result was less than right. 
    824831*/ 
    825 uint simpleSubAssign(uint [] result, uint [] right) 
     832uint simpleSubAssign(BigDigit [] result, BigDigit [] right) 
    826833{ 
    827834    assert(result.length >= right.length); 
    …… 
    832839 
    833840 
    834 void simpleAddAssign(uint [] result, uint [] right) 
     841void simpleAddAssign(BigDigit [] result, BigDigit [] right) 
    835842{ 
    836843   assert(result.length >= right.length); 
    …… 
    861868* scratchbuff      An array long enough to store all the temporaries. Will be destroyed. 
    862869*/ 
    863 void mulKaratsuba(uint [] result, uint [] x, uint[] y, uint [] scratchbuff) 
     870void mulKaratsuba(BigDigit [] result, BigDigit [] x, BigDigit[] y, BigDigit [] scratchbuff) 
    864871{ 
    865872    assert(x.length >= y.length); 
    …… 
    945952 * u[0..v.length] holds the remainder. 
    946953 */ 
    947 void schoolbookDivMod(uint [] quotient, uint [] u, in uint [] v) 
     954void schoolbookDivMod(BigDigit [] quotient, BigDigit [] u, in BigDigit [] v) 
    948955{ 
    949956    assert(quotient.length == u.length - v.length); 
    …… 
    951958    assert(u.length >= v.length); 
    952959    assert((v[$-1]&0x8000_0000)!=0); 
    953      
     960    uint vhi = v[$-1]; 
     961         
    954962    for (int j = u.length - v.length-1; j >= 0; j--) { 
    955963        // Compute estimate qhat of quotient[j]. 
    956         ulong bigqhat, rhat; 
    957         bigqhat = ( (cast(ulong)(u[j+v.length]) << 32) + u[j+v.length-1])  
    958                  / v[$-1]; 
    959         rhat = ((cast(ulong)(u[j+v.length]) << 32) + u[j+v.length-1])  
    960                - bigqhat * v[$-1]; 
     964        ulong uu = (cast(ulong)(u[j+v.length]) << 32) | u[j+v.length-1]; 
     965        ulong bigqhat = uu / vhi; 
     966        ulong rhat =  uu - bigqhat * vhi;         
    961967again: 
    962968        if ((bigqhat & 0xFFFF_FFFF_0000_0000L)  
    963969            || bigqhat*v[$-2] > ((rhat<<32) + u[j+v.length-2])) { 
    964970            --bigqhat; 
    965             rhat += v[$-1]; 
     971            rhat += vhi; 
    966972            if (rhat < 0x1_0000_0000L) goto again; 
    967973        } 
    …… 
    10031009// Returns the highest value of i for which left[i]!=right[i], 
    10041010// or 0 if left[]==right[] 
    1005 int highestDifferentDigit(uint [] left, uint [] right) 
     1011int highestDifferentDigit(BigDigit [] left, BigDigit [] right) 
    10061012{ 
    10071013    assert(left.length == right.length); 
    …… 
    10241030    scratch is temporary storage space, must be at least as long as quotient. 
    10251031*/ 
    1026 void recursiveDivMod(uint[] quotient, uint[] u, in uint[] v, 
    1027         uint[] scratch) 
     1032void recursiveDivMod(BigDigit[] quotient, BigDigit[] u, in BigDigit[] v, 
     1033                     BigDigit[] scratch) 
    10281034in { 
    10291035    assert(quotient.length == u.length - v.length); 
    …… 
    10521058// If would make rem negative, decrease quot until rem is >=0. 
    10531059// Needs (quot.length * k) scratch space to store the result of the multiply.  
    1054 void adjustRemainder(uint[] quot, uint[] rem, in uint[] v, int k, 
    1055         uint[] scratch) { 
     1060void adjustRemainder(BigDigit[] quot, BigDigit[] rem, in BigDigit[] v, int k, 
     1061                     BigDigit[] scratch) 
     1062{ 
    10561063    assert(rem.length == v.length); 
    10571064    mulInternal(scratch, quot, v[0 .. k]); 
    …… 
    10631070} 
    10641071 
    1065 void fastDivMod(uint [] quotient, uint [] u, in uint [] v) 
     1072void fastDivMod(BigDigit [] quotient, BigDigit [] u, in BigDigit [] v) 
    10661073{ 
    10671074    assert(quotient.length == u.length - v.length); 
    …… 
    10691076    assert(u.length >= v.length); 
    10701077    assert((v[$-1] & 0x8000_0000)!=0); 
    1071     uint [] scratch = new uint[v.length]; 
     1078    BigDigit [] scratch = new BigDigit[v.length]; 
    10721079 
    10731080    // Perform block schoolbook division, with 'v.length' blocks. 
Roadmap Timeline Tickets New Ticket Help / Guide About Trac
Login  |  
Trac dsource.org
RSS
Copyright © 2006-2008 Tango. All Rights Reserved. | Page Width: Static or Dynamic