Qt: Huge number of unique random quint64

Question

I have the following situation: I would like to generate M=500,000 unique random numbers between 10¹⁶ and 2⁶⁴-1. To simplify the situation, we can assume, that we need a number between 1 and N=2⁶⁴-1.

I already found references to this question >here< and >here< and >here<.

But I still have the feeling, that the methods mentioned in the references work if N is much smaller. I.e. it is no option to make a list of all numbers from 1 to N, mix them and take the first M. And somehow I think that there should be a much more effective way than try and error, since M<< N. And M<< N are always given. Therefore the algorithm has not to be good if N-M is small or even N=M. But somehow the big N gives me headache...

Related to this problem I tried to expand qrand() to get a random `quint64 with

quint64 MainWindow::longrand()
{
    quint64 erg=(quint64)qrand();
    for(int i=0;i<4;i++)
        erg=(erg<<(RAND_MAX+1))+qrand();
    erg=(erg<<16)+(qrand()%16);
    return erg;
}

I know that this is not a very good random number, but will it be sufficent or will this gives a problem for some algorithm?

So your whole questions is just whether your `longrand` function is OK? You're not asking about how to organize the large list of numbers and ensure they are unique? — David Grayson, Jun 16 '17 at 05:05
Faced same problem of neither C-runtime rand nor qrand able to generate quality random set. That is handled with modern C++ since C++11. No additional framework needed: https://stackoverflow.com/questions/14009637/c11-random-numbers — Alexander V, Jun 16 '17 at 05:34
@David: No, I'd like to ask both. First, are there a method which works O(M) without 2^64 flags? Second, does my longrand() work good enough for that method or will it yield problems? — Mundron Schmidt, Jun 16 '17 at 08:57
Why do you want numbers to be in that specific range? Your problems seems to be related to Universally Unique Identifier, see [`QUuid`](http://doc.qt.io/qt-5/quuid.html) — m7913d, Jun 16 '17 at 13:19

score 0 · Accepted Answer · answered Jun 16 '17 at 16:21

2^64-1 is a 64 bit number. DES uses a 64 bit block size. Using a fixed key, encrypt the numbers 0, 1, 2, 3, 4, ... with DES in ECB mode for as many numbers as you need. Because the inputs are unique and the key is fixed the 64-bit outputs are also guaranteed unique.

If a 64-bit number is < 10^16 just reject it and go on to the next input integer. That will happen about 1 in every 1,800 numbers (2^64 / 10^16).

If you record the key and the last number used you can add more numbers to the list as needed.

I assume there is a C++ DES implementation you can run from Qt.

Qt: Huge number of unique random quint64

1 Answers1