25 August 2009

Big Integer Arithmetics Library in JavaScript

Few days ago, I needed arithmetic functionalities of big integers (alternatively strings) in JavaScript. I was confident that it would get plenty of such libraries by googling, I might be in sweet trouble of choosing one. But unfortunately I did not find satisfactory library with at least 4 functionalities - add, subtract, multiply & divide. I was very surprised. May be my searching keywords were poor. Whatever, I have developed a small library with 6 basic functions (add, subtract, multiply, divide, remainder, isALessThanB) of non-negative big integer.

Big Integer Arithmetic Functions
  1. BigInt.add(n1, n2) returns n1+n2
  2. BigInt.subtract(n1, n2) returns n1-n2 [n1 must be greater than n2]
  3. BigInt.multiply(n1, n2) returns n1xn2
  4. BigInt.dividefunction(n1, n2) returns n1/n2 (integer part only)
  5. BigInt.remainder(n1,n2) returns n1%n2
  6. BigInt.isALessThanB(a,b) returns a <>

Big Integer Arithmetic Library

var BigInt =

{

add : function(n1, n2)

{

if(!this.isValidBigInt(n1) || !this.isValidBigInt(n2))

throw "Not a big integer.";

// make all input to string

n1 = n1 + "";

n2 = n2 + "";

var i;

var sum = "";

// reverse them for comfortable indexing

n1 = this.reverse( this.removeLeading0s(n1));

n2 = this.reverse(this.removeLeading0s(n2));

// make both of same length

var large = n1;

var small = n2;

if(n1.length<>

{

large = n2;

small = n1;

}

// pad with 0's

for(i=small.length; i

small += "0";

// start adding

var carry = 0;

for(i=0; i

{

var subSum = this.digitAt(small, i) + this.digitAt(large, i) + carry;

if(subSum <>

{

sum += (subSum + "");

carry = 0;

}

else

{

sum += (subSum - 10) + "";

carry = 1;

}

}

if(carry == 1)

sum += "1";

return this.removeLeading0s(this.reverse(sum));

},

subtract : function (n1, n2)

{

// n1: larger number

// n2: smalelr number

// returns n1 - n2

if(!this.isValidBigInt(n1) || !this.isValidBigInt(n2))

throw "Not a big integer.";

// make all input to string

n1 = n1 + "";

n2 = n2 + "";

var i;

var large = n1;

var small = n2;

large = this.reverse(large);

small = this.reverse(small);

// pad with 0's

for(i=small.length; i

small += "0";

var carry = 0;

var result = "";

for(i=0; i

{

var upDigit = this.digitAt(large,i);

var downDigit = this.digitAt(small, i);

var diff = upDigit - downDigit - carry;

if(diff >= 0)

{

result += (diff + "");

carry = 0;

}

else

{

result += (diff + 10 + "");

carry = 1;

}

}

return this.removeLeading0s( this.reverse(result) );

},

multiply : function(n1, n2)

{

// returns n1 * n2

// make all input to string

n1 = n1 + "";

n2 = n2 + "";

if(!this.isValidBigInt(n1) || !this.isValidBigInt(n2))

throw "Not a big integer.";

var mul = "";

var extra0s = "";

for(var i=n2.length-1; i>=0; i--)

{

var d = this.digitAt(n2,i);

var subMul = this.multiplyByOneDigit(n1, d);

if(i==n2.length-1)

{

mul = subMul;

}

else

{

extra0s += "0";

subMul += extra0s;

mul = this.add(mul, subMul);

}

}

return this.removeLeading0s(mul);

},

divide : function(n1, n2)

{

// returns Math.floor(n1/n2)

// make all input to string

n1 = n1 + "";

n2 = n2 + "";

if(!this.isValidBigInt(n1) || !this.isValidBigInt(n2))

throw "Not a big integer.";

n1 = this.removeLeading0s(n1);

n2 = this.removeLeading0s(n2);

var i;

var divisor = n2;

var result = "";

var rem = "";

for(i=0; i

{

rem += (n1[i]+"");

var iRem = rem;

if(this.isALessThanB(iRem, divisor))

{

result += "0";

}

else

{

var subDiv = this.shortDivide(iRem, divisor) + "";

result += (subDiv + "");

rem = this.subtract(iRem, this.multiply(subDiv, divisor));

}

}

return this.removeLeading0s(result);

},

isALessThanB : function (a,b)

{

if(!this.isValidBigInt(a) || !this.isValidBigInt(b))

throw "Not a big integer.";

// make all input to string

a = a + "";

b = b + "";

a = this.removeLeading0s(a);

b = this.removeLeading0s(b);

if(a.length != b.length)

return a.length <>

for(var i=0; i

{

var dA = this.digitAt(a,i);

var dB = this.digitAt(b,i);

if(dA != dB)

return dA <>

}

return false;

},

remainder : function(n1,n2)

{

// returns n1 % n2

// make all input to string

n1 = n1 + "";

n2 = n2 + "";

var d = this.divide(n1,n2);

return this.subtract(n1, this.multiply(d,n2));

},

shortDivide : function(a, b)

{

// a is less than 10b

var i=0;

while(!this.isALessThanB(a,b))

{

a = this.subtract(a,b);

i++;

}

return i;

},

multiplyByOneDigit : function (n, d)

{

// n: string

// d: number (0-9)

var n = this.reverse(n);

var carry = 0;

var result = "";

for(var i=0; i

{

var m = this.digitAt(n, i) * d + carry;

result += (m%10 + "");

carry = Math.floor(m/10);

}

if(carry > 0)

result += (carry + "");

return this.reverse(result);

},

reverse : function(s)

{

var iLen = s.length;

var strRev = "";

for(var i=iLen-1; i>=0; i--)

strRev += s.charAt(i);

return strRev;

},

digitAt : function(s, i)

{

var c = s[i];

return parseInt(c);

},

removeLeading0s : function(n)

{

n = n + "";

var result = "";

var i=0;

while(n[i] == '0')

i++;

if(i

{

result = n.substr(i);

}

if(result == "")

result = "0";

return result;

},

isValidBigInt : function(n)

{

if(typeof n != "string" && typeof n != "number")

return false;

// make it string (from both number & string)

n = n+"";

if(n.length == 0)

return false;

// check all digits

for(var i=0; i

if(n[i] < '0' || n[i] > '9')

return false;

return true;

}

};



Sample code of using this library

var num1 = "26093683160935360286936021";

var num2 = "4864306873315646901285";

var resAdd = BigInt.add(num1, num2);

var resSub = BigInt.subtract(num1, num2);

var resMul = BigInt.multiply(num1, num2);

var resDiv = BigInt.divide(num1, num2);

var resRem = BigInt.remainder(num1, num2);

var resLess = BigInt.isALessThanB(num1, num2);


0 Comments:

 

© 2007 t!ps n tr!cks: Big Integer Arithmetics Library in JavaScript



Template unik dari rohman


---[[ Skip to top ]]---