Error in pynac's numeric::gcd method

[DaveWitteMorris]

Functions in pynac expect the gcd of two rational numbers p and q to be the largest number d, such that p/d and q/d are integers (except that gcd(0,0) = 0). But pynac's numeric::gcd method says that gcd(p,1) = 1 for all p, which does not have to be true when p is not an integer.

Related ticket: #24880

Component: symbolics

Keywords: gcd, pynac

Author: Dave Morris

Branch/Commit: public/31477 @ 77bf8ce

Issue created by migration from https://trac.sagemath.org/ticket/31477

[DaveWitteMorris]

Branch: public/31477

[DaveWitteMorris]

comment:2

This is part of metaticket #31478.

---

New commits:

bf1ab79

trac 31477 fix pynac gcd(p,1)

[DaveWitteMorris]

Commit: bf1ab79

[tscrim]

comment:3

Wouldn't it make sense to check that if a.is_one() you return the denominator of b (and vice versa) so you don't completely loose the special case optimizations?

[mkoeppe]

comment:4

Moving to 9.4, as 9.3 has been released.

[DaveWitteMorris]

comment:5

Replying to @tscrim:

Wouldn't it make sense to check that if a.is_one() you return the denominator of b (and vice versa) so you don't completely loose the special case optimizations?

That seems reasonable, but needs some thought, because it will change the value of the function in some cases. Without the change you suggest, I think 1.gcd(b) will return 1 whenever b is a PyObject (such as a complex number), even if the denominator of b is not 1 (for example, if b is a rational multiple of I).

I think your change is probably correct (so the rest of the numeric::gcd code should be modified to match this), but this should be verified by looking at the uses of the gcd function to see what behaviour is expected.

Related ticket: #31884.

PS. Once the correct behaviour has been implemented, the description of the gcd(const numeric &a, const numeric &b) function (in this same file) should be corrected. It currently says "return The GCD of two numbers if both are integer, a numerical 1 if they are not."

[mkoeppe]

comment:6

With #32386, the new patch can just be applied to the merged-in sources

[mkoeppe]

comment:8

... by doing (cd src/sage/symbolic && patch -p1) < build/pkgs/pynac/patches/gcd1.patch

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

77bf8ce

fix pynac gcd(p,1)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bf1ab79 to 77bf8ce

[mkoeppe]

comment:10

9.5.beta2 has merged #32386, so I have applied your patch as indicated in comment:8