Pseudo random, unqiue integer numbers in a given range 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?
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).