-2
$\begingroup$

Is it possible to create $O(1)$ memory consuming algorithm, which is generating non-repeating pseudo random numbers?

I can remember numbers in the hash set and it will be $O(1)$ time, but the set will grow as numbers generated as $O(N)$. Is it possible to do $O(1)$?

UPDATE

Narrowing the question: we have parameter $N$. We need to generate all numbers from 1 to $N$ without repetition in (pseudo) random order.

UPDATE 2

May be there are reversible hash functions? I would compute just $H(i)$ then.

$\endgroup$
2
$\begingroup$

First, you should precisely define what you mean by random. One way to interpret you question is as follows. Given some fixed number $N$, you wish to sample elements from the uniform distribution over the set $\{1,...,N\}$. Let us denote by $S$ the set of samples seen so far, then we want to support a $Gen$ command, which upon calling returns a uniformly chosen element from $\{1,...,N\}\setminus S$. $Gen$ has access to additional memory $q\in\{0,1\}^*$ (the state), which can be altered upon invocation.

It can be easily shown that you cannot achieve the above goal while keeping $q$'s length bounded by some constant. Suppose $|q|\le c$ for some $c\in\mathbb{N}$, and choose $N$ such that $N > 2^c$. Consider the random variable $x_1,...,x_N$ obtained by invoking $Gen$ $N$ times. The difference in the distributions of $x_i,x_j$ depends solely on $q_i,q_j$ (the state during the sampling). Since there are less than $N$ possible states (values of $q$), there exists $i\neq j$ such that $x_i,x_j$ are drawn from the same distribution, contradiction.

$\endgroup$
  • $\begingroup$ How this works for repeating (usual) numbers? $\endgroup$ – Dims Mar 11 '18 at 15:45
  • 1
    $\begingroup$ I don't understand the question. What are usual numbers, and where did I use unusual numbers? $\endgroup$ – Ariel Mar 11 '18 at 15:47
  • $\begingroup$ "Usual numbers" are pseudorandom numbers available in all (most) modern computer languages. $\endgroup$ – Dims Mar 11 '18 at 15:56
  • 2
    $\begingroup$ I'm sorry, but I have no idea what you're talking about or how it relates to the question/answer. Pseudorandomness has a precise meaning in computer science, so I wouldn't use it unless you have a precise notion in mind. If my modeling in the first paragraph indeed reflects what you were trying to achieve, then the second paragraph proves that this is not possible (no hash or other magic tricks would help). $\endgroup$ – Ariel Mar 11 '18 at 16:27
  • $\begingroup$ I don't require $2^c<N$, just $c << N$. Let it be $2^c=10 N$ $\endgroup$ – Dims Mar 11 '18 at 21:30
1
$\begingroup$

Take any bijective memoryless function $f$ that scrambles the bits and use the sequence $f(i)$ for $i\in[0,N)$.

For instance, Gray codes.

$\endgroup$
  • $\begingroup$ Nice construction. That achieves the non-repeating part of the goal, but unfortunately not the "pseudorandom" part (at least, using Gray codes doesn't). $\endgroup$ – D.W. Mar 11 '18 at 17:26
0
$\begingroup$

Many pseudo-random number generating algorithms naturally produce a very long sequence of unique numbers, and the repeat the sequence. Of course if you have a sequence length of $2^{128}$ then the sequence is not repeating.

So the solution: If you need non-repeating numbers in the range 1 to n you use a PRNG with a cycle not longer than n. If n is small, it’s not going to be very random.

$\endgroup$
  • 1
    $\begingroup$ It should be mentioned that no matter what you do, if your PRNG has a state of $b$ bits it will at most output $2^b$ numbers before repeating. $\endgroup$ – orlp Mar 11 '18 at 11:46
0
$\begingroup$

Effectively what you want to compute is some permutation of a sequence of numbers $\{1, \ldots, n\}$.

Let $p_1$ and $p_2$ be two prime numbers. It can be shown that the sequence

$$(p_1)^1 \text{ mod } p_2, (p_1)^2 \text{ mod } p_2, (p_1)^3 \text{ mod } p_2, \ldots, (p_1)^{p_2} \text{ mod } p_2$$

does not have repetitions. So if you want to get a pseudo-random permutation of the numbers $\{1, \ldots, n\}$, you can set $p_2$ to be a prime number higher than $n$ and select $p_1$ somehow (e.g., close to 1/4 of $p_1$). Then, when enumerating the sequence above, you just drop all elements greater than n.

Note that the resulting sequence is only somewhat random according to some statistical tests.

$\endgroup$
0
$\begingroup$

No.

Any deterministic algorithm with bounded memory has a finite number of states and every state always leads to the same next state.

So whatever you generate will be periodical, with a period not excceding $2^S$for $S$ bits of memory.

$\endgroup$
  • $\begingroup$ Although not clearly specified, I believe the question is not really about PRGs, but given access to a truly random source, how to avoid repetitions while minimizing memory usage (see my interpretation). $\endgroup$ – Ariel Mar 11 '18 at 15:49
  • $\begingroup$ @Ariel I am not limiting sources, only memory. $\endgroup$ – Dims Mar 11 '18 at 15:59
  • $\begingroup$ The question specifies pseudorandom. $\endgroup$ – David Richerby Mar 11 '18 at 21:23
  • $\begingroup$ @DavidRicherby: this aswer was before the updates. Consider undownvoting. $\endgroup$ – Yves Daoust Mar 11 '18 at 21:59
  • $\begingroup$ @YvesDaoust Oh. I'd assumed that everything before "UPDATE:" had been there since day one. How annoying. I've undone my vote; you might consider deleting this answer, since it doesn't apply to the question any more. $\endgroup$ – David Richerby Mar 11 '18 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.