Practical Applications
The multiplicative inverse has innumerable applications in algorithms of computer science, particularly those related to number theory, since many such algorithms rely heavily on the theory of modular arithmetic. As a simple example, consider the exact division problem where you have a list of odd word-sized numbers each divisible by k and you wish to divide them all by k. One solution is as follows:
- Use the extended Euclidean algorithm to compute k−1, the modular multiplicative inverse of k mod 2w, where w is the number of bits in a word. This inverse will exist since the numbers are odd and the modulus has no odd factors.
- For each number in the list, multiply it by k−1 and take the least significant word of the result.
On many machines, particularly those without hardware support for division, division is a slower operation than multiplication, so this approach can yield a considerable speedup. The first step is relatively slow but only needs to be done once.
Read more about this topic: Multiplicative Inverse
Famous quotes containing the word practical:
“Philosophy, certainly, is some account of truths the fragments and very insignificant parts of which man will practice in this workshop; truths infinite and in harmony with infinity, in respect to which the very objects and ends of the so-called practical philosopher will be mere propositions, like the rest.”
—Henry David Thoreau (1817–1862)