<p>For the requirements</p>

<blockquote>
  <ol>
  <li>generate a sequence of random numbers r_i from a whole number interval I = [-(R+1), R], R > 0 with a statistical distribution like
  java.util.Random</li>
  <li>the sequence r_i must be strictly increasing (r_i > r_j for i > j)</li>
  </ol>
</blockquote>

<p>we could come up with a simple algorithm</p>

<pre><code>A1:
 - draw a random number r_i from I via a library call
 - discard it, if it is less or equal the last draw, try another pick
</code></pre>

<p>The possible complaint would be that this algorithm would probably give not the right number of generated r_i, there is a fuzzy requirement about N=10^12 expected numbers in total</p>

<blockquote>
  <ol start="3">
  <li>"need a generator for many (up to one trillion, 10^12) unique random 64-bit numbers"</li>
  </ol>
</blockquote>

<p>The solution for this would be </p>

<pre><code>A2:
 - to generate N numbers and then 
 - sort them
</code></pre>

<p>However there is another requirement, that there is not enough memory available.</p>

<blockquote>
  <ol start="4">
  <li>"I'd like to use at most a few MB of internal state."</li>
  </ol>
</blockquote>

<p>My conjecture is that it is not possible to fulfill all these requirements at once. </p>

<p>As a compromise I suggest</p>

<pre><code>A3:
 R=2^63 = 9 10^18  
 N=1 Trillion = 10^12
 - divide the range I=[-R,R-1] into N intervals of length (2R+1)/N each 
 - visit each of those intervals (visiting one interval after another)
 - draw a random number from that interval
</code></pre>

<p>This will give N random numbers, in increasing order. </p>

<p><strong>Update:</strong></p>

<p>After skimming the <a href="https://arxiv.org/abs/1702.03154" rel="nofollow noreferrer">BBHash paper</a> and <a href="https://github.com/rizkg/BBHash" rel="nofollow noreferrer">sources</a> a couple of times this is my understanding:</p>

<p>Given some integer set I and a subset S with N=|S| elements, the BBHash procedure will calculate a function f which maps S to some permutation of {1,..,N} (what permutation seems to be implicitly decided by the BBHash procedure) and maps all other elements from I to a special value Imax from I. </p>

<p>Possible tests:</p>

<p>Given S and f one might check if membership in S for some arbitrary element from I is properly calculated.</p>

<p>One might also check if f(S) = {1,..,N}.</p>

<p>My guess is that the requested algorithm is intended to calculate a sample set S for N=10^12 on the fly under tight memory budget, needing uniqueness of the random number sequence rather than monotony.</p>

<p>To quote <a href="https://stackoverflow.com/a/35050835/2579220">https://stackoverflow.com/a/35050835/2579220</a></p>

<blockquote>
  <p>Probabilistic data structures can't give you a definite answer,
  instead they provide you with a reasonable approximation of the answer
  and a way to approximate this estimation. They are extremely useful
  for big data and streaming application because they allow to
  dramatically decrease the amount of memory needed (in comparison to
  data structures that give you exact answers).</p>
  
  <p>In majority of the cases these data structures use hash functions to
  randomize the items. Because they ignore collisions they keep the size
  constant, but this is also a reason why they can't give you exact
  values.</p>
</blockquote>

<p>In case of BBHash a sequence of different hash functions h_i is used. One applies different h_i until no collision occurs. This only works if the input is unique. It will only work if the implementation has enough different h_i in store for the particular S. </p>
Random number generator that returns unique entries in sorted order
<p>I need a generator for many (up to one trillion, 10^12) unique random 64-bit numbers.
The generator needs to return the numbers in sorted order (Long.MIN_VALUE to Long.MAX_VALUE). The problem is that sorting $10^{12}$ numbers is slow. The use case is replicating a test that was run for <a href="https://github.com/rizkg/BBHash" rel="nofollow noreferrer">BBHash</a> (in the <a href="https://arxiv.org/pdf/1702.03154.pdf" rel="nofollow noreferrer">paper</a>, 4.5 Indexing a trillion keys).</p>

<p>The straightforward solution is to create a set in memory, using a huge bit set or so
to ensure no duplicates are returned.
But that uses too much memory or I/O.
I'd like to use at most a few MB of internal state.</p>

<p>The generator should use a java.util.Random internally.
It should be as "fair" as possible (have the same statistical distribution as if generated otherwise). I would also like to have a version for 128-bit numbers (2 longs).</p>

<p>What I have so far is code to create a set in memory (Java code):</p>

<pre><code>public static void main(String... args) {
    for(long x : randomSet(10, 0)) {
        System.out.println(x);
    }
}

static Iterable&lt;Long&gt; randomSet(int size, int seed) {
    Random r = new Random(seed);
    TreeSet&lt;Long&gt; set = new TreeSet&lt;Long&gt;();
    while (set.size() &lt; size) {
        set.add(r.nextLong());
    }
    return set;
}

-8292973307042192125
-7423979211207825555
-6688467811848818630
-4962768465676381896
-2228689144322150137
-1083761183081836303
-279624296851435688
4437113781045784766
6146794652083548235
7105486291024734541
</code></pre>

<p>The simplest (wrong) solution, which is not random, is to distribute the results evenly.
I don't think a solution along the line of "add a random gap" will work,
because it is slow, and the sum of such gaps, after 10^12, will not land where it should (well, maybe: remember how many numbers are left, then re-calculate the distribution...). I think the following should work, but is complex, and not sure what formulas to use: for each bit level,
recursively, calculating how many 0s / 1s will likely occur
(using the Binomial distribution or the approximation, the normal / Gaussian distribution, somehow).
Stop at some point (say, blocks of 1 million entries or less),
use the code above, for speed.
But maybe there is an elegant solution.
Maybe this is related to the Metropolis–Hastings algorithm, not sure.
I read "An Efficient Algorithm for Sequential Random Sampling",
but I think it is only for small n, and I find it hard to get to a simple algorithm from this.</p>

<p>Java code would be best, but C is fine (anyway at some point I might have to convert it to C / C++). I would like to not use too many libraries, to simplify porting.</p>