# 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][1] 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][2] 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} \$

<!-- begin snippet: js hide: true -->

<!-- language: lang-js -->

 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)

 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 = 10000

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

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

<!-- end snippet -->

**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)

<!-- begin snippet: js hide: true -->

<!-- language: lang-js -->

 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('');
 }

<!-- end snippet -->

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

<!-- begin snippet: js hide: true -->

<!-- language: lang-js -->

 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; 
 }

 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");

<!-- end snippet -->

My results are:

* Google Chrome 46.0.2490.80

<!-- code --> 

 preallocated: 1620.238ms
 plain: 4311.755ms

* Mozilla Firefox 41.0.2

<!-- code --> 

 preallocated: 849.72ms
 plain: 3747.05ms

## Nodejs and preallocation

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

<!-- begin snippet: js hide: true -->

<!-- language: lang-js -->

 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");

<!-- end snippet -->

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

<!-- code -->

 preallocated: 61737.298ms
 plain: 16982.603ms

* Mozilla Firefox 41.0.2

<!-- code --> 

 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.

 [1]: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER
 [2]: http://e-maxx.ru/algo/big_integer