Pattern visualizer
Pow(x, n)
Instead of multiplying x by itself n times (O(n)), halve the exponent each step: if n is even, x^n = (x^(n/2))^2; if odd, x^n = x * x^(n-1). This gets the answer in O(log n) multiplications. A negative n is handled by inverting x (1/x) and negating n first. Animated on: Fast exponentiation: x=2.0, n=10 (answer 1024.0). Halve n each step: n even → x=x*x,n/=2; n odd → result*=x,n-=1. Negative n inverts x first..
Math
step 1 / 12
10
[0]line 1
Step 1: myPow(2.0, 10). n=10 ≥ 0, so no sign flip. Call fastPow(2.0, 10).
Pseudocode
1FUNCTION myPow(x, n):2 IF n < 0: replace x with 1/x and n with -n3 RETURN fastPow(x, n)4FUNCTION fastPow(x, n):5 IF n is 0: RETURN 16 IF n is even:7 half = fastPow(x, n/2)8 RETURN half * half9 ELSE:10 RETURN x * fastPow(x, n-1)
← / → step · space play · Home restart