枫林在线论坛精华区>>程序设计
[323345] 主题： D语言大数类
作者： little (渺小·Happy^_^)
标题： D语言大数类[转载]
来自： 192.168.*.*
发贴时间： 2005年01月19日 14:31:18
长度： 7774字

import std.stdio;
import std.string;
import std.math;
import std.c.windows.windows;

class ZDNum
{
public:
    enum{BASELEN=5,BASE=100000};
    enum{MAX=20000};      //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: nega
tive
    this (ZDNum l){
        Assign(l);
    }
    void Assign(ZDNum l)
    {
        len=l.len;
        sign=l.sign;
        data[]=l.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);
        }
        i+=BASELEN;
        if(i>beg){
            char[] tmp=num[0..i];
            data[len++]=atoi(tmp);
        }       
    }
    
    ZDNum opNeg()
    {
        ZDNum ret = new ZDNum(this);
        ret.sign^=1;
        return ret;
    }
        
    int opEquals(ZDNum l){
        if(sign!=l.sign||len!=l.len) return 0;
        return data==l.data;        
    }
    
    
    
    int absCmp(ZDNum l, ZDNum r){
        if(l.len>r.len) return 1;
        else if(l.len<r.len) return 0;      
        
        for(int i=l.len-1;i>=0;i--){
            if(l.data[i]>r.data[i])
                return 1;
            else if(l.data[i]<r.data[i]) return 0;
        }
        return 0;       
    }
    
    int opCmp(ZDNum l)
    {
        if(sign<l.sign) return 1;
        else if(sign>l.sign) return 0;      
        if(sign==0) return absCmp(this,l);
        else return 1&absCmp(l,this);               
    }
        
    
    ZDNum opAdd(ZDNum l)
    {                               
        if(sign!=l.sign){
            l.sign^=1;
            ZDNum ret = this-l;
            l.sign^=1;
            return ret;
        }           
        ZDNum ret=new ZDNum();
        ret.sign = sign;
        uint tmp=0;     
        uint i;
        for(i=0;i<l.len&&i<len;i++){
            ret.data[i]= (data[i]+l.data[i]+tmp)%BASE;
            tmp = (data[i]+l.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<l.len)
            residual(l.len,l.data);
        ret.len=i;      
        if(tmp) ret.data[ret.len++]=tmp;        
        return ret;     
    }
        
    ZDNum opSub(ZDNum l)
    {                                
        if(sign!=l.sign){
            l.sign^=1;
            ZDNum ret=this+l;   
            l.sign^=1;
            return ret;
        }
        ZDNum big,small;
        ZDNum ret=new ZDNum();
        ZDNum absSub(ZDNum big,ZDNum 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,l)){         
            big=this;small=l;
            ret.sign = sign;
        }else{          
            small=this;big=l;
            ret.sign = sign^1;
        }                                               
        return absSub(big,small);
    }
        
    ZDNum opMul(ZDNum l){
        ZDNum ret = new ZDNum;
        ret.sign = (l.sign^sign);
        ret.len=(len+l.len-1);
        uint tmp=0;
        
        for(uint i=0;i<len;i++){
            for(int j=0;j<l.len;j++){
                int c;              
                c=(ret.data[i+j]+data[i]*l.data[j]+tmp)/BASE;
                //writefln(data[i],",",l.data[j],"
; ",data[i]*l.data[j]);
                
ret.data[i+j]=(ret.data[i+j]+data[i]*l.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;
    }
        
    ZDNum opDiv(ZDNum l){
        ZDNum ret = new ZDNum;
        if(len<l.len) return ret;       
        ret.sign = (l.sign^sign);       
        ret.len=len-l.len+1;
        ZDNum tmp=new ZDNum(this);      
        tmp>>=(len-l.len+1);        
        int i=len-l.len;
        for(;i>=0;i--){
            tmp<<=1;            
            tmp=tmp+new ZDNum(data[i]);
            ZDNum c2=new ZDNum(l);
            int j=1;
            for(;c2<=tmp && j<BASE;j++,c2=c2+l){};
 //very low 
efficiency,use binary search will be better
            j--;
            ret.data[i]=j;                      
            tmp=(tmp-c2+l);         
        }
        while(ret.data[ret.len-1]==0&&ret.len>1) ret.
len--; 
        return ret;
    }
    
    
    ZDNum opAddAssign(ZDNum l)
    {
        ZDNum tmp = this + l;
        Assign(tmp);
        return this;
    }
    
    ZDNum opSubAssign(ZDNum l)
    {
        ZDNum tmp = this - l;
        Assign(tmp);
        return this;
    }
    
    ZDNum opMulAssign(ZDNum l)
    {
        ZDNum tmp = this * l;
        Assign(tmp);
        return this;
    }
    ZDNum opDivAssign(ZDNum l)
    {
        ZDNum tmp = this / l;
        Assign(tmp);
        return this;
    }
    ZDNum opShr(uint s)
    {
        ZDNum ret = new ZDNum(this);
        ret>>=s;
        return ret;
    }
    
    ZDNum 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;
    }
        
    ZDNum 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;
    }
    
    ZDNum opShl(uint s)
    {
        ZDNum ret = new ZDNum(this);
        ret<<=s;
        return ret;
    }
    
    char[] toString(){
        char[] ret;
        if(sign) ret~="-";
        else     ret~="+";
        for(int i=len-1;i>=0;i--){
            ret~= .toString(data[i])~",";
        }
        ret~= "BASE:"~.toString(BASE);
        return ret;     
    }
}

int main(char[][] args)
{
    int time0=GetTickCount();
    ZDNum a = new ZDNum(1); //136780142
    ZDNum b = new ZDNum(1);     
    
    for(int i=2;i<=20000;i++){      
        b.len=1;
        b.data[0]=i;
        a=b*a;  
    }
    int time1=GetTickCount()-time0;
    writefln(a);    
    writefln(" time: ",time1);
    
    return 1;
}
 


--
※作者已于 2005-01-19 14:32:27 修改本文※

========== * * * * * ==========
返回