section_path: Efficient computation with integer exponents
section_name: Efficient computation with integer exponents
paragraph_text: Efficient computation with integer exponents
  
  Computing b using iterated multiplication requires n − 1 multiplication operations, but it can be computed more efficiently than that, as illustrated by the following example. To compute 2, apply Horner's rule to the exponent 100 written in binary:
  
  Then compute the following terms in order, reading Horner's rule from right to left.
  
  This series of steps only requires 8 multiplications instead of 99.
  
  In general, the number of multiplication operations required to compute b can be reduced to ♯ n + ⌊ log 2 n ⌋ − 1, {\displaystyle \sharp n+\lfloor \log _{2}n\rfloor -1,} by using exponentiation by squaring, where ♯ n {\displaystyle \sharp n} denotes the number of 1 s in the binary representation of n. For some exponents (100 is not among them), the number of multiplications can be further reduced by computing and using the minimal addition-chain exponentiation. Finding the minimal sequence of multiplications (the minimal-length addition chain for the exponent) for b is a difficult problem, for which no efficient algorithms are currently known (see Subset sum problem), but many reasonably efficient heuristic algorithms are available. However, in practical computations, exponentiation by squaring is efficient enough, and much more easy to implement.