SF patch 936813: fast modular exponentiation

This checkin is adapted from part 2 (of 3) of Trevor Perrin's patch set.

BACKWARD INCOMPATIBILITY:  SHIFT must now be divisible by 5.  AFAIK,
nobody will care.  long_pow() could be complicated to worm around that,
if necessary.

long_pow():
  - BUGFIX:  This leaked the base and power when the power was negative
    (and so the computation delegated to float pow).
  - Instead of doing right-to-left exponentiation, do left-to-right.  This
    is more efficient for small bases, which is the common case.
  - In addition, if the exponent is large (more than FIVEARY_CUTOFF
    digits), precompute [a**i % c for i in range(32)], and go left to
    right 5 bits at a time.
l_divmod():
  - The signature changed so that callers who don't want the quotient,
    or don't want the remainder, can pass NULL in the slot they don't
    want.  This saves them from having to declare a vrbl for unwanted
    stuff, and remembering to decref it.
long_mod(), long_div(), long_classic_div():
  - Adjust to new l_divmod() signature, and simplified as a result.

1 files changed, 13 insertions, 1 deletions

diff --git a/Misc/NEWS b/Misc/NEWS
index 431b343..660c49f 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -20,7 +20,11 @@ Core and builtins
   to compute 17**1000000 dropped from about 14 seconds to 9 on my box due
   to this much.  The cutoff for Karatsuba multiplication was raised,
   since gradeschool multiplication got quicker, and the cutoff was
-  aggressively small regardless.
+  aggressively small regardless.  The exponentiation algorithm was switched
+  from right-to-left to left-to-right, which is more efficient for small
+  bases.  In addition, if the exponent is large, the algorithm now does
+  5 bits (instead of 1 bit) at a time.  That cut the time to compute
+  17**1000000 on my box in half again, down to about 4.5 seconds.
 
 - OverflowWarning is no longer generated.  PEP 237 scheduled this to
   occur in Python 2.3, but since OverflowWarning was disabled by default,
@@ -156,6 +160,14 @@ Tools/Demos
 Build
 -----
 
+- Backward incompatibility:  longintrepr.h now triggers a compile-time
+  error if SHIFT (the number of bits in a Python long "digit") isn't
+  divisible by 5.  This new requirement allows simple code for the new
+  5-bits-at-a-time long_pow() implementation.  If necessary, the
+  restriction could be removed (by complicating long_pow(), or by
+  falling back to the 1-bit-at-a-time algorithm), but there are no
+  plans to do so.
+
 - bug #991962: When building with --disable-toolbox-glue on Darwin no
   attempt to build Mac-specific modules occurs.