TypeScript implementation of fast integer exponent calculation using divide and conquer

fastIntegerExponent.ts

/**
 * Return the exp-th power of base in O(lg exp) time complexity.
 * @param {number} base - any real number
 * @param {number} exp - any non negative integer
 * @returns base ^ exp
 */
export function pow(base: number, exp: number): number {
  if (exp <= 0) return 1
  if (exp === 1) return base

  const temp = pow(base, Math.floor(exp / 2))
  if (exp % 2) return temp * temp * base
  return temp * temp
}

/**
 * Return the exp-th power of base in O(lg exp) time complexity for field T.
 * @param {T} base - any T
 * @param {number} exp - any non negative integer
 * @param {Function} mul - multiplication of two components
 * @param {T} identity - multiplicative identity of field T
 * @returns mul(...mul(mul(base, base), base), ..., base) which is nested exp times
 */
export function generalizedPow<T>(base: T, exp: number, mul: (lval: T, rval: T) => T, identity: T): T {
  if (exp <= 0) return identity
  if (exp === 1) return base

  const temp = generalizedPow(base, Math.floor(exp / 2), mul, identity)
  if (exp % 2) return mul(mul(temp, temp), base)
  return mul(temp, temp)
}

Very classical divide-and-conquer algorithm for calculate integer exponents. The time complexity of involving operations is simply O(lg exp).

Usage

Actually it's not good to apply this for just normal number, since JavaScript support native ways for it (base ** exp).

But this is useful when it comes to more than just number. For example, assume you want to multiply same matrix for various purpose. Typical example is computing n-th Fibonacci number.

This can be used for any mathematical field with the definition of multiplication and its identity.

Proof for the time complexity

It's very strict forward. Let T(n) be the number of multiplications when exp = n.

T(0) = 0
T(1) = 0
T(n) = 2 + T((n - 1) / 2) if n is odd
       1 + T(n / 2)       otherwise
     ≤ 2 + T(floor(n / 2))
     = O(lg n)

Proof for the last line can be found in well known textbook: Introduction to Algorithms.

ETC

Actually if (exp === 1) return base line is not required, but it'll help to reduce the number of multiplications when exp is 1. Multiplication of identities is useless... and it drops performance when the cost of the multiplication is huge.