Opened 10 years ago

Last modified 5 years ago

#8111 new defect

gcd of rationals is trouble

Reported by: pdehaye Owned by: AlexGhitza
Priority: major Milestone: sage-6.4
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps: todo

Description

The GCD of rationals is still unclear (see trac 3214), and leads to definite problems with reduce().

K.<k>= QQ[];
print gcd(64,256)
print gcd(K(64),K(256))
print gcd(64*k^2+128,64*k^3+256)
frac = (64*k^2+128)/(64*k^3+256)
frac.reduce()
print frac

gives

64
1
1
(64*k^2 + 128)/(64*k^3 + 256)

The last line in particular is false, according to me.

Change History (10)

comment:1 Changed 10 years ago by burcin

I think the trouble here is our generic fraction field code, not how we define the gcd of rational numbers.

For efficiency, we should represent QQ(x) as Frac(ZZ[x]), and do the necessary normalisation of the denominator (it should be monic) when the user accesses it with .denominator().

comment:2 follow-up: Changed 9 years ago by kcrisman

#10771 is probably related/same thing.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 9 years ago by SimonKing

Replying to kcrisman:

#10771 is probably related/same thing.

It may be related, but my patch from #10771 does not touch the gcd for QQ['x'] (perhaps it should?). So far, the two tickets are about different issues.

comment:4 in reply to: ↑ 3 Changed 9 years ago by SimonKing

Replying to SimonKing:

Replying to kcrisman:

#10771 is probably related/same thing.

It may be related, but my patch from #10771 does not touch the gcd for QQ['x'] (perhaps it should?). So far, the two tickets are about different issues.

PS: It seems to me that for changing gcd for univariate polynomials over the rationals, one has to dive into flint. I'll not do that, it'd be too far off topic for me. BTW, the doc string explicitly states that gcd in QQ['x'] returns the monic gcd.

comment:5 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 5 years ago by kcrisman

Possibly related: this discussion.

comment:10 Changed 5 years ago by jakobkroeker

  • Stopgaps set to todo
Note: See TracTickets for help on using tickets.