Power Function

excerpt: This covers the iterative and recursive implementation of power function. tags: product-accumulator modulo-operator reduction-of-input-value odd even

Implement integer exponentiation. That is, implement the power(x, y) function, where x and y are integers and returns x^y.

Naive Implementation

The implementation for iterative power function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def power(x, n)
  result = 1
  
  n.times do
    result = result * x
  end
  
  result
end

p power(2, 3)

The key insight to write the code for exponentiation is that exponentiation is repeated multiplication.

Building Block

Product Accumulator

The recursive implementation of power function:

1
2
3
4
5
6
7
8
9
def power(x, n)
  if n == 0
    return 1
  end

  return x * power(x, n-1)  
end

p power(3, 3)

Faster Implementation

Can we do this faster than the naive method of repeated multiplication? Yes, we can the improve the performance. We can reduce the number of multiplications in the recursive approach:

𝑥^18 = 𝑥^9∗𝑥^9
𝑥^9 = 𝑥^4∗𝑥^4∗𝑥 𝑥^4 = 𝑥^2∗𝑥^2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def power(x, n)
  if n == 0
    return 1
  end
  
  if n == 1
    return x
  else
    half = power(x, n / 2)

    if n % 2 == 0
      # One multiplication
      return half * half
    else
      # Two multiplications
      return half * half * x
    end
  end
end

p power(3, 3)

The iterative improved version is shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def power(x, n)
  result = 1
  pow = x

  if n % 2 == 1
    result = x
  end
  
  n = n / 2

  # log n - 1 iterations
  while n != 0
    # 1 multiplication
    pow = pow * pow
    if n % 2 == 1
      # 1 multiplication
      result = result * pow
    end
    n = n / 2  
  end
  
  result
end

p power(3, 3)