Optimizing Lagged Fibonacci Generators for Large-Scale Computations

Lagged Fibonacci Generators (LFGs) are widely used in simulations and cryptography for generating pseudo-random sequences. While the naive implementation is straightforward, it becomes inefficient for large indices ($n$) due to its iterative nature and growing computational costs.

To address these challenges, we introduce an optimized approach using matrix exponentiation and modular arithmetic. By encoding the recurrence relation in a transformation matrix $\mathbf{Q}$, the sequence can be computed efficiently through binary exponentiation. This method scales well, especially with GPU acceleration via libraries like cupy, enabling faster computations for large-scale problems.

With a foundation in linear algebra, this approach not only improves runtime but also demonstrates the power of combining mathematical insights with computational techniques for efficient random number generation. Although the approach presented below is already pretty good, it has some shortcomings like large memory requirements. Other approaches such as generating functions, representing the series as the coefficients of a power series, might be advantageous in practice.

Follow along in the Jupyter notebook below: