1
$\begingroup$

I need an algorithm that gives me integer numbers with the following features:

  • Numbers must be in a given range $[n..m]$;

  • Numbers must be returned in pseudo-random order (random at visual inspection is enough; it is more important that numbers are well distributed over the given range);

  • Numbers may not repeat before each number in the range $[n..m]$ has been returned once;

  • Range may be huge (up to $2^{64}$; this excludes all list/shuffle based algorithms);

  • It should be possible to seed the function so it returns numbers in different order on repetition;

  • Algorithm should be as fast as possible and should return in constant time.

I wrote code that uses table based bit swapping and optionally XOR and/or addition. It works very well for bit-aligned $n$ and $m$. However it is a bit slow and if the range $n..m$ is not aligned to bits (i.e., $n$ other than $2^x$ and $m$ other than $2^y$), I get either gaps within the returned numbers or extremely non-constant runtime behavior.

How can this be solved?

$\endgroup$
  • 1
    $\begingroup$ If the range is huge, numbers won't repeat. If generating, say, $2^{20}$ numbers out of a random of size $2^{64}$, a repeat is rather unlikely (happens with probability less than $2^{-25}$). $\endgroup$ – Yuval Filmus Sep 26 '17 at 22:03
  • $\begingroup$ "seed the function so it returns numbers in different order": do you mean the same numbers ? $\endgroup$ – Yves Daoust Sep 27 '17 at 14:06
  • $\begingroup$ @Yuval: This does not work since I need up to $2^{64}$; numbers. Also the numbers in the range may not have gaps. I.e. I need to get all the numbers within $[n..m]$. $\endgroup$ – Silicomancer Sep 27 '17 at 20:14
  • $\begingroup$ @Yves: Yes, the same number in the range $[n..m]$ (but in a different order and beginning with a differnt number out of $[n..m]$) $\endgroup$ – Silicomancer Sep 27 '17 at 20:15
  • $\begingroup$ @Silicomancer: sorry, this answer is still ambiguous. $\endgroup$ – Yves Daoust Sep 28 '17 at 7:41
3
$\begingroup$

Without loss of generality, we can assume you need numbers in the range $\{0,..,n-1\}$. (Just add the appropriate offset.)

This can be solved by constructing a random permutation $f:\{0,\dots,n-1\} \to \{0,\dots,n-1\}$, then outputting the values $f(0),f(1),f(2),f(3),\dots$ as your sequence of pseudorandom numbers. Those numbers won't repeat until each number in the range has been defined. If $f$ can be computed efficiently, this will be fast.

So how do we construct such a random function $f$? One approach is to use format-preserving encryption, a technique from cryptography that allows you to construct a function $f$ that is a bijection on the set $\{0,\dots,n-1\}$ (for any $n$ of your choice), and that appears pseudorandom. There are many FPE algorithms.

See https://blog.cryptographyengineering.com/2011/11/10/format-preserving-encryption-or-how-to/ and https://crypto.stackexchange.com/questions/tagged/format-preserving for more (e.g., https://crypto.stackexchange.com/q/41450/351, https://crypto.stackexchange.com/q/504/351, https://crypto.stackexchange.com/q/29073/351, https://crypto.stackexchange.com/q/20035/351, https://crypto.stackexchange.com/q/16561/351, https://crypto.stackexchange.com/q/18988/351).

$\endgroup$
  • $\begingroup$ I will need some time. I agree your way of solving the problem is the right one. But currently I don't understand how to implement such a function without restricting it to bit aligned ranges. All of those algorithms seem to operate on bits and bytes. $\endgroup$ – Silicomancer Sep 27 '17 at 20:34
  • $\begingroup$ @Silicomancer, you can build format-preserving encryption for any range (the size of the range doesn't need to be a power of two, i.e., it doesn't need to be bit-aligned). Study the techniques and if you still don't see how to do it, ask on Crypto.SE or here. It may help to give a specific value of $n$, as I think the best technique varies depending on whether $n$ is small or large. $\endgroup$ – D.W. Sep 27 '17 at 20:55
1
$\begingroup$

You can use a Linear Feedback Shift Register to generate a maximum length sequence that cycles through all numbers that fit into the size of the LFSR without repetition. This is used in computer games for the so-called Fizzlefade effect. LFSRs are really efficient, so this might fit your performance requirements.

(This is of course a special case of the general technique mentioned by D.W.)

$\endgroup$
  • 1
    $\begingroup$ I tried something similar. However this is restricted to number ranges that are aligned to bits as well since it works bit oriented. $\endgroup$ – Silicomancer Sep 27 '17 at 20:19
  • $\begingroup$ This only works if the size of the range is a power of two. $\endgroup$ – D.W. Sep 27 '17 at 20:55
  • $\begingroup$ In the worst case you have to throw away half the numbers you generate, no? $\endgroup$ – adrianN Sep 28 '17 at 7:31

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.