[Python-bugs-list] [ python-Bugs-457066 ] pow(a,b,c) should accept b<0
noreply@sourceforge.net
noreply@sourceforge.net
Sat, 01 Sep 2001 14:20:01 -0700
Bugs item #457066, was opened at 2001-08-30 18:17
You can respond by visiting:
http://sourceforge.net/tracker/?func=detail&atid=105470&aid=457066&group_id=5470
Category: Python Library
Group: Feature Request
Status: Open
Resolution: Rejected
Priority: 5
Submitted By: Nobody/Anonymous (nobody)
Assigned to: Tim Peters (tim_one)
Summary: pow(a,b,c) should accept b<0
Initial Comment:
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.
----------------------------------------------------------------------
>Comment By: Tim Peters (tim_one)
Date: 2001-09-01 14:20
Message:
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.
----------------------------------------------------------------------
Comment By: paul rubin (phr)
Date: 2001-09-01 14:05
Message:
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 :-).
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2001-09-01 13:12
Message:
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.
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2001-09-01 13:04
Message:
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
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2001-09-01 11:19
Message:
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.
----------------------------------------------------------------------
Comment By: paul rubin (phr)
Date: 2001-08-31 23:38
Message:
Logged In: YES
user_id=72053
Argh. I meant to say I'm NOT enthused about changing /.
This item is jinxed :-).
----------------------------------------------------------------------
Comment By: Nobody/Anonymous (nobody)
Date: 2001-08-31 23:34
Message:
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.
----------------------------------------------------------------------
Comment By: Tim Peters (tim_one)
Date: 2001-08-30 22:23
Message:
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>.
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2001-08-30 18:49
Message:
Logged In: YES
user_id=6380
Of course I meant (1.0/(a**-b))%c. Sorry!
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2001-08-30 18:46
Message:
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...
----------------------------------------------------------------------
You can respond by visiting:
http://sourceforge.net/tracker/?func=detail&atid=105470&aid=457066&group_id=5470