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

Changeset 3914

Show
Ignore:
Timestamp:
08/26/08 00:07:05 (3 months ago)
Author:
Don Clugston
Message:

Major refactoring of the internal code. BigInt? is now implemented purely using a new (private) BigUint? class.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/tango/math/BigInt.d

    r3903 r3914  
    1212/** A struct representing an arbitrary precision integer 
    1313 * 
    14  * All arithmetic and logical operations are supported, except 
     14 * All arithmetic operations are supported, except 
    1515 * unsigned shift right (>>>). 
    1616 * It implements value semantics using copy-on-write. This means that 
    …… 
    2424struct BigInt 
    2525{ 
     26    // BigInt adds signed arithmetic to BigUint. 
    2627private: 
    27     uint[] data = [0]; // In D2 this would be invariant(uint)[] 
     28    BigUint data; 
    2829    bool sign; 
    29     static uint [] ZERO = [0]; 
    30     static uint [] ONE = [1]; 
    31 private: 
    32     void assignUint(uint u) { 
    33         if (u==0) data = ZERO; 
    34         else if (u==1) data = ONE; 
    35         else { 
    36             data = new uint[1]; 
    37             data[0] = u; 
    38         } 
    39     } 
    4030public: 
    4131    /// 
    4232    void opAssign(T:int)(T x) { 
    43         assignUint((x>=0)? x : -x); 
     33        data = (x>=0) ? x : -x; 
    4434        sign = (x<0); 
    4535    } 
    4636    /// 
    4737    BigInt opAdd(T: int)(T y) { 
    48         return addsubInternal(*this, cast(ulong)(y<0? -y: y), sign!=(y<0)); 
     38        BigInt r; 
     39        r.sign = sign; 
     40        r.data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), sign!=(y<0), &r.sign); 
     41        return r; 
    4942    }     
    5043    /// 
    5144    BigInt opAddAssign(T: int)(T y) { 
    52         *this = addsubInternal(*this, cast(ulong)(y<0? -y: y), sign!=(y<0)); 
    53         return *this; 
    54     }     
    55     /// 
    56     BigInt opAdd(T:BigInt)(BigInt y) { 
    57         return addsubInternal(*this, y, this.sign != y.sign); 
     45         data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), 
     46         sign!=(y<0), &sign); 
     47        return *this; 
     48    }     
     49    /// 
     50    BigInt opAdd(T: BigInt)(T y) { 
     51        BigInt r; 
     52        r.sign = sign; 
     53        r.data = BigUint.addOrSub(data, y.data, sign != y.sign, &r.sign); 
     54        return r; 
    5855    } 
    5956    /// 
    6057    BigInt opAddAssign(T:BigInt)(T y) { 
    61         *this = addsubInternal(*this, y, this.sign != y.sign); 
    62         return *this; 
    63     } 
    64      
     58        data = BigUint.addOrSub(data, y.data, sign != y.sign, &sign); 
     59        return *this; 
     60    }     
    6561    /// 
    6662    BigInt opSub(T: int)(T y) { 
    67         return addsubInternal(*this, cast(ulong)(y<0? -y: y), sign==(y<0)); 
     63        BigInt r; 
     64        r.sign = sign; 
     65        r.data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), sign==(y<0), &r.sign); 
     66        return r; 
    6867    }         
    6968    /// 
    7069    BigInt opSubAssign(T: int)(T y) { 
    71         *this = addsubInternal(*this, cast(ulong)(y<0? -y: y), sign==(y<0)); 
     70        data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), sign==(y<0), &sign); 
    7271        return *this; 
    7372    } 
    7473    /// 
    7574    BigInt opSub(T: BigInt)(T y) { 
    76         return addsubInternal(*this, y, this.sign == y.sign); 
     75        BigInt r; 
     76        r.sign = sign; 
     77        r.data = BigUint.addOrSub(data, y.data, sign == y.sign, &r.sign); 
     78        return r; 
    7779    }         
    7880    /// 
    7981    BigInt opSubAssign(T:BigInt)(T y) { 
    80         *this = addsubInternal(*this, y, this.sign == y.sign); 
    81         return *this; 
    82     } 
    83      
     82        data = BigUint.addOrSub(data, y.data, sign == y.sign, &sign); 
     83        return *this; 
     84    }     
    8485    /// 
    8586    BigInt opMul(T: int)(T y) { 
    …… 
    110111    }     
    111112    /// 
    112     BigInt opDiv(T:int)(T x) { 
    113         assert(x!=0); 
    114         BigInt r; 
    115         uint u = x < 0 ? -x : x; 
    116         r.data = biguintDivInt(data, u); 
    117         r.sign = r.isZero()? false : this.sign != (x<0); 
    118         return r; 
    119     } 
    120     /// 
    121     BigInt opDivAssign(T: int)(T x) { 
    122         assert(x!=0); 
    123         uint u = x < 0 ? -x : x; 
    124         data = biguintDivInt(data, u); 
    125         sign = isZero()? false : sign ^ (x<0); 
     113    BigInt opDiv(T:int)(T y) { 
     114        assert(y!=0, "Division by zero"); 
     115        BigInt r; 
     116        uint u = y < 0 ? -y : y; 
     117        r.data = BigUint.divInt(data, u); 
     118        r.sign = r.isZero()? false : this.sign != (y<0); 
     119        return r; 
     120    } 
     121    /// 
     122    BigInt opDivAssign(T: int)(T y) { 
     123        assert(y!=0, "Division by zero"); 
     124        uint u = y < 0 ? -y : y; 
     125        data = BigUint.divInt(data, u); 
     126        sign = data.isZero()? false : sign ^ (y<0); 
    126127        return *this; 
    127128    } 
    …… 
    130131        assert(y!=0); 
    131132        uint u = y < 0 ? -y : y; 
    132         int rem = biguintModInt(data, u); 
     133        int rem = BigUint.modInt(data, u); 
    133134        // x%y always has the same sign as x. 
    134135        // This is not the same as mathematical mod. 
    …… 
    139140        assert(y!=0); 
    140141        uint u = y < 0 ? -y : y; 
    141         int rem = biguintModInt(data, u); 
     142        data = BigUint.modInt(data, u); 
    142143        // x%y always has the same sign as x. 
    143144        // This is not the same as mathematical mod. 
    144         assignUint(rem); 
    145145        return *this; 
    146146    } 
    …… 
    161161    BigInt opPostInc() { 
    162162        BigInt old = *this; 
    163         *this = addsubInternal(*this, 1, false); 
     163        data = BigUint.addOrSubInt(data, 1, false, &sign); 
    164164        return old; 
    165165    } 
    …… 
    167167    BigInt opPostDec() { 
    168168        BigInt old = *this; 
    169         *this = addsubInternal(*this, 1, true); 
     169        data = BigUint.addOrSubInt(data, 1, true, &sign); 
    170170        return old; 
    171171    } 
    …… 
    173173    BigInt opShr(T:int)(T y) { 
    174174        BigInt r; 
    175         r.data = biguintShr(this.data, y); 
    176         r.sign = r.isZero()? false : sign; 
     175        r.data = BigUint.shr(data, y); 
     176        r.sign = r.data.isZero()? false : sign; 
    177177        return r; 
    178178    } 
    179179    /// 
    180180    BigInt opShrAssign(T:int)(T y) { 
    181         data = biguintShr(this.data, y); 
    182         if (isZero()) sign = false; 
     181        data = BigUint.shr(data, y); 
     182        if (data.isZero()) sign = false; 
    183183        return *this; 
    184184    } 
    …… 
    186186    BigInt opShl(T:int)(T y) { 
    187187        BigInt r; 
    188         r.data = biguintShl(this.data, y); 
     188        r.data = BigUint.shl(data, y); 
    189189        r.sign = sign; 
    190190        return r; 
    …… 
    192192    /// 
    193193    BigInt opShlAssign(T:int)(T y) { 
    194         data = biguintShl(this.data, y); 
     194        data = BigUint.shl(data, y); 
    195195        return *this; 
    196196    } 
    197197    /// 
    198198    int opEquals(BigInt y) { 
    199        return sign == y.sign && y.data[] == data[]; 
     199       return sign == y.sign && y.data == data; 
    200200    } 
    201201    /// 
    202202    int opCmp(BigInt y) { 
    203203        if (sign!=y.sign) return sign ? -1 : 1; 
    204         if (data.length!=y.data.length) return data.length - y.data.length; 
    205         return biguintCompare(data, y.data); 
     204        return BigUint.compare(data, y.data); 
    206205    } 
    207206public: 
    208207    /// BUG: For testing only, this will be removed eventually 
    209208    int numBytes() { 
    210         return data.length * uint.sizeof; 
     209        return data.numBytes(); 
    211210    } 
    212211    /// BUG: For testing only, this will be removed eventually 
    213212    char [] toDecimalString(){ 
    214         uint predictlength = 20+20*(data.length/2); // just over 19 
    215         char [] buff = new char[predictlength]; 
    216         int sofar = biguintToDecimal(buff, data.dup); 
    217         if (isNegative()) {--sofar; buff[sofar]='-'; } 
    218          
    219         return buff[sofar..$]; 
     213        char [] buff = data.toDecimalString(1); 
     214        if (isNegative()) buff[0] = '-'; 
     215        else buff = buff[1..$]; 
     216        return buff; 
    220217    } 
    221218    /// BUG: For testing only, this will be removed eventually 
    …… 
    225222        // The length will be less than 1 + s.length/log2(10) = 1 + s.length/3.3219. 
    226223        // 485 bits will only just fit into 146 decimal digits. 
    227         uint predictlength = (18*2 + 2* s.length)/19; 
    228         data = new uint[predictlength]; 
    229224        if (s[0]=='-') { sign=true; s=s[1..$]; } 
    230225        else sign = false; 
    231         uint hi = biguintFromDecimal(data, s); 
    232         data.length = hi; 
    233          
     226        data.fromDecimalString(s); 
    234227    } 
    235228    char [] toHex() { 
    236         int len = data.length*9; 
    237         int start = 0; 
    238         if (sign) { 
    239             ++len; 
    240             start = 1; 
    241         } 
    242         char [] buff = new char[len]; 
    243         if (sign) buff[0]='-'; 
    244         biguintToHex(buff[start..$], data,'_'); 
     229        char [] buff = data.toHexString(1); 
     230        if (isNegative()) buff[0] = '-'; 
     231        else buff = buff[1..$]; 
    245232        return buff; 
    246233    } 
    247     invariant() { assert(data.length==1 || data[$-1]!=0); } 
    248234private: 
    249     void negate() { if (!isZero()) sign = !sign; } 
    250  
    251     bool isZero() { return data.length==1 && data[0]==0; } 
     235    void negate() { if (!data.isZero()) sign = !sign; } 
     236    bool isZero() { return data.isZero(); } 
    252237    bool isNegative() { return sign; } 
    253 private: 
     238 
     239private:     
    254240    static BigInt addsubInternal(BigInt x, BigInt y, bool wantSub) { 
    255241        BigInt r; 
    256         if (wantSub) { // perform a subtraction 
    257             bool bSign; 
    258             r.data = biguintSub(x.data, y.data, &bSign); 
    259             r.sign = x.sign^bSign; 
    260             if (r.isZero()) { r.data = ZERO; r.sign = false; } 
    261         } else { 
    262             r.data = biguintAdd(x.data, y.data); 
    263             r.sign = x.sign; 
    264         } 
    265         return r; 
    266     } 
    267     static BigInt addsubInternal(BigInt x, ulong y, bool wantSub) { 
    268         BigInt r; 
    269242        r.sign = x.sign; 
    270         if (wantSub) { // perform a subtraction 
    271             if (x.data.length > 2) { 
    272                 r.data = biguintSubInt(x.data, y);                 
    273             } else { // could change sign! 
    274                 ulong xx = x.data[0]; 
    275                 if (x.data.length > 1) xx+= (cast(ulong)x.data[1]) << 32; 
    276                 ulong d; 
    277                 if (xx <= y) { 
    278                     d = y - xx; 
    279                     r.sign = !r.sign; 
    280                 } else { 
    281                     d = xx - y; 
    282                     r.sign = x.sign; 
    283                 } 
    284                 if (d==0) { 
    285                     r.data = ZERO; 
    286                     r.sign = false; 
    287                     return r; 
    288                 } 
    289                 r.data = new uint[ d>uint.max ? 2: 1]; 
    290                 r.data[0] = cast(uint)(d & 0xFFFF_FFFF); 
    291                 if (d>uint.max) r.data[1] = cast(uint)(d>>32); 
    292             } 
    293         } else { 
    294             r.data = biguintAddInt(x.data, y); 
    295         } 
     243        r.data = BigUint.addOrSub(x.data, y.data, wantSub, &r.sign); 
    296244        return r; 
    297245    } 
    298246    static BigInt mulInternal(BigInt x, BigInt y) { 
    299         uint len = x.data.length + y.data.length; 
    300         BigInt r; 
    301         r.data = new uint[len]; 
     247        BigInt r;         
     248        r.data = BigUint.mul(x.data, y.data); 
    302249        r.sign = x.sign ^ y.sign; 
    303         if (y.data.length > x.data.length) { 
    304             biguintMul(r.data, y.data, x.data); 
    305         } else { 
    306             biguintMul(r.data, x.data, y.data); 
    307         } 
    308         // the highest element could be zero,  
    309         // in which case we need to reduce the length 
    310         if (r.data.length > 1 && r.data[$-1] == 0) { 
    311             r.data = r.data[0..$-1]; 
    312         } 
    313         return r; 
    314     } 
     250        return r; 
     251    } 
     252     
    315253    static BigInt modInternal(BigInt x, BigInt y) { 
    316254        if (x.isZero()) return x; 
    317255        BigInt r; 
    318256        r.sign = x.sign; 
    319         r.data = biguintMod(x.data, y.data); 
     257        r.data = BigUint.mod(x.data, y.data); 
    320258        return r; 
    321259    } 
    …… 
    324262        BigInt r; 
    325263        r.sign = x.sign ^ y.sign; 
    326         r.data = biguintDiv(x.data, y.data); 
     264        r.data = BigUint.div(x.data, y.data); 
    327265        return r; 
    328266    } 
    …… 
    331269        BigInt r; 
    332270        if (y==0) { 
    333             r.sign=false; 
    334             r.data = ZERO; 
     271            r.sign = false; 
     272            r.data = 0; 
    335273            return r; 
    336274        } 
    337275        r.sign = negResult; 
    338         r.data = biguintMulInt(x.data, y); 
    339         if (r.data.length > 1 && r.data[$-1] == 0) { 
    340             r.data = r.data[0..$-1]; 
    341         } 
     276        r.data = BigUint.mulInt(x.data, y); 
    342277        return r; 
    343278    } 

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

    r3903 r3914  
    2020 
    2121private: 
    22 /*invariant */ uint [1] BIGINTZERO = [0]; 
     22const uint [] ZERO = [0]; 
     23const uint [] ONE = [1]; 
     24const uint [] TWO = [2]; 
     25const uint [] TEN = [10]; 
     26public:        
     27 
     28// BigUint performs the memory management and wraps the low-level calls. 
     29struct BigUint { 
     30private: 
     31    invariant() { assert(data.length==1 || data[$-1]!=0); } 
     32    uint [] data = ZERO;  
    2333public: 
    24  
     34    static BigUint opCall(uint []x) { 
     35       BigUint a; 
     36       a.data=x; 
     37       return a; 
     38    } 
     39    void opAssign(uint u) { 
     40        if (u==0) data = ZERO; 
     41        else if (u==1) data = ONE; 
     42        else if (u==2) data = TWO; 
     43        else if (u==10) data = TEN; 
     44        else { 
     45            data = new uint[1]; 
     46            data[0] = u; 
     47        } 
     48    } 
     49     
    2550// return 1 if x>y, -1 if x<y, 0 if equal 
    26 int biguintCompare(uint [] x, uint []y) 
    27 { 
    28     uint k = highestDifferentDigit(x, y); 
    29     if (x[k] == y[k]) return 0; 
    30     return x[k] > y[k] ? 1 : -1; 
    31 } 
     51static int compare(BigUint x, BigUint y) 
     52{ 
     53    if (x.data.length!=y.data.length) return x.data.length - y.data.length; 
     54    uint k = highestDifferentDigit(x.data, y.data); 
     55    if (x.data[k] == y.data[k]) return 0; 
     56    return x.data[k] > y.data[k] ? 1 : -1; 
     57} 
     58 
     59int opEquals(BigUint y) { 
     60       return y.data[] == data[]; 
     61} 
     62 
     63bool isZero() { return data.length==1 && data[0]==0; } 
     64 
     65/// BUG: For testing only, this will be removed eventually 
     66int numBytes() { 
     67    return data.length * uint.sizeof; 
     68} 
     69 
     70// the extra bytes are added to the start of the string 
     71char [] toDecimalString(int frontExtraBytes) 
     72{ 
     73    uint predictlength = 20+20*(data.length/2); // just over 19 
     74    char [] buff = new char[frontExtraBytes + predictlength]; 
     75    int sofar = biguintToDecimal(buff, data.dup);        
     76    return buff[sofar-frontExtraBytes..$]; 
     77} 
     78 
     79char [] toHexString(int frontExtraBytes) 
     80{ 
     81    int len = data.length*9 + frontExtraBytes; 
     82    char [] buff = new char[len]; 
     83    biguintToHex(buff[frontExtraBytes..$], data,'_'); 
     84    return buff; 
     85} 
     86 
     87void fromDecimalString(char [] s) 
     88{ 
     89    uint predictlength = (18*2 + 2* s.length)/19; 
     90    data = new uint[predictlength]; 
     91    uint hi = biguintFromDecimal(data, s); 
     92    data.length = hi; 
     93} 
     94 
     95// ////////////////////// 
     96// 
     97// All of these static member functions create a new BigUint. 
    3298 
    3399// return x >> y 
    34 uint [] biguintShr(uint[] x, ulong y) 
     100static BigUint shr(BigUint x, ulong y) 
    35101{ 
    36102    assert(y>0); 
    37103    uint bits = cast(uint)y & 31; 
    38     if ((y>>5) >= x.length) return BIGINTZERO; 
     104    if ((y>>5) >= x.data.length) return BigUint(ZERO); 
    39105    uint words = cast(uint)(y >> 5); 
    40106    if (bits==0) { 
    41         return x[words..$]; 
     107        return BigUint(x.data[words..$]); 
    42108    } else { 
    43         uint [] result = new uint[x.length - words]; 
    44         multibyteShr(result, x[words..$], bits); 
    45         if (result.length>1 && result[$-1]==0) return result[0..$-1]; 
    46         else return result; 
     109        uint [] result = new uint[x.data.length - words]; 
     110        multibyteShr(result, x.data[words..$], bits); 
     111        if (result.length>1 && result[$-1]==0) return BigUint(result[0..$-1]); 
     112        else return BigUint(result); 
    47113    } 
    48114} 
    49115 
    50116// return x << y 
    51 uint [] biguintShl(uint[] x, ulong y) 
     117static BigUint shl(BigUint x, ulong y) 
    52118{ 
    53119    assert(y>0); 
    54     if (x.length==1 && x[0]==0) return x; 
     120    if (x.data.length==1 && x.data[0]==0) return x; 
    55121    uint bits = cast(uint)y & 31; 
    56122    assert ((y>>5) < cast(ulong)(uint.max)); 
    57123    uint words = cast(uint)(y >> 5); 
    58     uint [] result = new uint[x.length + words+1]; 
     124    uint [] result = new uint[x.data.length + words+1]; 
    59125    result[0..words] = 0; 
    60126    if (bits==0) { 
    61         result[words..words+x.length] = x[]; 
    62         return result[0..words+x.length]; 
     127        result[words..words+x.data.length] = x.data[]; 
     128        return BigUint(result[0..words+x.data.length]); 
    63129    } else { 
    64         uint c = multibyteShl(result[words..words+x.length], x, bits); 
    65         if (c==0) return result[0..words+x.length]; 
     130        uint c = multibyteShl(result[words..words+x.data.length], x.data, bits); 
     131        if (c==0) return BigUint(result[0..words+x.data.length]); 
    66132        result[$-1] = c; 
    67         return result; 
    68     } 
    69 } 
     133        return BigUint(result); 
     134    } 
     135} 
     136 
     137    static BigUint addOrSubInt(BigUint x, ulong y, bool wantSub, bool *sign) { 
     138        BigUint r; 
     139        if (wantSub) { // perform a subtraction 
     140            if (x.data.length > 2) { 
     141                r.data = subInt(x.data, y);                 
     142            } else { // could change sign! 
     143                ulong xx = x.data[0]; 
     144                if (x.data.length > 1) xx+= (cast(ulong)x.data[1]) << 32; 
     145                ulong d; 
     146                if (xx <= y) { 
     147                    d = y - xx; 
     148                    *sign = !*sign; 
     149                } else { 
     150                    d = xx - y; 
     151                } 
     152                if (d==0) { 
     153                    r = 0; 
     154                    return r; 
     155                } 
     156                r.data = new uint[ d>uint.max ? 2: 1]; 
     157                r.data[0] = cast(uint)(d & 0xFFFF_FFFF); 
     158                if (d>uint.max) r.data[1] = cast(uint)(d>>32); 
     159            } 
     160        } else { 
     161            r.data = addInt(x.data, y); 
     162        } 
     163        return r; 
     164    } 
     165 
     166    static BigUint addOrSub(BigUint x, BigUint y, bool wantSub, bool *sign) { 
     167        BigUint r; 
     168        if (wantSub) { // perform a subtraction 
     169            r.data = sub(x.data, y.data, sign); 
     170            if (r.isZero()) { *sign = false; } 
     171        } else { 
     172            r.data = add(x.data, y.data); 
     173        } 
     174        return r; 
     175    } 
     176 
     177 
     178/** return x*y. 
     179 *  y must not be zero. 
     180 */ 
     181static BigUint mulInt(BigUint x, ulong y) 
     182{ 
     183    uint hi = cast(uint)(y >>> 32); 
     184    uint lo = cast(uint)(y & 0xFFFF_FFFF); 
     185    uint [] result = new uint[x.data.length+1+(hi!=0)]; 
     186    result[x.data.length] = multibyteMul(result[0..x.data.length], x.data, lo, 0); 
     187    if (hi!=0) { 
     188        result[x.data.length+1] = multibyteMulAdd!('+')(result[1..x.data.length+1], 
     189            x.data, hi, 0); 
     190    } 
     191    if (result.length > 1 && result[$-1] == 0) { 
     192            result = result[0..$-1]; 
     193    } 
     194    return BigUint(result); 
     195} 
     196 
     197static BigUint mul(BigUint x, BigUint y) 
     198{ 
     199    uint len = x.data.length + y.data.length; 
     200    BigUint r; 
     201    r.data = new uint[len]; 
     202    if (y.data.length > x.data.length) { 
     203        mulInternal(r.data, y.data, x.data); 
     204    } else { 
     205        mulInternal(r.data, x.data, y.data); 
     206    } 
     207    // the highest element could be zero,  
     208    // in which case we need to reduce the length 
     209    if (r.data.length > 1 && r.data[$-1] == 0) { 
     210        r.data = r.data[0..$-1]; 
     211    } 
     212    return r; 
     213} 
     214 
     215// return x/y 
     216static BigUint divInt(BigUint x, uint y) { 
     217    uint [] result = new uint[x.data.length]; 
     218    if ((y&(-y))==y) { 
     219        assert(y!=0); 
     220        // perfect power of 2 
     221        uint b = 0; 
     222        for (;y!=0; y>>=1) { 
     223            ++b; 
     224        } 
     225        multibyteShr(result, x.data, b); 
     226    } else { 
     227        result[] = x.data[]; 
     228        uint rem = multibyteDivAssign(result, y, 0); 
     229    } 
     230    if (result[$-1]==0 && result.length>1) { 
     231        return BigUint(result[0..$-1]); 
     232    } else return BigUint(result); 
     233} 
     234 
     235// return x%y 
     236static uint modInt(BigUint x, uint y) { 
     237    assert(y!=0); 
     238    if (y&(-y)==y) { // perfect power of 2         
     239        return x.data[0]&(y-1);    
     240    } else { 
     241        // horribly inefficient - malloc, copy, & store are unnecessary. 
     242        uint [] wasteful = new uint[x.data.length]; 
     243        wasteful[] = x.data[]; 
     244        uint rem = multibyteDivAssign(wasteful, y, 0); 
     245        delete wasteful; 
     246        return rem; 
     247    }    
     248} 
     249 
     250static BigUint div(BigUint x, BigUint y) 
     251{ 
     252    if (y.data.length > x.data.length) return BigUint(ZERO); 
     253    if (y.data.length == 1) return divInt(x, y.data[0]); 
     254    uint [] result = new uint[x.data.length - y.data.length + 1]; 
     255    schoolbookDivMod(result, null, x.data, y.data); 
     256    if (result.length>1 && result[$-1]==0) result=result[0..$-1]; 
     257    return BigUint(result); 
     258} 
     259 
     260static BigUint mod(BigUint x, BigUint y) 
     261{ 
     262    if (y.data.length > x.data.length) return x; 
     263    if (y.data.length == 1) return divInt(x, y.data[0]); 
     264    uint [] result = new uint[x.data.length - y.data.length + 1]; 
     265    uint [] rem = new uint[y.data.length]; 
     266    schoolbookDivMod(result, rem, x.data, y.data); 
     267    while (rem.length>1 && rem[$-1]==0) rem = rem[0..$-1]; 
     268    return BigUint(rem); 
     269} 
     270 
     271} // end BigUint 
     272 
     273private: 
     274 
    70275 
    71276/** General unsigned subtraction routine for bigints. 
    72277 *  Sets result = x - y. If the result is negative, negative will be true. 
    73278 */ 
    74 uint [] biguintSub(uint[] x, uint[] y, bool *negative) 
     279uint [] sub(uint[] x, uint[] y, bool *negative) 
    75280{ 
    76281    if (x.length == y.length) { 
    …… 
    110315 
    111316// return a + b 
    112 uint [] biguintAdd(uint[] a, uint [] b) { 
     317uint [] add(uint[] a, uint [] b) { 
    113318    uint [] x, y; 
    114319    if (a.length<b.length) { x = b; y = a; } else { x = a; y = b; } 
    …… 
    127332    } else return result[0..$-1]; 
    128333} 
    129  
    130  
     334     
    131335/** return x+y 
    132336 */ 
    133 uint [] biguintAddInt(uint[] x, ulong y) 
     337uint [] addInt(uint[] x, ulong y) 
    134338{ 
    135339    uint hi = cast(uint)(y >>> 32); 
    …… 
    148352} 
    149353 
    150 /** Return x-y.. 
     354/** Return x-y. 
    151355 *  x must be greater than y. 
    152356 */   
    153 uint [] biguintSubInt(uint[] x, ulong y) 
     357uint [] subInt(uint[] x, ulong y) 
    154358{ 
    155359    uint hi = cast(uint)(y >>> 32); 
    …… 
    163367} 
    164368 
    165 /** return x*y. 
    166  *  y must not be zero. 
    167  */ 
    168 uint [] biguintMulInt(uint [] x, ulong y) 
    169 { 
    170     uint hi = cast(uint)(y >>> 32); 
    171     uint lo = cast(uint)(y & 0xFFFF_FFFF); 
    172     uint [] result = new uint[x.length+1+(hi!=0)]; 
    173     result[x.length] = multibyteMul(result[0..x.length], x, lo, 0); 
    174     if (hi!=0) { 
    175         result[x.length+1] = multibyteMulAdd!('+')(result[1..x.length+1], x, hi, 0); 
    176     } 
    177     return result; 
    178 } 
    179  
    180369/** General unsigned multiply routine for bigints. 
    181370 *  Sets result = x*y. 
    …… 
    185374 *  
    186375 */ 
    187 void biguintMul(uint[] result, uint[] x, uint[] y) 
     376void mulInternal(uint[] result, uint[] x, uint[] y) 
    188377{ 
    189378    assert( result.length == x.length + y.length ); 
    …… 
    291480} 
    292481 
    293 // return x/y 
    294 uint[] biguintDivInt(uint [] x, uint y) { 
    295     uint [] result = new uint[x.length]; 
    296     if ((y&(-y))==y) { 
    297         assert(y!=0); 
    298         // perfect power of 2 
    299         uint b = 0; 
    300         for (;y!=0; y>>=1) { 
    301             ++b; 
    302         } 
    303         multibyteShr(result, x, b); 
    304     } else { 
    305         result[] = x[]; 
    306         uint rem = multibyteDivAssign(result, y, 0); 
    307     } 
    308     if (result[$-1]==0 && result.length>1) { 
    309         return result[0..$-1]; 
    310     } else return result; 
    311 } 
    312  
    313 // return x%y 
    314 uint biguintModInt(uint [] x, uint y) { 
    315     assert(y!=0); 
    316     if (y&(-y)==y) { // perfect power of 2         
    317         return x[0]&(y-1);    
    318     } else { 
    319         // horribly inefficient - malloc, copy, & store are unnecessary. 
    320         uint [] wasteful = new uint[x.length]; 
    321         wasteful[] = x[]; 
    322         uint rem = multibyteDivAssign(wasteful, y, 0); 
    323         delete wasteful; 
    324         return rem; 
    325     }    
    326 } 
    327  
    328 uint [] biguintDiv(uint [] x, uint [] y) 
    329 { 
    330     if (y.length > x.length) return BIGINTZERO; 
    331     if (y.length == 1) return biguintDivInt(x, y[0]); 
    332     uint [] result = new uint[x.length - y.length + 1]; 
    333     schoolbookDivMod(result, null, x, y); 
    334     if (result.length>1 && result[$-1]==0) result=result[0..$-1]; 
    335     return result; 
    336 } 
    337  
    338 uint [] biguintMod(uint [] x, uint [] y) 
    339 { 
    340     if (y.length > x.length) return x; 
    341     if (y.length == 1) return biguintDivInt(x, y[0]); 
    342     uint [] result = new uint[x.length - y.length + 1]; 
    343     uint [] rem = new uint[y.length]; 
    344     schoolbookDivMod(result, rem, x, y); 
    345     while (rem.length>1 && rem[$-1]==0) rem = rem[0..$-1]; 
    346     return rem; 
    347 } 
    348  
    349 public: 
     482 
     483private: 
    350484// Converts a big uint to a hexadecimal string. 
    351485// 
    …… 
    596730         
    597731    // Karatsuba multiply uses the following result: 
    598     // (Nx1 + x0)*(Ny1 + y0) = (N*N) x1y1 + x0y0 + N * mid 
     732    // (Nx1 + x0)*(Ny1 + y0) = (N*N)*x1y1 + x0y0 + N * mid 
    599733    // where mid = (x1+x0)*(y1+y0) - x1y1 - x0y0 
    600734    // requiring 3 multiplies of length N, instead of 4. 
    …… 
    619753    // This will generate carries of either 0 or 1. 
    620754    // TODO: Knuth's variant would save the extra two additions: 
    621     // (Nx1 + x0)*(Ny1 + y0) = (N*N) x1y1 + x0y0 - N * mid 
     755    // (Nx1 + x0)*(Ny1 + y0) = (N*N)*x1y1 + x0y0 - N * mid 
    622756    // where mid = (x0-x1)*(y0-y1) - x1y1 - x0y0 
    623757    // since then mid.length cannot exceed length N. 
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