Changes between Initial Version and Version 1 of Ticket #5663
 Timestamp:
 Dec 25, 2011 1:11:40 PM (2 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #5663
 Property Status changed from new to closed
 Property Difficulty changed from to Unknown
 Property Resolution changed from to worksforme

Ticket #5663 – Description
initial v1 1 I have encountered this issue on GHC HEAD, but it looks like it's been the case for a long time: The implementation of gcdInt#, which is used by gcd for Int#, some other integer types, and Integer when both parameters use the S# "small" constructor, is a wrapper around __gmpn_gcd_1(). The GMP documentation for mpn_gcd() states some input preconditions for its inputs, and the documentation for mpn_gcd_1()comes right after it and is very terse, implying that the same preconditions are assumed. We do in fact guarantee most of those preconditions, in particular that the first input is the larger one, but it specifies that the second input must be odd, and we don't check that. (I'm not quite clear on what we're supposed to do if it isn't, but presumably there's some simple algorithm ...)1 I have encountered this issue on GHC HEAD, but it looks like it's been the case for a long time: The implementation of gcdInt#, which is used by gcd for Int#, some other integer types, and Integer when both parameters use the S# "small" constructor, is a wrapper around `__gmpn_gcd_1()`. The GMP documentation for `mpn_gcd()` states some input preconditions for its inputs, and the documentation for `mpn_gcd_1()` comes right after it and is very terse, implying that the same preconditions are assumed. We do in fact guarantee most of those preconditions, in particular that the first input is the larger one, but it specifies that the second input must be odd, and we don't check that. (I'm not quite clear on what we're supposed to do if it isn't, but presumably there's some simple algorithm ...) 2 2 3 3 This is not just a theoretical problem. GMP has multiple implementations of its algorithms, for multiple architectures, and no doubt each one has slightly different characteristics; I have tested on an x8664 system, which uses the implementation of mpn_gcd_1() in the file libraries/integergmp/gmp/gmpbuild/mpn/x86_64/gcd_1.asm. I don't really want to make sense of the assembly language and figure out why it misbehaves, but we're violating the documentation and the entire mpn_* suite of functions is considered "internal and difficult to use correctly", so we are the ones who need to change, not them. 4 4 5 5 The problem can be seen as follows: 6 6 {{{ 7 7 GHCi, version 7.3.20111124: http://www.haskell.org/ghc/ :? for help 8 8 Loading package ghcprim ... linking ... done. … … 14 14 Prelude GHC.Integer.GMP.Internals GHC.Types GHC.Int GHC.Integer.GMP.Prim> I# (gcdInt# 0x2B992DDFA23249D6# 0xDE0B6B3A7640000#) 15 15 0 16 16 }}} 17 17 This should reproduce on any x8664 system, although I don't have access to another one to test that. In my setup, I'm using the intree GMP, which is GMP 5.0.2 as of this writing. 18 18