math.gcd 背后的算法是什么？为什么它是更快的欧几里得算法？

Question

测试表明 Python 的

math.gcd

比朴素的欧几里得算法实现快一个数量级：

import math
from timeit import default_timer as timer

def gcd(a,b):
        while b != 0:
                a, b = b, a % b
        return a

def main():
        a = 28871271685163
        b = 17461204521323
        start = timer()
        print(gcd(a, b))
        end = timer()
        print(end - start)

        start = timer()
        print(math.gcd(a, b))
        end = timer()
        print(end - start)

给予

$ python3 test.py
1
4.816000000573695e-05
1
8.346003596670926e-06

e-05

vs

e-06

。

我猜有一些优化或其他算法？

Answer 1

math.gcd()

当然是作为机器代码（即从“C”代码编译）运行的库函数上的Python shim，而不是由Python解释器运行的函数。另请参阅：math.py 和 sys.py 在哪里？