Logo

Programming-Idioms

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

Idiom #32 Integer exponentiation by squaring

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

sub exp {
   my ($x, $n) = @_;
   return 1 unless $n;
   return $x if $n == 1;
   return $x * exp($x*$x, ($n-1)/2) if $n%2;
   return exp($x*$x, $n/2);
}
sub exp {
   my ($x, $n) = @_;
   return undef if $x < 0 or $n < 0;
   return $x ** $n;
}
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...