A Power Procedure

Consider the integral power procedure. Each example in this section is presented in Scheme and in C. For code generation the Scheme example assumes the implementation provides a compile procedure, and the C example uses the DCG system [DCG].

This code looks clean and efficient, but often it is far from optimal. If the exponent were known to be, eg 20 (10100_2 =
20_{10}), you could instead use this specialized version:

Since the control flow, conditionals, and shifting of the original code depended only on the exponent, they can be eliminated. On typical RISC machines, this will run much faster (on a MIPS R3000 the C version ran 2.7 times faster; on an Alpha 2.4 times).

Sometimes the exponent isn't known at compile time, but you do know that, for whichever values arrives later, it will be called many times (perhaps 10,000). This situation is the motivation for run time code generation (RTCG), the synthesis of specialized machine code at run time [note run-time]. Using this technique, a generating extension is called with just the exponent. It returns a procedure that finishes the computation:

The lisp compiler is called to convert the sexpr data into a procedure. [note removing-times-one].

DCG is an efficient, retargetable, C-callable interface for RTCG [DCG]. The `D' stands for `Dynamic' (which is actually a better term than `run time'). Using it, power_gen looks something like this:

This compiler will run very fast.

The following sections follow a generalization of this procedure typically occuring in 3D graphics. But this represents only one possible path: in a mathematical library, you might want to provide a more general purpose power procedure that handled negative and then rational exponents. You might also support complex numbers. Such features require additional tests, but as long as they depend solely on the exponent, a compiler can eliminate them.