Opened 3 years ago

Closed 3 years ago

#24247 closed enhancement (fixed)

Implement __pow__ in the coercion model

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-8.2
Component: coercion Keywords:
Cc: Merged in:
Authors: Jeroen Demeyer Reviewers: Travis Scrimshaw, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 74d6700 (Commits) Commit: 74d67006dfbf205f8bd43d25ef2b4eebf695ae66
Dependencies: #24467 Stopgaps:

Description (last modified by jdemeyer)

We implement powering in the coercion model. One important difference between powering and other operators is that the most common use case for powering is powering something to an integer exponent.

To deal with this integer powering, we implement an action IntegerPowAction. This action calls a special method _pow_int() on the element. In other words, x ^ n for an integer n becomes x._pow_int(n). We also provide a default implementation of _pow_int for MonoidElement and RingElement which uses the square-and-multiply algorithm implemented in generic_power().

For backward compatibility reasons, we also call this action for elements of IntegerModRing(m). In the future, we may rethink what to do here, see #15709.

Apart from this, powering behaves like other binary operators: coercion to a common parent is done if no action is defined.

Note that the 3-argument version of pow() is not supported in the coercion model. Only specific types like Integer implement it. See also #5082.

Fixing powering for specific parents is not within the scope of this ticket, except where it was needed to fix doctest failures. For example, we fix various serious bugs in powering for RDF such as:

sage: RDF(0) ^ RDF(-1)
0.0
sage: RDF(-1) ^ RDF(2)
NaN

Change History (72)

comment:1 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24244 to #24248

comment:4 Changed 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/implement___pow___in_the_coercion_model

comment:5 Changed 3 years ago by git

  • Commit set to a18280f20d1a3a9d87300be699b5efa77ac10d8b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9ad8983Fake Integer interface
04235beNew functions integer_check_long() and integer_check_long_py()
ad34554Fix isinstance(x, int) calls in element.pyx
a18280fImplement __pow__ in the coercion model

comment:6 Changed 3 years ago by git

  • Commit changed from a18280f20d1a3a9d87300be699b5efa77ac10d8b to 8b194fb82d37eb5036f36ee37cf6b38bc27e0d30

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

bb114c9Fake Integer interface
4d76bc1New functions integer_check_long() and integer_check_long_py()
9c579c7Fix isinstance(x, int) calls in element.pyx
8b194fbImplement __pow__ in the coercion model

comment:7 Changed 3 years ago by git

  • Commit changed from 8b194fb82d37eb5036f36ee37cf6b38bc27e0d30 to 54eb896167c809daad138588f9bc86b5c5659591

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

54eb896Implement __pow__ in the coercion model

comment:8 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24248 to #24248, #24259

comment:9 Changed 3 years ago by git

  • Commit changed from 54eb896167c809daad138588f9bc86b5c5659591 to 5e031351b06fe41b299b1f2fb74cb294f3489fb1

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5e03135Implement __pow__ in the coercion model

comment:10 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24248, #24259 to #24248, #24259, #24260

comment:11 Changed 3 years ago by git

  • Commit changed from 5e031351b06fe41b299b1f2fb74cb294f3489fb1 to 0d3aa638f654dbc104ec85887eedfdb13e271589

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

88eaed5Declare Integer.value as array
5c1f43fDeprecate str ^ Integer
70592a8Fix compiler warning
d3db645Merge commit '88eaed585d8159a4a0763e56caaf3a767d4cb2f0'; commit '5c1f43f861165ff975616f60cab37c92d36d10f6'; commit '70592a850d7677928592c022760d6183bd81364f' into t/24247/implement___pow___in_the_coercion_model
0d3aa63Implement __pow__ in the coercion model

comment:12 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:13 Changed 3 years ago by git

  • Commit changed from 0d3aa638f654dbc104ec85887eedfdb13e271589 to 09afe6dd0312ea51fdb636440cab21f3cc6eccd6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

09afe6dImplement __pow__ in the coercion model

comment:14 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24248, #24259, #24260 to #24248, #24259, #24260, #24275, #24276

comment:15 Changed 3 years ago by git

  • Commit changed from 09afe6dd0312ea51fdb636440cab21f3cc6eccd6 to b0b4070a17e0ac455b569e3f37ace754abda7c89

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

cabd346Merge tag '8.1.rc4' into t/24247/implement___pow___in_the_coercion_model
b0b4070Various fixes

comment:16 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24248, #24259, #24260, #24275, #24276 to #24248, #24259, #24260, #24275, #24276, #24328

comment:17 Changed 3 years ago by git

  • Commit changed from b0b4070a17e0ac455b569e3f37ace754abda7c89 to f6d7ba296b19249e4b25a014ce5d3b6ea4986a9e

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c0aca1cNew module to implement generic_power
bcb70b3Merge commit '70592a850d7677928592c022760d6183bd81364f'; commit '88eaed585d8159a4a0763e56caaf3a767d4cb2f0'; commit '5c1f43f861165ff975616f60cab37c92d36d10f6'; commit 'c0aca1c0ac92b95d790f39369a683269efbde530' into t/24247/implement___pow___in_the_coercion_model
f6d7ba2Implement __pow__ in the coercion model

comment:18 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24248, #24259, #24260, #24275, #24276, #24328 to #24328, #24259, #24260, #24275, #24276

comment:19 Changed 3 years ago by git

  • Commit changed from f6d7ba296b19249e4b25a014ce5d3b6ea4986a9e to 7658aa46f07c76703ff6dc2e5598abd440306f7a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

fb9a0c2Various fixes related to generic_power()
de1c6f6Merge commit '70592a850d7677928592c022760d6183bd81364f'; commit '88eaed585d8159a4a0763e56caaf3a767d4cb2f0'; commit '5c1f43f861165ff975616f60cab37c92d36d10f6'; commit 'fb9a0c2e5a0dd88e82b7b6f1f56846deb696a56b' into t/24247/implement___pow___in_the_coercion_model
7658aa4Implement __pow__ in the coercion model

comment:20 Changed 3 years ago by git

  • Commit changed from 7658aa46f07c76703ff6dc2e5598abd440306f7a to edca7ab9da69ea2659f48cadbeb4915888f586f5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

edca7abImplement __pow__ in the coercion model

comment:21 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24328, #24259, #24260, #24275, #24276 to #24260, #24275, #24350

comment:22 Changed 3 years ago by jdemeyer

  • Dependencies #24260, #24275, #24350 deleted

comment:23 Changed 3 years ago by git

  • Commit changed from edca7ab9da69ea2659f48cadbeb4915888f586f5 to 4c442dc8a9f88811d0208c9d71f65a07162dd961

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4c442dcImplement __pow__ in the coercion model

comment:24 Changed 3 years ago by git

  • Commit changed from 4c442dc8a9f88811d0208c9d71f65a07162dd961 to cd95bbcace8f654401862748df5158f0f77be0d6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

cd95bbcImplement __pow__ in the coercion model

comment:25 Changed 3 years ago by git

  • Commit changed from cd95bbcace8f654401862748df5158f0f77be0d6 to 59a04410c0b0891d8836fe2f4a712cd21d38fa4d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

59a0441Implement __pow__ in the coercion model

comment:26 Changed 3 years ago by jdemeyer

  • Status changed from new to needs_review

comment:27 Changed 3 years ago by git

  • Commit changed from 59a04410c0b0891d8836fe2f4a712cd21d38fa4d to 19e671bcea9f0e6dc3b3f3a629a7f64c2bd3795f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

19e671bImplement __pow__ in the coercion model

comment:28 follow-up: Changed 3 years ago by nbruin

Isn't __pow__ just a right action, by either ZZ or RR?

comment:29 in reply to: ↑ 28 Changed 3 years ago by jdemeyer

Replying to nbruin:

Isn't __pow__ just a right action, by either ZZ or RR?

It could be an action. But I don't really understand what you are trying to say.

Are you saying that it should be an action?

Are you saying that there should not be a special method like _pow_int?

(Note that these are two independent questions)

Last edited 3 years ago by jdemeyer (previous) (diff)

comment:30 follow-up: Changed 3 years ago by nbruin

I was really just wondering if there would be a benefit to treating it as an action. There may be other hooks that are already available in the coercion framework, but the standard binary operation code tries (if I recall correctly) to find a *common* parent, and that's not the right thing to do for powering in general. Actions, on the other hand, should come pretty close. I have no feeling for the performance implications, though. I just raised the point because a brief scanning through the contributions here didn't seem to have considered this possibility.

For _pow_int: given the various powering strategies that exist for different types of rings (square-multiply, frobenius, power series expansion), my guess is that it's worth having a hook for it.

comment:31 in reply to: ↑ 30 Changed 3 years ago by jdemeyer

Replying to nbruin:

For _pow_int: given the various powering strategies that exist for different types of rings (square-multiply, frobenius, power series expansion), my guess is that it's worth having a hook for it.

OK good. So we are just talking about the code which calls this method.

comment:32 follow-ups: Changed 3 years ago by vdelecroix

Close to the arguments in comment:30, I am not sure that finding a common parent is a good solution to handle powerings. The only reasonable assumption that could be done with powering is (x^a)^b = x^(a*b) (that is: it is a multiplicative action).

Also, the command QQbar.gen()^(1/3) should not try to coerce 1/3 to QQbar. Rational, as integers, should definitely be treated apart. Though, do we have any concrete case where exponents can be something else than integer/rational? With respect to rational powering, this ticket raises an important question: what should be done with this coercion incoherence

sage: 4**(1/2)
2
sage: type(_)
<type 'sage.rings.rational.Rational'>
sage: 3**(1/2)
sqrt(3)
sage: type(_)
<type 'sage.symbolic.expression.Expression'>

Note also that x^a * y^a = (x*y)^a is wrong with rational exponents has often there is a choice of a root

sage: ((-1)^(1/3))^3
-1
sage: ((-1)^3)^(1/3)
(-1)^(1/3)

comment:33 in reply to: ↑ 32 Changed 3 years ago by nbruin

Replying to vdelecroix:

Also, the command QQbar.gen()^(1/3) should not try to coerce 1/3 to QQbar. Rational, as integers, should definitely be treated apart. Though, do we have any concrete case where exponents can be something else than integer/rational?

Yes, on anything with a real or complex analytic structure one probably wants that x^y is a shorthand for exp(log(x)*y) (although for serious use the latter is much better for understanding subtleties arising from multi-valuedness)

It does look like we might want to handle powering action by integers (no multi-valuedness problem, but may need existence or adjunction of inverses), by rationals, by appropriate completions of rationals as different actions, because of their different problems.

In principle, on a commutative multiplicative group of exponent N we'd even have a powering action by ZZ/N ZZ. I'm not so sure it's worth supporting that explicitly, though.

comment:34 Changed 3 years ago by jdemeyer

A lot of points are raised here.

First of all, the point of this ticket is making possible various ways of implementing powering in various parents, not to actually implement it that way. For example, I don't plan to re-implement powering for QQbar in this ticket. What is within the scope of this ticket is making it possible to implement a parent which treats powering by rationals in a specific way (by going through the coercion model which checks for actions and this QQbar^QQ powering should be an action).

Second, I do agree that powering by integers is special enough that there should be a default action (as suggested by Nils) which calls the special method _pow_int.

Third, I think that coercing to a common parent does make sense because:

  1. It is consistent with all other operators. Often multiplication is treated as an action too. Still, when no action is found, coercion to a common parent is done.
  1. There are several parents where a common parent for powering makes sense, in particular the various incarnations of real/complex numbers and the symbolic ring.
  1. If coercion to a common parent shouldn't be done, then what should be done by default if no action is found?

comment:35 in reply to: ↑ 32 Changed 3 years ago by jdemeyer

Replying to vdelecroix:

With respect to rational powering, this ticket raises an important question: what should be done with this coercion incoherence

sage: 4**(1/2)
2
sage: type(_)
<type 'sage.rings.rational.Rational'>
sage: 3**(1/2)
sqrt(3)
sage: type(_)
<type 'sage.symbolic.expression.Expression'>

Sorry, but that is a question about the implementation of powering for a specific parent, so not within the scope of this ticket.

comment:36 Changed 3 years ago by git

  • Commit changed from 19e671bcea9f0e6dc3b3f3a629a7f64c2bd3795f to 5b1435647c0d84a2a086afaa82e6359e77838b89

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d61f9eaBruhatTitsTree.lift: bail out if matrix is not invertible
5d6c831New abstract base class IntegerAction
5b14356Implement __pow__ in the coercion model

comment:37 Changed 3 years ago by jdemeyer

  • Dependencies set to #24450

comment:38 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-8.1 to sage-8.2
  • Status changed from needs_review to needs_work

comment:39 Changed 3 years ago by git

  • Commit changed from 5b1435647c0d84a2a086afaa82e6359e77838b89 to 186f2b88e64401027b9f347061afc0d8632ab345

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

56f2a64New abstract base class IntegerAction
186f2b8Implement __pow__ in the coercion model

comment:40 Changed 3 years ago by git

  • Commit changed from 186f2b88e64401027b9f347061afc0d8632ab345 to ec64a0e098309f31d6dc3e1181ccbc989ea6e1f4

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4443adfNew abstract base class IntegerAction
ec64a0eImplement __pow__ in the coercion model

comment:41 Changed 3 years ago by git

  • Commit changed from ec64a0e098309f31d6dc3e1181ccbc989ea6e1f4 to f2a59b900c81749b29c3eca97c88fead8aac98dc

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f2a59b9Implement __pow__ in the coercion model

comment:42 Changed 3 years ago by git

  • Commit changed from f2a59b900c81749b29c3eca97c88fead8aac98dc to 457bd56ec78916fb73c17baad7af93b59ab25b56

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

85cabe7Refactor IntegerMulAction
457bd56Implement __pow__ in the coercion model

comment:43 Changed 3 years ago by jdemeyer

  • Dependencies changed from #24450 to #24467

comment:44 Changed 3 years ago by git

  • Commit changed from 457bd56ec78916fb73c17baad7af93b59ab25b56 to c5b1be1372141cf3447ea4c28208b60aeaa3ae03

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c5b1be1Implement __pow__ in the coercion model

comment:45 Changed 3 years ago by jdemeyer

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

comment:46 Changed 3 years ago by git

  • Commit changed from c5b1be1372141cf3447ea4c28208b60aeaa3ae03 to 3a3bd034ff7236457414f11bfe33682fd0bb32ef

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a2d60efAlso verify IntegerAction instances
3a3bd03Implement __pow__ in the coercion model

comment:47 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:48 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:49 follow-ups: Changed 3 years ago by tscrim

I am not sure I agree with this change:

@@ -2015,8 +2003,8 @@ cdef class Integer(sage.structure.element.EuclideanDomainElement):
 
         TESTS::
 
-            sage: complex(0,1)^2
-            (-1+0j)
+            sage: complex(0,1) ^ 2
+            -1.0
             sage: R.<t> = QQ[]
             sage: 2^t
             Traceback (most recent call last):

In Python, we have

>>> complex(0,1)**2
(-1+0j)

and generally, I think x^2 should be the same as x * x. In this case, they are equal, but they are different types. While complex has all of the methods that float has, it is surprising to me that we do not get a complex result (in particular, since I thought it was suppose to be considered as an action). Also, can we add a test to check that complex(0,1) ^ int(2) is consistent?

For those Cython classes defining a cpdef _pow_int, do you need to declare that in the .pxd file since you are overwriting a cdef with a cpdef (see Integer and RealDoubleElement)? Or is the declaration in ModuleElement sufficient (but then why for its subclass RingElement)?

Have you looked at timings? I think this is almost certainly the way forward, but I am worried about how much of a speed regression this might have on taking integer exponentiation of, e.g., polynomials. (At least something I do in my research is combinatorial generating functions: sum(q^s(b) for b in B) for some set B and statistic s.)

comment:50 in reply to: ↑ 49 ; follow-up: Changed 3 years ago by jdemeyer

Replying to tscrim:

I am not sure I agree with this change:

@@ -2015,8 +2003,8 @@ cdef class Integer(sage.structure.element.EuclideanDomainElement):
 
         TESTS::
 
-            sage: complex(0,1)^2
-            (-1+0j)
+            sage: complex(0,1) ^ 2
+            -1.0
             sage: R.<t> = QQ[]
             sage: 2^t
             Traceback (most recent call last):

I thought that any operation between a Python type and a Sage parent should coerce everything to Sage. But it seems that this is not done consistently:

sage: parent(float(1) + 1)
<type 'float'>

For complex ^ ZZ, I think that CDF also makes sense as an answer: the Sage coercion model replaces complex by CDF and then does the powering CDF ^ ZZ. However, I understand why you would want it to return a complex. I'll think about this.

Also, can we add a test to check that complex(0,1) ^ int(2) is consistent?

What do you mean here? That wouldn't use any Sage code.

comment:51 in reply to: ↑ 49 ; follow-up: Changed 3 years ago by jdemeyer

Replying to tscrim:

For those Cython classes defining a cpdef _pow_int, do you need to declare that in the .pxd file since you are overwriting a cdef with a cpdef

If it inherits directly from Element (not ModuleElement or MonoidElement), then yes.

Or is the declaration in ModuleElement sufficient

I guess you mean MonoidElement or RingElement. But yes, that is sufficient.

comment:52 in reply to: ↑ 50 ; follow-up: Changed 3 years ago by tscrim

Replying to jdemeyer:

Replying to tscrim: I thought that any operation between a Python type and a Sage parent should coerce everything to Sage.

I wasn't aware that this was a policy, but I usually don't think too much about Python types.

But it seems that this is not done consistently:

sage: parent(float(1) + 1)
<type 'float'>

We probably haven't yet implemented the hooks for floats yet.

For complex ^ ZZ, I think that CDF also makes sense as an answer: the Sage coercion model replaces complex by CDF and then does the powering CDF ^ ZZ. However, I understand why you would want it to return a complex. I'll think about this.

CDF would be a good target. Whatever we decide, we should add the parent as part of the test.

Also, can we add a test to check that complex(0,1) ^ int(2) is consistent?

What do you mean here? That wouldn't use any Sage code.

Ah, right, the coercion model should not be called, and we run into similar sort of discrepancies when doing things like 1 / 2 in a .py file.

comment:53 in reply to: ↑ 51 ; follow-up: Changed 3 years ago by tscrim

Replying to jdemeyer:

Replying to tscrim:

For those Cython classes defining a cpdef _pow_int, do you need to declare that in the .pxd file since you are overwriting a cdef with a cpdef

If it inherits directly from Element (not ModuleElement or MonoidElement), then yes.

Then why do you add it for Expression?

Or is the declaration in ModuleElement sufficient

I guess you mean MonoidElement or RingElement. But yes, that is sufficient.

Whoops, yes I do.

comment:54 in reply to: ↑ 52 Changed 3 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Replying to tscrim:

I wasn't aware that this was a policy, but I usually don't think too much about Python types.

Now I don't think that there is such a policy either. I thought that was such a policy so I thought that CDF would be the correct parent for float ^ ZZ. But I can easily fix that to return a float instead, so let's do that.

comment:55 in reply to: ↑ 53 Changed 3 years ago by jdemeyer

Replying to tscrim:

Then why do you add it for Expression?

No particular reason. Maybe I needed to add it at some point during the development of this ticket. I'll remove it. The _pow_ needs to stay though since there is no default implementation.

comment:56 Changed 3 years ago by git

  • Commit changed from 3a3bd034ff7236457414f11bfe33682fd0bb32ef to 922717d473c74d5c2fee57ca481c575168ae0739

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

922717dFurther fixes for __pow__

comment:57 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:58 in reply to: ↑ 49 Changed 3 years ago by jdemeyer

Replying to tscrim:

In Python, we have

>>> complex(0,1)**2
(-1+0j)

In the latest commit, I fixed this: now a non-Element raised to a ZZ power will do the powering with an int exponent instead. For consistency, I did this for all base types, such that int(3) ^ (-3) now returns a float instead of a QQ element.

comment:59 Changed 3 years ago by jdemeyer

  • Status changed from needs_review to needs_work

The recent change seems to have introduced various doctest failures.

comment:60 Changed 3 years ago by git

  • Commit changed from 922717d473c74d5c2fee57ca481c575168ae0739 to 74d67006dfbf205f8bd43d25ef2b4eebf695ae66

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

74d6700Further fixes for __pow__

comment:61 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:62 in reply to: ↑ 49 Changed 3 years ago by jdemeyer

Replying to tscrim:

Have you looked at timings?

First of all, it is important to state that this ticket only changes powering for certain parents. It allows to implement powering using the coercion model, but many parents with a custom __pow__ still have that custom __pow__ after applying this ticket and won't use the coercion model. This is case for polynomials for example. So we only look at a few parents where the powering actually uses the new code.

Now the timings. The conclusion seems to be that powering for equal parents is slightly faster than before but that powering with non-equal parents is slower than before. This is because the latter goes through the coercion model now.

ZZZZ

Before:

sage: a = ZZ(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 122 ns per loop

After:

sage: a = ZZ(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 110 ns per loop

GF(2n)ZZ

Before:

sage: k.<a> = GF(4, impl="ntl"); n = 2; timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 377 ns per loop

After:

sage: k.<a> = GF(4, impl="ntl"); n = 2; timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 607 ns per loop

RDFRDF

Before:

sage: a = RDF(2); n = RDF(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 139 ns per loop

After:

sage: a = RDF(2); n = RDF(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 132 ns per loop

RDFZZ

Before:

sage: a = RDF(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 156 ns per loop

After:

sage: a = RDF(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 240 ns per loop

idealZZ

Before:

sage: a = ZZ.ideal(2); n = ZZ(2); timeit('a ^ n', number=10000, repeat=20)
10000 loops, best of 20: 13.2 µs per loop

After:

sage: a = ZZ.ideal(2); n = ZZ(2); timeit('a ^ n', number=10000, repeat=20)
10000 loops, best of 20: 14.6 µs per loop

comment:63 Changed 3 years ago by jdemeyer

Part of the slowdown is caused by Action.__call__ (see #24500). After optimizing that a bit, I go from

sage: k.<a> = GF(4, impl="ntl"); n = 2; timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 607 ns per loop

to

sage: k.<a> = GF(4, impl="ntl"); n = 2; timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 506 ns per loop

and from

sage: a = RDF(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 240 ns per loop

to

sage: a = RDF(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20)
100000 loops, best of 20: 182 ns per loop

comment:64 Changed 3 years ago by jdemeyer

Travis, please let me know what you think of the timings and whether #24500 should be a dependency of this ticket. Personally, I think that #24500 will be non-trivial, so I would rather not make it a dependency.

comment:65 follow-up: Changed 3 years ago by vdelecroix

I like very much the idea of moving powering inside the coercion model. Though, it is not a binary operator X x X -> X (do you have any example of this beyond NN or RR_+?). I still don't understand why you would need

Apart from this, powering behaves like other binary operators:
coercion to a common parent is done if no action is defined. 

comment:66 in reply to: ↑ 65 Changed 3 years ago by jdemeyer

Replying to vdelecroix:

I like very much the idea of moving powering inside the coercion model. Though, it is not a binary operator X x X -> X (do you have any example of this beyond NN or RR_+?). I still don't understand why you would need

Apart from this, powering behaves like other binary operators:
coercion to a common parent is done if no action is defined. 

Copying from 34:

I think that coercing to a common parent does make sense because:

  1. It is consistent with all other operators. Often multiplication is treated as an action too. Still, when no action is found, coercion to a common parent is done.
  1. There are several parents where a common parent for powering makes sense, in particular the various incarnations of real/complex numbers and the symbolic ring.
  1. If coercion to a common parent shouldn't be done, then what should be done by default if no action is found?

comment:67 follow-up: Changed 3 years ago by tscrim

Thank for the timings and explanation. I am the most concerned with the GF(2n)ZZ timings being ~2x slower as I would expect exponentiation to be a fairly common operation. For me personally, it is not important, but I know for the number theorist using Sage, it could have a much bigger impact. However, you know that area of math/Sage better than I, so if you think it will be okay, then no objection from me.

comment:68 in reply to: ↑ 67 Changed 3 years ago by jdemeyer

Replying to tscrim:

Thank for the timings and explanation. I am the most concerned with the GF(2n)ZZ timings being ~2x slower

It's actually only a factor 1.61 slower but that will improve significantly after #24500. Possibly, other optimizations in the coercion model are possible.

It is also important to note that I intentionally took the worst case of GF(4) implemented using NTL. The default implementation for that field size is Givaro, which is not affected by this ticket. Only for GF(2^16) and larger is NTL the default and then the cost of the coercion becomes a much smaller fraction of the actual computation.

comment:69 Changed 3 years ago by tscrim

Okay, then positive review from me.

Does anyone else have any other objections or questions?

comment:70 Changed 3 years ago by vdelecroix

fine for me

comment:71 Changed 3 years ago by jdemeyer

  • Reviewers set to Travis Scrimshaw, Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:72 Changed 3 years ago by vbraun

  • Branch changed from u/jdemeyer/implement___pow___in_the_coercion_model to 74d67006dfbf205f8bd43d25ef2b4eebf695ae66
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.