Number Theory Essentials

Opening scenario

Pow(x, n) (LC 50). Implement pow(x, n) — x a float, n a (possibly negative, possibly large) integer — without using the built-in power, and faster than multiplying x by itself n times. Follow-ups you should expect: Count Primes (LC 204) — count primes strictly less than n; and "compute gcd(a, b)" and "compute x^n mod m for huge n".

LC numbers identify LeetCode problems.

Compare computing x^8 with eight repeated factors to computing x^2, then x^4, then x^8. How much work can be reused? Here x^n denotes mathematical exponentiation; Python writes it as x ** n, since ^ means bitwise XOR.

Question progression

Q1 — Why is the loop result *= x n times not acceptable?

Question: The naive pow multiplies x into an accumulator n times. What is that costing, and what structure in n are you ignoring?

Reasoning: Naive pow is O(n)…