为什么python的内置乘法如此之快

Question

所以前几天我在python中尝试了一些东西,我试图在python中编写一个自定义乘法函数

def multi(x, y):
    z = 0
    while y > 0:
        z = z + x
        y = y - 1
    return z

然而,当我用非常大的数字运行时,如(1 << 90)和(1 << 45),即(2 ^ 90)*(2 ^ 45).计算花了很长时间.所以我试着研究不同类型的乘法,比如在那里实现的俄罗斯农民乘法技术,它非常快但不像多(x,y)那么可读

def russian_peasant(x, y):
    z = 0
    while y > 0:
        if y % 2 == 1: z = z + x
        x = x << 1
        y = y >> 1
    return z 

我想要你回答的是如何编程语言如python乘以数字？

Answer 1

您的multi版本以O(N)russian_peasant运行,而版本以O(logN)运行,这比O(N)好得多.

要了解您的russian_peasant版本有多快,请查看此信息

from math import log
print round(log(100000000, 2))   # 27.0

因此,循环必须只执行27次,但是你的multi版本的while循环必须执行100000000次,当时y为100000000.

要回答你的其他问题,

我想要你回答的是如何编程语言如python乘以数字？

Python 对小数字使用O(N ^ 2)级学校乘法算法,但对于大数字,它使用Karatsuba算法.

基本上乘法在C代码中处理,可以编译为机器代码并执行得更快.

Answer 2

Python 等编程语言使用计算机 CPU 提供的乘法指令。

此外，您必须记住，Python 是一种非常高级的编程语言，它运行在虚拟机上，而虚拟机本身运行在您的计算机上。因此，它本质上比本机代码慢几个数量级。将您的算法转换为汇编（或什至转换为 C）将导致巨大的加速——尽管它仍然比 CPU 的乘法运算慢。

从好的方面来说，与简单的汇编/C 不同，当您的数字大于 2**32 时，Python 会自动将整数提升为 bignum，而不是溢出。

Answer 3

你的问题的基本答案是这样的，乘法使用 *是通过 C 代码处理的。本质上，如果你用纯 python 写东西，它会比 C 实现慢，让我举个例子。

该operator.mul函数是用 C 实现的，但 alambda是用 Python 实现的，我们将尝试使用 using 找到数组中所有数字的乘积，functools.reduce我们将使用两种情况，一种使用operator.mul，另一种使用 a lambda，两者都可以同样的事情（表面上）：

from timeit import timeit
setup = """
from functools import reduce
from operator import mul
"""

print(timeit('reduce(mul, range(1, 10))', setup=setup))
print(timeit('reduce(lambda x, y: x * y, range(1, 10))', setup=setup))

输出：

1.48362842561
2.67425475375

operator.mul 如您所见，花费的时间更少。