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('');};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.
Long arithmetic addition in JS
javascript;algorithm;integer;complexity
Performance improvements related to approachInterger baseFor 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)) - 1BIG_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 > 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) {  lnum = readBigInteger(a, DIGITS)  rnum = readBigInteger(b, DIGITS)  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;        curr = add(prev, curr);        prev = temp;    }    return curr;};SIZE = 10000console.time(plainWithDifferentBase);fib(SIZE, plainWithDifferentBase);console.timeEnd(plainWithDifferentBase);console.time(plain);fib(SIZE, plain);console.timeEnd(plain);ResultsUsing \$ base = 10^{15} \$ is 90 times efficiently.plainWithDifferentBase: 23848msplain: 182856msPerformance improvements related to interpreterLook at this:formatting list of variablesconverting character to integer using charCodeAtpreallocating array of required sizeusing 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 < 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) // 1var a = []; a.length = size // 2Note: 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 browserJust open console in your browser and paste following codevar 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;  }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 < 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.80preallocated: 1620.238msplain: 4311.755msMozilla Firefox 41.0.2preallocated: 849.72msplain: 3747.05msNodejs and preallocationLets 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;        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: 1278msplain: 4249ms$ node --versionv0.12.7Warning: didn't run benchmark for node in you browser.Google Chrome 46.0.2490.80 gives timepreallocated: 61737.298msplain: 16982.603msMozilla Firefox 41.0.2preallocated: 12759.65msplain: 14391.38msSummaryWe have different results depending on platform. People love js because of 2 things:event loopsame codebase for backend and frontendBut, as you saw before, you have to optimize frontend and backend in different way. How to solve it is up to you.