search

wrengr / exact-combinatorics

Efficient exact computation of combinatoric functions.
BSD 3-Clause "New" or "Revised" License
9 stars 2 forks source link

Borwein vs Goetgheluck #1

Open chadbrewbaker opened 8 years ago

chadbrewbaker commented 8 years ago

More of an question than an issue. I would be happy to assist in benchmarking/implementation. I would also like to add in a faster prime sieve.

Borwein came up with an ingenious fast factorial algorithm that computes the exponent of each prime factor of $n!$ then multiplies them all together in one go.

Is Goetgheluck's algorithm which you use for the binomial calculation any faster than three Borwein table calculations? Ruby implementation of Borwein's fast factorial, https://gist.github.com/chadbrewbaker/8445183

wrengr commented 8 years ago

Not sure about the performance difference. When I get a chance I'll translate the Ruby gist and do some benchmarking. Thanks for the heads up

chadbrewbaker commented 8 years ago

The Goetgheluck algorithm wasn't something I was aware of. I think I can translate the Ruby gist of Borwein's fast factorial this week and do a pull request. Haskell uses GMP under the hood for Integer so I am assuming it beats the socks off of the Ruby implementation.