Adding some gmp bindings to integer-gmp (copied from the cvs-ghc list)
This is my first patch for GHC, so I apologize in advance if I do something wrong! I've actually attached three patches for libraries/base, libraries/integer-gmp, and libraries/integer-simple, but because there is no change to any exposed API and only a couple of extra functions added to GHC.Integer, I'm sending it here instead of to libraries at haskell.org.
Basically, I added cmm bindings to mpz_powm(_ui), mpz_tstbit, and mpz_sizeinbase. The modular exponentiation function is significantly faster than anything I could find in pure haskell, and the bit testing is way more efficient than the default Data.Bits implementation involving a potentially massive left shift (in fact, might that be better phrased as a right shift of the tested value?). The sizeinbase function (essentially an integer logarithm, unfortunately with the base restricted to a maximum of 62) also looked handy so I added it while I was there (at Bertram Felgenhauer's suggestion).
So these patches amount to:
- A one-line change to Data.Bits in base, adding our specialized testBit function.
- Some cmm code additions in integer-gmp, plus the Haskell glue to make them usable from outside.
- A very simplistic implementation of testBitInteger for integer-simple, so that the one-line change to Data.Bits doesn't fail
when building with integer-simple.
I've tested the code and it appears to be correct, and have validated it with both integer-simple and -gmp, in both cases encountering two unexpected ghci test failures (in OS X): ghci028 and 2816. Manuel Chakravarty said these were normal and that he'd experienced the build failures under OS X too, so I didn't look into them any more deeply.