Correct limb length and assertion for gcdExtInteger

Authored by DavidEichmann on Aug 3 2018, 9:51 AM.
DavidEichmann created this revision.Aug 3 2018, 9:51 AM
DavidEichmann added inline comments.Aug 6 2018, 3:29 AM

I notice here and in other functions in this file, we take the limbs and corresponding sizes instead of simply passing a mpz_t. This seems like unnecessary deconstructing and reconstructing of mpz_t. It also forces the Haskell code to decide on a limb size even though that is already handled by the gmp library. Is there a reason for this or can we refactor (accept/return mpz_t instead of mp_limb_t[] and mp_size_t)?

bgamari added inline comments.Aug 6 2018, 8:41 AM

Pinging @hvr who is the original author of this code.

bgamari updated the Trac tickets for this revision.Aug 6 2018, 1:58 PM
bgamari retitled this revision from Correct limb length and assertion for gcdExtInteger (fixes #15350) to Correct limb length and assertion for gcdExtInteger.
hvr added inline comments.Aug 6 2018, 2:21 PM

Well, this was an intentional design choice driven by the representation chosen for data Integer and to avoid constructing any C structs in Haskell-land and instead have the C FFI act as a facade which provides us a uniform FFI api (we actually want a mpn_*-style API; that's what we facade for here for a couple of high-level GMP operations which are currently only available w/ the less convenient mpz_t API) based on passing around limbs as Haskell-owned ByteArray#s w/ an Int# count separately (which was lateron intended to be pluggable w/ backends other than GMP but using the same common denominator FFI ABI). And if given the choice to do this kind of construction/deconstructing in Haskell or in C, I'd almost always pick the C side as it's more idiomatic to do so there. I really don't see any benefit in doing the co/denstruction in Haskell-land.

bgamari added inline comments.Aug 7 2018, 1:19 PM

@hvr, do you think you could plop this into a Note? It's quite helpful to have design decisions like this documented in the source.

Could you also add a test for gcdExtInteger (2^65 + 1) 2, and maybe one with negative operands?

Correct limb length assertion for gcdExtInteger (fixes Trac #15350)

Reviewers: hvr, bgamari

Subscribers: rwbarton, thomie, carter

Differential Revision:


  • Added more test cases.
monoidal accepted this revision.Aug 17 2018, 4:59 PM

I've checked this and it makes sense.

While we are at it, the description of integer_gmp_gcdext states that this function "set s and t to coefficients satisfying x*s + y*t = g", but it only sets s (t is not returned in any way). This shouldn't block merging though.

This revision is now accepted and ready to land.Aug 17 2018, 4:59 PM
Closed by commit rGHCc331592130ef: Correct limb length and assertion for gcdExtInteger (authored by DavidEichamnn <>, committed by bgamari). · Explain WhyAug 21 2018, 6:02 PM
This revision was automatically updated to reflect the committed changes.