Last active
August 29, 2015 14:24
-
-
Save afonsomatos/62d84c87f6fbd8dfff64 to your computer and use it in GitHub Desktop.
Sum of big integer strings
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*! | |
* 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!"); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*! | |
* 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)); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*! | |
* 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