[Python-Dev] negative modular exponentiation

Tim Peters tim.one at comcast.net
Tue May 4 13:31:20 EDT 2004


[Armin Rigo]
> SF patch 936813 (fast modular exponentiation) introduces some
> optimization of exponentiation with longs, including a new feature:
> in a pow(x,y,z), the exponent y is allowed to be negative when it
> makes mathematical sense.  The result of (x ** -y) % z is a number that
> is the inverse of (x ** y) % z, i.e. multiplying the two gives 1
> modulo z.

...

> As this is a new feature it should be approved of.

It's fine by me, and new features are finer by me than adding ever more
obscure optimizations in longobject.c.  The Python long implementation has a
great track record wrt portability and lack of bugs, and gonzo optimizations
work against that.  For example, did Python really need the Karatsuba
multiplication gimmick?  I added the patch for it after a lot of reworking,
but overall I'm not sure it was a net win; and the current patch in question
boosts the smallest integer at which Karatsuba triggers to such a large
value that anyone reaching it would probably be much better off using a GMP
wrapper anyway.

> If it is, I'd volunteer to review the patch

One thing I noticed a few times in the patch was neglecting to check C calls
for error returns.  Even _PyLong_NumBits() can fail!

> and make the necessary extension to the plain integer's pow() so that
> they work the same way.
>
> E.g.
>
> >>> pow(2,-1,9)
> 5
>
> because (5*2)%9 == 1.  Currently this gives a TypeError (why not a
> ValueError?) so changing the behaviour seems safe.

ValueError would make more sense to me too.  I expect it was TypeError for
compatibility with older exceptions raised by the float version.




More information about the Python-Dev mailing list