digitalmars.D - a Big Number module
- yidabu <yidabu.nospam gmail.com> Oct 13 2007
- yidabu <yidabu.nospam gmail.com> Oct 13 2007
- BCS <ao pathlink.com> Oct 13 2007
- Walter Bright <newshound1 digitalmars.com> Oct 14 2007
- yidabu <yidabu.nospam gmail.com> Oct 13 2007
- BCS <ao pathlink.com> Oct 13 2007
- yidabu <yidabu.nospam gmail.com> Oct 13 2007
- BCS <ao pathlink.com> Oct 14 2007
- Regan Heath <regan netmail.co.nz> Oct 14 2007
- yidabu <yidabu.nospam gmail.com> Oct 24 2007
- bearophile <bearophileHUGS lycos.com> Nov 04 2007
- yidabu <yidabu.nospam gmail.com> Nov 04 2007
- Bill Baxter <dnewsgroup billbaxter.com> Nov 04 2007
- yidabu <yidabu.nospam gmail.com> Nov 04 2007
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
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
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
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,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 {
-- 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?
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 DMDWould you like to put this in scrapple on DSource?
have the right.
send me your dsource username and I'll add 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.
DMD 1.012, and many articles about D in Chinese.
<coff> <coff> Walter? some links for you
Oct 13 2007
Content-Type: text/plain 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");send me your dsource username and I'll add you
my 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: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
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 ];my dsource username is yidabu
you are in
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. Regan
Thanks. 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: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 dead end. --bb
Nov 04 2007
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 dead end. --bb
I hope Phobos 2.X open the door to Tango team, if it is not a dead end.
Nov 04 2007