Random access to a random number sequence (Q1184612)

This paper presents an extension of the method by \textit{A. E. Koniges} and \textit{C. E. Leith} [ibid. 81, No. 1, 230-235 (1989; Zbl 0666.65002)] for direct jump to any desired \(k\)-th element \(\chi_ k\) of the linear congruential multiplier random number generator \(\chi_{k+1}=\lambda\chi_ k+c\), mod \(m\), \(k\geq 0\). It is shown that \(chi_ k\) is expressed as \(\chi_ k=X_ k+\Sigma_ k\) and \(X_ k\) and \(\Sigma_ k\) are both constructed using precalculated arrays \(P\) and \(S\), the solution. The authors show that we can evaluate \(X_ k\) and \(\Sigma_ k\), and then \(\chi_ k\), in a small number of multiplications and additions of \(P\) and \(S\) by suitable choice of the base \(b\) for the digits of \(k\).