[Python-checkins] python/dist/src/Include longintrepr.h,2.14,2.15

[tim_one at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Include
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv18253/Include

Modified Files:
	longintrepr.h 
Log Message:
SF patch 936813: fast modular exponentiation

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

x_mul()
  - sped a little by optimizing the C
  - sped a lot (~2X) if it's doing a square; note that long_pow() squares
    often
k_mul()
  - more cache-friendly now if it's doing a square
KARATSUBA_CUTOFF
  - boosted; gradeschool mult is quicker now, and it may have been too low
    for many platforms anyway
KARATSUBA_SQUARE_CUTOFF
  - new
  - since x_mul is a lot faster at squaring now, the point at which
    Karatsuba pays for squaring is much higher than for general mult


Index: longintrepr.h
===================================================================
RCS file: /cvsroot/python/python/dist/src/Include/longintrepr.h,v
retrieving revision 2.14
retrieving revision 2.15
diff -u -d -r2.14 -r2.15
--- longintrepr.h	12 Aug 2002 07:21:57 -0000	2.14
+++ longintrepr.h	29 Aug 2004 22:16:48 -0000	2.15
@@ -12,7 +12,7 @@
    contains at least 16 bits, but it's made changeable anyway.
    Note: 'digit' should be able to hold 2*MASK+1, and 'twodigits'
    should be able to hold the intermediate results in 'mul'
-   (at most MASK << SHIFT).
+   (at most (BASE-1)*(2*BASE+1) == MASK*(2*MASK+3)).
    Also, x_sub assumes that 'digit' is an unsigned type, and overflow
    is handled by taking the result mod 2**N for some N > SHIFT.
    And, at some places it is assumed that MASK fits in an int, as well. */