计算康威常数

html5 • • 问答 • 179 阅读

我发现了一个代码高尔夫挑战，要求您将康威常数计算为前 1000 位数字。问题是我找不到任何告诉如何计算这个的地方，只有网站显示多项式的变量 x 我不知道是什么。我使用以下代码计算了 Look-and-say 序列中的前 30 个数字：

const nums = ["1"],

  trailingSequences = seq => {
    const num = seq[0];
    let counter = 1;
    let idx = 0;
    for (let i = 1; i < seq; i++) {
      if (num == seq[i]) {
        counter++
        idx = i;
      } else {
        break
      };
    }
    return [`${counter}${num}`, idx + 1];
  },

  getNext = previous => {
    let next = "";
    while (true) {
      if (previous == "") {
        break
      };
      const part = trailingSequences(previous);
      next += part[0];
      previous = previous.slice(part[1]);
    }
    return next;
  }


for (let i = 0; i < 30; i++)
  nums.push(getNext(nums[nums.length - 1]))
  
console.log(nums.join("nnn"));

回答

康威常数是 71 阶多项式的唯一实数正根。正如您所料，它是无理数1，并且不能表示为有限连分数。

计算多项式根的最简单且一般来说最有效的方法之一是使用牛顿法：

其中x n是当前的猜测值，f(x n )是一个函数，用于计算x n处的目标多项式。

在任意精度实数/有理数不可用的情况下，结果可以按 10 的大幂进行缩放以计算所需的精度。下面的实现使用 V8 的BigInts 将康威常数计算到 1000 个位置。

/**
 * Evaluates a polynomial given by coeffs at x,
 * or the derivative thereof, scaled by a factor.
 */
function evalpoly(x, coeffs, scale, deriv) {
  let ret = 0n;
  const d = deriv ? 1 : 0;
  for(let i = coeffs.length - 1; i >= d; i--) {
    ret = x*ret / scale + BigInt(coeffs[i] * [1, i][d]) * scale;
  }
  return ret;
}


const poly = [
  -6, 3, -6, 12, -4, 7, -7, 1, 0, 5, -2, -4, -12, 2, 7, 12, -7, -10,
  -4, 3, 9, -7, 0, -8, 14, -3, 9, 2, -3, -10, -2, -6, 1, 10, -3, 1,
  7, -7, 7, -12, -5, 8, 6, 10, -8, -8, -7, -3, 9, 1, 6, 6, -2, -3,
  -10, -2, 3, 5, 2, -1, -1, -1, -1, -1, 1, 2, 2, -1, -2, -1, 0, 1]

const scale = 10n**1000n

// initial guess 1.333333...
let x = scale * 4n / 3n

for(let i = 0; i < 14; i++) {
  x -= evalpoly(x, poly, scale, 0) * scale / evalpoly(x, poly, scale, 1)
}

x

1 Finch, Steven R.，《数学常数》，第 642 页，剑桥大学出版社，2003 年。

以上是计算康威常数的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>
相关内容