Opened 5 years ago

Closed 5 years ago

#20889 closed enhancement (fixed)

truncated power for polynomials

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-7.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 vdelecroix)

Implement generic truncated power (method power_trunc) for polynomials.

Change History (23)

comment:1 Changed 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/20889
  • Commit set to f0b194b2edd3135ff0d014c13005a58ff5ebf6c3
  • Status changed from new to needs_review

New commits:

f0b194bTrac 20889: _pow_trunc_ for polynomials

comment:2 Changed 5 years ago by git

  • Commit changed from f0b194b2edd3135ff0d014c13005a58ff5ebf6c3 to d17dc6a93de5ca1ce49fb481044fd8772b8c0ce4

Branch pushed to git repo; I updated commit sha1. New commits:

e7c9ddeTrac 20889: better typing + use _pow_trunc_ in __pow__
394b562Trac 20889: _pow_trunc_ for fmpz_polynomial
d17dc6aTrac 20889: documentation

comment:3 Changed 5 years ago by git

  • Commit changed from d17dc6a93de5ca1ce49fb481044fd8772b8c0ce4 to 7e24e7abb3c962d90f4c64ec14adae17fe3e1fd9

Branch pushed to git repo; I updated commit sha1. New commits:

7e24e7aTrac 20889: _pow_trunc_ -> power_trunc

comment:4 Changed 5 years ago by vdelecroix

  • Description modified (diff)

comment:5 follow-up: Changed 5 years ago by bruno

  • 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 ; follow-up: Changed 5 years ago by vdelecroix

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 bruno

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 (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?

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 trade-off.

comment:8 Changed 5 years ago by git

  • Commit changed from 7e24e7abb3c962d90f4c64ec14adae17fe3e1fd9 to f1c00ded6ac3e777a41db5b6b330f7b89ab4fc19

Branch pushed to git repo; I updated commit sha1. New commits:

9a450b0Trac 20889: allow any input size
0b731e6Trac 20889: use power_trunc in nth_root
f1c00deTrac 20889: one more _power_trunc flint call

comment:9 Changed 5 years ago by vdelecroix

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

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 git

  • Commit changed from f1c00ded6ac3e777a41db5b6b330f7b89ab4fc19 to d7d124e53af86ddf8b29f404f5b1b92ef42e7f61

Branch pushed to git repo; I updated commit sha1. New commits:

d7d124eTrac 20889: generic_power_trunc to avoid duplication

comment:12 Changed 5 years ago by vdelecroix

Done! (the git-trac plugin did not sent me an e-mail)

comment:13 follow-up: Changed 5 years ago by bruno

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 ; follow-up: Changed 5 years ago by vdelecroix

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 vdelecroix

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 bruno

  • 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 because truncate is defined as cpdef Polynomial truncate(self, long prec). I don't mind changing the generic method to handle this case.

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

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 vbraun

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

  • Commit changed from d7d124e53af86ddf8b29f404f5b1b92ef42e7f61 to 446d833b0f8643c4cb3f4955b5553d3367a9ba98

Branch pushed to git repo; I updated commit sha1. New commits:

446d833Trac 20889: doc fix

comment:19 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Corrected the doc. Waiting for patchbot report...

comment:20 Changed 5 years ago by git

  • Commit changed from 446d833b0f8643c4cb3f4955b5553d3367a9ba98 to 8cbce5ea799e51eec21c80d386bfbff6aa4f9cfb

Branch pushed to git repo; I updated commit sha1. New commits:

8cbce5eTrac 20889: fix doctests

comment:21 Changed 5 years ago by bruno

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 vdelecroix

  • Status changed from needs_review to positive_review

It is indeed strange...

comment:23 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/20889 to 8cbce5ea799e51eec21c80d386bfbff6aa4f9cfb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.