Serhiy Storchaka <storchaka+cpyt...@gmail.com> added the comment:
Divide-and-conquer approach works pretty well for larger n. For results slightly out of the 64-bit range: $ ./python -m pyperf timeit -s 'from math import comb' 'comb(63, 31)' Mean +- std dev: 2.80 us +- 0.14 us -> 388 ns +- 19 ns: 7.22x faster $ ./python -m pyperf timeit -s 'from math import comb' 'comb(111, 15)' Mean +- std dev: 1.24 us +- 0.06 us -> 215 ns +- 18 ns: 5.76x faster $ ./python -m pyperf timeit -s 'from math import comb' 'comb(1450, 7)' Mean +- std dev: 654 ns +- 45 ns -> 178 ns +- 13 ns: 3.67x faster $ ./python -m pyperf timeit -s 'from math import comb' 'comb(3329023, 3)' Mean +- std dev: 276 ns +- 15 ns -> 175 ns +- 11 ns: 1.58x faster For very large n: $ ./python -m pyperf timeit 'from math import comb' 'comb(2**100, 2**10)' Mean +- std dev: 26.2 ms +- 1.7 ms -> 3.21 ms +- 0.20 ms: 8.16x faster $ ./python -m pyperf timeit 'from math import comb' 'comb(2**1000, 2**10)' Mean +- std dev: 704 ms +- 15 ms -> 103 ms +- 5 ms: 6.85x faster And it is faster than using factorial: $ ./python -m pyperf timeit -s 'from math import comb' 'comb(100_000, 50_000)' Mean +- std dev: 1.61 sec +- 0.02 sec -> 177 ms +- 9 ms: 9.12x faster $ ./python -m pyperf timeit -s 'from math import factorial as fact' 'fact(100_000) // (fact(50_000)*fact(50_000))' Mean +- std dev: 507 ms +- 20 ms math.perm() can benefit from reusing the same code: $ ./python -m pyperf timeit -s 'from math import perm' 'perm(63, 31)' Mean +- std dev: 1.35 us +- 0.07 us -> 1.18 us +- 0.06 us: 1.15x faster $ ./python -m pyperf timeit -s 'from math import perm' 'perm(111, 15)' Mean +- std dev: 601 ns +- 35 ns -> 563 ns +- 28 ns: 1.07x faster $ ./python -m pyperf timeit -s 'from math import perm' 'perm(2**100, 2**10)' Mean +- std dev: 5.96 ms +- 0.29 ms -> 2.32 ms +- 0.12 ms: 2.57x faster $ ./python -m pyperf timeit -s 'from math import perm' 'perm(2**1000, 2**10)' Mean +- std dev: 486 ms +- 14 ms -> 95.7 ms +- 4.2 ms: 5.08x faster $ ./python -m pyperf timeit -s 'from math import perm' 'perm(100_000, 50_000)' Mean +- std dev: 639 ms +- 23 ms -> 66.6 ms +- 3.2 ms: 9.60x faster Even in worst cases it is almost as fast as factorial: $ ./python -m pyperf timeit -s 'from math import perm' 'perm(100_000, 100_000)' Mean +- std dev: 2.55 sec +- 0.02 sec -> 187 ms +- 8 ms: 13.66x faster $ ./python -m pyperf timeit -s 'from math import factorial' 'factorial(100_000)' Mean +- std dev: 142 ms +- 7 ms ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue37295> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
