Opened 12 years ago
Closed 12 years ago
#5834 closed enhancement (fixed)
[with patch, positive review] Improvements to quadratic_forms/extras/py
Reported by: | cremona | Owned by: | justin |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.0 |
Component: | quadratic forms | Keywords: | quadratic forms |
Cc: | tornaria, jonhanke | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As first raised in #5627, concerning quadratic_forms/extras.py (which contains various utilities written for use in various places in thw quadratic_forms module):
I have added a patch after looking carefully at this, which does the following:
- I removed hilbert_symbol_rational(), making a trivial change to hilbert_symbol() so that it already works on rationals. I think this will useful outside the quadratic forms module.
- I moved
IsPadicSquare()
to a member function for rationals, so you now say r.is_padic_square(p) instead ofIsPadicSquare(r,p)
, while at the same time making the function simpler and cleaner. I think this will also be useful outside the quadratic forms module.
- I removed random_int_upto(n) since it does the same as ZZ.random_element(n).
- I simplified quadratic_nonresidue() (and changed its name to least_quadratic_nonresidue()) -- by putting in three simple tests for when the answer is 2, 3 or 5 the loop is avoided in 7/8 of the cases. I also changed the loop to "for r in xsrange(7,p)", in response to the discussion earlier on this ticket: adding the x gives an iterator instead of making the whole list and iterating through it (bad for large p!), and adding the s makes the iterator yield Sage integers (so it works for p too large to fit into a python int). I also added an is_prime() test on p, since otherwise if you give it a huge composite number there seemed to be a danger that it would run through a loop of length p before realising that the input was invalid.
- I simplified sgn().
All tests in sage/quadratic_forms pass, as do those in arith.py and rational.py which were also touched.
The patch needs to be applied to (at least) 3.4.1.rc3 + the two patches at #5627.
Attachments (2)
Change History (9)
comment:1 Changed 12 years ago by
- Summary changed from Improvements to quadratic_forms/extras/py to [with patch, neews review] Improvements to quadratic_forms/extras/py
comment:2 follow-up: ↓ 3 Changed 12 years ago by
- Cc tornaria jonhanke added
comment:3 in reply to: ↑ 2 Changed 12 years ago by
Replying to mabshoff:
Gonzalo, Jon,
this is your area of expertise. Can either one of you review?
And by the way: "3. I removed random_int_upto(n) since it does the same as ZZ.random_element(n)." is #5888. As it turned out that if you wanted some random number larger than 2^{53 you ended up with loads of integers that had a common divisor of 2}47 causing some trouble to Bill Hart today when he looked at the HNF code in Sage to compare some code he has written in FLINT.
Cheers,
Michael
Moral: do not reinvent the wheel, especially if your version is square. Use the wheels provided!
comment:4 Changed 12 years ago by
trac_5834-rebase.patch is rebased to 3.4.2.alpha0. (Totally trivial, only a couple of whitespace changes).
comment:5 Changed 12 years ago by
- Summary changed from [with patch, neews review] Improvements to quadratic_forms/extras/py to [with patch, positive review] Improvements to quadratic_forms/extras/py
This patch looks good, and I recommend it be approved.
A few comments:
- There is a
quadratic_nonresidue()
routine ininteger_mod_ring.py
which might benefit from using theleast_quadratic_residue()
routine. - What is the procedure for adding functionality present for rationals to integers? It might be useful for both integer and rational types to call the
is_padic_square()
method without explicit rational coercion.
Also, in an attached patch I made some very minor changes to the quadratic_form code where this replaced previous functionality.
comment:6 Changed 12 years ago by
Thanks, Jon. Your small extra patch looks ok to me but I did not try applying it.
I had not noticed the other quadratic_nonresidue() routine in integer_mod_ring.py!
On your other question, it seems rather random. I'm not sure what we can do about that. In some other languages, if there was a function which applied to rationals and you give it an integer, the compiler would insert the necessary coercion. But cannot do that (it would involve making integer a subclass of rational, which does not seem a good idea!)
comment:7 Changed 12 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged both patches in Sage 4.0.alpha0.
Cheers,
Michael
Gonzalo, Jon,
this is your area of expertise. Can either one of you review?
And by the way: "3. I removed random_int_upto(n) since it does the same as ZZ.random_element(n)." is #5888. As it turned out that if you wanted some random number larger than 2^{53 you ended up with loads of integers that had a common divisor of 2}47 causing some trouble to Bill Hart today when he looked at the HNF code in Sage to compare some code he has written in FLINT.
Cheers,
Michael