method of repeated squaring
Let be the map and be defined by . So far we recognize that evaluates to and evaluates to . But we caution that we do not define these functions with exponents because we want to demonstrate that from an algorithm to multiply we can create an efficient algorithm to exponentiate.
For define (recalling that may use the output of any previous evaluation)
Evidently, evaluates to . By induction, evaluates to and thus evaluates to . Therefore we establish that for all nonnegative integers . Furthermore, to evaluate uses multiplications.
Now write in binary: with for . Let be the indices for which , . Then define
Thus, evaluates to:
Because each uses the output of , the cost of evaluating is the cost of evaluating plus the final cost of multiplying . Thus, evaluating uses multiplications. As it follows that evaluating uses no more than multiplications. ∎
|Title||method of repeated squaring|
|Date of creation||2013-03-22 16:16:14|
|Last modified on||2013-03-22 16:16:14|
|Last modified by||Algeboy (12884)|