# 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 Nov 3 '15 at 11:47
• @kharandziuk, Sorry, I have omitted word "not" in sentence. Nov 3 '15 at 11:53
• please look at my answer it looks like your implementation actually slower then initial. Please check the measurement proccess Nov 3 '15 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 Nov 3 '15 at 13:10
• @kharandziuk check updates Nov 3 '15 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. Nov 3 '15 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. Nov 3 '15 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. Nov 3 '15 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. Nov 3 '15 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. Nov 3 '15 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. Nov 3 '15 at 12:33
• Actually, I just want to proof the statement that every code-specific optimization is just a concept without benchmark Nov 3 '15 at 12:47
• I'm running in Chome 46 my results: preallocated: 1620.238ms plain: 4311.755ms` Nov 3 '15 at 12:52
• I renewed my answer, can you share result on Safary? Nov 3 '15 at 13:02
• Interesting. I added node version(I test the application in console environment) Nov 3 '15 at 13:05