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:

    “The really efficient laborer will be found not to crowd his day with work, but will saunter to his task surrounded by a wide halo of ease and leisure.”
    —Henry David Thoreau (1817–1862)

    “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)

    “The Federal Constitution has stood the test of more than a hundred years in supplying the powers that have been needed to make the Central Government as strong as it ought to be, and with this movement toward uniform legislation and agreements between the States I do not see why the Constitution may not serve our people always.”
    —William Howard Taft (1857–1930)