[flint-devel] Fixed base exponention

[Peter S. <ps...@gm...>]

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