GeezerVison

Description

Fixes #1254

math.perm(n, k) multiplied the running product by one factor at a time, so its cost grew with the square of the result size and BigInteger.multiply never got two large operands. CPython splits the product as P(n, k) = P(n, j) * P(n - j, k - j) with j = k / 2 (mathmodule.c#L3634-L3649), so the large multiplications are between operands of similar size.

AS-IS

>>> t = time.time(); n = math.perm(615913, 286885); print(n.bit_length(), round(time.time() - t, 1))
5401202 27.6

TO-BE

5401202 0.3

Timings for math.perm(615913, 286885) on macOS arm64:

Changes

• Compute P(n, k) in PermNode by recursive halving instead of the sequential loop.
• Add test_perm_matches_product in a new tests/test_math_perm.py.

Testing

mx python-jvm on darwin-aarch64, then --tagged test_math (79 passed, same as master). The new test passes before and after the change; it checks values, not time. math.perm(n, k) equals factorial(n) // factorial(n - k) for every n < 60 and every k.