math/big: Int.GCD misbehaves when argument reused for result

[pat42smith]

Code of the form x.GCD(nil, nil, y, x) is likely to return an incorrect result. For example, this code:

package main
import "fmt"
import "math/big"
func main() {
    two := big.NewInt(2)
    fmt.Print(big.NewInt(0).GCD(nil, nil, two, big.NewInt(1)))
    x := big.NewInt(1)
    fmt.Print(x.GCD(nil, nil, two, x))
    fmt.Print(x)

    u := big.NewInt(0)
    v := big.NewInt(0)
    fmt.Print(big.NewInt(0).GCD(u, v, two, big.NewInt(1)))
    x = big.NewInt(1)
    fmt.Print(x.GCD(u, v, two, x))
    fmt.Println(x)
}

should print 111111. Instead, it prints 122111.

The cause is clear from examining the start of the binaryGCD method in int.go:

   682  func (z *Int) binaryGCD(a, b *Int) *Int {
   683      u := z
   684      v := new(Int)
   685  
   686      // use one Euclidean iteration to ensure that u and v are approx. the same size
   687      switch {
   688      case len(a.abs) > len(b.abs):
   689          u.Set(b)
   690          v.Rem(a, b)
   691      case len(a.abs) < len(b.abs):
   692          u.Set(a)
   693          v.Rem(b, a)
   694      default:
   695          u.Set(a)
   696          v.Set(b)
   697      }

In the misbehaving call, z and b point to the same object, so the calls to u.Set() will modify the value of b. Since the rest of the function does not use a and b, it should be possible to fix this by simply setting v before u in each of the three instances above.

Lastly, go version returns go version go1.4.2 linux/amd64

[randall77]

@griesemer

[griesemer]

Thanks for the analysis @pat42smith !

[pat42smith]

From opened to fixed and closed in under 24 hours! Thanks @griesemer !