JavaScript中的极大数

Question

我正在解决欧拉计划问题（目前在第13题）。

对于这个问题，我需要找出100个数字的总和的前10位数，这些数字的大小都类似于此:

91,942,213,363,574,161,572,522,430,563,301,811,072,406,154,908,250

我认为我可以使用类似Java的BigInteger，但我开始用JavaScript解决问题（我试图提高我的工作中js能力），我想继续使用它，甚至是解决这个问题。

如果可能的话，我想坚持纯JS。

- JEJoll

---

也许只是我个人而已，但我会用 Python 来解决这个问题。因为 Python 内置大数运算，比 Java 更容易使用。然后，我会选择一个更“JavaScripty”的挑战，比如使用 HTML5 画布元素进行绘图之类的事情。 - Jason S

你可以将数字保存为数字数组，然后编写函数以这种方式执行数学运算（就像你在小学时学习的老式数学方法一样）。 - jfriend00

Answer 1

最近Javascript新增了一种原始数据类型BigInt (截至2020年1月，已成为stage 4提案)。 https://github.com/tc39/proposal-bigint Chrome、Firefox等浏览器已经在新版本中开始支持它(在这里检查兼容性)，而其他浏览器仍在实现中。

https://developers.google.com/web/updates/2018/05/bigint

基本上，它可以使用字面量声明，例如： var a = 1n; 或者 var b = BigInt('22222222222222222222222222222222'); 数学运算符不会自动转换BigInt和Number之间的类型，因此：

1 + 1n

将会抛出一个错误。

- Qi Fan

Answer 2

你需要一个基于javascript的BigInteger库，有很多可以选择。这是其中之一：https://github.com/peterolson/BigInteger.js 你可以像这样使用它：

var n = bigInt("91942213363574161572522430563301811072406154908250")
    .plus("91942213363574161572522430563301811072406154908250");

- bhspencer

---

我实际上能够通过直接将所有值相加来得出正确的答案。我之前的代码可能有错别字。但是我接受了这个答案，因为它似乎是最可靠的，而且我怀疑我的简单解决方案在所有情况下都有效--可能只是偶然。 - JEJoll

Answer 3

我使用数组并通过函数更新所有条目来完成此操作。

function f(a) {
  for (let i = 0; i < a.length - 1; i++) {
      a[i + 1] = a[i + 1] + parseInt(a[i] / 10);
      a[i] = a[i] % 10;
  }
  return a;
}
// remember to init the array with enough elements for all digits
var a = Array(200);
a.fill(0);
a[0] = 1;

这里是一个包含问题20代码的JSFiddle。

- cheesehead

---

Project Euler明确指出（每次解决问题时）您不应该公开发布您的解决方案。 - Jessica B

Answer 4

令人惊讶的是，将所有值放入数组中并将它们全部相加，然后只取前10位数字就可以了。之前当它不起作用时，我一定在代码中打错了某个字。

我确信这样做并不适用于所有情况（就像@AlexMcmillan和@zerkms一直在辩论的那些情况）。我认为最安全的方法是使用@bhspencer提到的BigInteger库，但在某些情况下，似乎也值得尝试将前x个有效数字与y个数字作为缓冲区相加。

- JEJoll

---

这几乎总是有效的。所有常见的JS实现都使用64位浮点数来表示数字，这给你大约15个有效数字。因此，当精确求和的前10个数字后面没有足够连续的“9”数字时，您的前10个数字将是正确的，以便计算结果四舍五入到最后一位数字，使您的结果在第十位数字上偏差1。 - Mike Housky

Answer 5

你可以将你的总数转换为一个字符串，去掉其中的“.”并获取结果 - 就像这样：

var sum = 2384762348723648237462348;
sum = sum.toString(); // "2.3847623487236483e+24"

// Rip out the "."
sum = sum.substr(0, 1) + sum.substr(2);

// Grab the first 10 characters
var firstTen = sum.substr(0, 10);

- Alex McMillan

---

这样做你不会得到准确的答案。 - bhspencer

@bhspencer，实际上，如果您取前15个有效数字（IEEE754双精度数保证准确）并总结其中的100个，则额外的5个数字间隔将使您免于不准确。至少我想不到错误可能会进一步传播的情况。 - zerkms

@bhspencer 根据问题，您需要获取结果的前10位数字。因此，初始数字有多长并不重要。 - zerkms

@AlexMcMillan var firstTen = sum.substr(0, 10); - 你正在取出确切的10个数字。要精确地添加100个数字，你需要至少有3个以上的安全“缓冲区”。 - zerkms

@zerkms 这里我们不进行任何数学计算 - 假设已经通过产生 sum 变量完成了计算（因此命名为“sum”）。而且，OP只想要总和的前10个数字，因此返回13或15个数字是错误的。 :) - Alex McMillan