Content deleted Content added
No edit summary |
No edit summary |
||
Line 5:
*'''Analysis'''
*The numbers computed are always less than z<sup>2</sup>, and the final answer is less than z.
*The method of computing w as x<sup>y</sup> and then reducing w modulo z is not feasible for large numbers. For example, computing f(10, 10<sup>300</sup>, 17) in this way, would involve computing a number w consisting of a 1 followed by 10<sup>300</sup> zeros. If one atom were used to write each zero, then the observable universe would not contain enough atoms to write out w, since it contains fewer than 10<sup>82</sup> atoms. The final answer, in any case, will be less than 17, and the above algorithm for the discrete exponential would compute it in fewer than 2400 steps, since 10<sup>300</sup> < 16<sup>300</sup> < 2<sup>1200</sup>, and every two steps the exponent is cut in half.
| |||