Logo

Programming-Idioms

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

Idiom #32 Integer exponentiation by squaring

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

function exp(x: integer; n: integer): integer;

begin
  if n = 0 then
    Result := 1
  else if n = 1 then
    Result := x
  else if (n and 1) = 0 then
    Result := exp(x * x, n div 2)
  else
    Result := x * exp(x * x, n div 2);
end;

The integer type overflows very fast.
function exp(x: QWord; n: integer): QWord;

begin
  if n = 0 then
    Result := 1
  else if n = 1 then
    Result := x
  else if (n and 1) = 0 then
    Result := exp(x * x, n div 2)
  else
    Result := x * exp(x * x, n div 2);
end;

QWord is 64-bit, it overflows less quickly than integer.
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...