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

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; //initialize as 0
    uint len; //initialize as 0
    int sign; //initialize as 0 ; 0: positive; 1: negative
    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=num%BASE;
            num/=BASE;
        }
    }
    
    this(char num){
        if(num.length==0) {len=1;return;}
        int beg=0;
        switch(num){
        case '-': {sign=1;}
        case '+': {++beg;}
        default : break;
        }
        int i=num.length-BASELEN;
        for(;i>=beg;i-=BASELEN){
            char tmp=num;
            data=atoi(tmp);
        }
        i+=BASELEN;
        if(i>beg){
            char tmp=num;
            data=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>r.data)
                return 1;
            else if(l.data<r.data) 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= (data+l.data+tmp)%BASE;
            tmp = (data+l.data+tmp)/BASE;
        }
        void residual(uint len,uint data){
            for(;i<len;i++){
                ret.data=(tmp+data)%BASE;
                tmp = (tmp+data)/BASE;
            }
        }
        if(i<len)
            residual(len,data);
        else if(i<l.len)
            residual(l.len,l.data);
        ret.len=i;
        if(tmp) ret.data=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+tmp;
                tmp=(t>big.data);
                ret.data=(BASE&(-tmp))+big.data-t;
            }
            for(;i<big.len;i++){
                uint t=tmp;
                tmp=(t>big.data);
                
ret.data=(BASE&(-tmp))+big.data-t;
            }
            while(ret.data==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+data*l.data+tmp)/BASE;
                //writefln(data,",",l.data," ",data*l.data);
                
ret.data=(ret.data+data*l.data+tmp)%BASE;
                tmp=c;
            }
        }
        if(tmp)
            ret.data=tmp;
        while(ret.data==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);
            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=j;
            tmp=(tmp-c2+l);
        }
        while(ret.data==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=data;
        for(;i<len;i++)data=0;
        len-=s;
        return this;
    }
        
    ZDNum opShlAssign(uint s){
        assert(len+s<MAX);
        int i;
        for(i=len-1;i>=0;i--)
            data=data;
        for(i=0;i<s;i++) data=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)~",";
        }
        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=i;
        a=b*a;
    }
    int time1=GetTickCount()-time0;
    writefln(a);
    writefln(" time: ",time1);
    
    return 1;
}
 


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

========== * * * * * ==========
上级目录
Copyright © 2001-2025 枫林在线(www.FengLin.info)
All Rights Reserved