Logo

Programming-Idioms

  • Lisp
  • Pascal

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: 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;

The integer type overflows very fast.
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;

QWord is 64-bit, it overflows less quickly than integer.
(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)))

All of the odd values are multiplied into multiple while base is squared with each iteration.

Since specification is "non-negative" handle the case of the power being 0 separately
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...
< > ⌨
programming-idioms.org 
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;
(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)))
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 = (^)
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)
}
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);
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)