Fast Powering

Definition

Definition

The Fast Powering Algorithm, also known as Exponentiation by Squaring, is a method used to efficiently compute large powers of a number. It reduces the number of multiplications required, making it significantly faster than the naive approach of repeated multiplication

Explanation

First step involves checking if the exponent (n) is 0; if it is, the algorithm returns 1. Next, for even exponents, the algorithm recursively computes the value of x raised to the power of half of n. On the other hand, for odd exponents, it multiplies x by the result of x raised to half of (n - 1), and then continues this process recursively. Finally, the algorithm combines the results obtained from both even and odd exponent calculations to obtain the final result

Guidance

• See if the exponent n is 0. If it is, just give back 1
• If n is an even number, find out what x raised to the power of half of n is, and do it again until you get the answer
• If n is an odd number, first find out what x raised to the power of half of (n - 1) is, then multiply it by x, and repeat until you get the answer
• Combine the results obtained and return the final result

Tips

• utilize recursion efficiently to minimize the number of multiplications
• optimize for even and odd exponents separately

Practice

Practice

fast_power(x, n):
  if n == 0:
    return 1
  else if n % 2 == 0:
    temp = fast_power(x, n/2)
    return temp * temp
  else:
    temp = fast_power(x, (n-1)/2)
    return x * temp * temp

Solution

package main

// iterative
func fastPowerIterative(x, n int) int {
    result := 1
    for n > 0 {
        if n&1 == 1 {
            result *= x
        }
        x *= x
        n >>= 1
    }
    return result
}

// recursive
func fastPowerRecursive(x, n int) int {
    if n == 0 {
        return 1
    }
    temp := fastPowerRecursive(x, n/2)
    if n%2 == 0 {
        return temp * temp
    }
    return x * temp * temp
}

public class Main {

  // iterative
  public static int fastPowerIterative(int x, int n) {
    int result = 1;
    while (n > 0) {
      if ((n & 1) == 1) {
        result *= x;
      }
      x *= x;
      n >>= 1;
    }
    return result;
  }

  // recursive
  public static int fastPowerRecursive(int x, int n) {
    if (n == 0) {
      return 1;
    }
    int temp = fastPowerRecursive(x, n / 2);
    if (n % 2 == 0) {
      return temp * temp;
    }
    return x * temp * temp;
  }
}

// iterative
function fastPowerIterative(x, n) {
  let result = 1;
  while (n > 0) {
    if (n & 1) {
      result *= x;
    }
    x *= x;
    n >>= 1;
  }
  return result;
}

// recursive
function fastPowerRecursive(x, n) {
  if (n === 0) {
    return 1;
  }
  const temp = fastPowerRecursive(x, Math.floor(n / 2));
  if (n % 2 === 0) {
    return temp * temp;
  }
  return x * temp * temp;
}

// iterative
fun fastPowerIterative(x: Int, n: Int): Int {
    var result = 1
    var base = x
    var exponent = n
    while (exponent > 0) {
        if (exponent and 1 == 1) {
            result *= base
        }
        base *= base
        exponent = exponent shr 1
    }
    return result
}

// recursive
fun fastPowerRecursive(x: Int, n: Int): Int {
    if (n == 0) {
        return 1
    }
    val temp = fastPowerRecursive(x, n / 2)
    return if (n % 2 == 0) temp * temp else x * temp * temp
}

# iterative
def fast_power_iterative(x, n):
    result = 1
    while n > 0:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

# recursive
def fast_power_recursive(x, n):
    if n == 0:
        return 1
    temp = fast_power_recursive(x, n // 2)
    if n % 2 == 0:
        return temp * temp
    return x * temp * temp

// iterative
fn fast_power_iterative(x: i32, n: i32) -> i32 {
    let mut result = 1;
    let mut base = x;
    let mut exponent = n;
    while exponent > 0 {
        if exponent & 1 == 1 {
            result *= base;
        }
        base *= base;
        exponent >>= 1;
    }
    result
}

// recursive
fn fast_power_recursive(x: i32, n: i32) -> i32 {
    if n == 0 {
        return 1;
    }
    let temp = fast_power_recursive(x, n / 2);
    if n % 2 == 0 {
        temp * temp
    } else {
        x * temp * temp
    }
}

// iterative
function fastPowerIterative(x: number, n: number): number {
  let result = 1;
  while (n > 0) {
    if (n & 1) {
      result *= x;
    }
    x *= x;
    n >>= 1;
  }
  return result;
}

// recursive
function fastPowerRecursive(x: number, n: number): number {
  if (n === 0) {
    return 1;
  }
  const temp = fastPowerRecursive(x, Math.floor(n / 2));
  if (n % 2 === 0) {
    return temp * temp;
  }
  return x * temp * temp;
}