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 &lt; 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('');
};
assert(strAdd('1', '9') === '10');
assert(strAdd('1', '0') === '1');
assert(strAdd('5', '5') == '10');
assert(strAdd('2', '2') === '4');
assert(strAdd('20', '202') === '222');


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 &lt; 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)

function readBigInteger(str, base) {
  var res = [];
  for (var i = str.length; i &gt; 0; i -= base)
    if (i &lt; 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 &lt; integer.length; ++i) {
      var s = FILL_STRING + integer[i]
      integer[i] = s.substr(s.length - base)
  }
  return integer.reverse().join('');
}

function plainWithDifferentBase (a, b) {
  lnum = readBigInteger(a, DIGITS)
  rnum = readBigInteger(b, DIGITS)

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

  for (var i = 0; i &lt; 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 &lt; num) {
        temp = curr;
        curr = add(prev, 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;  
}
 
function longAdd(lnum, rnum) {
  // 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 &lt; 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 &lt; 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;  
}

function longAdd(lnum, rnum) {
  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 &lt; 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;
        curr = add(prev, curr);
        prev = temp;
    }
    return curr;
};

console.time("preallocated");
fib(1000, longAdd);
console.timeEnd("preallocated");

console.time("plain");
fib(1000, strAdd);
console.timeEnd("plain");




My results are:


Google Chrome 46.0.2490.80


 

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 &lt; 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 &gt; 1000)
      res.length = len;
  for(var i = 0; i &lt; len; i++) {
    var subres = Number(lnum[i] || 0) + Number(rnum[i] || 0) + acc;
    acc = ~~(subres / 10); // integer division
    if (len &gt; 1000)
      res[i] = subres % 10
    else
      res.push(subres % 10);
  }
  if (acc !== 0) {
    if (len &gt; 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;
        curr = add(prev, 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.