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:
“The English masses are lovable: they are kind, decent, tolerant, practical and not stupid. The tragedy is that there are too many of them, and that they are aimless, having outgrown the servile functions for which they were encouraged to multiply. One day these huge crowds will have to seize power because there will be nothing else for them to do, and yet they neither demand power nor are ready to make use of it; they will learn only to be bored in a new way.”
—Cyril Connolly (1903–1974)