Opened 11 years ago

Closed 11 years ago

#11685 closed defect (fixed)

Pari finite field extension: element created by list not recognised as zero

Reported by: johanbosman Owned by: AlexGhitza
Priority: major Milestone: sage-4.7.2
Component: algebra Keywords: finite fields, pari
Cc: Merged in: sage-4.7.2.alpha3
Authors: Johan Bosman, Jeroen Demeyer Reviewers: Simon King, Johan Bosman, Peter Bruin
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by leif)

In sage-4.7.1:

sage: K.<a> = GF(3^11)
sage: K([])
0
sage: K([]) == 0
False

Apply

  1. 11685_against_4.7.2.alpha1.patch
  2. 11685_referee.patch

to the Sage library.

Attachments (4)

trac_11685_pari_zero_list.patch (1.6 KB) - added by johanbosman 11 years ago.
11685_referee.patch (3.2 KB) - added by SimonKing 11 years ago.
Referee patch, adding documentation
11685.patch (17.5 KB) - added by jdemeyer 11 years ago.
New alternative patch, rewrites PARI->Integer coercion, fast and many features
11685_against_4.7.2.alpha1.patch (17.4 KB) - added by johanbosman 11 years ago.
11685.patch rebased against sage-4.7.2.alpha1

Download all attachments as: .zip

Change History (60)

comment:1 Changed 11 years ago by johanbosman

  • Summary changed from Pari finite field extension created by list not recognised as zero to Pari finite field extension: element created by list not recognised as zero

comment:2 Changed 11 years ago by johanbosman

  • Keywords pari added

Changed 11 years ago by johanbosman

comment:3 Changed 11 years ago by johanbosman

  • Authors set to Johan Bosman
  • Status changed from new to needs_review

comment:4 Changed 11 years ago by SimonKing

  • Reviewers set to Simon King
  • Status changed from needs_review to positive_review

Looking at the value of the attribute __value, I can confirm that there has been a bug, and I can confirm that your patch fixes it. The fix is tested, and the long doctests of both devel/sage-main/doc and devel/sage-main/sage pass.

Hence, I give it a positive review.

comment:5 Changed 11 years ago by jdemeyer

  • Authors changed from Johan Bosman to Johan Bosman, Jeroen Demeyer
  • Status changed from positive_review to needs_work

I add an alternative patch which IMHO fixes the problem in a better way, adds more tests and simplifies some other code regarding zero elements.

comment:6 Changed 11 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:7 follow-up: Changed 11 years ago by johanbosman

  • Status changed from needs_review to needs_work

There are doctests that fail:

sage -t  1.rc1/devel/sage-main/sage/rings/polynomial/polynomial_zz_pex.pyx # 9 doctests failed

comment:8 in reply to: ↑ 7 ; follow-ups: Changed 11 years ago by johanbosman

  • Description modified (diff)

Replying to johanbosman:

There are doctests that fail:

sage -t  1.rc1/devel/sage-main/sage/rings/polynomial/polynomial_zz_pex.pyx # 9 doctests failed

In combination with the fixes in #11684, that is.

comment:9 Changed 11 years ago by johanbosman

  • Reviewers changed from Simon King to Simon King, Johan Bosman

comment:10 in reply to: ↑ 8 Changed 11 years ago by SimonKing

Replying to johanbosman:

In combination with the fixes in #11684, that is.

If it is only in combination with #11684, then please test whether the problem persists if only the patch from here is applied.

comment:11 in reply to: ↑ 8 Changed 11 years ago by jdemeyer

Replying to johanbosman:

Replying to johanbosman:

There are doctests that fail:

sage -t  1.rc1/devel/sage-main/sage/rings/polynomial/polynomial_zz_pex.pyx # 9 doctests failed

In combination with the fixes in #11684, that is.

Agreed. The problem here is the empty list []. I did not realize this was a legal argument to the constructor.

comment:12 Changed 11 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:13 Changed 11 years ago by jdemeyer

  • Description modified (diff)

comment:14 Changed 11 years ago by SimonKing

With trac_11685_pari_zero_list.patch, we have (correctly)

sage: K.<a>=GF(next_prime(2**60)**3)
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value
Mod(Mod(0, 1152921504606847009), Mod(1, 1152921504606847009)*a^3 + Mod(1132330333307175281, 1152921504606847009)*a^2 + Mod(564283687250211459, 1152921504606847009)*a + Mod(455334297379199858, 1152921504606847009))

With 11685.patch, that example fails as follows:

sage: K.<a>=GF(next_prime(2**60)**3)                                            
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value  
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1140, 0))

---------------------------------------------------------------------------
PariError                                 Traceback (most recent call last)
...
PariError: incorrect type (11)

I think it should be possible to use the value of a pari element for the creation of a pari element. Hence, either we use the first patch, or the second patch needs work.

Perhaps, one could merge the two patches and use Johan's algorithm together with Jeroen's examples?

comment:15 Changed 11 years ago by SimonKing

  • Status changed from needs_review to needs_work

comment:16 Changed 11 years ago by jdemeyer

  • Status changed from needs_work to needs_review

New code, new tests to implement Simon King's suggestion.

comment:17 follow-up: Changed 11 years ago by SimonKing

  • Status changed from needs_review to needs_info

The error has changed, but there's still an error:

sage: K.<a>=GF(next_prime(2**60)**3)                                            
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1140, 0))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: unable to coerce

If we want to make that kind of conversion work (perhaps Johan can express his point of view?) then something needs to be done.

comment:18 Changed 11 years ago by johanbosman

Also, we should keep speed in mind. I've done some timings:

With my patch:

sage: K.<a> = GF(3^11)
sage: timeit('K([])')
625 loops, best of 3: 38.7 µs per loop

With Jeroen's current patch:

sage: K.<a> = GF(3^11)
sage: timeit('K([])')
625 loops, best of 3: 153 µs per loop

comment:19 in reply to: ↑ 17 Changed 11 years ago by johanbosman

Replying to SimonKing:

The error has changed, but there's still an error:

sage: K.<a>=GF(next_prime(2**60)**3)                                            
sage: b = K([0])
sage: K([b._FiniteField_ext_pariElement__value])._FiniteField_ext_pariElement__value
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1140, 0))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: unable to coerce

If we want to make that kind of conversion work (perhaps Johan can express his point of view?) then something needs to be done.

Yes, I certainly think it is a good idea to have such a conversion work.

comment:20 follow-up: Changed 11 years ago by SimonKing

  • Status changed from needs_info to needs_review

If both the stability and the timings speak for the first patch, then I'd say y'all should merge your two patches into one. I do believe that the doc tests from the second patch are more thorough, and it would also be nice to include the corner cases that came up in the discussion.

comment:21 Changed 11 years ago by SimonKing

  • Status changed from needs_review to needs_work

comment:22 in reply to: ↑ 20 ; follow-up: Changed 11 years ago by jdemeyer

Replying to SimonKing:

If both the stability and the timings speak for the first patch, then I'd say y'all should merge your two patches into one.

I think that the fact that your example works for the first patch is an unintentional side-effect and not really an intended feature. I believe my code is much more clear and simple.

I believe that I am fixing much more than what the ticket requires, but I will fix my patch anyway.

comment:23 in reply to: ↑ 22 ; follow-ups: Changed 11 years ago by SimonKing

Replying to jdemeyer:

I think that the fact that your example works for the first patch is an unintentional side-effect and not really an intended feature.

Intended or not doesn't matter. It is a feature, I think.

I believe that I am fixing much more than what the ticket requires, ...

Indeed it does, namely:

sage: k.<x> = GF(3^11)
sage: k([ k(0),k(1) ]) 
x 
sage: k([0,1/2]) 
2 
sage: R.<y> = PolynomialRing(k) 
sage: k([ R(0),R(1) ]) 
x

It a strength of your patch that the examples above work (they wouldn't, with the other patch).

Do you see a way to make both work?

I wouldn't say that your patch is simpler, because you first convert into a list of prime field elements and then convert into pari; a double conversion, so it seems to me, tends to be fragile.

I mean, the only problem with k([k([0])._FiniteField_ext_pariElement__value]) in your patch is the fact that the pari value (which, after all, is zero) can not be converted into the zero of a finite field. There could be a work around, such as

value = [GFp(c) for c in value if c else GFp.zero_element()] 

Concerning speed, one should test whether k([]) is the only case in which your patch is slower. Since you have a special case for k([]) anyway, it would be perfectly fine to have a short-cut, such as

if not value:  # or value==[], if that's faster
    self.__value = (pari(0) * parent._pari_one()).Mod(parent._pari_modulus()) 

comment:24 in reply to: ↑ 23 Changed 11 years ago by jdemeyer

  • Status changed from needs_work to needs_review

Replying to SimonKing:

I mean, the only problem with k([k([0])._FiniteField_ext_pariElement__value]) in your patch is the fact that the pari value (which, after all, is zero) can not be converted into the zero of a finite field.

This is not true, because this problem is not specific to zero. The problem really is that conversion of PARI finite field elements to ZZ fails. I rewrote the PARI -> ZZ conversion to fix this (the old code used strings(!) for the conversion)

comment:25 in reply to: ↑ 23 Changed 11 years ago by jdemeyer

Replying to SimonKing:

I wouldn't say that your patch is simpler, because you first convert into a list of prime field elements and then convert into pari; a double conversion, so it seems to me, tends to be fragile.

I would rather argue the opposite: I break the conversion down to two simpler independent steps.

It is probably true that my code is slower, but it all depends on what you want. Pick two:

  • Fast code
  • Simple code
  • Code with many features

comment:26 follow-up: Changed 11 years ago by jdemeyer

Note that most of the timing overhead in my latest patch is due to the creation of the FiniteField object. Maybe we could add a prime_field() cached method and use that?

comment:27 Changed 11 years ago by johanbosman

  • Status changed from needs_review to needs_work

Let me add that I discovered this bug while working on #11684, which is a speed issue. Normally I don't care so much about speed, but in this case things are really *far* too slow already; we should definitely not make them any slower, especially since this is not necessary. Seemingly innocent computations in Sage are often dominated by enormous chains of type conversions rather than the actual computations they intend to be.

In conclusion: it may be a good idea to either use such a cached method or avoid creating FiniteFields? at all. ;).

comment:28 in reply to: ↑ 26 Changed 11 years ago by SimonKing

Replying to jdemeyer:

Note that most of the timing overhead in my latest patch is due to the creation of the FiniteField object. Maybe we could add a prime_field() cached method and use that?

There is a prime_subfield() method, and you are perfectly right that it ought to be a cached method. Hopefully someone finally manages to review #11115: It would make cached methods very fast.

"Breaking down into two simpler steps" makes sense. But one should keep in mind that it will now be two steps that could break. And if you measure simplicity in lines of code: Both patches have six lines of code in the section we are now talking about (if I did not miscount).

Perhaps we should clarify what we want to do with a list.

Let K be a finite field that is not a prime field. To the very least, we want: If L is a list of elements of the prime subfield k of K then K(L) should first interprete L as the list of coefficients of a polynomial, and interprete the polynomial as an element of K.

Ideally, we also want to allow in L objects that can be converted into k, even though their parent is not k in the first place. We seem to disagree on how that conversion is best done.

1) The first patch seems to argue that, ultimately, we want to put stuff into pari, and so we should start to put it into pari as soon as possible, and do all further conversions there: We can put a list of field elements into pari, and we can easily convert things like pari(K(0)) into an element of pari(k).

2) The second patch seems to argue that we are Sage programmers, and thus the conversion should follow Sage standards, not pari standards. Thus, k is a finite prime field in Sage, and we only accept things that can be converted into that prime field. Apparently, an element of pari(K) that happens to belong to pari(k) fails to convert into k, sadly.

I think that both approaches are equally simple, and both approaches make sense.

So, I suggest to decide based on (a) speed and (b) generality. (b) could be problematic, since at the moment we have examples that only work with the first patch and examples that only work with the second patch.

According to Johan, things are already quite slow, so, speed should really matter most.

By the way, I'd prefer fast code with many features, if I can pick only two out of three...

comment:29 Changed 11 years ago by jdemeyer

  • Status changed from needs_work to needs_review

New patch uses PARI if possible with a generic fallback if PARI fails. This should be quite fast and still work in general.

comment:30 Changed 11 years ago by johanbosman

  • Status changed from needs_review to positive_review

The patch passes all long doctests, the speed is okay, and it works in combination with #11684. Conclusion: positive review. :).

comment:31 follow-up: Changed 11 years ago by SimonKing

  • Status changed from positive_review to needs_info

I tend to a positive review as well.

However, I have one question (thus "needs info"): Why did you remove the if not check: ... section? If one knows that the input is sane then it is very common to use check=False in order to save time.

comment:32 in reply to: ↑ 31 ; follow-up: Changed 11 years ago by jdemeyer

  • Status changed from needs_info to needs_review

Replying to SimonKing:

I tend to a positive review as well.

However, I have one question (thus "needs info"): Why did you remove the if not check: ... section? If one knows that the input is sane then it is very common to use check=False in order to save time.

1) That option and the code was completely undocumented and the purpose is not clear.

2) The logic seems backward: executing more code when not checking?

3) The check code changes the functionality of the function, which is usually not desired. To me checking should be something read-only, checking for invalid input and throwing exceptions. But not modifying the input.

4) the check code is related to the handling of zero inputs which is anyway handled separately in the code below.

comment:33 in reply to: ↑ 32 Changed 11 years ago by SimonKing

  • Status changed from needs_review to needs_work

First of all, note that the option check==False is used, as you can see by studying the arithmetic operations on finite field elements. And it is clearly beneficial! For example:

Without patches, I get

sage: K.<a> = GF(5^9)
sage: b = 4*a^7 + 2*a^5 + 4*a^4 + 4*a^3 + 3*a^2 + 3*a
sage: %timeit b+3  # here, you will find that "check=False".
625 loops, best of 3: 30.9 µs per loop
sage: %timeit copy(b)
625 loops, best of 3: 14.3 µs per loop

With your patch, it takes 42 µs resp. 25.9 µs per loop.

25-30% difference is relevant. Thus, I'd prefer to keep the "check=False" code.

Moreover, I can still not understand your rationale for removing the code:

Replying to jdemeyer:

1) That option and the code was completely undocumented and the purpose is not clear.

If code is not documented then it should be documented, not removed.

The purpose is very clear: Provide better speed by avoiding any tests (or conversions, in this case). I think it is fairly common to have that option in Sage, of course for internal use only.

The price to pay for the speed is that one needs to provide very specific input: It must be pari.

2) The logic seems backward: executing more code when not checking?

You can't be serious.

If one has check=False then one just has

        if not check:
            if not value:  # see comment below about this workaround
                self.__value = pari(0).Mod(parent._pari_modulus())*parent._pari_one()
            else:
                self.__value = value
            return

and nothing more: Note the "return" in the last line.

3) The check code changes the functionality of the function, which is usually not desired.

It is quite usual that the check option does change the behaviour of the function, in the sense that a very specific input is expected, and it is not tested whether the user really got it right.

Here, check=False means that the input must be an element in the pari interface. Only since "zero" is a special case (see comments in the code), you have the test "if not value". As a side effect, the input [] or None or False would result in a zero element as well.

To me checking should be something read-only, checking for invalid input and throwing exceptions. But not modifying the input.

Sometimes you have two separate options check and coerce. Here, indeed, checking means that the input is also converted, when necessary. convert_to_pari might be a better name than check.

But since it is for internal use anyway, I see not much reason to change the name.

4) the check code is related to the handling of zero inputs which is anyway handled separately in the code below.

No. The check code simply provides a short cut for pari input. Only since pari is inconsistent in the way how different types of zero are dealt with, a special case is needed.

I suggest to use your patch without removing the if check: part. Can you please update it? And since the arguments of the __init__ method are not documented at all, I suggest that I create a referee patch that fixes the documentation.

comment:34 Changed 11 years ago by jdemeyer

SimonKing?: I agree with your comments, I somehow totally misread the check=False code.

comment:35 Changed 11 years ago by SimonKing

  • Status changed from needs_work to needs_review

I see, so you change check into value_from_pari. So, I'll change my (not yet submitted) referee patch accordingly, and will run full doc tests. And then it'll hopefully be fine...

comment:36 follow-up: Changed 11 years ago by SimonKing

I see that you just do

if value_from_pari: 
    self.__value = value

without a special case for a vanishing value.

I assume that the special case if not value: was there on purpose. Let's see what the tests say...

Changed 11 years ago by SimonKing

Referee patch, adding documentation

comment:37 Changed 11 years ago by SimonKing

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

The tests pass, hence, it was not necessary to have a special case for zero if value_from_pari==True.

I have attached a referee patch, that documents the arguments and adds a few examples. I hope my words are clear and concise enough, as the possible input can be very different.

If you think that my referee patch needs work, then feel free to complain.

Apply 11685.patch 11685_referee.patch

comment:38 in reply to: ↑ 36 Changed 11 years ago by jdemeyer

Replying to SimonKing:

I assume that the special case if not value: was there on purpose. Let's see what the tests say...

I guess the special case was needed precisely because of some earlier badly-initialized zero. If we don't start with a bad zero, we cannot somehow end up with a bad zero (I hope).

comment:39 Changed 11 years ago by jdemeyer

  • Status changed from positive_review to needs_work

I changed the patch by re-enabling the use of PARI's exponentiation. There was a warning which does not apply any more. The only change is in the __pow__() method, needs review.

comment:40 Changed 11 years ago by jdemeyer

  • Status changed from needs_work to needs_review

Changed 11 years ago by jdemeyer

New alternative patch, rewrites PARI->Integer coercion, fast and many features

comment:41 follow-up: Changed 11 years ago by johanbosman

  • Status changed from needs_review to needs_info

I do get some fuzz applying the patch to sage-4.6.2.alpha1:

applying 11685.patch
patching file sage/rings/integer.pyx
Hunk #2 succeeded at 3081 with fuzz 2 (offset 2525 lines).
Hunk #4 succeeded at 610 with fuzz 2 (offset -24 lines).
now at: 11685.patch

How bad is that?

comment:42 in reply to: ↑ 41 ; follow-up: Changed 11 years ago by SimonKing

Replying to johanbosman:

I do get some fuzz applying the patch to sage-4.6.2.alpha1:

Do you mean "sage-4.7.2.alpha1" (not 4.6.2 but 4.7.2)?

Hunk #2 succeeded at 3081 with fuzz 2 (offset 2525 lines). Hunk #4 succeeded at 610 with fuzz 2 (offset -24 lines).

If I remember correctly, fuzz 2 will not be accepted by the release manager, because it is not improbable that the patch was applied in the wrong location - in particular when the offset is a couple of thousand lines.

comment:43 in reply to: ↑ 42 Changed 11 years ago by johanbosman

Do you mean "sage-4.7.2.alpha1" (not 4.6.2 but 4.7.2)?

Yes, I meant that indeed. :).

Hunk #2 succeeded at 3081 with fuzz 2 (offset 2525 lines). Hunk #4 succeeded at 610 with fuzz 2 (offset -24 lines).

If I remember correctly, fuzz 2 will not be accepted by the release manager, because it is not improbable that the patch was applied in the wrong location - in particular when the offset is a couple of thousand lines.

Okay, so in that case it needs to be rebased.

comment:44 Changed 11 years ago by johanbosman

  • Status changed from needs_info to needs_review

I've uploaded a rebased patch. If someone can double-check it, then we can give this ticket a positive review again.

comment:45 Changed 11 years ago by jdemeyer

  • Status changed from needs_review to needs_work

negative_review because the patch is applied in the wrong place (as was hinted in a comment above).

comment:46 Changed 11 years ago by johanbosman

What do you mean by "applied in the wrong place"?

Changed 11 years ago by johanbosman

11685.patch rebased against sage-4.7.2.alpha1

comment:47 Changed 11 years ago by johanbosman

  • Status changed from needs_work to needs_review

It appears that I'm blind. :P. Second try. ;).

comment:48 follow-up: Changed 11 years ago by SimonKing

What patches are to be applied? That's to say, shouldn't the ticket description be changed, so that 11685_against_4.7.2.alpha1.patch is applied instead of 11685.patch?

comment:49 in reply to: ↑ 48 Changed 11 years ago by johanbosman

Replying to SimonKing:

What patches are to be applied? That's to say, shouldn't the ticket description be changed, so that 11685_against_4.7.2.alpha1.patch is applied instead of 11685.patch?

That depends on the release manager, I guess. I do not really know which of those 2 patches should be in the description, i.e. either the patch that applies against the latest stable release or the patch that applies against the latest alpha release. But in any case, 11685_against_4.7.2.alpha1.patch is most likely the one that is going to be applied.

comment:50 Changed 11 years ago by leif

  • Description modified (diff)

Latest devel of course.

comment:51 Changed 11 years ago by leif

Anyone to review this? #11684 depends on it.

comment:52 follow-up: Changed 11 years ago by pbruin

  • Reviewers changed from Simon King, Johan Bosman to Simon King, Johan Bosman, Peter Bruin

I have read the patches, applied them, checked by hand whether it worked and tested the whole Sage installation. Everything runs without problems in version 4.7.1. I am now going to test it with 4.7.2.alpha1 before giving it a positive review.

comment:53 in reply to: ↑ 52 ; follow-up: Changed 11 years ago by johanbosman

Replying to pbruin:

I have read the patches, applied them, checked by hand whether it worked and tested the whole Sage installation. Everything runs without problems in version 4.7.1. I am now going to test it with 4.7.2.alpha1 before giving it a positive review.

FYI: the patch against 4.7.2.alpha1 should also work against 4.7.2.alpha2, which is the most recent development version. ;)

comment:54 in reply to: ↑ 53 Changed 11 years ago by pbruin

Replying to johanbosman:

FYI: the patch against 4.7.2.alpha1 should also work against 4.7.2.alpha2, which is the most recent development version. ;)

OK, I'm now testing it with 4.7.2.alpha2 instead.

comment:55 Changed 11 years ago by pbruin

  • Status changed from needs_review to positive_review

All tests passed in 4.7.2.alpha2 as well, so I'm giving it a positive review.

comment:56 Changed 11 years ago by leif

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