]> granicus.if.org Git - python/commit
SF patch 936813: fast modular exponentiation
authorTim Peters <tim.peters@gmail.com>
Mon, 30 Aug 2004 02:44:38 +0000 (02:44 +0000)
committerTim Peters <tim.peters@gmail.com>
Mon, 30 Aug 2004 02:44:38 +0000 (02:44 +0000)
commit47e52ee0c5c8868db903d476b49c3368fce4d79a
treefed354561308995cb0f8090e201d5138e17ddce8
parent48bd7f3a71c05dafec820dbbf76e611add7a9849
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.
Include/longintrepr.h
Misc/NEWS
Objects/longobject.c