Efficient Computation of Integer Powers
The simplest method of computing bn requires n−1 multiplication operations, but it can be computed more efficiently than that, as illustrated by the following example. To compute 2100, note that 100 = 64 + 32 + 4. Compute the following in order:
- 22 = 4
- (22)2 = 24 = 16
- (24)2 = 28 = 256
- (28)2 = 216 = 65,536
- (216)2 = 232 = 4,294,967,296
- (232)2 = 264 = 18,446,744,073,709,551,616
- 264 232 24 = 2100 = 1,267,650,600,228,229,401,496,703,205,376
This series of steps only requires 8 multiplication operations instead of 99 (since the last product above takes 2 multiplications).
In general, the number of multiplication operations required to compute bn can be reduced to Θ(log n) by using exponentiation by squaring or (more generally) addition-chain exponentiation. Finding the minimal sequence of multiplications (the minimal-length addition chain for the exponent) for bn is a difficult problem for which no efficient algorithms are currently known (see Subset sum problem), but many reasonably efficient heuristic algorithms are available.
Read more about this topic: Complex Numbers Exponential
Famous quotes containing the words efficient, computation and/or powers:
“I make no secret of the fact that I would rather lie on a sofa than sweep beneath it. But you have to be efficient if you’re going to be lazy.”
—Shirley Conran (b. 1932)
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“I have come slowly into possession of such powers as I have ... I receive the opinions of my day. I do not conceive them. But I receive them into a vivid mind.”
—Woodrow Wilson (1856–1924)