Javascript - adding Integers using arrays

Question

I am using an array in order to calculate large powers of 2. The arrays add to each other and afterwords they calculate the carries and loop n-1 amount of times until i end up with the number as an array. I do this in order to avoid the 15 digit limit that JavaScript has.

Everything works fine once i reach n = 42, where the carries start to be overlooked and numbers aren't reduced, producing wrong answers.

I tried changing the method of which the carry is processed inside the while loop from basic addition to integer division and modulus Sounds stupid but i added an extra loop to check if any elements are greater than 10 but it didn't find them.

  for (var n = 1; n <= 100; n++) {
    for (var i = 0, x = [2]; i < n - 1; i++) { // Loop for amount of times to multiply
      x.unshift(0)
      for (var j = x.length - 1; j > 0; j--) { // Double each element of the array
        x[j] += x[j]
      }
      for (j = x.length - 1; x[j] > 0; j--) { // Check if element >= 10 and carry
        while (x[j] >= 10) {
          x[j - 1] += Math.floor(x[j] / 10)
          x[j] = x[j] % 10
        }
      }
      if (x[0] === 0) {
        x.shift()
      }
    }
    console.log('N: ' + n + ' Array: ' + x)
  }

The expected results are that each element in the array will be reduced into a single number and will "carry" onto the element to its left like :

N: 1 Array: 2
N: 2 Array: 4
N: 3 Array: 8
N: 4 Array: 1,6
N: 5 Array: 3,2
N: 6 Array: 6,4

but starting at n=42 carries get bugged looking like this:

N: 42 Array: 4,2,18,18,0,4,6,5,1,1,1,0,4
N: 43 Array: 8,4,36,36,0,8,12,10,2,2,2,0,8
N: 44 Array: 1,7,5,9,2,1,8,6,0,4,4,4,1,6
N: 45 Array: 2,14,10,18,4,2,16,12,0,8,8,8,3,2
N: 46 Array: 7,0,3,6,8,7,4,4,1,7,7,6,6,4
N: 47 Array: 14,0,7,3,7,4,8,8,3,5,5,3,2,8

What's the error that could be throwing it off like this?

You should really consider using BigInt. It has native support now by using a postfix n on number literals. — Patrick Roberts
– Patrick Roberts, Commented Mar 22, 2019 at 19:42
although you should use BigInt, as of your algorithm, should't you check in the inner for loop for j > 0 rather than x[j] > 0 ? (line 8) — Gonzalo.-
– Gonzalo.-, Commented Mar 22, 2019 at 19:49
You could always attempt to debug, too. The code is way too (over-)complicated to just understand and step through in my head for larger numbers. Debugging it you should find the issue in a second, but in any case there has to be a better way to calculate this without using lists. — mhpcc
– mhpcc, Commented Mar 22, 2019 at 19:50

Georgy · Accepted Answer · 2019-03-22 20:06:05Z

I think the reason your code doesn't work is this line for (j = x.length - 1; x[j] > 0; j--) { // Check if element >= 10 and carry you don't want to check for x[j] > 0 but j > 0.

Also your second loop: for (var i = 0, x = [2]; i < n - 1; i++) { - you don't need it, there is no reason to recalculate everything on every iteration, you can use previous result.

You can also double values this way : x = x.map(n => n * 2) (seems a bit more coventional to me).

And there is no need to x[j - 1] += Math.floor(x[j] / 10) it could be just x[j - 1] += 1 as previous numbers are up to 9, doubled they are no more than 18 so 1 is the only case if x[j] >= 10.

Could be the code:

let x = [2] // starting point
for (var n = 1; n <= 100; n++) {
  x = [0, ...x].map(n => n * 2)
  for (j = x.length - 1; j > 0; j--) {
    if (x[j] >= 10) {
      x[j - 1] += 1
      x[j] %= 10
    }
  }
  if (x[0] === 0) {
    x = x.slice(1)
  }
  console.log('N: ' + n + ' Array: ' + x)
}

mhpcc · Accepted Answer · 2019-03-22 20:33:25Z

0

If all you want are large powers of 2, why are you going through the insane hassle of using lists to calculate that? Isn't this the exact same:

function BigPow2(x, acc=2.0) {
    //document.writeln(acc);
    acc = acc >= 5 ? acc / 5 : acc * 2;
    return x <= 1 ? acc : BigPow2(x-1, acc);
}

Or alternatively, use BigInt?

edited Mar 22, 2019 at 20:33

answered Mar 22, 2019 at 20:08

mhpcc

1451 silver badge13 bronze badges

Collectives™ on Stack Overflow

Javascript - adding Integers using arrays

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related