1

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.

Andrew Tatomyr
  • 111
  • I do not understand what the term "reflection" has to do with this. -- Also, you can compute the linear congruential generator without depending on previous results. Simply compute $f(x)=ax+b\bmod m$ afresh for each new $x$. It is just a lot easier and faster to compute $f(x)$ if you already know $f(x-1)$ (and you do not even need to now the infinite precision integer $x$) – Hagen von Eitzen May 18 '19 at 11:00
  • Doesn't $f(x) = ax + b$ mod $m$ eventually repeats itself, do it? – Andrew Tatomyr May 18 '19 at 11:10
  • would word 'transformation' work better than 'reflection'? – Andrew Tatomyr May 18 '19 at 11:17

1 Answers1

1

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.

kimchi lover
  • 24,277
  • Thanks a lot! Your answer is correct, however I forgot to mention that using an irrational number is prohibited since precise calculating of them for a very long $i$ is actually the problem I'm trying to avoid :) – Andrew Tatomyr May 19 '19 at 12:16
  • My third suggestion does not involve irrationals, but I'm sure you'll come up with some objection to it, of the form that your stated conditions are not your real conditions. – kimchi lover May 19 '19 at 14:05
  • You're right. It looks like the third option eventually will lead to a self-repeating pattern for any rational $k$, won't it? Still I will doublecheck it when I have an opportunity. – Andrew Tatomyr May 20 '19 at 16:39
  • I don't think you understood my 3d example. I have rewritten it. – kimchi lover May 20 '19 at 17:57