Monday, September 08, 2008

Large Integer division remainder

Recently, I had to obtain the remainder of a (seriously) large integer division (32 digits long divided by another shorter integer; base 10) and found that JavaScript reliably supports operations only on 15-digit long integers. Thus, this what I came up with:

// Gets the remainder from the division operation for LARGE numbers
// Support: positive integers; first parameter must not be 0
function GetRemainder(x, y) {
if ((y != 0) && (x.slice(0, 1) != "-") && (y.slice(0, 1) != "-"))
{
var nr = x;

// Removing the potential first '+' character
if (nr.slice(0, 1) == "+") {nr = nr.slice(1);}
if (y.slice(0, 1) == "+") {y = y.slice(1);}

// Removing leading blank and tab characters on both numbers
while ( (nr.charCodeAt(0) == 32) || (nr.charCodeAt(0) == 9) ){
nr = nr.slice(1);
}
while ( (y.charCodeAt(0) == 32) || (y.charCodeAt(0) == 9) ){
y = y.slice(1);
}

var len = nr.length;

// Checking if any non-digit characters are embedded into the input string
var i = 0;
for (i = 0; i < len; i++)
if (!((nr.charCodeAt(i) >= 48) && (nr.charCodeAt(i) <= 57)) ) {
return -1;
}

var number = parseInt(y,10);
var remainder = 0;
var ignore = 0;
var k = '';

while (ignore < len) {
if (remainder == 0) {
var w1 = y+' ';
var w2 = w1.length-1;
k = nr.slice(ignore, ignore+w2);

ignore += w2;
remainder = parseInt(remainder+k, 10) % number;
} else {
k = nr.slice(ignore, ignore+1);
ignore += 1;
remainder = parseInt(remainder+k, 10) % number;
}
}

return remainder;
}

return -1;
}


Usage:

document.write(GetRemainder("12345678901234567890123456789012", "123"))

will output 27.

2 comentarii:

Anonymous said...

Nice Post. Thanks for sharing this information with us.

BlackDoom said...

Hope it was suitable for your context.

I've tried to have it be both effective yet safe - see all those checks and invalid characters removal sections.

Nice to see I haven't post it for nothing :-)!

Cheers!