## digitalmars.D - a Big Number module

• yidabu (325/325) Oct 13 2007 Examples:
• yidabu (1/1) Oct 13 2007 see attach.
• BCS (10/51) Oct 13 2007 A few questions:
• yidabu (9/66) Oct 13 2007 3. scrapple is a good project on DSource. I'm greatly appreciate if I ha...
• BCS (8/26) Oct 13 2007 cool
• yidabu (6/15) Oct 13 2007 I try yourt implementtation of Big Number, I do know how to use a arbit...
• BCS (15/29) Oct 14 2007 My implementation uses binary directly so the best wat to set a value is...
• Walter Bright (4/6) Oct 14 2007 Thanks for the link! Also, could you add "D Programming Language" to the...
• Regan Heath (4/4) Oct 14 2007 You might find this interesting:
• yidabu (2/8) Oct 24 2007 Thanks. this project seems dead.
• bearophile (17/17) Nov 04 2007 Nice. Can it made to work with Phobos alone too?
• yidabu (3/23) Nov 04 2007 Thanks!
• Bill Baxter (5/32) Nov 04 2007 It *was* a dead end. But now it's back and under new management. So
• yidabu (2/36) Nov 04 2007 I hope Phobos 2.X open the door to Tango team, if it is not a dead end.
yidabu <yidabu.nospam gmail.com> writes:
```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

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);
}

// +
{
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 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
yidabu <yidabu.nospam gmail.com> writes:
```see attach.
```
Oct 13 2007
```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

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

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)

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
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

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.

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)

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
```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?

2. I'm new to ASM. I'm happy if someone can will do that.

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?

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.

<coff> <coff> Walter? some links for you
```
Oct 13 2007
yidabu <yidabu.nospam gmail.com> writes:
```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");

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.

```
Oct 13 2007
```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

I try yourt implementtation of Big Number,  I do know how to use a
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
];

you are in
```
Oct 14 2007
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
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
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

```
Oct 24 2007
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
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
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

--bb
```
Nov 04 2007
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