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.
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
yidabu <yidabu.nospam gmail.com> 
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
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,-- yidabu <yidabu.nospam gmail.com> D China: http://bbs.yidabu.com/forum-10-1.htmlExamples: 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
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?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 DMDdid you consider tying to implement it with ASM?2. I'm new to ASM. I'm happy if someone can will do that.send me your dsource username and I'll add youWould 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.<coff> <coff> Walter? some links for youFrom 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.
Oct 13 2007
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 DMDI 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 youmy dsource username is yidabu4. 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
Reply to yidabu,BCS Wrote: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 ];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 DMDI try yourt implementtation of Big Number, I do know how to use a arbitrary size input number like: auto a = new Bignumber("12345678901234567890123456789012345678901234567890");my dsource username is yidabuyou are in
Oct 14 2007
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
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
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. ReganThanks. this project seems dead.
Oct 24 2007
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
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
yidabu wrote:bearophile Wrote: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. --bbNice. 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, bearophileThanks! since Phobos is dead end, I not use it if possible.
Nov 04 2007
Bill Baxter Wrote:yidabu wrote:I hope Phobos 2.X open the door to Tango team, if it is not a dead end.bearophile Wrote: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. --bbNice. 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, bearophileThanks! since Phobos is dead end, I not use it if possible.
Nov 04 2007