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

Changeset 3915

Show
Ignore:
Timestamp:
08/27/08 02:50:44 (3 months ago)
Author:
Don Clugston
Message:

Conversion from decimal is now done by the constructor. Some parsing bugfixes.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/tango/math/BigInt.d

    r3914 r3915  
    2424struct BigInt 
    2525{ 
    26     // BigInt adds signed arithmetic to BigUint. 
    2726private: 
    28     BigUint data; 
    29     bool sign; 
     27    BigUint data;     // BigInt adds signed arithmetic to BigUint. 
     28    bool sign = false; 
    3029public: 
     30    /// Construct a BigInt from a decimal or hexadecimal string. 
     31    /// The number must be in the form of a D decimal or hex literal: 
     32    /// It may have a leading + or - sign; followed by "0x" if hexadecimal. 
     33    /// Underscores are permitted. 
     34    static BigInt opCall(char [] s) { 
     35        BigInt r; 
     36        if (s[0] == '-') { 
     37            r.sign = true; 
     38            s = s[1..$]; 
     39        } else if (s[0]=='+') { 
     40            s = s[1..$]; 
     41        } 
     42        auto q = 0X3; 
     43        bool ok; 
     44        if (s.length>2 && (s[0..2]=="0x" || s[0..2]=="0X")) { 
     45            ok = r.data.fromHexString(s[2..$]); 
     46        } else { 
     47            ok = r.data.fromDecimalString(s); 
     48        } 
     49        assert(ok); 
     50        return r; 
     51    } 
    3152    /// 
    3253    void opAssign(T:int)(T x) { 
    33         data = (x>=0) ? x : -x; 
    34         sign = (x<0); 
     54        data = (x < 0) ? -x : x; 
     55        sign = (x < 0); 
    3556    } 
    3657    /// 
    3758    BigInt opAdd(T: int)(T y) { 
    38         BigInt r; 
    39         r.sign = sign; 
    40         r.data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), sign!=(y<0), &r.sign); 
     59        ulong u = cast(ulong)(y < 0 ? -y : y); 
     60        BigInt r; 
     61        r.sign = sign; 
     62        r.data = BigUint.addOrSubInt(data, u, sign!=(y<0), &r.sign); 
    4163        return r; 
    4264    }     
    4365    /// 
    4466    BigInt opAddAssign(T: int)(T y) { 
    45         data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), 
    46         sign!=(y<0), &sign); 
     67        ulong u = cast(ulong)(y < 0 ? -y : y); 
     68        data = BigUint.addOrSubInt(data, u, sign!=(y<0), &sign); 
    4769        return *this; 
    4870    }     
    …… 
    6183    /// 
    6284    BigInt opSub(T: int)(T y) { 
    63         BigInt r; 
    64         r.sign = sign; 
    65         r.data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), sign==(y<0), &r.sign); 
     85        ulong u = cast(ulong)(y < 0 ? -y : y); 
     86        BigInt r; 
     87        r.sign = sign; 
     88        r.data = BigUint.addOrSubInt(data, u, sign == (y<0), &r.sign); 
    6689        return r; 
    6790    }         
    6891    /// 
    6992    BigInt opSubAssign(T: int)(T y) { 
    70         data = BigUint.addOrSubInt(data, cast(ulong)(y<0? -y: y), sign==(y<0), &sign); 
     93        ulong u = cast(ulong)(y < 0 ? -y : y); 
     94        data = BigUint.addOrSubInt(data, u, sign == (y<0), &sign); 
    7195        return *this; 
    7296    } 
    …… 
    85109    /// 
    86110    BigInt opMul(T: int)(T y) { 
    87         return mulInternal(*this, cast(ulong)(y<0? -y: y), sign!=(y<0)); 
     111        ulong u = cast(ulong)(y < 0 ? -y : y); 
     112        return mulInternal(*this, u, sign != (y<0)); 
    88113    } 
    89114    ///     
    90115    BigInt opMulAssign(T: int)(T y) { 
    91         *this = mulInternal(*this, cast(ulong)(y<0? -y: y), sign!=(y<0)); 
     116        ulong u = cast(ulong)(y < 0 ? -y : y); 
     117        *this = mulInternal(*this, u, sign != (y<0)); 
    92118        return *this; 
    93119    } 
    …… 
    102128    } 
    103129    /// 
    104     BigInt opDivAssign(T: BigInt)(T y) { 
    105         *this = divInternal(*this, y); 
    106         return *this; 
    107     }     
    108     /// 
    109     BigInt opDiv(T: BigInt)(T y) { 
    110         return divInternal(*this, y); 
    111     }     
    112     /// 
    113130    BigInt opDiv(T:int)(T y) { 
    114131        assert(y!=0, "Division by zero"); 
    …… 
    116133        uint u = y < 0 ? -y : y; 
    117134        r.data = BigUint.divInt(data, u); 
    118         r.sign = r.isZero()? false : this.sign != (y<0); 
     135        r.sign = r.isZero()? false : sign != (y<0); 
    119136        return r; 
    120137    } 
    …… 
    127144        return *this; 
    128145    } 
     146    /// 
     147    BigInt opDivAssign(T: BigInt)(T y) { 
     148        *this = divInternal(*this, y); 
     149        return *this; 
     150    }     
     151    /// 
     152    BigInt opDiv(T: BigInt)(T y) { 
     153        return divInternal(*this, y); 
     154    }     
    129155    /// 
    130156    int opMod(T:int)(T y) { 
    …… 
    146172    } 
    147173    /// 
     174    BigInt opMod(T: BigInt)(T y) { 
     175        return modInternal(*this, y); 
     176    }     
     177    /// 
    148178    BigInt opModAssign(T: BigInt)(T y) { 
    149179        *this = modInternal(*this, y); 
    …… 
    151181    }     
    152182    /// 
    153     BigInt opMod(T: BigInt)(T y) { 
    154         return modInternal(*this, y); 
    155     }     
    156     /// 
    157     BigInt opNeg() { negate(); return *this; } 
     183    BigInt opNeg() { 
     184        negate(); 
     185        return *this; 
     186    } 
    158187    /// 
    159188    BigInt opPos() { return *this; }     
    …… 
    216245        return buff; 
    217246    } 
    218     /// BUG: For testing only, this will be removed eventually 
    219     void fromDecimalString(char [] s) { 
    220         // Convert to base 10_000_000_000_000_000_000. 
    221         // (this is the largest power of 10 that will fit into a long). 
    222         // The length will be less than 1 + s.length/log2(10) = 1 + s.length/3.3219. 
    223         // 485 bits will only just fit into 146 decimal digits. 
    224         if (s[0]=='-') { sign=true; s=s[1..$]; } 
    225         else sign = false; 
    226         data.fromDecimalString(s); 
    227     } 
     247    /// Convert to a hexadecimal string, with an underscore every 
     248    /// 8 characters. 
    228249    char [] toHex() { 
    229         char [] buff = data.toHexString(1); 
     250        char [] buff = data.toHexString(1, '_'); 
    230251        if (isNegative()) buff[0] = '-'; 
    231252        else buff = buff[1..$]; 
    …… 
    247268        BigInt r;         
    248269        r.data = BigUint.mul(x.data, y.data); 
    249         r.sign = x.sign ^ y.sign; 
     270        r.sign = r.isZero() ? false : x.sign ^ y.sign; 
    250271        return r; 
    251272    } 
    …… 
    278299    } 
    279300} 
     301 
     302debug(UnitTest) 
     303{ 
     304unittest { 
     305    // Radix conversion 
     306    assert( BigInt("-1_234_567_890_123_456_789").toDecimalString  
     307        == "-1234567890123456789"); 
     308    assert( BigInt("0x1234567890123456789").toHex == "123_45678901_23456789"); 
     309    assert( BigInt("0x00000000000000000000000000000000000A234567890123456789").toHex 
     310        == "A23_45678901_23456789"); 
     311    assert( BigInt("0x000_00_000000_000_000_000000000000_000000_").toHex == "0"); 
     312 
     313} 
     314} 

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

    r3914 r3915  
    11/** Fundamental operations for arbitrary-precision arithmetic 
     2 * 
     3 * These functions are for internal use only. 
    24 * 
    35 * Copyright: Copyright (C) 2008 Don Clugston.  All rights reserved. 
    …… 
    2628public:        
    2729 
    28 // BigUint performs the memory management and wraps the low-level calls. 
     30// BigUint performs memory management and wraps the low-level calls. 
    2931struct BigUint { 
    3032private: 
    …… 
    3840    } 
    3941    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; 
     42        if (u == 0) data = ZERO; 
     43        else if (u == 1) data = ONE; 
     44        else if (u == 2) data = TWO; 
     45        else if (u == 10) data = TEN; 
    4446        else { 
    4547            data = new uint[1]; 
    …… 
    6163} 
    6264 
    63 bool isZero() { return data.length==1 && data[0]==0; } 
    64  
    65 /// BUG: For testing only, this will be removed eventually 
     65bool isZero() { return data.length == 1 && data[0] == 0; } 
     66 
    6667int numBytes() { 
    6768    return data.length * uint.sizeof; 
    …… 
    7778} 
    7879 
    79 char [] toHexString(int frontExtraBytes) 
    80 { 
    81     int len = data.length*9 + frontExtraBytes; 
     80char [] toHexString(int frontExtraBytes, char separator = 0) 
     81{ 
     82    int len = data.length*8 + frontExtraBytes + (separator? (data.length-1): 0); 
    8283    char [] buff = new char[len]; 
    83     biguintToHex(buff[frontExtraBytes..$], data,'_'); 
    84     return buff; 
    85 } 
    86  
    87 void fromDecimalString(char [] s) 
    88 { 
    89     uint predictlength = (18*2 + 2* s.length)/19; 
     84    biguintToHex(buff[frontExtraBytes..$], data, separator); 
     85    // Strip leading zeros. 
     86    int z = frontExtraBytes; 
     87    while (z< buff.length-1 && buff[z]=='0') ++z; 
     88    return buff[z-frontExtraBytes..$]; 
     89} 
     90 
     91// return false if invalid character found 
     92bool fromHexString(char [] s) 
     93{ 
     94    //Strip leading zeros 
     95    int firstNonZero = 0;     
     96    while ((firstNonZero < s.length -1) &&  
     97        (s[firstNonZero]=='0' || s[firstNonZero]=='_')) { 
     98            ++firstNonZero; 
     99    }     
     100    int len = (s.length - firstNonZero + 15)>>4; 
     101    data = new uint[len+1]; 
     102    uint part = 0; 
     103    uint sofar = 0; 
     104    uint partcount = 0; 
     105    assert(s.length>0); 
     106    for (int i = s.length - 1; i>=firstNonZero; --i) { 
     107        assert(i>=0); 
     108        char c = s[i]; 
     109        if (s[i]=='_') continue; 
     110        uint x = (c>='0' && c<='9')? c - '0' : c>='A' && c<='F'? c-'A'+10 : 
     111            c>='a' && c<='f' ? c-'a' + 10 : 100; 
     112        if (x==100) return false; 
     113        part >>= 4; 
     114        part |= (x<<(32-4)); 
     115        ++partcount; 
     116        if (partcount==8) { 
     117            data[sofar] = part; 
     118            ++sofar; 
     119            partcount = 0; 
     120            part = 0; 
     121        } 
     122    } 
     123    if (part) { 
     124        for (;partcount!=8; ++partcount) part >>= 4; 
     125        data[sofar]=part; 
     126        ++sofar; 
     127    } 
     128    if (sofar==0) { data = ZERO; } 
     129    else data = data[0..sofar]; 
     130    return true; 
     131} 
     132 
     133// return true if OK; false if erroneous characters found 
     134bool fromDecimalString(char [] s) 
     135{ 
     136    //Strip leading zeros 
     137    int firstNonZero = 0;     
     138    while ((firstNonZero < s.length -1) &&  
     139        (s[firstNonZero]=='0' || s[firstNonZero]=='_')) { 
     140            ++firstNonZero; 
     141    }     
     142    uint predictlength = (18*2 + 2* (s.length-firstNonZero))/19; 
    90143    data = new uint[predictlength]; 
    91     uint hi = biguintFromDecimal(data, s); 
     144    uint hi = biguintFromDecimal(data, s[firstNonZero..$]); 
    92145    data.length = hi; 
     146    return true; 
    93147} 
    94148 
    …… 
    135189} 
    136190 
    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); 
     191// If wantSub is false, return x+y 
     192// If wantSub is true, return x-y, and negating sign if x<y 
     193static BigUint addOrSubInt(BigUint x, ulong y, bool wantSub, bool *sign) { 
     194    BigUint r; 
     195    if (wantSub) { // perform a subtraction 
     196        if (x.data.length > 2) { 
     197            r.data = subInt(x.data, y);                 
     198        } else { // could change sign! 
     199            ulong xx = x.data[0]; 
     200            if (x.data.length > 1) xx+= (cast(ulong)x.data[1]) << 32; 
     201            ulong d; 
     202            if (xx <= y) { 
     203                d = y - xx; 
     204                *sign = !*sign; 
     205            } else { 
     206                d = xx - y; 
    159207            } 
    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. 
     208            if (d==0) { 
     209                r = 0; 
     210                return r; 
     211            } 
     212            r.data = new uint[ d > uint.max ? 2: 1]; 
     213            r.data[0] = cast(uint)(d & 0xFFFF_FFFF); 
     214            if (d > uint.max) r.data[1] = cast(uint)(d>>32); 
     215        } 
     216    } else { 
     217        r.data = addInt(x.data, y); 
     218    } 
     219    return r; 
     220} 
     221 
     222// If wantSub is false, return x+y 
     223// If wantSub is true, return x-y, and negating sign if x<y 
     224static BigUint addOrSub(BigUint x, BigUint y, bool wantSub, bool *sign) { 
     225    BigUint r; 
     226    if (wantSub) { // perform a subtraction 
     227        r.data = sub(x.data, y.data, sign); 
     228        if (r.isZero()) { 
     229            *sign = false; 
     230        } 
     231    } else { 
     232        r.data = add(x.data, y.data); 
     233    } 
     234    return r; 
     235} 
     236 
     237 
     238/*  return x*y. 
    179239 *  y must not be zero. 
    180240 */ 
    …… 
    195255} 
    196256 
     257/*  return x*y. 
     258 */ 
    197259static BigUint mul(BigUint x, BigUint y) 
    198260{ 
    …… 
    248310} 
    249311 
     312// return x/y 
    250313static BigUint div(BigUint x, BigUint y) 
    251314{ 
    …… 
    258321} 
    259322 
     323// return x%y 
    260324static BigUint mod(BigUint x, BigUint y) 
    261325{ 
    …… 
    274338 
    275339 
    276 /** General unsigned subtraction routine for bigints. 
     340/* General unsigned subtraction routine for bigints. 
    277341 *  Sets result = x - y. If the result is negative, negative will be true. 
    278342 */ 
    …… 
    333397} 
    334398     
    335 /** return x+y 
     399/* return x+y 
    336400 */ 
    337401uint [] addInt(uint[] x, ulong y) 
    …… 
    367431} 
    368432 
    369 /** General unsigned multiply routine for bigints. 
     433/* General unsigned multiply routine for bigints. 
    370434 *  Sets result = x*y. 
    371435 * 
    …… 
    495559        x+=8; 
    496560        if (separator) { 
    497             if (i>0) buff[x]='_'; 
     561            if (i>0) buff[x] = separator; 
    498562            ++x; 
    499563        } 
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