What simple function $f(i)$ produces an evenly distributed pseudorandom output for $i \in [1, 2, ...)$?

68 Views Asked by At

I'm looking for a transformation $N \to S$ where $N$ is natural numbers sequence, whereas $S$ is an infinite pseudorandom sequence that doesn't end up with a repeating pattern and has a uniform distribution in some specified range, say $[0, r)$. Desirably the output of the function $f$ to be an integer.

Some analog could be the Bailey–Borwein–Plouffe formula for calculating a specific digit of $\pi$ . The goal is to find a simple solution in terms of computational complexity.

Searching through StackExchange, I found this topic. Unfortunately, the answer doesn't satisfy me since I don't want to use Linear congruential generator. I don't want to depend on a previous result when doing calculations. The function $f$ should solely rely on its parameter $i$. And also the sequence $S$ needs to be non-periodical.

1

There are 1 best solutions below

4
On

If all you care about is aperiodicity and the uniform distribution of values of $f(i)$ (as opposed to the joint distribution of tuples of values like $(f(i),f(i+1))$) you should be content with the equidisribution theorem of Weyl. Examples like $$f(i)=\lfloor r (\pi i \bmod 1)\rfloor$$ or $$f(i)=\lfloor r (\sqrt 2 i \bmod 1)\rfloor$$ do the trick.

Abandoning Weyl's theorem, you could use a recipe like $$f(i) = (i+k)\bmod r \text{ for $i$ in the range } r^{k-1}\le i < r^k,$$ which is to say $$f(i) = (i+\lfloor \log_r (rk)\rfloor) \bmod r,$$ which can be computed by examining the base $r$ representation of $i$ and not evaluating the logarithm directly.

Or, for another example in this vein, if $i$ has base $r$ representation $i=\sum_k b_k r^k$ for $0\le b_k<r$, to let $f(i)=\left(\sum_k b_k\right) \bmod r$. For instance, if $r=2$ this is the parity of the binary digits in the base 2 representation of $i$. These examples are especially easy to compute and not periodic in the precise sense of the word.

All of the above use the particular definition of "uniformly distributed" that is explained in the cited article.