An algorithm for multiplying two 32-bit integers modulo a 32-bit constant without using any intermediates larger than 32 bits. It is also useful in certain types of random number generators.
Schrage's Algorithm
Explore with Wolfram|Alpha
References
Bratley, P.; Fox, B. L.; and Schrage, E. L. A Guide to Simulation, 2nd ed. New York: Springer-Verlag, 1996.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Random Numbers." Ch. 7 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, p. 269, 1992.Schrage, L. "A More Portable Fortran Random Number Generator." ACM Trans. Math. Software 5, 132-138, 1979.Referenced on Wolfram|Alpha
Schrage's AlgorithmCite this as:
Weisstein, Eric W. "Schrage's Algorithm." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SchragesAlgorithm.html