💾 Archived View for disconnect.wiki › algorithms › binary-exponentiation.gmi captured on 2022-03-01 at 15:01:55. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Binary Exponentiation

Problem description

How to calculate an exponentiation of a number without using pow()?

Video about the problem on Youtube

Naive Solution

Complexity :: O(n)

const range = (from, to) => {
    let result = [];
    let curr = from;

    while (curr < to) {
        result.push(curr);
        curr += 1;
    }

    return result;
};

const pow = (base, exp) => range(1, exp).reduce((accum, _) => accum * base, base);

const assert = require('assert');
assert.equal(pow(2,4), 16);

Optimized Solution

Complexity :: O(log(n))

const pow = (base, exp) => {
    if (exp == 0) {
        return 1;
    }

    const tmp = pow(base, Math.floor(exp/2));
    return tmp * tmp * (exp % 2 == 1 ? base : 1);
};

const assert = require('assert');
assert.equal(pow(2,4), 16);

Iteractive Solution

Complexity :: O(log(n))

Less indirection and simpler to write, harder to remember.

const pow = (base, exp) => {
    let result = 1;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result *= base;
        }

        base *= base;
        exp /= 2;

    }

    return result;
};

const assert = require('assert');
assert.equal(pow(2,4), 16);