Complex Numbers Exponential - Efficient Computation of Integer Powers

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:

  1. 22 = 4
  2. (22)2 = 24 = 16
  3. (24)2 = 28 = 256
  4. (28)2 = 216 = 65,536
  5. (216)2 = 232 = 4,294,967,296
  6. (232)2 = 264 = 18,446,744,073,709,551,616
  7. 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)

    “Dear to us are those who love us, the swift moments we spend with them are a compensation for a great deal of misery; they enlarge our life;Mbut dearer are those who reject us as unworthy, for they add another life: they build a heaven before us, whereof we had not dreamed, and thereby supply to us new powers out of the recesses of the spirit, and urge us to new and unattempted performances.”
    —Ralph Waldo Emerson (1803–1882)