** Next:** An introduction to the ALDOR
**Up:** What are our requirements for
** Previous:** Post-facto extensions

In any MONOID exponentiation can de defined by the binary powering
algorithm
(^)(x: %, n: NonNegativeInteger): % ==
(n < 0) =>
error "power: negative exponent";
n = 0 => 1;
n = 1 => x;
n = 2 => x*x;
-- General code.
i: SingleInteger := 0;
l: SingleInteger := length n;
u: % := 1;
repeat {
if bit(n, i) then u := u * x;
if i >= l then break;
x := x * x;
i := i + 1;
}
u
}

Assume that in the interface MONOID the exponentiation
has been defined as above.
In the MONOID
/*p* (where *p* is a prime)
we can do better because of little Fermat theorem
which states that for *x* 0 we have
*x*^{p-1} = 1.
Hence we need to overwrite the above definition
for
/*p* by something like
(^)(x: %, n: NonNegativeInteger): % == {
n := positiveRemainder(n,p);
zero? n => 1;
one? x => x;
local acc: %;
if odd? n then acc := x else acc := 1;
repeat {
n := shift(n,-1);
zero? n => return acc;
x := (x * x) mod p;
if odd? n then acc := (acc * x) mod p;
}
}

This will be made possible by __INHERITANCE.__
In a polynomial ring *R*[*x*] one can do better too in some
special cases depending on the coefficient ring, as we have seen before.
This will be made possible by __CONDITIONAL__ __IMPLEMENTATION.__
We will see later how these conditional statements combined
with __POST-FACTO__ __EXTENSIONS__ can be used for
optimizing the source code.

** Next:** An introduction to the ALDOR
**Up:** What are our requirements for
** Previous:** Post-facto extensions
*Marc Moreno Maza *

2003-06-06