Opened 5 years ago
Closed 5 years ago
#20889 closed enhancement (fixed)
truncated power for polynomials
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  algebra  Keywords:  
Cc:  bruno, defeo, mmezzarobba  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Bruno Grenet 
Report Upstream:  N/A  Work issues:  
Branch:  8cbce5e (Commits)  Commit:  8cbce5ea799e51eec21c80d386bfbff6aa4f9cfb 
Dependencies:  Stopgaps: 
Description (last modified by )
Implement generic truncated power (method power_trunc
) for polynomials.
Change History (23)
comment:1 Changed 5 years ago by
 Branch set to u/vdelecroix/20889
 Commit set to f0b194b2edd3135ff0d014c13005a58ff5ebf6c3
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Commit changed from f0b194b2edd3135ff0d014c13005a58ff5ebf6c3 to d17dc6a93de5ca1ce49fb481044fd8772b8c0ce4
comment:3 Changed 5 years ago by
 Commit changed from d17dc6a93de5ca1ce49fb481044fd8772b8c0ce4 to 7e24e7abb3c962d90f4c64ec14adae17fe3e1fd9
Branch pushed to git repo; I updated commit sha1. New commits:
7e24e7a  Trac 20889: _pow_trunc_ > power_trunc

comment:4 Changed 5 years ago by
 Description modified (diff)
comment:5 followup: ↓ 6 Changed 5 years ago by
 Status changed from needs_review to needs_work
 How much does it gain to statically type the arguments of the method? One drawback is that you cannot do the following (though the computation would be fast):
sage: p = 7 sage: R.<x> = GF(p)[] sage: f = x^2 + x + 1 sage: f.power_trunc(2^100, 1000) Traceback (most recent call last): ... OverflowError: long int too large to convert
 On a related note, do you think it may be useful to allow for a negative power? The code could be as follows:
if n < 0: return self.inverse_series_trunc(prec).power_trunc(n, prec)
 The first line of documentation is pretty terse...
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 5 years ago by
Replying to bruno:
 How much does it gain to statically type the arguments of the method? One drawback is that you cannot do the following (though the computation would be fast):
sage: p = 7 sage: R.<x> = GF(p)[] sage: f = x^2 + x + 1 sage: f.power_trunc(2^100, 1000) Traceback (most recent call last): ... OverflowError: long int too large to convert
The reason is that I want to use library calls when available. Some of them does not support arbitrary precision exponent. I used the type from flint.
 On a related note, do you think it may be useful to allow for a negative power? The code could be as follows:
if n < 0: return self.inverse_series_trunc(prec).power_trunc(n, prec)
I don't know. I do not think of power_trunc
as a convenience function. I want to use it in algorithms (like nth_root
). We might propose _power_trunc_
(or _power_trunc
or any other names) with restricted types. And on the other hand power_trunc
with arbitrary precision and possibly negative input... Library calls would just override the specialized function _power_trunc_
. What do you think?
 The first line of documentation is pretty terse...
I will change it.
comment:7 in reply to: ↑ 6 Changed 5 years ago by
Replying to vdelecroix:
I don't know. I do not think of
power_trunc
as a convenience function. I want to use it in algorithms (likenth_root
). We might propose_power_trunc_
(or_power_trunc
or any other names) with restricted types. And on the other handpower_trunc
with arbitrary precision and possibly negative input... Library calls would just override the specialized function_power_trunc_
. What do you think?
There are two things: About negative powers, I mostly don't care though it may be handy to have the possibility. About large powers, I think that public methods with integer inputs should be able to handle any element of ZZ
. So there are two solutions that I prefer against the current situation: Either remove the static types, or manually catch the exception for large powers. I suspect that the second solution cannot be implemented while keeping the static types...
I find your solution of having both power_mod
as public interface and _power_mod
is a good tradeoff.
comment:8 Changed 5 years ago by
 Commit changed from 7e24e7abb3c962d90f4c64ec14adae17fe3e1fd9 to f1c00ded6ac3e777a41db5b6b330f7b89ab4fc19
comment:9 Changed 5 years ago by
 Status changed from needs_work to needs_review
It is a bit of duplication but now the code handles any integer size for the power n
. The specialized code is only used when it fits into an unsigned long.
comment:10 Changed 5 years ago by
I am mostly happy with this ticket, though I wonder whether code duplication is really useful: Is it necessary to have the generic method _power_trunc
? My brief tests do not show significant speedup when using this generic implementation instead of power_trunc
. The speedup is notable when one uses the specialized implementations (using Flint) of course.
I would simply remove _power_trunc
in src/sage/rings/polynomial/polynomial_element.pyx
, and add a test to know whether _power_trunc
exists. I guess you are much more experienced than me in Cython, so I may be saying something stupid.
comment:11 Changed 5 years ago by
 Commit changed from f1c00ded6ac3e777a41db5b6b330f7b89ab4fc19 to d7d124e53af86ddf8b29f404f5b1b92ef42e7f61
Branch pushed to git repo; I updated commit sha1. New commits:
d7d124e  Trac 20889: generic_power_trunc to avoid duplication

comment:12 Changed 5 years ago by
Done! (the gittrac plugin did not sent me an email)
comment:13 followup: ↓ 14 Changed 5 years ago by
I am sorry if I am becoming painful...
 I would allow more general integers in
generic_power_trunc
to allow computations as follows:
sage: R.<x> = PolynomialRing(ZZ, sparse=True) sage: p = x^2^100 + 1 sage: p.power_trunc(100, 2^100+1) 100*x^1267650600228229401496703205376 + 1
 A curiosity question: Why did you write
generic_power_trunc
outside from any class?
comment:14 in reply to: ↑ 13 ; followup: ↓ 16 Changed 5 years ago by
Replying to bruno:
I am sorry if I am becoming painful...
I wish I had every review like this one!
 I would allow more general integers in
generic_power_trunc
to allow computations as follows:sage: R.<x> = PolynomialRing(ZZ, sparse=True) sage: p = x^2^100 + 1 sage: p.power_trunc(100, 2^100+1) 100*x^1267650600228229401496703205376 + 1
I see. You mean for prec
. As in your example, this would only be interesting for sparse polynomials. Note that it will not work at all for dense polynomials because truncate
is defined as cpdef Polynomial truncate(self, long prec)
. I don't mind changing the generic method to handle this case.
 A curiosity question: Why did you write
generic_power_trunc
outside from any class?
I did not have any other option. As you said we could have checked whether the method _power_trunc
is implemented in subclasses but this is not as simple as it seems with cpdef
methods.
comment:15 Changed 5 years ago by
I can not change long > Integer
for prec
. The reason is that truncate
(for both dense and sparse polynomials) is declared as cpdef truncate(self, long n)
.
comment:16 in reply to: ↑ 14 Changed 5 years ago by
 Reviewers set to Bruno Grenet
 Status changed from needs_review to positive_review
Replying to vdelecroix & vdelecroix:
I see. You mean for
prec
. As in your example, this would only be interesting for sparse polynomials. Note that it will not work at all for dense polynomials becausetruncate
is defined ascpdef Polynomial truncate(self, long prec)
. I don't mind changing the generic method to handle this case.
I can not change
long > Integer
forprec
. The reason is thattruncate
(for both dense and sparse polynomials) is declared ascpdef truncate(self, long n)
.
For dense polynomials, this makes sense because of the size of the representation. For sparse polynomials, I think this is a problem and I encountered it several times: For sparse polynomials to have an interest, one should not bound their degree. But anyway, this is not the purpose of this ticket.
comment:17 Changed 5 years ago by
 Status changed from positive_review to needs_work
Documentation doesn't build
There are more test failures, see patchbot report.
comment:18 Changed 5 years ago by
 Commit changed from d7d124e53af86ddf8b29f404f5b1b92ef42e7f61 to 446d833b0f8643c4cb3f4955b5553d3367a9ba98
Branch pushed to git repo; I updated commit sha1. New commits:
446d833  Trac 20889: doc fix

comment:19 Changed 5 years ago by
 Status changed from needs_work to needs_review
Corrected the doc. Waiting for patchbot report...
comment:20 Changed 5 years ago by
 Commit changed from 446d833b0f8643c4cb3f4955b5553d3367a9ba98 to 8cbce5ea799e51eec21c80d386bfbff6aa4f9cfb
Branch pushed to git repo; I updated commit sha1. New commits:
8cbce5e  Trac 20889: fix doctests

comment:21 Changed 5 years ago by
As far as I can tell, this now passes all the tests and the documentation correctly builds. I am not sure to be able to interpret patchbot messages, so I let somebody else setting the ticket to positive review
if everything's OK. (Vincent, you can do it yourself on my behalf.)
comment:22 Changed 5 years ago by
 Status changed from needs_review to positive_review
It is indeed strange...
comment:23 Changed 5 years ago by
 Branch changed from u/vdelecroix/20889 to 8cbce5ea799e51eec21c80d386bfbff6aa4f9cfb
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac 20889: _pow_trunc_ for polynomials