2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)

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

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

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.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 < 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: 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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – kharandziuk Nov 3 '15 at 11:47
  • 2
    \$\begingroup\$ @kharandziuk, Sorry, I have omitted word "not" in sentence. \$\endgroup\$ – outoftime Nov 3 '15 at 11:53
  • \$\begingroup\$ please look at my answer it looks like your implementation actually slower then initial. Please check the measurement proccess \$\endgroup\$ – kharandziuk Nov 3 '15 at 12:27
  • \$\begingroup\$ 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 \$\endgroup\$ – kharandziuk Nov 3 '15 at 13:10
  • \$\begingroup\$ @kharandziuk check updates \$\endgroup\$ – outoftime Nov 3 '15 at 14:29
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I have updated my answer with different base is it \$ 10^{15} \$ for most 64 bit interpreters. \$\endgroup\$ – outoftime Nov 3 '15 at 15:56
  • \$\begingroup\$ @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. \$\endgroup\$ – sqykly Nov 3 '15 at 17:26
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – sqykly Nov 3 '15 at 17:28
  • \$\begingroup\$ @outoftime didn't realize you were not OP! Oops. In any case, the complexity is not improved by this idea, just the running time. \$\endgroup\$ – sqykly Nov 3 '15 at 17:45
  • \$\begingroup\$ 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. \$\endgroup\$ – outoftime Nov 3 '15 at 18:27
0
\$\begingroup\$

The code which benchmarks initial solution vs @outoftime`s 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;  
}

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

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

assert(longAdd('1', '9') === '10');
assert(longAdd('1', '0') === '1');
assert(longAdd('5', '5') == '10');
assert(longAdd('2', '2') === '4');
assert(longAdd('20', '202') === '222');

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");
console.log(fib(1000, longAdd));
console.timeEnd("preallocated");

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

The result on my macbook is:

preallocated: 398ms plain: 197ms

node -v v0.12.2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.