生成2的平方根位数

Question

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

<>我知道Newton-Raphson，但是我没有太多线索，如何在C或C++中实现它，因为缺少大整数支持。有人能告诉我正确的方向吗？

另外，如果有人知道如何使用python（我是一个初学者），我也会很感激。

Answer 1

编辑：我比以前更喜欢这个版本。这是一个同时接受整数和小数的一般解；n=2，精度=100000，大约需要两分钟。感谢Paul McGuire的建议和其他建议欢迎！

def sqrt_list(n, precision):
    ndigits = []        # break n into list of digits
    n_int = int(n)
    n_fraction = n - n_int

    while n_int:                            # generate list of digits of integral part
        ndigits.append(n_int % 10)
        n_int /= 10
    if len(ndigits) % 2: ndigits.append(0)  # ndigits will be processed in groups of 2

    decimal_point_index = len(ndigits) / 2  # remember decimal point position
    while n_fraction:                       # insert digits from fractional part
        n_fraction *= 10
        ndigits.insert(0, int(n_fraction))
        n_fraction -= int(n_fraction)
    if len(ndigits) % 2: ndigits.insert(0, 0)  # ndigits will be processed in groups of 2

    rootlist = []
    root = carry = 0                        # the algorithm
    while root == 0 or (len(rootlist) < precision and (ndigits or carry != 0)):
        carry = carry * 100
        if ndigits: carry += ndigits.pop() * 10 + ndigits.pop()
        x = 9
        while (20 * root + x) * x > carry:
                x -= 1
        carry -= (20 * root + x) * x
        root = root * 10 + x
        rootlist.append(x)
    return rootlist, decimal_point_index

Answer 2

对于任意大数，你可以查看The GNU Multiple Precision Arithmetic Library（对于C/C++）。

Answer 3

您可以尝试使用映射：

从a= 1, b= 1开始。这收敛到sqrt（2）（实际上给出了它的连分式表示）。

关键是：这可以表示为矩阵乘法（类似于斐波那契）

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

[12][a_n b_n]^T=[a_（n+1）b_（n+1）]^T
[11]

现在给了我们

[1 2]ⁿ[a_1 b_1]^T=[a_（n+1）b_（n+1）]^T
[11]

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

还要注意的是，你得到的a/b总是以简化形式（因为gcd（a，b）=gcd（a+2b，a+b）），所以如果你想用分数类来表示中间结果，不要！

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

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

而且，这很容易被平行化，不像牛顿-拉斐逊等迭代法