a small integer.

The example , , and is presented again. The algorithm performs the iteration thirteen times:
:
:
:
:
:
:
:
:
:
:
:
:
:

The final answer for is therefore 445, as in the direct method.

Like the first method, this requires multiplications to complete. However, since the numbers used in these calculations are much smaller than the numbers used in the first algorithm's calculations, the computation time decreases by a factor

1.Previous
3.Next