# Long arithmetic addition in JS

The implementation of the algorithm which adds two number in string form with arithmetic rules.

var assert = require('assert');

var strAdd = function(lnum, rnum) {
lnum = lnum.split('').reverse();
rnum = rnum.split('').reverse();
var len = Math.max(lnum.length, rnum.length),
acc = 0,
res = [];
for(var i = 0; i < len; i++) {
var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
acc = ~~(subres / 10); // integer division
res.push(subres % 10);
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
};


Is there a better way(in terms of complexity) to achieve the same result? Any style advice is appreciated.

# Performance improvements related to approach

## Interger base

For better performance we can split number not by every digit but by set of digits with given base. Look at Number.MAX_SAFE_INTEGER and some math

$max\_number = 2 ^ {53} - 1 = 9007199254740991$

$digits = \lfloor \log_{10} max\_number \rfloor$

$base = 10 ^ { digits }$

Note: base will be lower by one if logarithm gives interger.

What I want to say?

$max\_number$ can hold $digits$ digits to be able to handle overflowing during additions.

What meaning of $base$ ?

Currently you are using algo with $base = 10 ^ {digits} = 10$.

Here res.push(subres % 10); you are performing modulo operation with base equals 10. Which means you are storing array with numbers that consists of single digit.

But Number allows you to store up to 15 digits. Execute Math.log10(Number.MAX_SAFE_INTEGER) in you browser to find this value (do not forger to take floor of resulted decimal).

Look at c++ example at e-maxx.ru for idea how to implement this. I have not found good enough english article, but you can use google translate.

## Benchmark base $10^1$ vs base $10^{15}$

function plain(lnum, rnum) {
lnum = lnum.split('').reverse();
rnum = rnum.split('').reverse();

var len = Math.max(lnum.length, rnum.length)
, acc = 0
, res = [];

for (var i = 0; i < len; i++) {
var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
acc = ~~(subres / 10);
res.push(subres % 10);
}

if (acc !== 0) {
res.push(acc);
}

return res.reverse().join('');
}

DIGITS = Math.floor(Math.log10(Number.MAX_SAFE_INTEGER)) - 1
BIG_INTEGER_BASE = Math.pow(10, DIGITS);
FILL_STRING = (BIG_INTEGER_BASE + '').substr(1)

var res = [];
for (var i = str.length; i > 0; i -= base)
if (i < base)
res.push(Number(str.substr(0, i)));
else
res.push(Number(str.substr(i - base, base)));
return res;
}

function printBigInteger(integer, base) {
for (var i = 0; i + 1 < integer.length; ++i) {
var s = FILL_STRING + integer[i]
integer[i] = s.substr(s.length - base)
}
return integer.reverse().join('');
}

function plainWithDifferentBase (a, b) {

var len = Math.max(lnum.length, rnum.length)
, acc = 0
, res = [];

for (var i = 0; i < len; i++) {
var subres = (lnum[i] || 0) + (rnum[i] || 0) + acc;
acc = ~~(subres / BIG_INTEGER_BASE);
res.push(subres % BIG_INTEGER_BASE);
}

if (acc !== 0) {
res.push(acc);
}

return printBigInteger(res, DIGITS);
}

var fib = function(num, add) {
var prev = '1',
curr = '1',
temp;
while (curr.length < num) {
temp = curr;
prev = temp;
}
return curr;
};

SIZE = 10000

console.time("plainWithDifferentBase");
fib(SIZE, plainWithDifferentBase);
console.timeEnd("plainWithDifferentBase");

console.time("plain");
fib(SIZE, plain);
console.timeEnd("plain");

Results

Using $base = 10^{15}$ is 90 times efficiently.

plainWithDifferentBase: 23848ms
plain: 182856ms


# Performance improvements related to interpreter

Look at this:

• formatting list of variables
• converting character to integer using charCodeAt
• preallocating array of required size
• using standard language library API (builtins)

function characterToInt(char) {
// 48 is char code of zero.
return char.charCodeAt(0) - 48;
}

// Here we didn't use lambda function (anonimous) to prevent creating
// additaional objects and give less work to GC.
lnum = lnum.split('').reverse().map(characterToInt);
rnum = rnum.split('').reverse().map(characterToInt);
// With comma as third character you didn't broke approach of formating
// using 2 whitespaces.
var len = Math.max(lnum.length, rnum.length)
, acc = 0
// Allocate required space for an array to prevent reallocation overhead
, res = new Array(len);
for (var i = 0; i < len; ++i) {
var subres = (lnum[i] || 0) + (rnum[i] || 0) + acc;
// Use Math.floor instead of 2 additional operations, as it is library
// function which can be written with some optimizations.
acc = Math.floor(subres / 10);
res[i] = subres % 10;
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
}

Possible ways to allocate array of required size:

var a = new Array(size) // 1
var a = []; a.length = size // 2


Note: it is not final or most optimized version ever, I have tried to show you set of approached you might want to know to optimize your code even further.

## Benchmark using browser

Just open console in your browser and paste following code

var strAdd = function(lnum, rnum) {
lnum = lnum.split('').reverse();
rnum = rnum.split('').reverse();
var len = Math.max(lnum.length, rnum.length),
acc = 0;
res = [];
for(var i = 0; i < len; i++) {
var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
acc = ~~(subres / 10); // integer division
res.push(subres % 10);
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
};

function characterToInt(char) {
return char.charCodeAt(0) - 48;
}

lnum = lnum.split('').reverse().map(characterToInt);
rnum = rnum.split('').reverse().map(characterToInt);
var len = Math.max(lnum.length, rnum.length)
, acc = 0
, res = new Array(len);
for (var i = 0; i < len; ++i) {
var subres = (lnum[i] || 0) + (rnum[i] || 0) + acc;
acc = Math.floor(subres / 10);
res[i] = subres % 10;
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
}

var fib = function(num, add) {
var prev = '1',
curr = '1',
temp;
while (curr.toString().length !== num) {
temp = curr;
prev = temp;
}
return curr;
};

console.time("preallocated");
console.timeEnd("preallocated");

console.time("plain");
console.timeEnd("plain");

My results are:

preallocated: 1620.238ms
plain: 4311.755ms

• Mozilla Firefox 41.0.2
preallocated: 849.72ms
plain: 3747.05ms


## Nodejs and preallocation

Lets start with this test where we conditionally switches allocation from static to dynamic.

var plain = function(lnum, rnum) {
lnum = lnum.split('').reverse();
rnum = rnum.split('').reverse();
var len = Math.max(lnum.length, rnum.length),
acc = 0;
res = [];
for(var i = 0; i < len; i++) {
var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
acc = ~~(subres / 10); // integer division
res.push(subres % 10);
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
};

var preallocated = function(lnum, rnum) {
lnum = lnum.split('').reverse();
rnum = rnum.split('').reverse();
var len = Math.max(lnum.length, rnum.length),
acc = 0;
res = [];
if (len > 1000)
res.length = len;
for(var i = 0; i < len; i++) {
var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
acc = ~~(subres / 10); // integer division
if (len > 1000)
res[i] = subres % 10
else
res.push(subres % 10);
}
if (acc !== 0) {
if (len > 1000)
res = res.concat(acc)
else
res.push(acc);
}
return res.reverse().join('');
};

var fib = function(num, add) {
var prev = '1',
curr = '1',
temp;
while (curr.toString().length !== num) {
temp = curr;
prev = temp;
}
return curr;
};

console.time("preallocated");
fib(2000, preallocated);
console.timeEnd("preallocated");

console.time("plain");
fib(2000, plain);
console.timeEnd("plain");

I have results:

$node /tmp/help.js preallocated: 1278ms plain: 4249ms$ node --version
v0.12.7


Warning: didn't run benchmark for node in you browser.

• Google Chrome 46.0.2490.80 gives time
preallocated: 61737.298ms
plain: 16982.603ms

• Mozilla Firefox 41.0.2
preallocated: 12759.65ms
plain: 14391.38ms


## Summary

We have different results depending on platform. People love js because of 2 things:

• event loop
• same codebase for backend and frontend

But, as you saw before, you have to optimize frontend and backend in different way. How to solve it is up to you.

• Note: it is final or most optimized version ever, I have tried to show you set of approached you might want to know to optimize your code even further Thanks, for the answer but actually you can't provide such statement without any benchmark Commented Nov 3, 2015 at 11:47
• @kharandziuk, Sorry, I have omitted word "not" in sentence. Commented Nov 3, 2015 at 11:53
• please look at my answer it looks like your implementation actually slower then initial. Please check the measurement proccess Commented Nov 3, 2015 at 12:27
• I tried in my Chrome. The result is similar to yours: preallocated: 468.002ms plain: 1891.843ms Can you check with node? I guess it's really interesting Commented Nov 3, 2015 at 13:10
• @kharandziuk check updates Commented Nov 3, 2015 at 14:29

No, not in terms of complexity. Other reviewers have offered good, proven ways to optimize by reducing the constant term of the running time, but reducing the complexity is impossible given the nature of the problem.

By definition, a long-addition operates on some fixed size of data at a time - in your case, base 10 digits with values 0-9. You can pick the idea apart in a lot of ways; reduce the number of digits by expressing your number in hexadecimal or base 64, for instance. No matter what digit you choose, there is a number that will not fit in it, for which you will need multiple digits, so adding two numbers with N digits can always produce a number with N+1 digits. Even in the case of BigNums, which can be thought of as strings of digits in base 4 billion+, if you're adding one fixed quantity of data at a time, you must touch on each datum once, which makes your complexity O(N).

• I have updated my answer with different base is it $10^{15}$ for most 64 bit interpreters. Commented Nov 3, 2015 at 15:56
• @outoftime that isn't what I was getting at. What you were doing in the OP has exactly the same complexity as your new scheme, O(n). As long as you are breaking the number up into chunks, you can't have any less complexity. Looking at your implementation, this is due to the for loop, which will always run N times for an N-long string. Not sure if this has been covered, but the string methods split, reverse, and join also have O(n) complexity, so unless you get rid of all of those methods and the loop, your complexity does not change. Commented Nov 3, 2015 at 17:26
• @outoftime also, please do not modify code in the question to reflect the answers you get. It invalidates the answer because the code that was actually reviewed is gone. Commented Nov 3, 2015 at 17:28
• @outoftime didn't realize you were not OP! Oops. In any case, the complexity is not improved by this idea, just the running time. Commented Nov 3, 2015 at 17:45
• I agree about complexity in terms of pure math, but if you will test authors original code with different bases you will see that difference is more than number of digit in base, because of additional overhead related to number of elements in array. I agree about complexity in terms of pure math. Commented Nov 3, 2015 at 18:27

The code which benchmarks initial solution vs @outoftimes one

var assert = require('assert');

var strAdd = function(lnum, rnum) {
lnum = lnum.split('').reverse();
rnum = rnum.split('').reverse();
var len = Math.max(lnum.length, rnum.length),
acc = 0;
res = [];
for(var i = 0; i < len; i++) {
var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
acc = ~~(subres / 10); // integer division
res.push(subres % 10);
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
};

function characterToInt(char) {
// 48 is char code of zero.
return char.charCodeAt(0) - 48;
}

// Here we didn't use lambda function (anonimous) to prevent creating
// additaional objects and give less work to GC.
lnum = lnum.split('').reverse().map(characterToInt);
rnum = rnum.split('').reverse().map(characterToInt);
// With comma as third character you didn't broke approach of formating
// using 2 whitespaces.
var len = Math.max(lnum.length, rnum.length)
, acc = 0
// Allocate required space for an array to prevent reallocation overhead
, res = new Array(len);
for (var i = 0; i < len; ++i) {
var subres = (lnum[i] || 0) + (rnum[i] || 0) + acc;
// Use Math.floor instead of 2 additional operations, as it is library
// function which can be written with some optimizations.
acc = Math.floor(subres / 10);
res[i] = subres % 10;
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
}

var fib = function(num, add) {
var prev = '1',
curr = '1',
temp;
while (curr.toString().length !== num) {
temp = curr;
prev = temp;
}
return curr;
};

console.time("preallocated");
console.timeEnd("preallocated");

console.time("plain");
console.timeEnd("plain");


The result on my macbook is:

preallocated: 398ms plain: 197ms

node -v v0.12.2

• Try: 1. use numbers of random size, 2. use different way of array allocation, look at my update. Commented Nov 3, 2015 at 12:33
• Actually, I just want to proof the statement that every code-specific optimization is just a concept without benchmark Commented Nov 3, 2015 at 12:47
• I'm running in Chome 46 my results: preallocated: 1620.238ms plain: 4311.755ms Commented Nov 3, 2015 at 12:52
• I renewed my answer, can you share result on Safary? Commented Nov 3, 2015 at 13:02
• Interesting. I added node version(I test the application in console environment) Commented Nov 3, 2015 at 13:05

Review comments are inline in ///.

/// Use const for imported modules.
var assert = require('assert');

/// Use const for function variables.
/// Would addLongNumbers(left = "0", right = "0") be more appropriate?
/// Having default values for params makes it easier to handle
/// the undefined cases.
/// the usage of this API.
/// Would you wanna export this API?
var strAdd = function(lnum, rnum) {
/// Need to have null checks, prefer ?.
lnum = lnum.split('').reverse();
rnum = rnum.split('').reverse();
/// Prefer verbose names for better readability, e.g. length,
/// or more contextual, maxLength or effectiveLength.
/// Prefer one declaration per line to help prevent accidental
/// global variables.
/// As the context is addition here, carry would be closer than
/// acc to convey intention.
/// nit:result over res. It could be a const.
var len = Math.max(lnum.length, rnum.length),
acc = 0,
res = [];
for(var i = 0; i < len; i++) {
/// Would sum be a more appropriate name? Also it doesn't change
/// later so could be a const.
var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
/// Explain the faster floor trick in your comment.
/// Prefer leaving a MDN link on the topic if available.
acc = ~~(subres / 10); // integer division
res.push(subres % 10);
}
if (acc !== 0) {
res.push(acc);
}
return res.reverse().join('');
};
/// The tests should cover -
/// - Large numbers (> Math.MAX_SAFE_INTEGER, < Math.MIN_SAFE_INTEGER*).
///   *From the code and tests it's not clear if this function is supposed
///   to handle negative large numbers are well. If it is so, there
///   needs to be changes in the code to handle these cases.
/// - Nullability tests (one of the arguments is missing or null)
/// - Type coercion tests.

/// Overall assessment -
`