Function EXPT-MOD


expt-mod n exponent divisor => result

Arguments and Values:

n---a number.

exponent---a number.

divisor---a number.

result---a number.


expt-mod returns n raised to the exponent power, modulo divisor. (expt-mod n exponent divisor) is equivalent to (mod (expt n exponent) divisor).

Exceptional situations:

The exceptional situations are the same as those for (mod (expt n exponent) divisor).


One might wonder why we shouldn't simply write (mod (expt n exponent) divisor). This function exists because the naïve way of evaluating (mod (expt n exponent) divisor) produces a gigantic intermediate result, which kills performance in applications which use this operation heavily. The operation can be done much more efficiently. Usually the compiler does this optimization automatically, producing very fast code. However, we can't depend on this behavior if we want to produce code that is guaranteed not to perform abysmally on some Lisp implementations.

Therefore cl-utilities provides a standard interface to this composite operation which uses mediocre code by default. Specific implementations can usually do much better, but some do much worse. We can get the best of both by simply using the same interface and doing read-time conditionalization within cl-utilities to get better performance on compilers like SBCL and Allegro CL which optimize this operation.

Manual Index