a Big Number module
yidabu
yidabu.nospam at gmail.com
Sat Oct 13 02:30:08 PDT 2007
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 at gmail.com>
D China:
http://bbs.yidabu.com/forum-10-1.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Bignumer.d
Type: text/x-dsrc
Size: 9106 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20071013/2bf98b34/attachment.d>
More information about the Digitalmars-d
mailing list