JavaScript/Maths/BinaryExponentiationIterative.js at master · TheAlgorithms/JavaScript · GitHub

24 lines (20 loc) · 557 Bytes

// To calculate x^n i.e., exponent(x, n) in O(log n) time in iterative way

// n is an integer and n >= 0

// Explanation: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

// Examples:

// 2^3 = 8

// 5^0 = 1

// Uses the fact that

// exponent(x, n)

// = exponent(x*x, floor(n/2)) ; if n is odd

// = x*exponent(x*x, floor(n/2)) ; if n is even

const exponent = (x, n) => {

let answer = 1

while (n > 0) {

if (n % 2 !== 0) answer *= x

n = Math.floor(n / 2)

if (n > 0) x *= x

}

return answer

}

export { exponent }

Expand file tree