Author serhiy.storchaka
Recipients PedanticHacker, mark.dickinson, mcognetta, pablogsal, rhettinger, serhiy.storchaka, tim.peters
Date 2021-10-20.11:47:48
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1634730468.86.0.407730927351.issue37295@roundup.psfhosted.org>
In-reply-to
Content
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
History
Date User Action Args
2021-10-20 11:47:48serhiy.storchakasetrecipients: + serhiy.storchaka, tim.peters, rhettinger, mark.dickinson, PedanticHacker, mcognetta, pablogsal
2021-10-20 11:47:48serhiy.storchakasetmessageid: <1634730468.86.0.407730927351.issue37295@roundup.psfhosted.org>
2021-10-20 11:47:48serhiy.storchakalinkissue37295 messages
2021-10-20 11:47:48serhiy.storchakacreate