# Ticket #13213(closed enhancement: fixed)

Opened 11 months ago

## Comparisons in quadratic number field

Reported by: Owned by: vdelecroix vdelecroix major sage-5.10 number fields real number field, comparison N/A Burcin Erocal, Volker Braun Vincent Delecroix sage-5.10.beta4

The order of quadratic field with specified embedding is not induced from the order of RR and CC. More precisely we have

```sage: K.<sqrt2> = NumberField(x^2 - 2, 'sqrt2', embedding=1.4142)
sage: sqrt2 < 100
False

sage: K.<s> = NumberField(x^3 - 2, 's', embedding=1.26)
sage: s < 100
False
```

which is not compatible with the order of RR and

```sage: K.<i> = QuadraticField(-1)
sage: i > 1
True
sage: 1 > i
True
```

which is not compatible (!) with the order of CC.

The ticket implements the order for quadratic field (for which comparisons are made using only operations on integers).

Note:

• this patch is partly a duplicate because of #7160
• the modifications for quadratic field field modify the behavior of many commands (especially about output order).
• the patch introduces a new attribute to NumberFieldElement?_quadratic called standard_embedding (of type bint)

There is no significant lost of speed as shown on the following timings.

```sage: K.<sqrt2> = QuadraticField(2, 'sqrt2', embedding=1.4142)
sage: a = (3*sqrt2 + 18)/7
sage: b = (5*sqrt2 + 14)/5
sage: %timeit a < b
1000000 loops, best of 3: 408 ns per loop

sage: a = 3*s + 2/4
sage: b = 5/7*s + 1/3
sage: %timeit a < b
1000000 loops, best of 3: 352 ns per loop
```

Timings without the patch

```sage: sage: K.<sqrt2> = QuadraticField(2,'sqrt2',embedding=1.4142)
sage: a = (3*sqrt2 + 18)/7
sage: b = (5*sqrt2 + 14)/5
sage: %timeit a < b
1000000 loops, best of 3: 393 ns per loop

sage: a = 3*s+2/4
sage: b = 5/7*s+1/3
sage: %timeit a < b
1000000 loops, best of 3: 344 ns per loop
```

Apply:

## Change History

### comment:1 Changed 11 months ago by aapitzsch

• Authors changed from vdelecroix to Vincent Delecroix

I had a short look at your patch. Could you use Python 3 compatible syntax to raise errors. E.g.

```raise ValueError("absolute value not implemented for complex embeddings")
```

### comment:2 Changed 11 months ago by vdelecroix

• Description modified (diff)

### comment:3 Changed 11 months ago by vdelecroix

• Description modified (diff)

### comment:4 Changed 11 months ago by vdelecroix

• Description modified (diff)

### comment:5 follow-up: ↓ 6 Changed 11 months ago by burcin

• Reviewers set to Burcin Erocal

Thanks again for the patch. A few comments:

• reimplementing the comparison of quadratic number field elements is a well defined unit of change itself. I suggest moving floor() and ceil() implementations to a separate patch, even a different ticket.
• Do you really need to use rich comparisons? Working only with __cmp__ should simplify the case comparisons before the return statements and avoid the new python_object.pxi include.
• I guess speed could be further improved by using an approximation (with doubles say) first and falling back to the exact computation if the results are too close.
• left.D is of type Integer. Cython tries to do the right thing for <unsigned int> left.D, but it would be better to use mpz_mul() with left.D.value.
• mpz_sgn() returns 0 if the argument is 0. You don't seem to cover this case, though I couldn't find any example that returns wrong results.
• To avoid code duplication, it might be better change the if statement to:
```        if mpz_sgn(i)*mpz_sgn(j) == 1:
# both i and j are positive or negative
mpz_mul(i, i, i)
mpz_mul(j, j, j)
mpz_mul_ui(j, j, <unsigned int> left.D)

test = mpz_cmp(i, j)
if mpz_sgn(i) == -1:
# both i and j are negative
test *= -1
```

### comment:6 in reply to: ↑ 5 Changed 11 months ago by vdelecroix

• Description modified (diff)
• reimplementing the comparison of quadratic number field elements is a well defined unit of change itself. I suggest moving floor() and ceil() implementations to a separate patch, even a different ticket.
• left.D is of type Integer. Cython tries to do the right thing for <unsigned int> left.D, but it would be better to use mpz_mul() with left.D.value.

Done and done.

• Do you really need to use rich comparisons? Working only with __cmp__ should simplify the case comparisons before the return statements and avoid the new python_object.pxi include.

We loose speed (~1 micro sec) by doing this. I quickly look at the code of comparison for Integer. The comparison is directly implemented inside richcmp and avoid as much as possible the coercion machinery (ie the type of the input is check with the cython function PY_TYPE_CHECK). Do you think we should proceed that way ?

• I guess speed could be further improved by using an approximation (with doubles say) first and falling back to the exact computation if the results are too close.

What do you mean by too close ? How do I certify that my float comparison is accurate enough ? Moreover, if we proceed that way we have to perform conversion from mpz_t to float (or double or real_mpfr). A way it may work is to look first if a,b, D and denom have reasonable values (recall that mpz_t have unlimited precision) and if yes, convert it to double and try to compare the arguments. Last, I'm not sure the gain of speed would be terrific. Comparison requires only 7 integer operations.

• mpz_sgn() returns 0 if the argument is 0. You don't seem to cover this case, though I couldn't find any example that returns wrong results.

Actually there is no problem since we compute the sign of an expression of the form a2 + b2 D where a and b are both integers (and one of them is non null) and D is a square free integer. Hence the sign is never 0.

• To avoid code duplication, it might be better change the if statement to:
```        if mpz_sgn(i)*mpz_sgn(j) == 1:
# both i and j are positive or negative
mpz_mul(i, i, i)
mpz_mul(j, j, j)
mpz_mul_ui(j, j, <unsigned int> left.D)

test = mpz_cmp(i, j)
if mpz_sgn(i) == -1:
# both i and j are negative
test *= -1
```

Sure but that way we call twice mpz_sgn(i)... I may change it if you prefer.

Actually, the part where a lot of time is lost is the check for embedding

```if not RDF.has_coerce_map_from(left._parent):
...
```

By replacing it by

```if left.D < 0:
...
```

I pass from 4 micro second to 2 micro seconds. That way comparison without embedding for positive discriminant will be equivalent to comparison with the standard embedding. This is in the last version of the patch. What do you think about that ?

### comment:7 Changed 10 months ago by vdelecroix

• Status changed from new to needs_review

### comment:8 Changed 10 months ago by vdelecroix

The code for comparison introduces a small bug as it ask to the parent whether the embedding is standard or not (via the boolean attribute _standard_embedding). But the latter was not defined for Cyclotomic field of order 3,4,6 (which are the ones which are quadratic). In that case, the attribute _standard_embedding is created at the initialization of the cyclotomic field.

The new patch takes care of this.

### comment:9 Changed 10 months ago by vdelecroix

• Status changed from needs_review to needs_work
• Description modified (diff)

### comment:10 Changed 10 months ago by vdelecroix

Because there are many parents for quadratic elements, I was obliged to test whether the parent has a method '_standard_embedding' or not. I correct all tests (many output have changed) and waiting for patchbot and reviewer!

### comment:11 Changed 10 months ago by vdelecroix

• Status changed from needs_work to needs_review

### comment:12 Changed 10 months ago by vdelecroix

I corrected the two last tests that have failed...

### comment:13 Changed 10 months ago by jdemeyer

How does this patch here relate to #7160?

### comment:14 Changed 10 months ago by jdemeyer

In the ticket title "real number field", should it say "quadratic number field" instead?

### comment:15 follow-up: ↓ 16 Changed 10 months ago by vdelecroix

Hi Jeroen,

From the last comment of Burcin on #7160, it seems to me that we will close #7160 as a duplicate. On the other hand, an other patch is coming for comparisons of general number field. Would you prefer to have it on a separate ticket ?

### comment:16 in reply to: ↑ 15 Changed 10 months ago by jdemeyer

From the last comment of Burcin on #7160, it seems to me that we will close #7160 as a duplicate. On the other hand, an other patch is coming for comparisons of general number field. Would you prefer to have it on a separate ticket ?

I don't care very much, but I think it should be clear how the various tickets relate to eachother.

Also #10064 is related, at least it has #7160 as dependency.

### comment:17 Changed 10 months ago by vdelecroix

• Description modified (diff)

### comment:18 Changed 10 months ago by tkluck

Just had a quick look at your patch. How about using @cached_method as a decorator for _gen_approx? Then you don't have to implement caching yourself. It makes the code a little bit easier to read.

### comment:19 Changed 9 months ago by vdelecroix

Hello,

Actually, a lot of time is lost for asking questions to the parent. For quadratic number field, it is for asking about the attribute _standard_embedding. I build a new patch with a bint attribute added to NumberFieldElement?_quadratic and the speed of comparison is divided by 10 (from 4 milliseconds to 400 nanoseconds). It will be updated as soon as possible. As modifying the structure of NumberFieldElement?_quadratic is a major change, I will split the patch into two parts : quadratic number fields and general number fields.

Vincent

### comment:20 Changed 2 weeks ago by vdelecroix

• Description modified (diff)
• Summary changed from Comparisons in real number field to Comparisons in quadratic number field

### comment:22 follow-up: ↓ 23 Changed 2 weeks ago by jpflori

• Status changed from needs_review to needs_work
• Description modified (diff)
• Work issues set to rebase 5.10.beta2

This fails to apply on 5.10.beta2. Having a look right now.

### comment:23 in reply to: ↑ 22 Changed 2 weeks ago by vdelecroix

This fails to apply on 5.10.beta2.

Yes, it is a minor rejection on sage/schemes/elliptic_curves/ell_number_field.py and a more serious problem with python_object.pxi that seems to not exist anymore.

Having a look right now.

Does it mean that I should wait for your modifications ?

### comment:24 Changed 2 weeks ago by jpflori

No, if you identified the issues, please go ahead. I've just untarred 10.beta2 and are currently on something else, so you will definitely get faster.

### comment:25 Changed 2 weeks ago by vdelecroix

For the second problem I simply removed the import of python_object.pxi which was not needed anymore.

### comment:26 Changed 2 weeks ago by vdelecroix

• Status changed from needs_work to needs_review

### comment:27 Changed 2 weeks ago by vdelecroix

Last minute modification: more tests, more docs.

### comment:28 Changed 2 weeks ago by kcrisman

#7545 is possibly a related ticket.

### comment:29 follow-up: ↓ 30 Changed 2 weeks ago by vdelecroix

• Status changed from needs_review to needs_work

There is a strange problem

```sage: K.<sqrt2> = QuadraticField(2)
sage: 1/2 + sqrt2 > 0
False
```

### comment:30 in reply to: ↑ 29 Changed 2 weeks ago by vdelecroix

There is a strange problem

```sage: K.<sqrt2> = QuadraticField(2)
sage: 1/2 + sqrt2 > 0
False
```

I got the problem... it was because there is a natural morphism implemented from the rational field to quadratic number field (sage.rings.number_field.number_field_element_quadratic.Q_to_quadratic_field_element) which uses a non properly initialized instance of a quadratic element !

### comment:31 Changed 2 weeks ago by vdelecroix

• Status changed from needs_work to needs_review

### comment:32 follow-up: ↓ 33 Changed 11 days ago by vbraun

I get a doctest failure with sage-5.10.beta2:

```File "devel/sage/doc/de/tutorial/tour_advanced.rst", line 483, in doc.de.tutorial.tour_advanced
Failed example:
M.T(2).charpoly('x').factor()
Expected:
(x - 2*zeta6 - 1) * (x - zeta6 - 2) * (x + zeta6 + 1)^2
Got:
(x - zeta6 - 2) * (x - 2*zeta6 - 1) * (x + zeta6 + 1)^2
**********************************************************************
[118 tests, 1 failure, 1.44 s]
```

### comment:33 in reply to: ↑ 32 Changed 9 days ago by vdelecroix

I get a doctest failure with sage-5.10.beta2:

```File "devel/sage/doc/de/tutorial/tour_advanced.rst", line 483, in doc.de.tutorial.tour_advanced
Failed example:
M.T(2).charpoly('x').factor()
Expected:
(x - 2*zeta6 - 1) * (x - zeta6 - 2) * (x + zeta6 + 1)^2
Got:
(x - zeta6 - 2) * (x - 2*zeta6 - 1) * (x + zeta6 + 1)^2
**********************************************************************
[118 tests, 1 failure, 1.44 s]
```

Thanks for that. I got the same error on my computer and change the patch accordingly. Why was patchbot happy with the former patch ?

### comment:34 Changed 9 days ago by vbraun

The patchbot apparently doesn't check German docs. Enttäuschend! ;-)

### comment:35 Changed 9 days ago by vbraun

• Status changed from needs_review to positive_review
• Reviewers changed from Burcin Erocal to Burcin Erocal, Volker Braun

All tests pass.

### comment:36 Changed 9 days ago by kcrisman

• Work issues rebase 5.10.beta2 deleted

### comment:37 Changed 8 days ago by jdemeyer

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-5.10.beta4
Note: See TracTickets for help on using tickets.