我需要把很多分数相加。 我不使用 float，因为IEEE-754双精度浮点数只有53位尾数，因此53 × log10(2) ≈ 15.954589770191003位有效十进制数字。

那为什么我要这么多位数？ 我想把超越性数学常数计算到任意高的精度，这就是原因。 我先用Python实现我的算法以便原型开发，因为我在做原型，最终我会用C++实现该算法，使用我已经在C++20中实现的任意精度整数。

不管怎么说，我发现要把一堆分数相加，使用 fractions.Fraction 会因为Python对象开销和分数简化而变慢，使用 math.gcd 会变慢，因为每次约简都要再多做一次GCD和两次额外的整除，这很慢，使用 math.lcm 也会变慢，因为它在底层调用GCD，使用Python函数会变慢，因为调用函数的开销，使用条件语句会变慢，因为分支预测失误，使用multiprocessing也会变慢，因为所有的开销。

把分数相加最快的方法是使用a/b + c/d = (ad + bc)/(b*d)，只需要分离分子和分母，永远不要进行除法。

要把一堆分数加在一起，我们可以逐个线性相加。或者我们可以更聪明一些：如果有n 个分数，我们有n//2对分数，每对可以独立相加；如果n 为奇数，会有一个未配对的分数。这样处理后我们得到n//2个分数和n//4对，可能还会有一个剩余分数。我们可以把剩下的重新加入到列表中，并把第一轮的输出作为第二轮的输入，第二轮的输出作为第三轮的输入，依此类推。每轮迭代将分数数量减半，直到最终只剩下一个分数，即为列表中所有分数的和。

而且我发现了一件我无法解释的事：

from itertools import batched
from math import gcd


def arctan_derivative(x: int, y: int) -> tuple[int, int]:
    return y * y, x * x + y * y


def primitive_rationals_simple(denominator: int) -> list[tuple[int, int]]:
    assert isinstance(denominator, int) and denominator > 0
    result = []
    for numerator in range(denominator + 1):
        common = gcd(numerator, denominator)
        result.append((numerator // common, denominator // common))

    return result


def make_test_case(n: int) -> list[tuple[int, int]]:
    return [arctan_derivative(*frac) for frac in primitive_rationals_simple(n)]


def test1(fracs: list[tuple[int, int]]) -> tuple[int, int]:
    num, den = 0, 1
    for tnum, tden in fracs:
        num, den = num * tden + tnum * den, den * tden

    return num, den


def test2(fracs: list[tuple[int, int]]) -> tuple[int, int]:
    while (length := len(fracs)) > 1:
        carry = fracs.pop(-1) if length & 1 else None
        fracs = [(a * d + b * c, b * d) for (a, b), (c, d) in batched(fracs, 2)]
        if carry:
            fracs.append(carry)

    return fracs[0]

In [83]: data = make_test_case(360)

In [84]: test1(data) == test2(data)
Out[84]: True

In [85]: %timeit test1(data)
271 μs ± 9.95 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [86]: %timeit test2(data)
166 μs ± 948 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [87]: (271 - 166)/271
Out[87]: 0.3874538745387454

第二种方法大约比朴素的线性方法快40%。但这怎么可能呢？它们在同一台计算机硬件、同一操作系统、同一编程语言、同一个Python解释器、同一组同时运行的程序上执行……它们接收相同的输入，进行相同的计算，总迭代次数也应该相同。

但一个明显比另一个快。

我只是想理解为什么这里第二种方法更快。上面的描述只是一种背景，他们解释了我为什么要用分数以及为什么要用交叉相乘。我也不清楚我自己设计的方法为什么会比蛮力更快。

解决方案

将所有两个整数的乘法替换为对这个函数的调用，这个函数不仅执行乘法，还会分析操作数的大小：

def mul(a, b):
    a_digits = -(-a.bit_length() // sys.int_info.bits_per_digit)
    b_digits = -(-b.bit_length() // sys.int_info.bits_per_digit)
    if a_digits > 40 and b_digits > 40:
        print(a_digits, b_digits)
    return a * b

输出随之显示，只有当两个操作数都超过40位时才需要相乘：

• 56位乘以57位
• 112位乘以48位

Python只有在两者都超过70位时才会使用Karatsuba，因此这并没有发生，也不是原因。

因此所有乘法都使用普通竖式算法。我们可以统计进行了多少次位乘法：

def mul(a, b):
    a_digits = -(-a.bit_length() // sys.int_info.bits_per_digit)
    b_digits = -(-b.bit_length() // sys.int_info.bits_per_digit)
    global count
    count += a_digits * b_digits
    return a * b

将全局 count 设置为 0，然后运行你的一次测试，再打印 count。在 test1 时得到85041，在 test2 时只有40197。因此 test2 的工作量要少得多。

但 为什么 test2 的工作量会少这么多呢？请注意，这里的“digit”是指base 2sys.int_info.bits_per_digit的位宽，如今对几乎所有实现来说都是2^30。也就是说一个“digit”就是一段30位的数字。像360这样的数只是一个digit。甚至1073741823（那是2^30-1）也仍然只是一个digit。你的分数的分子和分母最大只有258481（就是3592+3602）。而 test1 的乘法总是包含其中一个这样的digit，这样做是浪费的，因为位段其实可以大得多。相比之下 test2 只是在开始时就使用如此小的位段，但随后会快速处理能充分利用大多数位段潜力的数字。

让我们也统计“按位逐位”乘法的次数，好像Python并不是对整个digit进行乘法：

def mul(a, b):
    global count
    count += a.bit_length() * b.bit_length()
    return a * b

现在的计数为34,716,165（test1）和34,358,880（test2）。几乎相同，正如预期，因为不存在像考虑整个位时那样的浪费潜力。因此如果Python真的是逐位乘法而不是逐位对digit相乘，我预计两个测试大致耗时相同。

带有我的 mulfunction的脚本