Logo

Programming-Idioms

# 32 Integer exponentiation by squaring
Create function exp which calculates (fast) the value x power n.
x and n are non-negative integers.
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations 
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) {
  var r = 1;
  while (true) {
    if (n.isOdd) r *= x;
    n ~/= 2;
    if (n == 0) break;
    x *= x;
  }
  return r;
}
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;
}
: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;
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 undef if $x < 0 or $n < 0;
   return $x ** $n;
}
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);
}
def exp(x, n):
        return x**n

def exp(x, n)
  x ** n
end
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
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),
    }     
}
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)

Preview