Opened 12 years ago

Closed 12 years ago

# [with patch, positive review] Improvements to quadratic_forms/extras/py

Reported by: Owned by: cremona justin minor sage-4.0 quadratic forms quadratic forms tornaria, jonhanke

### 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:

1. 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.
1. I moved `IsPadicSquare()` to a member function for rationals, so you now say r.is_padic_square(p) instead of `IsPadicSquare(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.
1. I removed random_int_upto(n) since it does the same as ZZ.random_element(n).
1. 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.
1. 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.

### comment:1 Changed 12 years ago by cremona

• 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 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 253 you ended up with loads of integers that had a common divisor of 247 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

### comment:3 in reply to: ↑ 2 Changed 12 years ago by cremona

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 253 you ended up with loads of integers that had a common divisor of 247 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!

### Changed 12 years ago by cremona

Replaces earlier patch, based on 3.4.2.alpha0

### comment:4 Changed 12 years ago by cremona

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 jonhanke

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

• There is a `quadratic_nonresidue()` routine in `integer_mod_ring.py` which might benefit from using the `least_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.

### Changed 12 years ago by jonhanke

Very minor changed to the rebase patch above

### comment:6 Changed 12 years ago by cremona

Thanks, Jon. Your small extra patch looks ok to me but I did not try applying it.

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 mabshoff

• Resolution set to fixed
• Status changed from new to closed

Merged both patches in Sage 4.0.alpha0.

Cheers,

Michael

Note: See TracTickets for help on using tickets.