Fast-Forwarding LCGs

🌈 Abstract

This article discusses the idea of fast-forwarding Linear Congruential Generators (LCGs) and explores different approaches to achieve this. The author explains how to update LCGs at twice the rate, as well as how to perform multiple bit steps at a time. They also introduce the concept of manipulating LCG generators directly using matrix form and discuss the potential for parallelism in LCG evaluations.

📄 Section Summary

Fast-Forwarding LCGs

The basic idea of fast-forwarding LCGs is to update them at a faster rate. By stepping an LCG at twice the rate, another LCG with different coefficients can be obtained that proceeds twice as fast as the original one.

Precomputation for Faster Evaluation

To avoid limiting oneself to binary steps, precomputation can be used. By doing multiple bits at a time, it is possible to step the LCG to an arbitrary position with a smaller constant factor.

Manipulating Generators Directly

Instead of funneling everything into x, there is more latent parallelism if the generators are manipulated directly. This can be done by representing LCG operations in matrix form and raising the matrix to the power of n.

Left-Associative Fast Exponentiation Loop

An alternative version of the fast exponentiation loop is introduced, which is left-associative rather than right-associative. This allows for splitting into several dependency chains and vectorization within a single LCG evaluation.

💡 Key insights

• Fast-forwarding LCGs involves updating them at a faster rate.
• Precomputation can be used to perform multiple bit steps at a time.
• Manipulating generators directly allows for more parallelism.
• Left-associative fast exponentiation loops enable splitting into dependency chains and vectorization within a single evaluation.