Changes between Initial Version and Version 1 of Ticket #5663


Ignore:
Timestamp:
Dec 25, 2011 1:11:40 PM (2 years ago)
Author:
igloo
Comment:

I can't reproduce this either on amd64/Linux using Debian's GMP 2:4.3.2+dfsg-1:

GHCi, version 7.5.20111219: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :m + GHC.Integer.GMP.Internals GHC.Types GHC.Int GHC.Integer.GMP.Prim
Prelude GHC.Integer.GMP.Internals GHC.Types GHC.Int GHC.Integer.GMP.Prim> :set -XMagicHash
Prelude GHC.Integer.GMP.Internals GHC.Types GHC.Int GHC.Integer.GMP.Prim> I# (gcdInt# 0x2B992DDFA23249D6# 0xDE0B6B3A7640000#)
2

nor using the in-tree GMP on amd64 OS X.

http://gmplib.org/manual/Low_002dlevel-Functions.html says

— Function: mp_size_t mpn_gcd (mp_limb_t *rp, mp_limb_t *xp, mp_size_t xn, mp_limb_t *yp, mp_size_t yn)

    Set {rp, retval} to the greatest common divisor of {xp, xn} and {yp, yn}. The result can be up to yn limbs, the return value is the actual number produced. Both source operands are destroyed.

    {xp, xn} must have at least as many bits as {yp, yn}. {yp, yn} must be odd. Both operands must have non-zero most significant limbs. No overlap is permitted between {xp, xn} and {yp, yn}.

— Function: mp_limb_t mpn_gcd_1 (const mp_limb_t *xp, mp_size_t xn, mp_limb_t ylimb)

    Return the greatest common divisor of {xp, xn} and ylimb. Both operands must be non-zero.

My reading of that is that the only pre-condition for mpn_gcd_1 is that both operands must be non-zero.

Like you say, as far as I know no-one else has run into this, so I think the problem lies elsewhere.

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 ...) 
     1I 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 ...) 
    22 
    33This 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 x86-64 system, which uses the implementation of mpn_gcd_1() in the file libraries/integer-gmp/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. 
    44 
    55The problem can be seen as follows: 
    6  
     6{{{ 
    77GHCi, version 7.3.20111124: http://www.haskell.org/ghc/  :? for help 
    88Loading package ghc-prim ... linking ... done. 
     
    1414Prelude GHC.Integer.GMP.Internals GHC.Types GHC.Int GHC.Integer.GMP.Prim> I# (gcdInt# 0x2B992DDFA23249D6# 0xDE0B6B3A7640000#) 
    15150 
    16  
     16}}} 
    1717This should reproduce on any x86-64 system, although I don't have access to another one to test that.  In my setup, I'm using the in-tree GMP, which is GMP 5.0.2 as of this writing. 
    1818