Opened 6 years ago

Closed 6 years ago

#17180 closed enhancement (fixed)

Move and fix rational reconstruction

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-6.4
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Jeroen Demeyer Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 8107b4e (Commits) Commit: 8107b4e44e909a4e194858d25c4e2182b4f0b996
Dependencies: #16428 Stopgaps:

Description (last modified by jdemeyer)

rational_reconstruction modifies its input:

sage: a = -1
sage: a.rational_reconstruction(5)
-1
sage: a
4

Move the implementation of rational reconstruction to src/sage/libs/gmp/rational_reconstruction.pyx as part of the effort to clean up gmp.pxi.

Change History (14)

comment:1 Changed 6 years ago by jdemeyer

  • Description modified (diff)
  • Summary changed from Move rational_reconstruction to fast_arith.pyx to Move rational reconstruction to dedicated file

comment:2 Changed 6 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Description modified (diff)
  • Summary changed from Move rational reconstruction to dedicated file to Move and fix rational reconstruction

comment:3 Changed 6 years ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/17180
  • Created changed from 10/19/14 19:29:25 to 10/19/14 19:29:25
  • Modified changed from 10/19/14 19:42:45 to 10/19/14 19:42:45

comment:4 Changed 6 years ago by git

  • Commit set to 6254633fbdb3326759debf9614fa5adfd0d21220

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

6254633Fix rational reconstruction

comment:5 Changed 6 years ago by jdemeyer

  • Status changed from new to needs_review

comment:6 Changed 6 years ago by git

  • Commit changed from 6254633fbdb3326759debf9614fa5adfd0d21220 to f9645edf887bb52bc984d2cb57b8921dc95f02cb

Branch pushed to git repo; I updated commit sha1. New commits:

f9645edTypo

comment:7 follow-up: Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_info

Hello,

In rational_reconstruction.pyx why did you import Integer from sage.rings.integer?

The following also looks like a type as there is neither w1 nor w2

            mpz_swap(u1, v1)       # u1 = v1; v1 = w1
            mpz_swap(u2, v2)       # u2 = v2; v2 = w2

Beyond that, it looks nice.

Vincent

comment:8 Changed 6 years ago by jdemeyer

The w1 and w2 are not typos: they are "virtual" variables, see the lines above

mpz_submul(u1, q, v1) # w1 = u1 - q*v
mpz_submul(u2, q, v2) # w2 = u2 - q*v2
mpz_swap(u1, v1) # u1 = v1; v1 = w1
mpz_swap(u2, v2) # u2 = v2; v2 = w2

Introducing actual variables w1 and w2 would be slower than reusing u1 and u2. Perhaps this should be documented better, but it's not a mistake.

comment:9 in reply to: ↑ 7 Changed 6 years ago by jdemeyer

Replying to vdelecroix:

Hello,

In rational_reconstruction.pyx why did you import Integer from sage.rings.integer?

No reason, this can be removed.

comment:10 Changed 6 years ago by git

  • Commit changed from f9645edf887bb52bc984d2cb57b8921dc95f02cb to 8107b4e44e909a4e194858d25c4e2182b4f0b996

Branch pushed to git repo; I updated commit sha1. New commits:

8107b4eRemove unused import of Integer

comment:11 Changed 6 years ago by jdemeyer

  • Status changed from needs_info to needs_review

comment:12 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:13 Changed 6 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix

comment:14 Changed 6 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/17180 to 8107b4e44e909a4e194858d25c4e2182b4f0b996
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.