Amongst the many ways of implementing the factorial function in Haskell (Evolution of a Haskell programmer), I have yet to see one that calls the GNU MP function mpz_fac_ui on the internal implementation of Integer. (Of course, such an implementation would not be portable.) That implementation is quite heavily algorithmically optimized, most notably by organizing the computation (binary splitting) to take advantage of subquadratic multiplication of two large multiplicands, which the tenured professor's method product [1..n] does not do.
Previously, benchmarking mpz_fac_ui on very large inputs from C++.
In the vein of wanting bindings to GMP, we would also like access to mpz_export and mpz_import for fast conversion to ByteStrings.
Someday, I may write these.
2 comments :
I'm curious to see how the GMP version compares to the version in exact-combinatorics. Presumably it's still faster, though it'd be nice to see the benchmarks.
GHC 7.8 will provide integer-gmp 0.5.1 that export the mpz_import & mpz_export api for fast conversion between integer and bytestring.
There's an example on how to use it there:
crypto-number Serialize.hs L49
Post a Comment