Editing Exponentiation by squaring (section)

===With constant auxiliary memory===

The variants described in this section are based on the formula
:<math> yx^n=
    \begin{cases}
                (yx) \, ( x^{2})^{(n - 1)/2}, & \mbox{if } n \mbox{ is odd} \\
                y\,(x^{2})^{n/2} , & \mbox{if } n \mbox{ is even}.
     \end{cases}
</math>

If one applies recursively this formula, by starting with {{math|1=''y'' = 1}}, one gets eventually an exponent equal to {{math|0}}, and the desired result is then the left factor.

This may be implemented as a tail-recursive function:
<syntaxhighlight lang="pascal">
  Function exp_by_squaring(x, n)
    return exp_by_squaring2(1, x, n)
  Function exp_by_squaring2(y, x, n)
    if n < 0 then return exp_by_squaring2(y, 1 / x, -n);
    else if n = 0 then return y;
    else if n is even then return exp_by_squaring2(y, x * x, n / 2);
    else if n is odd then return exp_by_squaring2(x * y, x * x, (n - 1) / 2).
</syntaxhighlight>

The iterative version of the algorithm also uses a bounded auxiliary space, and is given by

<syntaxhighlight lang="pascal">
  Function exp_by_squaring_iterative(x, n)
    if n < 0 then
      x := 1 / x;
      n := -n;
    if n = 0 then return 1
    y := 1;
    while n > 1 do
      if n is odd then
        y := x * y;
        n := n - 1;
      x := x * x;
      n := n / 2;
    return x * y
</syntaxhighlight>

The correctness of the algorithm results from the fact that <math>yx^n</math> is invariant during the computation; it is <math>1\cdot x^n=x^n</math> at the beginning; and it is <math>yx^1=xy </math> at the end.

These algorithms use exactly the same number of operations as the algorithm of the preceding section, but the multiplications are done in a different order.