python - 生成 2 的平方根的数字

Question

我想生成二到 300 万位的平方根的数字。

我知道 Newton-Raphson但由于缺乏双整数支持，我不知道如何在 C 或 C++ 中实现它。有人能指出我正确的方向吗？

此外，如果有人知道如何在 python 中执行此操作(我是初学者)，我也将不胜感激。

Answer 1

您可以尝试使用映射:

a/b -> (a+2b)/(a+b) 从 a= 1, b= 1 开始。这收敛于 sqrt(2)(实际上给出了它的连分数表示)。

现在是关键点:这可以表示为矩阵乘法(类似于斐波那契)

如果 a_n 和 b_n 是步骤中的第 n 个数字，则

[1 2] [a_n b_n]^T = [a_(n+1) b_(n+1)]^T
[1 1]

现在给我们

[1 2]ⁿ [a_1 b_1]^T = [a_(n+1) b_(n+1)]^T
[1 1]

因此，如果 2x2 矩阵是 A，我们需要计算 Aⁿ，这可以通过重复平方来完成并且仅使用整数运算(因此您不必担心精度问题)。

另请注意，您获得的 a/b 将始终采用简化形式(如 gcd(a,b) = gcd(a+2b, a+b))，因此如果您考虑使用分数类来代表中间结果，不要!

由于第 n 个分母类似于 (1+sqrt(2))^n，要获得 300 万个数字，您可能需要计算到第 3671656 个 项。

请注意，即使您正在寻找约第 360 万项，重复平方将允许您计算 O(Log n) 乘法和加法中的第 n 项。

此外，这可以很容易地并行化，不像 Newton-Raphson 等迭代方法。