Author serhiy.storchaka
Recipients PedanticHacker, mark.dickinson, mcognetta, pablogsal, rhettinger, serhiy.storchaka, tim.peters
Date 2021-10-18.18:49:25
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1634582966.04.0.182201022595.issue37295@roundup.psfhosted.org>
In-reply-to
Content
Microbenchmarks:

$ ./python -m pyperf timeit -s 'from math import comb' '[comb(n, k) for n in range(63) for k in range(n+1)]'
Mean +- std dev: 1.57 ms +- 0.07 ms -> 209 us +- 11 us: 7.53x faster

$ ./python -m pyperf timeit -s 'from math import comb' 'comb(62, 31)'
Mean +- std dev: 2.95 us +- 0.14 us -> 296 ns +- 11 ns: 9.99x faster

$ ./python -m pyperf timeit -s 'from math import comb' 'comb(110, 15)'
Mean +- std dev: 1.33 us +- 0.06 us -> 95.8 ns +- 3.1 ns: 13.86x faster

$ ./python -m pyperf timeit -s 'from math import comb' 'comb(1449, 7)'
Mean +- std dev: 689 ns +- 33 ns -> 59.0 ns +- 3.2 ns: 11.69x faster

$ ./python -m pyperf timeit -s 'from math import comb' 'comb(3329022, 3)'
Mean +- std dev: 308 ns +- 19 ns -> 57.2 ns +- 4.2 ns: 5.39x faster

Now I want to try to optimize for larger arguments. Perhaps using recursive formula C(n, k) = C(n, j)*C(n-j, k-j)//C(k, j) where j=k//2 could help.
History
Date User Action Args
2021-10-18 18:49:26serhiy.storchakasetrecipients: + serhiy.storchaka, tim.peters, rhettinger, mark.dickinson, PedanticHacker, mcognetta, pablogsal
2021-10-18 18:49:26serhiy.storchakasetmessageid: <1634582966.04.0.182201022595.issue37295@roundup.psfhosted.org>
2021-10-18 18:49:26serhiy.storchakalinkissue37295 messages
2021-10-18 18:49:25serhiy.storchakacreate