pow(a,b,c) should accept b<0

[50eff062-408a-4098-b1b2-8222303b9d0c]

BPO	457066
Nosy	@gvanrossum, @tim-one

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = 'https://github.com/gvanrossum' closed_at = created_at = labels = ['type-feature', 'library'] title = 'pow(a,b,c) should accept b<0' updated_at = user = 'https://bugs.python.org/anonymous' ``` bugs.python.org fields: ```python activity = actor = 'thomasahle' assignee = 'gvanrossum' closed = True closed_date = None closer = None components = ['Library (Lib)'] creation = creator = 'anonymous' dependencies = [] files = [] hgrepos = [] issue_num = 457066 keywords = [] message_count = 17.0 messages = ['6266', '6267', '6268', '6269', '6270', '6271', '6272', '6273', '6274', '6275', '6276', '6277', '6278', '6279', '6280', '6281', '151764'] nosy_count = 5.0 nosy_names = ['gvanrossum', 'tim.peters', 'nobody', 'phr', 'thomasahle'] pr_nums = [] priority = 'normal' resolution = 'rejected' stage = None status = 'closed' superseder = None type = 'enhancement' url = 'https://bugs.python.org/issue457066' versions = [] ```

[3772858d-27d8-44b0-a664-d68674859f36]

You should be able to raise integers to negative powers mod n. If b\<0, pow(a,b,c)==pow(pow(a,-1,c),-b,c) where pow(a,-1,c) is a's multiplicative inverse mod c, computed with the extended Euclid algorithm. This would be in Python's spirit of math completeness and would save people from the trouble of having to figure out the algorithm over and over.

I can come up with a patch for this if it's agreed on as desirable.

[gvanrossum]

Logged In: YES user_id=6380

Hm.

In 2.2a2, currently, pow(a, b, c) for ints a, b, c where b \< 0 is defined as pow(float(a), float(b), float(c)), IOW (1.0/(a**b))%c. This doesn't make a lot of sense for the three-argument version though, because the result tends to be between 0.0 and 1.0... But it is consistent with the (future) rule that operations on integers and floats should give results with the same value only a different type.

Assigning to Tim, whose mathematical sensibilities are more refined than mine...

[gvanrossum]

Logged In: YES user_id=6380

Of course I meant (1.0/(a**-b))%c. Sorry!

[tim-one]

Logged In: YES user_id=31435

The desire is understandable but this isn't the right way to do it, so I'm rejecting this. While 2.2a2 changed the specifics, the general rule remains that

pow(a, b, c) == a**b % c

except that the LHS may be very much faster for large integer arguments.

"The right way" to do modular arithmetic is to define a class for it, and do the full job (+ - * /, not just modular pow). egcd is easy to code in Python, and because it's an obscure speciality need (it gets asked about maybe twice per year on c.l.py) doesn't really belong in the core even if it weren't. I'm not even sure how 3-argument pow got in, but am grateful it did and don't want to press our luck \<wink>.

[3772858d-27d8-44b0-a664-d68674859f36]

Logged In: NO

Making a 3-arg integer pow return a tiny floating point number seems weird to me. I don't see any situation where I'd want that. If I call pow with b\<0 without expecting it to use the egcd to get the integer answer mod c, I've almost certainly made a mistake. So my first preference is still egcd, but second preference is to stay with the old behavior of throwing an exception rather than have my integer calculation suddenly turn into a floating point calculation without my realizing it.

I'm also enthused about changing / to turn 2/3 into a float, but at least I understand the argument that 2/3=0 confuses newbies. But newbies won't be using 3-arg pow(), so we needn't worry about confusing them. IMHO anyone using 3-arg pow on integers will expect an integer result.

By the way (off topic), 3-arg pow with \~150 decimal digits is about 5x slower in Python than in carefully optimized asm on an x86, which is pretty good. But on a StrongARM it appears to be about 30x slower :-(. This can't really be fixed without adding a lot more code. Sigh.

[91e69f45-91d9-4b12-87db-a02908296c81]

Logged In: YES user_id=72053

Argh. I meant to say I'm NOT enthused about changing /. This item is jinxed :-).

[gvanrossum]

Logged In: YES user_id=6380

Hm. There's something to say for making 3-arg pow() only work for ints (and longs), and then the egcd would make sense. But that would mean removing the 3-arg pow() for floats. Why would anyone use 3-arg pow() with floats? I don't know, but that doesn't mean it doesn't happen. *If* there are no community objections against making 3-arg pow() raise a TypeError on float or complex arguments, I'm OK with the egcd interpretation. But this is PEP material -- that's the only way to find out. phr, would you mind writing a PEP? It can be short and sweet.

[tim-one]

Logged In: YES user_id=31435

Changed Resolution to None since this was opened again.

I still don't like this. It's a wart no matter how you cut it: implement the egcd meaning, and it's still a wart, because the "multiplicative inverse" meaning doesn't always make sense. For example, pow(4, -1, 6) -- 4 has no multiplicative inverse mod 6. The best it can return is 2, i.e. the best pow(i, -1, k) can return is an integer x s.t. i*x is congruent to gcd(i, k) mod k. But Python provides no way to get the gcd, so there's no way (short of computing gcd separately) to know what the result of pow (i, -1, k) really means (and it doesn't mean "inverse" unless the gcd is 1; OTOH, raise an exception if the gcd isn't one, and then you've artificially ruled out legitimate uses of egcd apparently not related to Paul's particular interest today).

The natural way to spell egcd as a library routine would return the gcd too; e.g.,

def egcd(aorig, borig):
.    """Return (g, i) s.t. g=gcd(aorig, borig) and i*aorig 
% borig = g."""
.    a, b = aorig, borig
.    a1, a2 = 1, 0
.    while b:
.        q, r = divmod(a, b)
.        a1, a2 = a2, a1-q*a2
.        a, b = b, r
.    if __debug__:
.        b1, r = divmod(a - a1*aorig, borig)
.        assert r == 0
.        assert a1*aorig + b1*borig == a
.    return a, a1

[gvanrossum]

Logged In: YES user_id=6380

The resolution remains Rejected -- apparently selecting "None" signals a "no change" to SF. :-(

I don't like it either -- my suggestion to write a PEP was a passive-aggressive way to reject the proposal. :-)

Still, it's unclear whether 3-arg pow() makes any sense at all for floats. Maybe that *should* be rejected. And then we could reject 3-arg() pow with negative second arg as well.

[91e69f45-91d9-4b12-87db-a02908296c81]

Logged In: YES user_id=72053

If b\<0 uses egcd, then pow(4,-1,6) should definitely throw a value error, like dividing by 0. Pow isn't advertised as computing gcd's. It just happens that egcd is a way of computing inverses mod n.

I'm fine with 3-arg pow throwing an error on non-integer args. I like that better than unexpected conversions.

How about continuing to throw an error on b\<0, but adding an egcd function to the math library?

What got me started on this was wanting a modular inverse, not remembering how egcd worked and having to figure it out again, and realizing I've been thru that same exercise many times over the years :-).

[tim-one]

Logged In: YES user_id=31435

Well, speaking as an old fp number-cruncher, mod makes little sense for floats on its own, and even less so combining it with pow (math.fmod makes sense for floats, but that's a different operation than the builtin float %). As a practical matter, x%1.0 is sometimes used to get at the fractional bits of a float x >= 0, but I haven't seen that combined with pow (in practice -- "in theory" pow (theta, n, 1.0) has interesting properties for irrational theta, but fp arithmetic isn't precise enough to exploit them).

OTOH, I can't doubt that some existing code uses integers that just happen to be in fp format, and then e.g. pow(3., 4., 7.) makes as much sense as pow(3, 4, 7). If you want a model where it's a number's value that matters-- not especially its type --that's worth preserving. But then "something should be done about" stuff like this:

>>> pow(3., 500., 7.)
4.0
>>> pow(3, 500, 7)
2
>>>

So, as currently implemented, floats in 3-arg pow are surprising even when they denote whole integers.

3-arg pow makes clear sense for ints and longs when the power is non-negative, and compelling sense for "go fast" reasons, so I'd like to see it restricted to that. We already complain about 3-arg pow with a complex argument.
I haven't found any actual examples of 3-arg float pow on the web ... but who knows? Let's break it in 2.a3 and see whether anyone screams? I can ask on c.l.py too.

[gvanrossum]

Logged In: YES user_id=6380

OK. Sounds like a good plan: break 3-arg pow() for all float args in 2.2a3, and see in anybody screams. I predict dead silence.

[91e69f45-91d9-4b12-87db-a02908296c81]

Logged In: YES user_id=72053

Sounds good to me re breaking float pow. It's doing something really weird in 2.2.1 anyway. pow(3.,500.,7.) returns 2, pow(3,5000,7) returns 2, pow(3.,5000.,7.) returns 4.0, but 3.**5000. returns inf. pow(3.,50000.,7.) returns NaN.

The roundoff errors though don't bother me especially more than any other float roundoff errors, e.g. 3.**99+1-3.**99 = 0.

[gvanrossum]

Logged In: YES user_id=6380

Can we close this now that it's been rejected and we've made pow(a,b,c) illegal for float args?

[tim-one]

Logged In: YES user_id=31435

That's up to you -- I closed it before, and you opened it again. Since I'm not clear on why it was reopened, assigning back to you. Disallowing 3-arg pow for floats didn't preclude the possibility of giving 3-arg integer pow with negative 2nd arg a "modular inverse" meaning (which is the substance of the feature request, not float behavior), and I've got nothing new to say about that.

[gvanrossum]

Logged In: YES user_id=6380

I reopened it because there was a different action item then (forbid triple-float-arg pow()). Since that has been taken care of now, I'm closing it again.

[aba6650f-6d95-4e8a-9135-c1a742b98fb7]

For anyone who finds this through google, if you are finding the inverse mod a prime, you can use fermats little theorem: pow(a, -1, mod) = pow(a, a-2, mod). (You also need that mod doesn't divide a).