www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - a Big Number module

reply yidabu <yidabu.nospam gmail.com> writes:
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit

Examples:

    auto a = new Bignumer("12345678901234567890123456789012345678901234567890");
    auto b = new Bignumer("12345678901234567890123456789012345678901234567890");
    auto c = a - b;
    Trace("a - b = ")( c.toUtf8() ).newline;
    c = a + b -b;
    Trace("a + b - b = ")( c.toUtf8() ).newline;
    c = a * b / b;      //lost data here!
    Trace("a * b / b = ")( c.toUtf8() ).newline;
    c = a / b * b;
    Trace("a / b * b = ")( c.toUtf8() ).newline;

Bug: very low  efficiency of opDiv now. 


CODE Begin:

/*******************************************************************************
        
        copyright:      Copyright (c) 2007  (yidabu  g m a i l at com) All
rights reserved

        license:        BSD style: $(LICENSE)

        version:        Initial release: 2007

        author:         modified by yidabu ( D China :
http://bbs.yidabu.com/forum-10-1.html )
        original post:  http://www.fenglin.info/gen_ex/53/Algorithm/323345.html

*******************************************************************************/

module dwin.lab.Bignumer;


import tango.text.convert.Integer;
debug( UnitTest ) import tango.util.log.Trace;  

class Bignumer 
{ 
public: 
    enum{BASELEN = 3,BASE = 1_000}; 
    enum{MAX = 100};      //i'm thinking change this to dynamic array if 
possible.... 
    uint data[MAX];   //initialize as 0 
    uint len;         //initialize as 0  
    int  sign;        //initialize as 0   ; 0: positive; 1: negative 
	
    this (Bignumer b){ 
        Assign(b); 
    } 
    void Assign(Bignumer b) 
    { 
        len = b.len; 
        sign = b.sign; 
        data[]=b.data[]; 
    } 
    this(int num = 0){                 
        if(num == 0){len = 1;return;} 
        if(num < 0){ 
            sign = 1; 
            num = -num; 
        }        
        while(num > 0){            
            data[len++] = num % BASE; 
            num /= BASE; 
        } 
    } 
     
    this(char[] num){        
        if(num.length == 0) {len = 1;return;} 
        int beg = 0;       
        switch(num[0]){ 
			case '-': {sign = 1;}; 
			case '+': {++beg;} ;
			default : break; 
        } 
        int i = num.length - BASELEN; 
        for(; i >= beg; i -= BASELEN){     
            char[] tmp = num[i..i+BASELEN]; 
            data[len++] = atoi(tmp); 
            //data[len++] = std.conv.toUint(tmp); 
        } 
        i += BASELEN; 
        if(i>beg){ 
            char[] tmp = num[0..i]; 
            data[len++] = atoi(tmp); 
            //data[len++] = std.conv.toUint(tmp); 
        }        
    } 
     
    Bignumer opNeg() 
    { 
        Bignumer ret = new Bignumer(this); 
        ret.sign ^= 1; 
        return ret; 
    } 
         
    int opEquals(Bignumer b){ 
        if(sign != b.sign || len != b.len) return 0; 
        return data == b.data;         
    } 
     
    int absCmp(Bignumer b, Bignumer r){ 
        if(b.len>r.len) return 1; 
        else if(b.len<r.len) return 0;       
         
        for(int i = b.len-1;i >= 0; i--){ 
            if(b.data[i] > r.data[i]) 
                return 1; 
            else if(b.data[i] < r.data[i]) return 0; 
        } 
        return 0;        
    } 
     
    int opCmp(Bignumer b) 
    { 
        if(sign < b.sign) return 1; 
        else if(sign > b.sign) return 0;       
        if(sign == 0) return absCmp(this,b); 
        else return 1&absCmp(b,this);                
    } 
         
     // +
    Bignumer opAdd(Bignumer b) 
    {                                
        if(sign!=b.sign){ 
            b.sign ^= 1; 
            Bignumer ret = this-b; 
            b.sign ^= 1; 
            return ret; 
        }            
        Bignumer ret = new Bignumer(); 
        ret.sign = sign; 
        uint tmp = 0;      
        uint i; 
        for(i = 0; i<b.len && i<len; i++){ 
            ret.data[i]= (data[i] + b.data[i] + tmp) % BASE; 
            tmp = (data[i] + b.data[i] + tmp) / BASE;          
        }        
        void residual(uint len,uint data[]){ 
            for(;i < len; i++){ 
                ret.data[i] = (tmp + data[i]) % BASE; 
                tmp = (tmp + data[i]) / BASE;                       
     
            } 
        } 
        if(i < len) 
            residual(len, data);                              
        else if(i < b.len) 
            residual(b.len, b.data); 
        ret.len = i;       
        if(tmp) ret.data[ret.len++] = tmp;         
        return ret;      
    } 
         
	// -
    Bignumer opSub(Bignumer b) 
    {                                 
        if(sign != b.sign){ 
            b.sign ^= 1; 
            Bignumer ret = this + b;    
            b.sign ^= 1; 
            return ret; 
        } 
        Bignumer big,small; 
        Bignumer ret = new Bignumer(); 
        Bignumer absSub(Bignumer big,Bignumer small){  //assume big > small    
      
            int tmp = 0; 
            uint i;          
            ret.len = big.len; 
            for(i = 0;i<small.len&&i<big.len;i++){  
           
                uint t = small.data[i]+tmp; 
                tmp = (t>big.data[i]); 
                ret.data[i]=(BASE&(-tmp))+big.data[i]-t; 
            }                    
            for(;i<big.len;i++){ 
                uint t = tmp; 
                tmp = (t>big.data[i]); 
				ret.data[i]=(BASE&(-tmp))+big.data[i]-t;                    
     
            } 
            while(ret.data[ret.len-1] == 0&&ret.len>1) 
				ret.len--;      
            return ret; 
        }                    
        if(absCmp(this,b)){          
            big = this;small = b; 
            ret.sign = sign; 
        }else{           
            small = this;big = b; 
            ret.sign = sign^1; 
        }                                                
        return absSub(big,small); 
    } 
         
	// *
    Bignumer opMul(Bignumer b){ 
        Bignumer ret = new Bignumer; 
        ret.sign = (b.sign^sign); 
        ret.len = (len+b.len-1); 
        uint tmp = 0; 
         
        for(uint i = 0;i<len;i++){ 
            for(int j = 0;j<b.len;j++){ 
                int c;               
                c = (ret.data[i+j]+data[i]*b.data[j]+tmp)/BASE; 
                //writefln(data[i],",",b.data[j],"; ",data[i]*b.data[j]); 
                 
				ret.data[i+j]=(ret.data[i+j]+data[i]*b.data[j]+tmp)%BASE;       
         
                tmp = c; 
            }            
        }                
        if(tmp) 
            ret.data[ret.len++]=tmp; 
        while(ret.data[ret.len-1] == 0&&ret.len>1) ret.
			len--;  
        return ret; 
    } 
         
	// /
    Bignumer opDiv(Bignumer b){ 
        Bignumer ret = new Bignumer; 
        if( len < b.len) return ret;        
        ret.sign = (b.sign ^ sign);        
        ret.len = len-b.len+1; 
        Bignumer tmp = new Bignumer(this);       
        tmp >>= (len-b.len+1);         
        int i = len-b.len; 
        for(; i >= 0; i--){ 
            tmp <<= 1;             
            tmp = tmp + new Bignumer(data[i]); 
            Bignumer c2 = new Bignumer(b); 
            int j = 1; 
            for(; c2 <= tmp && j < BASE; j++, c2 = c2+b){};
			//very low  efficiency,use binary search will be better 
			j--; 
            ret.data[i]=j;                       
            tmp = (tmp-c2+b);          
        } 
        while(ret.data[ret.len-1] ==0 && ret.len > 1) ret.len--;  
        return ret; 
    } 
     
     
    Bignumer opAddAssign(Bignumer b) 
    { 
        Bignumer tmp = this + b; 
        Assign(tmp); 
        return this; 
    } 
     
    Bignumer opSubAssign(Bignumer b) 
    { 
        Bignumer tmp = this - b; 
        Assign(tmp); 
        return this; 
    } 
     
    Bignumer opMulAssign(Bignumer b) 
    { 
        Bignumer tmp = this * b; 
        Assign(tmp); 
        return this; 
    } 
    Bignumer opDivAssign(Bignumer b) 
    { 
        Bignumer tmp = this / b; 
        Assign(tmp); 
        return this; 
    } 
    Bignumer opShr(uint s) 
    { 
        Bignumer ret = new Bignumer(this); 
        ret>>=s; 
        return ret; 
    } 
     
    Bignumer opShrAssign(uint s){ 
        uint i; 
        for(i = 0;i<(len-s);i++) 
            data[i]=data[i+s];       
        for(;i<len;i++)data[i]=0; 
        len-=s; 
        return this; 
    } 
         
    Bignumer opShlAssign(uint s){ 
        assert(len+s<MAX); 
        int i;                       
        for(i = len-1;i>=0;i--)        
            data[i+s]=data[i];       
        for(i = 0;i<s;i++) data[i]=0; 
        len+=s; 
        return this; 
    } 
     
    Bignumer opShl(uint s) 
    { 
        Bignumer ret = new Bignumer(this); 
        ret<<=s; 
        return ret; 
    } 
     
    //char[] toString(){ 
    char[] toUtf8(){ 
        char[64] tmp;
        char[] ret; 
        if(sign) ret~="-"; 
        else     ret~="+"; 
        for(int i = len-1; i >= 0; i--){ 
            //ret~= .toString(data[i]) ~ ","; 
            ret ~= itoa(tmp, data[i] ) ~ ","; 
        } 
        //ret ~= "BASE:"~ .toString(BASE); 
        //ret ~= "BASE:"~ itoa(tmp, BASE); 
        return ret;      
    } 
} 


debug( UnitTest ) unittest
{ 
    auto a = new Bignumer("12345678901234567890123456789012345678901234567890");
    auto b = new Bignumer("12345678901234567890123456789012345678901234567890");
    auto c = a - b;
    Trace("a - b = ")( c.toUtf8() ).newline;
    c = a + b -b;
    Trace("a + b - b = ")( c.toUtf8() ).newline;
    c = a * b / b;      //lost data here!
    Trace("a * b / b = ")( c.toUtf8() ).newline;
    c = a / b * b;
    Trace("a / b * b = ")( c.toUtf8() ).newline;
         
} 


CODE End.




-- 
yidabu <yidabu.nospam gmail.com>
D China:
http://bbs.yidabu.com/forum-10-1.html
Oct 13 2007
next sibling parent yidabu <yidabu.nospam gmail.com> writes:
Content-Type: text/plain

see attach.
Oct 13 2007
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
A few questions:


Why did you chouse to represent the number in base 1000? (BTW you can save 
space by using ushort to store the digits or by switching to base 1_000_000)

did you consider tying to implement it with ASM?

Would you like to put this in scrapple on DSource?

From the links below It looks like someone has translated the D docs into 
Chinese(!) If this is more than a little bit done, I'm sure Walter would 
be vary interested in links.

The the spelling of the type (Bignumer vs. Bignumber) intentional?

Reply to yidabu,

 Examples:
 
 auto a = new
 Bignumer("12345678901234567890123456789012345678901234567890");
 auto b = new
 Bignumer("12345678901234567890123456789012345678901234567890");
 auto c = a - b;
 Trace("a - b = ")( c.toUtf8() ).newline;
 c = a + b -b;
 Trace("a + b - b = ")( c.toUtf8() ).newline;
 c = a * b / b;      //lost data here!
 Trace("a * b / b = ")( c.toUtf8() ).newline;
 c = a / b * b;
 Trace("a / b * b = ")( c.toUtf8() ).newline;
 Bug: very low  efficiency of opDiv now.
 
 CODE Begin:
 
 /*********************************************************************
 **********
 
 copyright:      Copyright (c) 2007  (yidabu  g m a i l at com)
 All rights reserved
 
 license:        BSD style: $(LICENSE)
 
 version:        Initial release: 2007
 
 author:         modified by yidabu ( D China :
 http://bbs.yidabu.com/forum-10-1.html )
 original post:
 http://www.fenglin.info/gen_ex/53/Algorithm/323345.html
 **********************************************************************
 *********/
 
 module dwin.lab.Bignumer;
 
 import tango.text.convert.Integer;
 debug( UnitTest ) import tango.util.log.Trace;
 class Bignumer
 {

Oct 13 2007
parent Walter Bright <newshound1 digitalmars.com> writes:
yidabu wrote:
 4. D China ( http://bbs.yidabu.com/forum-10-1.html ) has D docs above
 DMD 1.012, and many articles about D in Chinese.

Thanks for the link! Also, could you add "D Programming Language" to the template for the web site so every page on it about D has the phrase on it? This helps Google tie together all the D sites. Thanks!
Oct 14 2007
prev sibling next sibling parent reply yidabu <yidabu.nospam gmail.com> writes:
 Why did you chouse to represent the number in base 1000? (BTW you can save 
 space by using ushort to store the digits or by switching to base 1_000_000)

1. now use base 1_000_000.
 did you consider tying to implement it with ASM?
 

2. I'm new to ASM. I'm happy if someone can will do that.
 Would you like to put this in scrapple on DSource?
 

3. scrapple is a good project on DSource. I'm greatly appreciate if I have the right.
 From the links below It looks like someone has translated the D docs into 
 Chinese(!) If this is more than a little bit done, I'm sure Walter would 
 be vary interested in links.
 

4. D China ( http://bbs.yidabu.com/forum-10-1.html ) has D docs above DMD 1.012, and many articles about D in Chinese.
 The the spelling of the type (Bignumer vs. Bignumber) intentional?
 

5. thx. fixed now.
 Reply to yidabu,
 
 Examples:
 
 auto a = new
 Bignumer("12345678901234567890123456789012345678901234567890");
 auto b = new
 Bignumer("12345678901234567890123456789012345678901234567890");
 auto c = a - b;
 Trace("a - b = ")( c.toUtf8() ).newline;
 c = a + b -b;
 Trace("a + b - b = ")( c.toUtf8() ).newline;
 c = a * b / b;      //lost data here!
 Trace("a * b / b = ")( c.toUtf8() ).newline;
 c = a / b * b;
 Trace("a / b * b = ")( c.toUtf8() ).newline;
 Bug: very low  efficiency of opDiv now.
 
 CODE Begin:
 
 /*********************************************************************
 **********
 
 copyright:      Copyright (c) 2007  (yidabu  g m a i l at com)
 All rights reserved
 
 license:        BSD style: $(LICENSE)
 
 version:        Initial release: 2007
 
 author:         modified by yidabu ( D China :
 http://bbs.yidabu.com/forum-10-1.html )
 original post:
 http://www.fenglin.info/gen_ex/53/Algorithm/323345.html
 **********************************************************************
 *********/
 
 module dwin.lab.Bignumer;
 
 import tango.text.convert.Integer;
 debug( UnitTest ) import tango.util.log.Trace;
 class Bignumer
 {


-- yidabu <yidabu.nospam gmail.com> D China: http://bbs.yidabu.com/forum-10-1.html
Oct 13 2007
parent reply BCS <ao pathlink.com> writes:
Reply to yidabu,

 1. now use base 1_000_000.
 

cool I assume you are sticking to powers of ten so that output is easier?
 did you consider tying to implement it with ASM?
 


actually I have an arbitrary static sized implementation in dsource that does use ASM (x86 only) but it only works up to about 1000 bits (I think, and that's old so who knows) before it crashes DMD
 Would you like to put this in scrapple on DSource?
 

have the right.

send me your dsource username and I'll add you
 From the links below It looks like someone has translated the D docs
 into Chinese(!) If this is more than a little bit done, I'm sure
 Walter would be vary interested in links.
 

DMD 1.012, and many articles about D in Chinese.

<coff> <coff> Walter? some links for you
Oct 13 2007
parent reply yidabu <yidabu.nospam gmail.com> writes:
Content-Type: text/plain

BCS Wrote:

 actually I have an arbitrary static sized implementation in dsource that 
 does use ASM (x86 only) but it only works up to about 1000 bits (I think, 
 and that's old so who knows) before it crashes DMD

I try yourt implementtation of Big Number, I do know how to use a arbitrary size input number like: auto a = new Bignumber("12345678901234567890123456789012345678901234567890");
 send me your dsource username and I'll add you

my dsource username is yidabu
 4. D China ( http://bbs.yidabu.com/forum-10-1.html ) has D docs above
 DMD 1.012, and many articles about D in Chinese.
 

Walter? some links for you.

Oct 13 2007
parent BCS <ao pathlink.com> writes:
Reply to yidabu,

 BCS Wrote:
 
 actually I have an arbitrary static sized implementation in dsource
 that does use ASM (x86 only) but it only works up to about 1000 bits
 (I think, and that's old so who knows) before it crashes DMD
 

arbitrary size input number like: auto a = new Bignumber("12345678901234567890123456789012345678901234567890");

My implementation uses binary directly so the best wat to set a value is to somehow covert the value to hex and then push that into the strut BigNum!(8) bn; bn.values = [ // set to 2^255 + 2^127 0x8000_0000u, //*2^224 0x0, //*2^192 0x0, //*2^160 0x0, //*2^128 0x8000_0000u, //*2^96 0x0, //*2^64 0x0, //*2^32 0x0 //*2^0 ];
 my dsource username is yidabu
 

you are in
Oct 14 2007
prev sibling parent reply Regan Heath <regan netmail.co.nz> writes:
You might find this interesting:
http://www.dsource.org/projects/deimos/browser/trunk/etc

It was written more than 3 years ago.

Regan
Oct 14 2007
parent reply yidabu <yidabu.nospam gmail.com> writes:
Regan Heath Wrote:

 You might find this interesting:
 http://www.dsource.org/projects/deimos/browser/trunk/etc
 
 It was written more than 3 years ago.
 
 Regan

Thanks. this project seems dead.
Oct 24 2007
parent reply bearophile <bearophileHUGS lycos.com> writes:
Nice. Can it made to work with Phobos alone too?

Maybe the function bigintLLCountOnes() can be speed up with this:

/*********************************
Quickly return the number of set bits in the given uint
(functions similar to this one can work on 64 bits too).
*/
int countBitUint(TyNumber)(TyNumber v) {
    // This templating trick is useful to avoid processing ulongs
    static if( is(TyNumber == uint) ) {
        v = v - ((v >> 1) & 0x55555555);    // reuse input as temporary
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);        // temp
        return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
    } else
        assert(false, "countBitUint() works only with uint, not with " ~
typeid(TyNumber).toString);
}

Bye,
bearophile
Nov 04 2007
parent reply yidabu <yidabu.nospam gmail.com> writes:
bearophile Wrote:

 Nice. Can it made to work with Phobos alone too?
 
 Maybe the function bigintLLCountOnes() can be speed up with this:
 
 /*********************************
 Quickly return the number of set bits in the given uint
 (functions similar to this one can work on 64 bits too).
 */
 int countBitUint(TyNumber)(TyNumber v) {
     // This templating trick is useful to avoid processing ulongs
     static if( is(TyNumber == uint) ) {
         v = v - ((v >> 1) & 0x55555555);    // reuse input as temporary
         v = (v & 0x33333333) + ((v >> 2) & 0x33333333);        // temp
         return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
     } else
         assert(false, "countBitUint() works only with uint, not with " ~
typeid(TyNumber).toString);
 }
 
 Bye,
 bearophile

Thanks! since Phobos is dead end, I not use it if possible.
Nov 04 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
yidabu wrote:
 bearophile Wrote:
 
 Nice. Can it made to work with Phobos alone too?

 Maybe the function bigintLLCountOnes() can be speed up with this:

 /*********************************
 Quickly return the number of set bits in the given uint
 (functions similar to this one can work on 64 bits too).
 */
 int countBitUint(TyNumber)(TyNumber v) {
     // This templating trick is useful to avoid processing ulongs
     static if( is(TyNumber == uint) ) {
         v = v - ((v >> 1) & 0x55555555);    // reuse input as temporary
         v = (v & 0x33333333) + ((v >> 2) & 0x33333333);        // temp
         return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
     } else
         assert(false, "countBitUint() works only with uint, not with " ~
typeid(TyNumber).toString);
 }

 Bye,
 bearophile

Thanks! since Phobos is dead end, I not use it if possible.

It *was* a dead end. But now it's back and under new management. So there's hope yet. ... er except if you mean D1.x. Then yeh, Phobos is a dead end. --bb
Nov 04 2007
parent yidabu <yidabu.nospam gmail.com> writes:
Bill Baxter Wrote:

 yidabu wrote:
 bearophile Wrote:
 
 Nice. Can it made to work with Phobos alone too?

 Maybe the function bigintLLCountOnes() can be speed up with this:

 /*********************************
 Quickly return the number of set bits in the given uint
 (functions similar to this one can work on 64 bits too).
 */
 int countBitUint(TyNumber)(TyNumber v) {
     // This templating trick is useful to avoid processing ulongs
     static if( is(TyNumber == uint) ) {
         v = v - ((v >> 1) & 0x55555555);    // reuse input as temporary
         v = (v & 0x33333333) + ((v >> 2) & 0x33333333);        // temp
         return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
     } else
         assert(false, "countBitUint() works only with uint, not with " ~
typeid(TyNumber).toString);
 }

 Bye,
 bearophile

Thanks! since Phobos is dead end, I not use it if possible.

It *was* a dead end. But now it's back and under new management. So there's hope yet. ... er except if you mean D1.x. Then yeh, Phobos is a dead end. --bb

I hope Phobos 2.X open the door to Tango team, if it is not a dead end.
Nov 04 2007