June 01, 1995
Quick and Portable Random Number Generators
June 1995/Quick and Portable Random Number Generators/Sidebar
Approximate Factoring
Suppose you want to compute
(a*x) mod m where
a and
x are positive and less than the modulus
m. If integer overflow is not an issue, you can do this by computing
k1 = a*x/m*m where,
a*x/m signifies the largest integer less than or equal to
a*x/m, and then computing the result
k1*m, called the residue. Suppose, however, that the intermediate value
a*x would overflow. The modulus
m can always be approximately factored into
m = a*q + r with
q = m/a. Now calculate
k=ax/aq. Note that
k is
x/q, thereby avoiding this overflow of
a*x. Using the fact that
m = a*q+r, you can see that the residue is:
a*x- k1*m
or
a*(x - k*q) - k*r + (k-k1)*m
If
a*a is less than
m, k-k1 is either zero or one, and
x is positive and less than
m, the following code fragment using signed integers computes the residue correctly without overflow:
k = x / q;
residue = a* (x - k * q) - k * r;
if (residue < 0)
residue += m;
The check against only negative values can be used in computing the residue if zero values are impossible, as they are if
m is prime.
Previous Page |
1
|
2
|
3
|
4
|
5
|
6
|
7
Next Page
