[Python-bugs-list] [ python-Bugs-457066 ] pow(a,b,c) should accept b<0

noreply@sourceforge.net noreply@sourceforge.net
Fri, 31 Aug 2001 23:34:42 -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: Closed
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: 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