python - 如何更快地乘以大数？

Question

我正在尝试用 python 乘以大数。为了我的目的，我试图评估。

2*odd*(4*odd^2 + 7)/3 - 6*odd^2 - 3

现在我的问题归结为如何在 python 中更快地乘以数字。用 float 做它更快吗？答案似乎不是。以

为例

n*(n+1)/2

我的想法是下面的代码更快

product = 1
if n % 2 == 0:
    product *= n/2
    product *= n
else:
    product *= (n+1)/2
    product *= n
return product

为什么这样会更快？好吧，您不必将巨大的数字 n*(n+1) 除以二。然而，确实浪费了一次检查数字模 2 的计算。也许 try exception 更快？

所以我的问题归结为。如何计算 python 中非常大的数的乘积和除法？这是我的工作代码。不要求对此代码进行特别的速度改进。但更广泛的问题是如何处理大数的除法和乘法。我的数字范围在 10^(10^6) atm 左右。

def spiral_sum_fast(num):
    rem = num % 6
    if rem % 2 == 0:
        raise Exception("The sidelength must be a odd number")
    odd = 1 + num / 2
    odd_squared = 2 * odd**2

    if rem % 3 == 0:
        temp = odd / 3
        temp *= 8 * odd_squared + 14
    else:
        temp = (4 * odd_squared + 7) / 3
        temp *= 2 * odd
    return temp - 3 * odd_squared - 3


if __name__ == '__main__':

    k = 10**(10**6) + 1
    spiral_sum_fast(k)

Answer 1

首先，4*odd^2 + 7 总是 2 mod 3。所以你不需要检查。

但是无论如何您都不想重新排序这些操作。考虑一下 4*5/3 与 4/3*5 的整数算术会发生什么。第一个结果是 6。而第二个结果是 5。对于更大的数字，如果将除法移到操作顺序中更早的位置，您会丢失更多信息。

还有一点:你永远不想做x**2。 ** 使用 C 的 pow() 所以它会有一个浮点结果。只需使用 x*x 即可。它会更快、更准确。

至于n*(n+1)/2的例子，n*(n+1)总是能被2整除。而你所做的一切将一个大数向右移动 1 位并且您知道您丢失的位是 0。

您似乎通常担心将大数除以小数。但是(如我给出的第一个示例)，如果过早进行除法，您将丢失信息并得到不太准确的答案。计算也不会更快。如果您将大数除以大数，您可能需要像这样的技巧，但如果您将大数除以小数(并且您正在使用整数运算)，结果将只比您开始的大数短几位. “早除”或使用浮点运算既不会更快，也不会更准确。