Search code examples
javascriptnode.jsalgorithmieee-754

Is it possible to handle integer overflow without an external library in JavaScript?

In Javascript (in Chrome devtools console panel and Node.js v0.12.5), I'm getting an incorrect answer for the product of these two large numbers:

input: 41962049 * 1827116622

output: 76669557221078480

In C++ and C#, I get the correct answer of 76669557221078478 when casting the expression to a 64-bit int.

I'm assuming this is an integer overflow issue, but I certainly could be wrong.

Is there a way to get accurate arithmetic products for large numbers in Javascript without using an external library like BigInteger? This is for an online class that doesn't allow additional libraries.

Thanks for your help.

EDIT: Thanks for the explanation explaining how this isn't actually integer overflow, Patrick Roberts! Very useful.

EDIT 2: jfriend00, I think this question is different than the one you linked to because I am trying to figure out if there is a way to work around JS's limitations without relying on an external library. The answer you provided in the comments helped answer my question, so thank you!

Solution

  • This is not integer overflow, this is due to the limitations of double precision floating point. The highest accurately representable integer in JavaScript is 2^53 due to the epsilon in the range of 2^52 to 2^53 being exactly 1. Above that, integer precision breaks down, but the result of that multiplication is not due to an integer overflow.

    Below is the relevant quote from wikipedia on the IEEE 754 standard:

    Between 252=4,503,599,627,370,496 and 253=9,007,199,254,740,992 the representable numbers are exactly the integers. For the next range, from 253 to 254, everything is multiplied by 2, so the representable numbers are the even ones, etc. Conversely, for the previous range from 251 to 252, the spacing is 0.5, etc.

    The spacing as a fraction of the numbers in the range from 2n to 2n+1 is 2n−52. The maximum relative rounding error when rounding a number to the nearest representable one (the machine epsilon) is therefore 2−53.

    To answer your question though, it is very possible. Here is a small library I just wrote in the past couple hours for unsigned integer addition and multiplication that is able to display values in base 10:

    class BigUint {
  static get WORD() {
    return 100000000000000;
  }

  static get HALF() {
    return 10000000;
  }

  static map(word, index) {
    if (index === 0) {
      return word.toString();
    }

    return `000000${word}`.slice(-7);
  }

  static from(array) {
    return Object.create(BigUint.prototype, {
      words: {
        configurable: true,
        enumerable: true,
        value: new Uint32Array(array),
        writable: true
      }
    });
  }

  constructor(number) {
    if (/\D/.test(`${number}`)) {
    	throw new TypeError('seed must be non-negative integer as number or string');
    }
    
    this.words = new Uint32Array(`${number}`.split(/(?=(?:.{7})+$)/).map(s => +s));
  }

  [Symbol.toPrimitive](hint) {
    let string = this.toString();

    switch (hint) {
    case 'number':
      return +string;
    default:
      return string;
    }
  }

  get length() {
    return this.words.length;
  }

  toString() {
    return Array.from(this.words).map(BigUint.map).join('');
  }

  add(that) {
    const thisLength = this.length;
    const thatLength = that.length;
    const maxLength = Math.max(thisLength, thatLength);
    const minLength = Math.min(thisLength, thatLength);
    const max = maxLength === thisLength ? this : that;

    const words = [];

    let augend, addend, sum, keep, carry = 0, index;

    for (index = 1; index <= minLength; index++) {
      augend = this.words[thisLength - index];
      addend = that.words[thatLength - index];

      sum = augend + addend + carry;

      keep = sum % BigUint.HALF;
      carry = (sum - keep) / BigUint.HALF;

      words.unshift(keep);
    }

    for (; index <= maxLength; index++) {
      sum = max.words[maxLength - index] + carry;

      keep = sum % BigUint.HALF;
      carry = (sum - keep) / BigUint.HALF;

      words.unshift(keep);
    }

    if (carry > 0) {
      words.unshift(carry);
    }

    return BigUint.from(words);
  }

  multiply(that) {
    const thisLength = this.length;
    const thatLength = that.length;
    const minLength = Math.min(thisLength, thatLength);
    const maxLength = Math.max(thisLength, thatLength);
    const min = minLength === thisLength ? this.words : that.words;
    const max = maxLength === thatLength ? that.words : this.words;

    const partials = [];

    let product, words, keep, carry = 0, sum, addend;

    for (let outerIndex = minLength - 1; outerIndex >= 0; outerIndex--) {
      words = [];

      partials.push(words);

      for (let j = minLength - 1; j > outerIndex; j--) {
        words.unshift(0);
      }

      for (let innerIndex = maxLength - 1; innerIndex >= 0; innerIndex--) {
        product = min[outerIndex] * max[innerIndex] + carry;

        keep = product % BigUint.HALF;
        carry = (product - keep) / BigUint.HALF;

        words.unshift(keep);
      }

      if (carry > 0) {
        words.unshift(carry);

        carry = 0;
      }
    }

    sum = BigUint.from(partials.pop());

    while (partials.length > 0) {
      sum = sum.add(BigUint.from(partials.pop()));
    }

    return sum;
  }
}

const a = document.getElementById('a');
const b = document.getElementById('b');
const c = document.getElementById('c');
const op = document.querySelector('select');

function calculate() {
	c.textContent = new BigUint(a.value)[op.value](new BigUint(b.value));
}

document.addEventListener('input', calculate);

calculate();
    <input id="a" type="number" min="0" step="1" value="41962049">
<select>
  <option value="add">+</option>
  <option value="multiply" selected>&times;</option>
</select>
<input id="b" type="number" min="0" step="1" value="1827116622">
=
<span id="c"></span>