Skip to content

Instantly share code, notes, and snippets.

@afonsomatos
Last active August 29, 2015 14:24
Show Gist options
  • Save afonsomatos/62d84c87f6fbd8dfff64 to your computer and use it in GitHub Desktop.
Save afonsomatos/62d84c87f6fbd8dfff64 to your computer and use it in GitHub Desktop.
Sum of big integer strings
/*!
* Big Integer Sum Algorithm
*
*
* Result sum( '5' * 10^7, '8' * 10^7)
* real 0m2.995s
* user 0m2.928s
* sys 0m0.060s
*/
function sum(n1, n2) {
// Create new result array
var re = [];
// Point to the last index
var ix = n1.length - 1;
// Carry number along calculation
var ca = 0;
// Start adding
for (var su; ~ix; --ix) {
// Calculate sum between the two right most numbers and carry
sum = n1[ix] || 0 + n2[ix] || 0 + ca;
// Shit right most number
re[ix] = sum % 10;
// Add carry if needed
ca = +(sum > 9);
}
// Check if there is any carry remaining
// if (ca) return [ca].concat(re);
return re;
}
// Create array numbers
var n1 = "5".repeat(10000000).split('').map(Number, Number.call);
var n2 = "8".repeat(10000000).split('').map(Number, Number.call);
// Start the operation
var n = Date.now();
var re = sum(n1, n2);
console.log(Date.now() - n);
// Print result
console.log("Done!");
/*!
* Big Integer Sum Algorithm
*
* Kind of slow algorithm, sums each digit of a string number using
* carry operations
*
* Result sum( '5' * 10^7, '8' * 10^7)
* real 0m1.274s
* user 0m1.208s
* sys 0m0.092s
*/
function sum(left, right) {
// Add leading zeros to make them the same length
if (left.length > right.length) {
right = '0'.repeat(left.length - right.length) + right;
} else {
left = '0'.repeat(right.length - left.length) + left;
}
// var result
var result = "";
// Point to the last index
var ptr = right.length - 1;
// Carry number along calculation
var carry = 0;
// Start calculation
for (var sum ; ptr >= 0 ; ptr--) {
// Calculate the sum between the two right most numbers
sum = +left[ptr] + +right[ptr];
// Add the carry
sum = sum + carry;
// Check if number is result needs more carry
if (sum > 9) {
// Shift the right most digit
result = sum % 10 + result;
// Add other digits to carry
carry = 1;
} else {
// If it doesn't shift the result
result = sum + result;
// Set carry to 0
carry = 0;
}
}
// Check if there is any carry remaining
if (carry) {
result = carry + result;
}
// Return resulting number as string
return result;
}
// Start the operation
var s1 = "5".repeat(10000000);
var s2 = "8".repeat(10000000);
var n = Date.now();
var re = sum(s1,s2);
console.log(Date.now() - n);
// Print result
console.log("Starts in " + re.slice(0, 4) + " and ends in " + re.slice(-4));
/*!
* Big Integer Sum Algorithm
*
* Result sum( '5' * 10^7, '8' * 10^7)
* real 0m0.756s
* user 0m0.724s
* sys 0m0.028s
*/
function sum(left, right) {
// Creates the resulting buffer
var bres = Buffer(left.length);
// Point to the last element
var ptr = bres.length - 1;
// Carry number along calculation
var car = 0;
// Start calculation
for (var sum; ptr >= 0; --ptr) {
// Sum of two right most digits
sum = left[ptr] + right[ptr] + car;
// If result needs more carry
if (sum > 9) {
// Shift the right most digit
bres[ptr] = sum % 10;
// Add other digits to carry
car = 1;
} else {
// Shift all
bres[ptr] = sum;
// Has nothign else to carry
car = 0;
}
}
return car ? Buffer.concat([Buffer([car]), bres]) : bres;
}
var bleft = Buffer("5".repeat(10000000).split('')),
bright = Buffer("8".repeat(10000000).split(''));
var n = Date.now();
var re = sum(bleft, bright);
console.log(Date.now() - n);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment