Opened 2 years ago

Last modified 4 days ago

#31477 needs_work defect

Error in pynac's numeric::gcd method

Reported by: gh-DaveWitteMorris Owned by:
Priority: major Milestone:
Component: symbolics Keywords: gcd, pynac
Cc: Merged in:
Authors: Dave Morris Reviewers:
Report Upstream: N/A Work issues:
Branch: public/31477 (Commits, GitHub, GitLab) Commit: 77bf8ced66673b76ca9a28cfa9c55d8b0f55a58b
Dependencies: Stopgaps:

Status badges

Description

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

Change History (14)

comment:1 Changed 2 years ago by gh-DaveWitteMorris

Branch: public/31477

comment:2 Changed 2 years ago by gh-DaveWitteMorris

Commit: bf1ab79e7a0bfb758d55ad0a9bdbd35ac400c39d
Status: newneeds_review

This is part of metaticket #31478.


New commits:

bf1ab79trac 31477 fix pynac gcd(p,1)

comment:3 Changed 22 months ago by 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?

comment:4 Changed 21 months ago by mkoeppe

Milestone: sage-9.3sage-9.4

Moving to 9.4, as 9.3 has been released.

comment:5 in reply to:  3 Changed 20 months ago by gh-DaveWitteMorris

Status: needs_reviewneeds_work

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."

comment:6 Changed 18 months ago by mkoeppe

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

comment:7 Changed 18 months ago by mkoeppe

Milestone: sage-9.4sage-9.5

comment:8 Changed 17 months ago by mkoeppe

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

comment:9 Changed 16 months ago by git

Commit: bf1ab79e7a0bfb758d55ad0a9bdbd35ac400c39d77bf8ced66673b76ca9a28cfa9c55d8b0f55a58b

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

77bf8cefix pynac gcd(p,1)

comment:10 Changed 16 months ago by mkoeppe

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

comment:11 Changed 14 months ago by mkoeppe

Milestone: sage-9.5sage-9.6

comment:12 Changed 9 months ago by mkoeppe

Milestone: sage-9.6sage-9.7

comment:13 Changed 5 months ago by mkoeppe

Milestone: sage-9.7sage-9.8

comment:14 Changed 4 days ago by mkoeppe

Milestone: sage-9.8
Note: See TracTickets for help on using tickets.