Idiom #32 Integer exponentiation by squaring
Create function exp which calculates (fast) the value x power n.
x and n are non-negative integers.
Programming-Idioms
Please choose a nickname before doing this
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);
}
def exp(x, n):
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);
}
(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;
}
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).
function exp(x,n) result(I) I=x**n end function exp
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 = (^)
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);
}
const exp = Math.pow;
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 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)