Opened 11 years ago

Closed 4 months ago

#8111 closed task (fixed)

gcd of rationals is trouble

Reported by: pdehaye Owned by: AlexGhitza
Priority: minor Milestone: sage-9.2
Component: basic arithmetic Keywords: sd109
Cc: Merged in:
Authors: Jonathan Kliem Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: bed3abb (Commits) Commit: bed3abb1364df5a4e0588953f535b3cc9b563766
Dependencies: Stopgaps: todo

Description (last modified by gh-kliem)

The following was solved along the way. We add a doctest.

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 (17)

comment:1 Changed 11 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 10 years ago by kcrisman

#10771 is probably related/same thing.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 10 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 10 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 7 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 6 years ago by kcrisman

Possibly related: this discussion.

comment:10 Changed 5 years ago by jakobkroeker

  • Stopgaps set to todo

comment:11 follow-up: Changed 5 months ago by gh-kliem

  • Authors set to Jonathan Kliem
  • Description modified (diff)
  • Keywords sd109 added
  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

comment:12 in reply to: ↑ 11 Changed 5 months ago by kcrisman

  • Authors Jonathan Kliem deleted
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-9.3
  • Priority changed from major to minor
  • Status changed from needs_review to needs_info
  • Type changed from defect to task

If this is fixed, we should probably have a doctest then. Unless it wasn't an error to begin with? Or it's possible it was fixed elsewhere and doctested, which is fine too.

comment:13 Changed 5 months ago by gh-kliem

  • Authors set to Jonathan Kliem
  • Branch set to public/8111
  • Commit set to bed3abb1364df5a4e0588953f535b3cc9b563766
  • Description modified (diff)
  • Status changed from needs_info to needs_review

New commits:

bed3abbadd doctest for 8111

comment:14 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.2

comment:15 Changed 4 months ago by mkoeppe

  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to positive_review

comment:16 Changed 4 months ago by gh-kliem

Thank you.

comment:17 Changed 4 months ago by vbraun

  • Branch changed from public/8111 to bed3abb1364df5a4e0588953f535b3cc9b563766
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.