# 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,n) result(I)
I=x**n
end function exp``````
``````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);
}``````
``````(defn exp [x n]
(let [x-squared (* x x)]
(cond
(= n 0) 1
(= n 1) x
(= (mod n 2) 0) (exp x-squared (/ n 2))
:else (* x (exp x-squared (/ (- n 1) 2))))))``````
``````int pow(int x, int p)
{
if (p == 0) return 1;
if (p == 1) return x;

int tmp = pow(x, p/2);
if (p%2 == 0) return tmp * tmp;
else return x * tmp * tmp;
}``````
``using System;``
``````long exp(long x, long n) {
return (long) Math.Pow(x, n);
}``````
``````long exp(long x, long n){
if (n == 0)
return 1;
if (n == 1)
return x;
if (n % 2 == 0)
return exp(x * x, n / 2);
else
return x * exp(x * x, (n - 1) / 2);
}``````
``````uint exp(uint x, uint n) {
if(n == 0)
return 1;
if(n == 1)
return x;
if(n % 2 == 0)
return exp(x * x, n / 2);
else
return x * exp(x * x, (n - 1) / 2);
}``````
``````int exp(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
var r = exp(x * x, n ~/ 2);
if (n % 2 == 1) r *= x;
return r;
}``````
``````int exp(int x, int n) {
var r = 1;
while (true) {
if (n.isOdd) r *= x;
n ~/= 2;
if (n == 0) break;
x *= x;
}
return r;
}``````
``:math.pow(x, n)``
``	``
``````-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).
``````
``````func exp(x, n int) int {
switch {
case n == 0:
return 1
case n == 1:
return x
case n%2 == 0:
return exp(x*x, n/2)
default:
return x * exp(x*x, (n-1)/2)
}
}``````
``exp = (^)``
``const exp = Math.pow;``
``````function exp(x, n) {
if (n===0) return 1;
if (n===1) return x;
return n%2 ? x * exp(x*x, (n-1)/2)
: exp(x*x, n/2);
}``````
``````int exp(int x, int n){
if(n==0)
return 1;
if(n==1)
return x;
if(n%2==0)
return exp(x*x, n/2);
else
return x * exp(x*x, (n-1)/2);
}``````
``````fun exp(x: Int, n: Int): Int = when {
n == 0 -> 1
n == 1 -> x
n % 2 == 0 -> exp(x * x, n / 2)
else -> x * exp(x * x, (n - 1) / 2)
}``````
``````(loop
for (power rem) = (list p 0) then (multiple-value-list (floor power 2))
for multiple = 1 then (if (zerop rem) multiple (* multiple base))
for base = x then (* base base)
when (= power 0) return 1
when (= power 1) return (* multiple base)))``````
``````function exp(x, n)
return x^n
end``````
``````unsigned exp(unsigned x,unsigned n) {
switch (n) {
case 0: return 1;
case 1: return x;
}
if (n&1) return x*exp(x*x,(n-1)/2);
return exp(x*x,n/2);
}
``````
``````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);``````
``````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;``````
``````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;``````
``````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;
}``````
``````def exp(x, n):
return x**n
``````
``````def exp(x, n)
return 1 if n == 0
return x if n == 1
return exp(x*x, n/2) if n.even?
x * exp(x*x, (n-1)/2)
end``````
``````def exp(x, n)
x ** n
end``````
``````fn exp(x: u64, n: u64) -> u64 {
match n {
0 => 1,
1 => x,
i if i % 2 == 0 => exp(x * x, n / 2),
_ => x * exp(x * x, (n - 1) / 2),
}
}``````
``````fn exp(x: u64, n: u32) -> u64 {
x.pow(n)
}``````
``````def exp(x: Int, n: Int): Int {
if(n == 0) {
1
} else if(n == 1) {
x
} else if(n%2 == 0) {
exp(x*x, n/2)
} else {
x * exp(x*x, (n-1)/2)
}
}``````
``````exp: n
n = 0 ifTrue: [^ 1].
n = 1 ifTrue: [^ self].
n%2 = 0 ifTrue: [^ self * self exp: n/2].
^ self * (self * self exp: n-1/2)``````

programming-idioms.org