Fast Exponentiation by Squaring

Fast exponentiation using at most 2 * log₂(n) multiplications, with a partial forward.

When dealing with large exponents, the naive implementation is inefficient. To enhance performance, an alternative approach called Exponentiation by Squaring is commonly used. This method has several implementations.

One of these methods consists of recursive calls to the function with computation based on n:

If n equals to 0, stop the loop and return base
If n is even, square base and divide n by 2, that is, return <function> (base * base, n / 2): this corresponds to calculate 2^6 as 4^3
If n is odd, multiply the result by the base and reduce e by 1, that is, return base * <function> (base, n – 1): this corresponds to calculate 2^3 as 2 * 2^2

This Exponentiation by Squaring algorithm requires a maximum of 2 * log₂(n) iterations for computation, which is significantly fewer than the n iterations needed in previous algorithms.

To implement this algorithm, we need a forward block to perform a loop, as recursive logic cannot be used in safety-critical embedded systems, and local variables (or output values) for the current value of the base, the exponent, and the final value to return.

A forward block iterates as a loop-like construct over arrays of values or ranges of numbers and can return any number of outputs that could be scalar values or arrays. Moreover, while the body of the fold operator contains an operator, the body of the forward block is a scope, allowing more complex modeling.

A forward iteration can be stopped under a condition before the last step has been reached: this is called partial forward.

To implement our algorithm, we use a forward until (that is, partial forward) with:


Number of iterations	We have a maximum of 2 log₂(maximum representable integer for exponent) iterations. As we want to support 64-bits integers, we set the number of iterations to 2 64 = 128
Local variables	We set 2 local variables in the scope of the forward block: e and b, representing respectively the current values of the exponent (initialized to n with a last) and base (initialized to base with a last).
Stop condition (until)	We stop the loop when the current value of exponent, e, is null.
Output value	We use a return value result, initialized to 1. Moreover, for a forward until, the first output value corresponds to the number of iteration steps that were executed. As we are not interested in this value, we assign the 2^nd output value of the forward block to the output of our function.
Body for the forward block	We implement the body using an ActivateIf block with 2 cases based on oddness/evenness of e: If e is even, square the value of b and divide e by 2 If e is odd, update result by multiplying it with b and reduce e by 1 Each case of the ActivateIf corresponds to a specific scope. In each scope, we require access to the values of variables e, b, and result from the previous iteration. The pre keyword may seem like a viable solution; however, it only retrieves the last value set within the given scope, resulting in the same value being referenced throughout the entire loop if it is not modified in the scope (that is, the value of b in the case where e is odd). Instead, we can utilize the last keyword, which enables us to access the values of the previous iterations and correctly reference the desired variables. So, for example, in the case where e is odd, we have result = last ‘result last ‘b*.

Tip: When working within a forward operator, remember that the last and pre keywords applied to variables defined inside the scope have different meanings compared to those defined outside. Inside a forward operator, these keywords refer to the values from the previous iteration, rather than the previous cycle as in the case of variables not enclosed by the forward block.

The corresponding model is the following:

function FastExp (base: 'T; n: 'U;)
returns (y: 'T;)
where 'T numeric
where 'U unsigned

The forward block defines the following local variables:

e: 'U last = n
b: 'T last = base

Table 1. Pros and cons of exponentiation by squaring implemented using forward until
Pros	Cons
Simple implementation: the model is still easy to understand Efficient computation: the computation is performed on a maximum of 2 log₂(n)* iterations	Condition check at each cycle: a computation time is required to check the until clause at each iteration