我要生成2到3百万位数的平方根的位数。
我知道Newton-Raphson，但由于缺少大整数支持，在C或C++中如何实现它，我没有太多的线索。有人能给我指个方向吗？
另外，如果有人知道如何使用Python（我是一个初学者），我也会很感激。
最佳答案
您可以尝试使用映射：a/b -> (a+2b)/(a+b)从a= 1, b= 1开始。这收敛到sqrt（2）（实际上给出了它的连续分数表示）。
现在关键点：这可以表示为矩阵乘法（类似于斐波那契）。
如果a和b是步骤中的第n个数字，那么
[1 2][a_n b_n]t=[a_（n+1）b_（n+1）]t
〔1 1〕
它现在给了我们
[1 2]n[a_1 b_1]t=[a_（n+1）b_（n+1）]t
〔1 1〕
因此，如果2x2矩阵是A，我们需要计算一个可以通过重复的平方来完成的，并且只使用整数算法（所以您不必担心精度问题）。
还请注意，您得到的A/B将始终是简化形式（如gcd（a，b）=gcd（a+2b，a+b）），因此如果您打算使用分数类来表示中间结果，请不要！
由于第n个分母类似于（1+sqrt（2））^n，要得到300万位数，您可能需要计算到3671656项。
注意，即使您正在寻找约360万个项，重复的平方运算将允许您计算o（log n）乘法和加法中的第n个项。
而且，这很容易被平行化，不像牛顿·拉斐逊等迭代法。