summaryrefslogtreecommitdiffstats
path: root/Include
diff options
context:
space:
mode:
authorTim Peters <tim.peters@gmail.com>2004-08-29 22:16:50 (GMT)
committerTim Peters <tim.peters@gmail.com>2004-08-29 22:16:50 (GMT)
commit0973b99e1cfe13b3d197e1b6c449a2d75b55d17a (patch)
tree56d50378b5dd36f12a23149c54554f07bc5784f7 /Include
parentafb5f9421719e7c7ada1a236bb226c9f84eaf880 (diff)
downloadcpython-0973b99e1cfe13b3d197e1b6c449a2d75b55d17a.zip
cpython-0973b99e1cfe13b3d197e1b6c449a2d75b55d17a.tar.gz
cpython-0973b99e1cfe13b3d197e1b6c449a2d75b55d17a.tar.bz2
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
Diffstat (limited to 'Include')
-rw-r--r--Include/longintrepr.h2
1 files changed, 1 insertions, 1 deletions
diff --git a/Include/longintrepr.h b/Include/longintrepr.h
index 5755adb..9ed1fe7 100644
--- a/Include/longintrepr.h
+++ b/Include/longintrepr.h
@@ -12,7 +12,7 @@ extern "C" {
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. */