Exponentiation - 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:  Exponentiation

Famous quotes containing the words efficient, computation and/or powers:

    “An efficient and valuable man does what he can, whether the community pay him for it or not. The inefficient offer their inefficiency to the highest bidder, and are forever expecting to be put into office. One would suppose that they were rarely disappointed.”
    —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)

    “For human nature, being more highly pitched, selved, and distinctive than anything in the world, can have been developed, evolved, condensed, from the vastness of the world not anyhow or by the working of common powers but only by one of finer or higher pitch and determination than itself.”
    —Gerard Manley Hopkins (1844–1889)