|
From: Peter S. <ps...@gm...> - 2008-08-04 13:56:05
|
Hello
I was looking at powering algorithms and found a couple that only work for
fixed bases but could be quicker as they use precomputed numbers.
The first is in "Crandall and Pomerance: Prime Numbers a Computational
Perspective". The psudo-code is:
Computes x^y
y is written in base B as y_0 y_1 .... y_(D-1) with y_(D-1)>0 the high
digit.
We assume that (B-1)*(D-1) numbers have been precalculated:
x^(i*(B^j)) (x to the power of (i times (B to the power of j)) for i=1
to B-1, j=1 to D-1
Initialize:
z=1;
Loop:
for (0<=j<D){
z=z*x^(y_j*(B^j))
}
return z;
The other algorithm can be found near the bottom of page 15 on:
www.daimi.au.dk/~ivan/FastExpproject.pdf
According to the author the fixed base algorithm is 3 times faster then the
general purpose one. Not much of an improvement but in the conclusion the
author says he/she was using a programing language that was really slow at
accessing arrays so we may be able to get more out of it
Peter
|