Generation of nonrecursive 𝑛-bit pseudorandom numbers based on 𝛽-transformation on [1, 2) (𝑛 = 64, 128, 192, …, 8192)

Abstract We show that we can generate nonrecursive 𝑛-bit pseudorandom numbers using a simple algorithm whose essential computation is five times repetition of (𝑛-bit) <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mo>×</m:mo> </m:math> \times (𝑛-bit) multiplication and taking out an 𝑛-bit integer from the result of multiplication. The algorithm can be described by 𝛽-transformation <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mrow> <m:mrow> <m:mrow> <m:msub> <m:mi>T</m:mi> <m:mi>β</m:mi> </m:msub> <m:mo>⁢</m:mo> <m:mrow> <m:mo stretchy="false">(</m:mo> <m:mi>X</m:mi> <m:mo stretchy="false">)</m:mo> </m:mrow> </m:mrow> <m:mo>=</m:mo> <m:mrow> <m:mrow> <m:mrow> <m:mi>β</m:mi> <m:mo>⁢</m:mo> <m:mi>X</m:mi> </m:mrow> <m:mo>−</m:mo> <m:mrow> <m:mo stretchy="false">⌊</m:mo> <m:mrow> <m:mi>β</m:mi> <m:mo>⁢</m:mo> <m:mi>X</m:mi> </m:mrow> <m:mo stretchy="false">⌋</m:mo> </m:mrow> </m:mrow> <m:mo>+</m:mo> <m:mn>1</m:mn> </m:mrow> </m:mrow> <m:mo rspace="1.167em">,</m:mo> <m:mrow> <m:mrow> <m:mi>X</m:mi> <m:mo>∈</m:mo> <m:mrow> <m:mo stretchy="false">[</m:mo> <m:mn>1</m:mn> <m:mo>,</m:mo> <m:mn>2</m:mn> <m:mo stretchy="false">)</m:mo> </m:mrow> </m:mrow> <m:mo rspace="0.337em">,</m:mo> <m:mrow> <m:mi>β</m:mi> <m:mo>&gt;</m:mo> <m:mn>1</m:mn> </m:mrow> </m:mrow> </m:mrow> <m:mo lspace="0em">.</m:mo> </m:mrow> </m:math> T_{\beta}(X)=\beta X-\lfloor\beta X\rfloor+1,\quad X\in[1,2),\,\beta&gt;1. We consider the condition that repetition of 𝛽-transformation generates random numbers, and see why our simple algorithm works well for various values of 𝑛