Implement pow in the coercion model #24247

jdemeyer · 2017-11-20T09:42:56Z

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

Depends on #24467

Component: coercion

Author: Jeroen Demeyer

Branch/Commit: 74d6700

Reviewer: Travis Scrimshaw, Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/24247

The text was updated successfully, but these errors were encountered:

jdemeyer · 2017-11-20T12:19:48Z

Changed dependencies from #24244 to #24248

jdemeyer · 2017-11-20T16:21:43Z

Branch: u/jdemeyer/implement___pow___in_the_coercion_model

sagetrac-git · 2017-11-20T16:26:47Z

Commit: a18280f

sagetrac-git · 2017-11-20T16:26:47Z

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

`9ad8983`	`Fake Integer interface`
`04235be`	`New functions integer_check_long() and integer_check_long_py()`
`ad34554`	`Fix isinstance(x, int) calls in element.pyx`
`a18280f`	Implement `__pow__` in the coercion model

sagetrac-git · 2017-11-20T18:13:10Z

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

`bb114c9`	`Fake Integer interface`
`4d76bc1`	`New functions integer_check_long() and integer_check_long_py()`
`9c579c7`	`Fix isinstance(x, int) calls in element.pyx`
`8b194fb`	Implement `__pow__` in the coercion model

sagetrac-git · 2017-11-20T18:13:10Z

Changed commit from a18280f to 8b194fb

sagetrac-git · 2017-11-21T13:17:28Z

Changed commit from 8b194fb to 54eb896

sagetrac-git · 2017-11-21T13:17:28Z

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

`54eb896`	Implement `__pow__` in the coercion model

jdemeyer · 2017-11-21T13:20:07Z

Changed dependencies from #24248 to #24248, #24259

sagetrac-git · 2017-11-21T14:17:00Z

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

`5e03135`	Implement `__pow__` in the coercion model

sagetrac-git · 2017-11-21T14:17:00Z

Changed commit from 54eb896 to 5e03135

jdemeyer · 2017-11-21T14:42:05Z

Changed dependencies from #24248, #24259 to #24248, #24259, #24260

sagetrac-git · 2017-11-21T17:38:02Z

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

`88eaed5`	`Declare Integer.value as array`
`5c1f43f`	`Deprecate str ^ Integer`
`70592a8`	`Fix compiler warning`
`d3db645`	`Merge commit '88eaed585d8159a4a0763e56caaf3a767d4cb2f0'; commit '5c1f43f861165ff975616f60cab37c92d36d10f6'; commit '70592a850d7677928592c022760d6183bd81364f' into t/24247/implement___pow___in_the_coercion_model`
`0d3aa63`	Implement `__pow__` in the coercion model

sagetrac-git · 2017-11-21T17:38:02Z

Changed commit from 5e03135 to 0d3aa63

sagetrac-git · 2017-11-24T15:00:57Z

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

`09afe6d`	Implement `__pow__` in the coercion model

sagetrac-git · 2017-11-24T15:00:57Z

Changed commit from 0d3aa63 to 09afe6d

jdemeyer · 2017-11-24T15:16:20Z

Changed dependencies from #24248, #24259, #24260 to #24248, #24259, #24260, #24275, #24276

sagetrac-git · 2017-12-05T09:18:45Z

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

`cabd346`	`Merge tag '8.1.rc4' into t/24247/implement___pow___in_the_coercion_model`
`b0b4070`	`Various fixes`

sagetrac-git · 2017-12-05T09:18:45Z

Changed commit from 09afe6d to b0b4070

jdemeyer · 2017-12-05T09:32:11Z

Changed dependencies from #24248, #24259, #24260, #24275, #24276 to #24248, #24259, #24260, #24275, #24276, #24328

sagetrac-git · 2017-12-05T10:07:51Z

Changed commit from b0b4070 to f6d7ba2

sagetrac-git · 2017-12-05T10:07:51Z

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

`c0aca1c`	`New module to implement generic_power`
`bcb70b3`	`Merge commit '70592a850d7677928592c022760d6183bd81364f'; commit '88eaed585d8159a4a0763e56caaf3a767d4cb2f0'; commit '5c1f43f861165ff975616f60cab37c92d36d10f6'; commit 'c0aca1c0ac92b95d790f39369a683269efbde530' into t/24247/implement___pow___in_the_coercion_model`
`f6d7ba2`	Implement `__pow__` in the coercion model

jdemeyer · 2017-12-06T14:14:53Z

Changed dependencies from #24248, #24259, #24260, #24275, #24276, #24328 to #24328, #24259, #24260, #24275, #24276

jdemeyer · 2018-01-09T14:43:31Z

comment:62

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.

ZZ^ZZ

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(2ⁿ)^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

RDF^RDF

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

RDF^ZZ

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

ideal^ZZ

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

jdemeyer · 2018-01-09T14:55:09Z

comment:63

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

jdemeyer · 2018-01-09T15:36:57Z

comment:64

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.

videlec · 2018-01-09T16:15:17Z

comment:65

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.

jdemeyer · 2018-01-09T18:55:19Z

comment:66

Replying to @videlec:

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 [comment:34]:

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

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.
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.
If coercion to a common parent shouldn't be done, then what should be done by default if no action is found?

tscrim · 2018-01-09T20:57:43Z

comment:67

Thank for the timings and explanation. I am the most concerned with the GF(2ⁿ)^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.

jdemeyer · 2018-01-10T08:48:15Z

comment:68

Replying to @tscrim:

Thank for the timings and explanation. I am the most concerned with the GF(2ⁿ)^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.

tscrim · 2018-01-10T16:55:44Z

comment:69

Okay, then positive review from me.

Does anyone else have any other objections or questions?

videlec · 2018-01-11T08:03:08Z

comment:70

fine for me

jdemeyer · 2018-01-11T14:52:03Z

Reviewer: Travis Scrimshaw, Vincent Delecroix

vbraun · 2018-01-15T22:29:32Z

Changed branch from u/jdemeyer/implement___pow___in_the_coercion_model to 74d6700

…s Integer The `absolute_discriminant()` of any number field should be a Sage `Integer`. This is currently not properly doctested, leading to a subtle failure in sagemath#24247. URL: https://trac.sagemath.org/24462 Reported by: jdemeyer Ticket author(s): Frédéric Chapoton Reviewer(s): Travis Scrimshaw

jdemeyer added this to the sage-8.1 milestone Nov 20, 2017

jdemeyer added c: coercion labels Nov 20, 2017

This comment has been minimized.

Sign in to view

jdemeyer added the s: needs review label Jan 9, 2018

jdemeyer added s: positive review and removed s: needs review labels Jan 11, 2018

vbraun removed the s: positive review label Jan 15, 2018

vbraun closed this as completed in 05825d6 Jan 15, 2018

kcrisman mentioned this issue Jun 7, 2021

Fix ComplexNumber.__pow__ to allow float^complex #11323

Closed

wluebbe mannequin mentioned this issue Aug 31, 2020

Python 3 preparation: integer types #16072

Closed

videlec mentioned this issue Dec 29, 2022

Powering in RLF and CLF broken #24492

Open

This was referenced Nov 29, 2018

Implement actions using _act_ instead of _call_ #24500

Closed

Use new powering functions in integer_mod.pyx #24750

Open

Shay2Shay mentioned this issue Aug 28, 2024

Raising integers to finite-field elements coerces the base into the field #32287

Open

kwankyu mentioned this issue Sep 4, 2024

Give deprecation warning when raising negative AlgebraicReal to fractional odd power #38362

Closed

5 tasks

Implement __pow__ in the coercion model #24247

Implement __pow__ in the coercion model #24247

Comments

jdemeyer commented Nov 20, 2017

This comment has been minimized.

This comment has been minimized.

jdemeyer commented Nov 20, 2017

jdemeyer commented Nov 20, 2017

sagetrac-git mannequin commented Nov 20, 2017

sagetrac-git mannequin commented Nov 20, 2017

sagetrac-git mannequin commented Nov 20, 2017

sagetrac-git mannequin commented Nov 20, 2017

sagetrac-git mannequin commented Nov 21, 2017

sagetrac-git mannequin commented Nov 21, 2017

jdemeyer commented Nov 21, 2017

sagetrac-git mannequin commented Nov 21, 2017

sagetrac-git mannequin commented Nov 21, 2017

jdemeyer commented Nov 21, 2017

sagetrac-git mannequin commented Nov 21, 2017

sagetrac-git mannequin commented Nov 21, 2017

This comment has been minimized.

sagetrac-git mannequin commented Nov 24, 2017

sagetrac-git mannequin commented Nov 24, 2017

jdemeyer commented Nov 24, 2017

sagetrac-git mannequin commented Dec 5, 2017

sagetrac-git mannequin commented Dec 5, 2017

jdemeyer commented Dec 5, 2017

sagetrac-git mannequin commented Dec 5, 2017

sagetrac-git mannequin commented Dec 5, 2017

jdemeyer commented Dec 6, 2017

jdemeyer commented Jan 9, 2018

jdemeyer commented Jan 9, 2018

jdemeyer commented Jan 9, 2018

videlec commented Jan 9, 2018

jdemeyer commented Jan 9, 2018

tscrim commented Jan 9, 2018

jdemeyer commented Jan 10, 2018

tscrim commented Jan 10, 2018

videlec commented Jan 11, 2018

jdemeyer commented Jan 11, 2018

vbraun commented Jan 15, 2018

Implement pow in the coercion model #24247

Implement pow in the coercion model #24247