next up previous
Next: Fast algorithms and slow Up: Contents Previous: Algorithms for repeated squaring

Predicting how many computer steps are needed by an algorithm

In order to predict how long a computer will take to execute an algorithm, we need a way to predict how long it will take to execute a single multiplication. Now the time per multiplication really should depend on how many digits are involved. For purposes of this class, we shall say therefore that the number of computer steps needed to multiply two numbers is the number of digits in the result of the multiplication. When the multiplication is done in modular arithmetic, the result is always less than the modulus and hence has about the same number of digits as the modulus. Thus our estimate for the number of computer steps required for a mod m multiplication is 1 plus the number of decimal digits in m.

For example, the naive algorithm for calculating tex2html_wrap_inline93 takes k-1 multiplications, all mod m. Since each multiplication takes roughly tex2html_wrap_inline235 steps, the total number of computer steps is roughly tex2html_wrap_inline237 .

The repeated squaring algorithm for the same computational problem takes a number of multiplications that is at most twice the number of bits of k minus one. Since the number of bits of k is at most 1 plus the base-2 logarithm of k, the number of multiplications is at most tex2html_wrap_inline245 . Each multiplication is done modulo m, and therefore takes at most tex2html_wrap_inline235 computer steps. Thus the total number of computer steps for this algorithm is roughly tex2html_wrap_inline251 .



Lisa Eckstein
Tue Oct 22 00:20:45 EDT 1996