在 JavaScript 中是否可以在没有外部库的情况下处理整数溢出？

Question

在 Javascript 中（在 Chrome devtools 控制台面板和 Node.js v0.12.5 中），我得到了这两个大数的乘积的错误答案：

输入：41962049 * 1827116622

输出：76669557221078480

在 C++ 和 C# 中，当将表达式转换为 64 位整数时，我得到了 76669557221078478 的正确答案。

我假设这是一个整数溢出问题，但我肯定是错的。

有没有一种方法可以在不使用 BigInteger 等外部库的情况下为 Javascript 中的大数获得准确的算术积？这是针对不允许附加库的在线 class。

感谢您的帮助。

编辑：感谢您解释这实际上不是整数溢出，Patrick Roberts！很有用。

编辑 2：jfriend00，我认为这个问题与您链接到的问题不同，因为我想弄清楚是否有一种方法可以在不依赖外部库的情况下解决 JS 的限制。您在评论中提供的答案帮助回答了我的问题，非常感谢！

Answer 1

这不是整数溢出，这是由于double precision floating point的限制。 JavaScript 中可精确表示的最高整数是 2^53，因为 2^52 到 2^53 范围内的 epsilon 恰好为 1。在此之上，整数精度会下降，但该乘法的结果不会由于整数溢出。

以下是维基百科关于 IEEE 754 标准的相关引述：

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

The spacing as a fraction of the numbers in the range from 2ⁿ to 2ⁿ⁺¹ is 2ⁿ⁻⁵². The maximum relative rounding error when rounding a number to the nearest representable one (the machine epsilon) is therefore 2⁻⁵³.

不过要回答你的问题，很有可能。这是我在过去几个小时内刚刚编写的一个小型库，用于无符号整数加法和乘法，能够以 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>

在 JavaScript 中是否可以在没有外部库的情况下处理整数溢出？

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

javascript

node.js

algorithm

ieee-754