Logo

Programming-Idioms

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

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 custom_exp($x, $n)
{
    if ($n === 0) {
        return 1;
    }

    if ($n === 1) {
        return $x;
    }

    if (!($n % 2)) {
        return custom_exp($x * $x, $n / 2);
    }

    return $x * custom_exp($x * $x, ($n - 1) / 2);
}

echo custom_exp(5, 10);

A custom exp function using recursion. Note: an exp function already exists in PHP for powers of the constant e. See documentation for pow function and "**" operator.
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...