Update of /cvsroot/python/python/dist/src/Misc In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv27357/Misc Modified Files: NEWS Log Message: 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. Index: NEWS =================================================================== RCS file: /cvsroot/python/python/dist/src/Misc/NEWS,v retrieving revision 1.1119 retrieving revision 1.1120 diff -u -d -r1.1119 -r1.1120 --- NEWS 29 Aug 2004 22:16:49 -0000 1.1119 +++ NEWS 30 Aug 2004 02:44:37 -0000 1.1120 @@ -20,7 +20,11 @@ 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 @@ 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.