AlgoScope

Fast Exponentiation

Square the base once per bit of the exponent, and multiply in on every 1 bit.

Mathematics, algorithm, intermediateAlso called binary exponentiation, exponentiation by squaring
Bit is 1. Multiplying in, result 3.10110213i
Bit is 1. Multiplying in, result 3.10110213i

Number Theory Basics: 3 to the 13, mod 7

Decision, step 2 of 9

This bit is 1, so multiply the current power in: 1 x 3 mod 7 = 3.

How number theory basics works

Cost

Best
O(log e)
Average
O(log e)
Worst
O(log e)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Number Theory Basics covers these too, in the same run.