Opened 8 years ago

Closed 5 years ago

#3489 closed feature request (fixed)

Adding some gmp bindings to integer-gmp (copied from the cvs-ghc list)

Reported by: pumpkin Owned by: igloo
Priority: normal Milestone: 7.6.1
Component: Compiler Version: 6.11
Keywords: Cc: leather@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Attachments (3)

integer-gmp.patch (10.0 KB) - added by pumpkin 8 years ago.
integer-simple.patch (1.9 KB) - added by pumpkin 8 years ago.
base.patch (8.8 KB) - added by pumpkin 8 years ago.

Download all attachments as: .zip

Change History (13)

Changed 8 years ago by pumpkin

Attachment: integer-gmp.patch added

Changed 8 years ago by pumpkin

Attachment: integer-simple.patch added

Changed 8 years ago by pumpkin

Attachment: base.patch added

comment:1 Changed 8 years ago by igloo

difficulty: Unknown
Milestone: 6.14.1

Thanks for the patch. We'll take a look in the 6.14 branch.

comment:2 Changed 8 years ago by spl

Cc: leather@… added

comment:3 Changed 7 years ago by ross

Type: proposalfeature request
Type of failure: None/Unknown

comment:4 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:5 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:6 Changed 6 years ago by igloo

Status: newpatch

comment:7 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:8 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1

comment:9 Changed 6 years ago by igloo

Owner: set to igloo

comment:10 Changed 5 years ago by igloo

Resolution: fixed
Status: patchclosed

Thanks, I've applied the testBit parts of the patches.

It looks like the other parts aren't used by Integer, and I don't think we want to make bindings for the whole GMP API. The internals are exposed, though, so a separate package could do so.

Note: See TracTickets for help on using tickets.