生成2的平方根数字

Question

我想生成两到三百万个数字的平方根数字.

我知道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等迭代的那样.

Answer 2

编辑:我比以前更喜欢这个版本.这是一个接受整数和小数分数的通用解决方案; 当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