Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Erlang

Idiom #32 Integer exponentiation by squaring

Create function exp which calculates (fast) the value x power n.
x and n are non-negative integers.

	
-module  (int_power).
-export  ([exp/2]).

exp (X, N) -> exp (X, N, 1).

exp (_X, 0, Y) -> Y;
exp (X, N, Y) when N rem 2 =:= 0 ->
  exp (X * X, N div 2, Y);
exp (X, N, Y) ->
  exp (X * X, N div 2, X * Y).

Right-to-left exponentiation by squaring. Knuth TAOCP Volume 2, 3rd edition, p 462. This cleans up Algorithm A of section 4.6.3.
unsigned int exp(unsigned int x,unsigned int n)
{
    if(n==0)
    {
        return 1;
    }
    if(n==1)
    {
        return x;
    }
    if(!(n%2))
    {
        return exp(x*x,n/2);
    }
    return x*exp(x*x,(n-1)/2);
}

New implementation...