Large Integer Methods
Methods designed for hardware implementation generally do not scale to integers with thousands or millions of decimal digits; these frequently occur, for example, in modular reductions in cryptography. For these large integers, more efficient division algorithms transform the problem to use a small number of multiplications, which can then be done using an asymptotically efficient multiplication algorithm such as the Karatsuba algorithm, Toom–Cook multiplication or the Schönhage–Strassen algorithm. It results that the computational complexity of the division is of the same order (up a multiplicative constant) as that of the multiplication. Examples include reduction to multiplication by Newton's method as described above as well as the slightly faster Barrett reduction algorithm. Newton's method's is particularly efficient in scenarios where one must divide by the same divisor many times, since after the initial Newton inversion only one (truncated) multiplication is needed for each division.
Read more about this topic: Division Algorithm
Famous quotes containing the words large and/or methods:
“Frequently also some fair-weather finery ripped off a vessel by a storm near the coast was nailed up against an outhouse. I saw fastened to a shed near the lighthouse a long new sign with the words “ANGLO SAXON” on it in large gilt letters, as if it were a useless part which the ship could afford to lose, or which the sailors had discharged at the same time with the pilot. But it interested somewhat as if it had been a part of the Argo, clipped off in passing through the Symplegades.”
—Henry David Thoreau (1817–1862)
“All good conversation, manners, and action, come from a spontaneity which forgets usages, and makes the moment great. Nature hates calculators; her methods are saltatory and impulsive.”
—Ralph Waldo Emerson (1803–1882)