Generating huge amounts of unique random numbers (theoretical)

Question

This is a theoretical question; it's something I've thought about as a computer science enthusiast and am trying to understand the logic and methodology that might be (or is being) used to approach this problem.

Problem: Assume you have a number space to roam around in for some sort of ID value. You need to generate RANDOM numbers within this space.

Requirements:

• No number should be generated more than once, forever, within this number space. It's OK for your "generate" algorithm to fail when all numbers are exhausted. It's better for it to fail than to silently generate duplicates, but at least it should exhaust all numbers before doing dupes. The generated numbers would be used as unique ID values.
• A local set of generated numbers should be as random as possible. For example:
  • If 100 numbers are generated in one second, and then another 100 numbers are generated at a rate of one per day, there should be little to no detectable difference in the "randomness" of the set.
  • Given a number or even a set of numbers, it should be "as impossible as possible" to statistically analyze those numbers to determine characteristics like the time they were generated, how fast, etc.
• For this thought experiment, assume that an overlapping ID is the WORST case scenario and cannot be allowed to occur. (For example, assume that an overlapping ID might result in a huge security breach, resulting in a lawsuit that puts your organization in a proverbial cardboard box on a rainy day.) However, statistically analyzable strings of numbers could also prove detrimental - example: if someone can figure out a pattern, they can guess the IDs and access others' private data.

There are four approaches I've considered for generating these huge sets of unique numbers:

• The naive approach: Just use a big number space and use a cryptographic algorithm based number generator. The idea is that in theory the key space should be so large that given a good algorithm it's "unlikely enough" that two values might overlap. This MIGHT be enough if you can use a large enough number space for your IDs, like 256 bits. But if you have to limit your IDs to say 64 bits, the chance of overlap becomes far too great.
• The horribly unscalable approach: Each time a number is generated, search for it in the list of already generated numbers. This works fine for small data sets, but imagine if you had 50 trillion IDs generated, and now you had to scan that list each time just to ensure that the ID you just generated isn't used.
• The "scalable" approach: Same as the previous idea, but build an optimized database that is able to do fast queries on enormous data sets. A simplistic approach that is actually used is to, say, make 100 tables - all numbers ending with the digits 00 end up in the first, 01 in the next, and so on - and then you can narrow down and optimize your DB query quite quickly.
• Use an algorithm like the GUID algorithm to generate guaranteed unique numbers. This is inappropriate because the GUID does have a "structure" and most generators will follow it, thus its data is not random, just unique.

Of course, I get there is no "best" option for this without considering an actual use case. I'm more interested in just the thought and logic experiment that this sort of problem takes me on, and am interested to hear if anyone else has used other techniques or at least thought of other ones to approach a problem like this. You do see something at least partly similar to this in, say, YouTube with the video IDs. Of course Google is the company that can "search the Internet" for you in less than a second, so their approach may not be appropriate for "everyone else".

Answer 1

Maybe my library will work for you (or help)? This is a generator which init with O(1) time complexity. Intn() method (get new random number) take O(1) time complexity since no duplicate/conflict will occur. During the usage, worst space complexity is O(N).

If all numbers used up, a panic will be throw, and no number will be wasted. The library use lock to implement concurrency safety, may think about lock-free method in the future.

Here is the link:
https://github.com/yihaoye/lurand

Simple explain:

Use a map[int]int to implement large-scale unique random number generation.
For example, start by generating random numbers between 0 and 1,000,000.
Suppose the random number generated is 999. If the map does not have this number as a key,
return this number and store the current last available number (e.g., 999,999) in this key-value pair,
i.e., <999: 999,999>. Then, the next random number should be generated between 0 and 999,998 (decrement max by 1).
Similarly, if the next random number's key exists in the map, return its value,
and overwrite it with the last available number, while decrementing max by 1.
This is similar to the Fisher–Yates Shuffle

Answer 2

I can think of two solutions not yet mentioned, although they may be simple and/or inefficient.

Generate a list containing the set of all possibilities in the space, randomly shuffle it, and then pull your ID numbers by sequentially by index. Although it guarantees uniqueness and is more CPU efficient than randomizing the index position pulled and checking against past IDs for each new ID generated, it suffers from the same high storage and is less secure (via breaking the initial shuffle).

Use Cantor's Diagonalization proof to generate a tree of unique IDs. Although this will eventually produce a set containing all possible IDs, the order in which they're generated will be based on the random generation of 0 or 1 at every branch. You could further randomize the process exponentially by applying combinations of methods like:

• Running an iteration LSB->MSB || MSB->LSB
• Starting a given iteration at different bit positions
• Splitting each full ID into multiple sub-IDs, running the same (or different, if you wanna get really random) iterative conditions on each of them, and then reassembling them.

Answer 3

Using the scalable approach, beyond the occupying of memory, the slowing down of the extraction takes place. However, assuming to have a space of N numbers, if it is represented by a one-dimensional array, to carry out the extraction of a number of such space I will have to perform, on average, an amount of (N / 2) iterations; but if this space is a square matrix, for example, for each number that I extract, I will have, on average, an amount of (Sqrt (N) / 2 + Sqrt (N) / 2) iterations; it is the row search and the column search: less iterations. With a 3-dimensional matrix the number of iterations is even smaller: ( N ^ (1/3) / 2 + N ^ (1/3) / 2 + N ^ (1/3) / 2), and so on, increasing the number of dimensions of the structure associated with the number space, the number of overall iterations is always smaller. Obviously for each dimension above the first one, I have to take into account the number of available elements of the immediately smaller dimension of the vector space.

For example, I report this unit, written in assembler (protected mode) under Delphi. To extract 2 ^ 27 numbers, the GetRndGRNum () function, on an old ACER TravelMate 4220 laptop, takes 37 seconds:

unit x;

interface

Const GRMinCellValue=-1 ShL 31;
  GRMaxDeltaNum=(1 ShL 27)-1;

Type   {2} TGRData0=Record
   {1}  GRNumArrAmount0,
   {1}  GRNumArr0:Byte;
       End;
  {16} TGRArr1=Array [0..7] Of TGRData0;
  {17} TGRData1=Record
   {1}  GRNumArrAmount1:Byte;
  {16}  GRNumArr1:TGRArr1;
       End;
 {136} TGRArr2=Array [0..7] Of TGRData1;
 {137} TGRData2=Record
   {1}  GRNumArrAmount2:Byte;
 {136}  GRNumArr2:TGRArr2;
       End;
{1096} TGRArr3=Array [0..7] Of TGRData2;
{1097} TGRData3=Record
   {1}  GRNumArrAmount3:Byte;
{1096}  GRNumArr3:TGRArr3;
       End;
{8776} TGRArr4=Array [0..7] Of TGRData3;
{8777} TGRData4=Record
   {1}  GRNumArrAmount4:Byte;
{8776}  GRNumArr4:TGRArr4;
       End;
   {70216} TGRArr5=Array [0..7] Of TGRData4;
   {70217} TGRData5=Record
   {1}  GRNumArrAmount5:Byte;
   {70216}  GRNumArr5:TGRArr5;
       End;
  {561736} TGRArr6=Array [0..7] Of TGRData5;
  {561737} TGRData6=Record
   {1}  GRNumArrAmount6:Byte;
  {561736}  GRNumArr6:TGRArr6;
       End;
 {4493896} TGRArr7=Array [0..7] Of TGRData6;
 {4493897} TGRData7=Record
   {1}  GRNumArrAmount7:Byte;
 {4493896}  GRNumArr7:TGRArr7;
       End;
{35951176} TGRArr8=Array [0..7] Of TGRData7;
{35951185} TGRData8=Record
   {1}  GRNumArrAmount8:Byte;
   {4}  GRNumMin8,
   {4}  GRNumMax8:Integer;
{35951176}  GRNumArr8:TGRArr8;
       End;
       TGRData8Ptr=^TGRData8;
       TRndXSeed=Array[0..3] Of Cardinal;

Var RndXSeed:TRndXSeed=(123456789, (* X: Seed *)
            362436000, (* Y: Must be <>0 *)
            521288629, (* Z: Must be <>0 *)
            7654321);  (* C: Must be <>0 *)

Function  GetPtr         (PValue:Integer):Pointer;

{Trasforma il valore PValue IN un PUNTATORE POINTER.

 NOTE: È scritta IN ASSEMBLER.

   Non chiama alcuna Sub-ROUTINE.

   Testata con successo}

Function  GetPtrValue    (P:Pointer):Integer;

{Converte il PUNTATORE P IN un valore.

 NOTE: È scritta IN ASSEMBLER.

   Non chiama alcuna Sub-ROUTINE.

   Testata con successo}

Procedure MyFillChar     (M:Pointer;S,V:Cardinal);

{ Analoga alla System.FillChar(), ma più veloce.

  NOTE: è scritta interam. IN ASSEMBLER.

    Non effettua alcun salto (CALL, Jmp o salto condizionato),
    ed è molto veloce.

    Per impostare a 0 la VAR. A
    (di tipo BYTE, WORD, SMALLINT o INTEGER):

    MyFillChar(@A,SIZEOF(A),0);

    Per impostare a 0 la VAR. A
    (di tipo T=RECORD):

    MyFillChar(@A,SIZEOF(A),0) }

Procedure ReSetGRConfig  (GRConfig:TGRData8Ptr;
              Min,Max:Integer);

(* (Re)inizializza l' estrazione di numeri casuali,
   compresi tra Min e Max, con GetRndGRNum(GRConfig).

   I valori ammessi per Min e Max
   vanno da -2147483647 a +2147483647,
   ma il numero massimo di numeri
   che si possono estrarre è 134217728.

   Se Min e Max costituiscono un range troppo ampio,
   sarà ristretto il suddetto range e
   sarà alzato il valore minimo.

   è possibile specificare Min>Max *)

Function  GetRndGRNum    (GRConfig:TGRData8Ptr):Integer;

(* Estrae un numero casuale nel range Min-Max sempre
   diverso da quelli estratti precedentemente.

   Ritorna GRMinCellValue (-2147483648)
   se non ci sono altri numeri da estrarre.

   Inizializzare l' estrazione con ReSetGRConfig(GRConfig,Min,Max) *)

implementation

Uses Math;

Function  GetPtr(PValue:Integer):Pointer; Assembler;

Asm

 Mov   EAX,PValue

End;

Function  GetPtrValue(P:Pointer):Integer; Assembler;

Asm

 Mov   EAX,P

End;

Procedure MyFillChar(M:Pointer;S,V:Cardinal); Assembler;

Asm

 Push  EDI

 Mov   EDI,M (* EAX *)
 Mov   EAX,V (* ECX *)
 Mov   ECX,S (* EDX *)

 ClD

 Mov   AH,AL
 Mov   DX,AX
 ShL   EAX,16
 Mov   AX,DX

 Mov   EDX,ECX
 ShR   ECX,2
 Rep   StoSD

 SetB  CL
 Rep   StoSW

 Test  DL,1
 SetNE CL
 Rep   StoSB

 Pop   EDI

End;

Procedure ReSetGRConfig(GRConfig:TGRData8Ptr;
            Min,Max:Integer);

Var I0,I1,I2,I3,I4,I5,I6,I7,I8:Byte;
Diff,Amount,Filled:Integer;

Begin

 Inc(Min,Integer(Min=GRMinCellValue));

 Diff:=Max-Min+Integer(Max=GRMinCellValue);
 Dec(Diff,Integer(Abs(Diff)>GRMaxDeltaNum)*
      (Diff-Sign(Diff)*GRMaxDeltaNum));

 Filled:=0;

 If Assigned(GRConfig) Then
  With GRConfig^ Do
   Begin

GRNumMin8:=Max-Diff*Integer(Diff>=0);

Diff:=Abs(Diff);

GRNumMax8:=GRNumMin8+Diff;

Amount:=Diff+1;

I8:=0;
Inc(Filled,9);

While (I8<8) And (Amount<>0) Do
 With GRNumArr8[I8] Do
  Begin
   I7:=0;
   Inc(Filled);
   While (I7<8) And (Amount<>0) Do
    With GRNumArr7[I7] Do
     Begin
      I6:=0;
      Inc(Filled);
      While (I6<8) And (Amount<>0) Do
       With GRNumArr6[I6] Do
    Begin
     I5:=0;
     Inc(Filled);
     While (I5<8) And (Amount<>0) Do
      With GRNumArr5[I5] Do
       Begin
        I4:=0;
        Inc(Filled);
        While (I4<8) And (Amount<>0) Do
         With GRNumArr4[I4] Do
          Begin
           I3:=0;
           Inc(Filled);
           While (I3<8) And (Amount<>0) Do
        With GRNumArr3[I3] Do
         Begin
          I2:=0;
          Inc(Filled);
          While (I2<8) And (Amount<>0) Do
           With GRNumArr2[I2] Do
            Begin
             I1:=0;
             Inc(Filled);
             While (I1<8) And (Amount<>0) Do
              With GRNumArr1[I1] Do
               Begin
            I0:=Integer((8+Amount-Abs(8-Amount)) ShR 1);
            GRNumArrAmount0:=I0;
            GRNumArr0:=0;
            Dec(Amount,I0);
            Inc(Filled,2);
            Inc(I1);
               End;
             GRNumArrAmount1:=I1;
             Inc(I2);
            End;
          GRNumArrAmount2:=I2;
          Inc(I3);
         End;
           GRNumArrAmount3:=I3;
           Inc(I4);
          End;
        GRNumArrAmount4:=I4;
        Inc(I5);
       End;
     GRNumArrAmount5:=I5;
     Inc(I6);
    End;
      GRNumArrAmount6:=I6;
      Inc(I7);
     End;
   GRNumArrAmount7:=I7;
   Inc(I8);
  End;

GRNumArrAmount8:=I8;

(* 108'000'000= $66ff300

   I6=7, I5=7, I4=16, I3=16, I2=3, I1=16, I0=16 = $7700300 *)

MyFillChar(GetPtr(GetPtrValue(GRConfig)+Filled),
       SizeOf(GRConfig^)-Filled,0);

   End;

End;

Function GetRndGRNum(GRConfig:TGRData8Ptr):Integer; Assembler;

Var Am7P,
Am6P,
Am5P,
Am4P,
Am3P,
Am2P,
Am1P,
GRData8Ptr:Integer;
RndN0,
RndN1,
RndN2,
RndN3,
RndN4,
RndN5,
RndN6,
RndN7,
RndN8,
RC7,
RC6,
RC5,
RC4,
RC3,
RC2,
RC1,
RC0:Byte;

Asm

 Push  EDI          { Salva il registro EDI sullo STACK }

  (* ---------------------------------------- *)

 Mov   EDI,GRConfig     { Carica         GRConfig (EAX) nel reg. EDI }

 Mov   EAX,GRMinCellValue   { Carica il reg. di output con GRMinCellValue }

 Or    EDI,EDI          { Se GRConfig=Nil ... }
 JE    @@00         { ... Ha finito, esce }

 Cmp   Byte Ptr [EDI],0     { Se GRConfig^.GRNumArrAmount6=0 ... }
 JE    @@00         { ... Ha finito, esce }

 Mov   GRData8Ptr,EDI       { Salva GRConfig su GRData8Ptr }

  (* ======================================== *)

 LEA   EDI,RndXSeed     { Carica in EDI l' offs. di MyStrUt.MyRndXSeed }

  (* ---------------------------------------- *)
  (* - Generaz. di un num. casuale a 32 Bit - *)
  (* ---------------------------------------- *)

 Mov   EAX,[EDI]
 Mov   EDX,69069
 Mul   EDX
 Add   EAX,12345
 Mov   [EDI],EAX    // RndXSeed[0]:=69069*RndXSeed[0]+12345;

 Mov   EAX,[EDI+4]
 ShL   EAX,13
 XOr   [EDI+4],EAX  // RndXSeed[1]:=RndXSeed[1] XOr (RndXSeed[1] ShL 13);

 Mov   EAX,[EDI+4]
 ShR   EAX,17
 XOr   [EDI+4],EAX  // RndXSeed[1]:=RndXSeed[1] XOr (RndXSeed[1] ShR 17);

 Mov   EAX,[EDI+4]
 ShL   EAX,5
 XOr   [EDI+4],EAX  // RndXSeed[1]:=RndXSeed[1] XOr (RndXSeed[1] ShL 5);

 Mov   EAX,[EDI+8]
 Mov   EDX,698769069
 Mul   EDX
 Add   EAX,[EDI+12]
 AdC   EDX,0        // EDX:EAX:=698769069*RndXSeed[2]+RndXSeed[3];

 Mov   [EDI+12],EDX // RndXSeed[3]:=T ShR 32;

 Cmp   EAX,[EDI+8]
 Mov   EAX,0
 SetE  AL

 Or    EDX,EDX
 SetE  DL

 And   AL,DL       // EAX:=Cardinal(RndXSeed[2]=T)

 Add   EAX,[EDI]
 Add   EAX,[EDI+4] // RndX:=RndXSeed[0]+RndXSeed[1]+Cardinal(RndXSeed[2]=T);

  (* ---------------------------------------- *)
  (* - Fine generazione numero casuale ------ *)
  (* ---------------------------------------- *)

 Mov   DL,AL            { Carica i 7 Bit meno significat ... }
 And   DL,127           { ... del numero casuale generato ... }
 Mov   RndN0,DL         { ... in RndN0 }

 ShR   EAX,7

 Mov   DL,AL            { Carica i 7 Bit meno significat ... }
 And   DL,127           { ... del numero casuale generato ... }
 Mov   RndN1,DL         { ... in RndN1 }

 ShR   EAX,7

 Mov   DL,AL            { Carica i 7 Bit meno significat ... }
 And   DL,127           { ... del numero casuale generato ... }
 Mov   RndN2,DL         { ... in RndN2 }

 ShR   EAX,7

 Mov   DL,AL            { Carica i 7 Bit meno significat ... }
 And   DL,127           { ... del numero casuale generato ... }
 Mov   RndN3,DL         { ... in RndN3 }

 ShR   EAX,7

 Mov   RndN4,AL

  (* ---------------------------------------- *)
  (* - Generaz. di un num. casuale a 32 Bit - *)
  (* ---------------------------------------- *)

 Mov   EAX,[EDI]
 Mov   EDX,69069
 Mul   EDX
 Add   EAX,12345
 Mov   [EDI],EAX

 Mov   EAX,[EDI+4]
 ShL   EAX,13
 XOr   [EDI+4],EAX

 Mov   EAX,[EDI+4]
 ShR   EAX,17
 XOr   [EDI+4],EAX

 Mov   EAX,[EDI+4]
 ShL   EAX,5
 XOr   [EDI+4],EAX

 Mov   EAX,[EDI+8]
 Mov   EDX,698769069
 Mul   EDX
 Add   EAX,[EDI+12]
 AdC   EDX,0

 Mov   [EDI+12],EDX

 Cmp   EAX,[EDI+8]
 Mov   EAX,0
 SetE  AL

 Or    EDX,EDX
 SetE  DL

 And   AL,DL

 Add   EAX,[EDI]
 Add   EAX,[EDI+4]

  (* ---------------------------------------- *)
  (* - Fine generazione numero casuale ------ *)
  (* ---------------------------------------- *)

 Mov   DL,AL
 And   DL,7
 ShL   DL,4
 Or    RndN4,DL

 ShR   EAX,3

 Mov   DL,AL            { Carica i 7 Bit meno significat ... }
 And   DL,127           { ... del numero casuale generato ... }
 Mov   RndN5,DL         { ... in RndN5 }

 ShR   EAX,7

 Mov   DL,AL            { Carica i 7 Bit meno significat ... }
 And   DL,127           { ... del numero casuale generato ... }
 Mov   RndN6,DL         { ... in RndN6 }

 ShR   EAX,7

 Mov   DL,AL            { Carica i 7 Bit meno significat ... }
 And   DL,127           { ... del numero casuale generato ... }
 Mov   RndN7,DL         { ... in RndN7 }

 ShR   EAX,7

 And   AL,127
 Mov   RndN8,AL

 Mov   EDI,GRData8Ptr       { Carica GRConfig in EDI }

  (* ======================================== *)
  (* = Ricerca del record TGRData7  ========= *)
  (* ======================================== *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr8[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData8.GRNumArr8-TYPE(TGRData7) { EDI <- OFFSET ... }
                { ... GRConfig^.GRNumArr8-SizeOf(TGRData7) }

  (* ---------------------------------------- *)

@@L8:Add   EDI,TYPE(TGRData7)   { EDI += SizeOf(TGRData7) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr8[CL].GRNumArrAmount7<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L8         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   Am7P,EDI         { Salva OFFS(GRNumArr8[CL].GRNumArrAmount7) ...}
                {  ... (EDI) in Am7P }
 Mov   RC7,CL           { Salva RC (CL) in RC7 }

  (* ======================================== *)
  (* = Ricerca del record TGRData6  ========= *)
  (* ======================================== *)

 Mov   AL,RndN7

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr7[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData7.GRNumArr7-TYPE(TGRData6) { EDI <- OFFSET ... }
                { ... GRConfig^.GRNumArr7-SizeOf(TGRData6) }

  (* ---------------------------------------- *)

@@L7:Add   EDI,TYPE(TGRData6)   { EDI += SizeOf(TGRData6) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr7[CL].GRNumArrAmount6<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L7         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   Am6P,EDI         { Salva OFFS(GRNumArr7[CL].GRNumArrAmount6) ...}
                {  ... (EDI) in Am6P }
 Mov   RC6,CL           { Salva RC (CL) in RC6 }

  (* ======================================== *)
  (* = Ricerca del record TGRData5  ========= *)
  (* ======================================== *)

 Mov   AL,RndN6

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr6[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData6.GRNumArr6-TYPE(TGRData5) { EDI <- OFFSET ... }
                { ... GRConfig^.GRNumArr6-SizeOf(TGRData5) }

  (* ---------------------------------------- *)

@@L6:Add   EDI,TYPE(TGRData5)   { EDI += SizeOf(TGRData5) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr6[CL].GRNumArrAmount5<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L6         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   Am5P,EDI         { Salva OFFS(GRNumArr6[CL].GRNumArrAmount5) ...}
                {  ... (EDI) in Am5P }
 Mov   RC5,CL           { Salva RC (CL) in RC5 }

  (* ======================================== *)
  (* = Ricerca del record TGRData4  ========= *)
  (* ======================================== *)

 Mov   AL,RndN5

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr5[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData5.GRNumArr5-TYPE(TGRData4) { EDI <- OFFSET ... }
                { ... TGRData5.GRNumArr5-SizeOf(TGRData4) }

  (* ---------------------------------------- *)

@@L5:Add   EDI,TYPE(TGRData4)   { EDI += SizeOf(TGRData4) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr5[CL].GRNumArrAmount4<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L5         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   Am4P,EDI         { Salva OFFS(GRNumArr5[CL].GRNumArrAmount4) ...}
                {  ... (EDI) in Am4P }
 Mov   RC4,CL           { Salva RC (CL) in RC4 }

  (* ======================================== *)
  (* = Ricerca del record TGRData3  ========= *)
  (* ======================================== *)

 Mov   AL,RndN4

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr4[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData4.GRNumArr4-TYPE(TGRData3) { EDI <- OFFSET ... }
                { ... TGRData4.GRNumArr4-SizeOf(TGRData3) }

  (* ---------------------------------------- *)

@@L4:Add   EDI,TYPE(TGRData3)   { EDI += SizeOf(TGRData3) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr4[CL].GRNumArrAmount3<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L4         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   Am3P,EDI         { Salva OFFS(GRNumArr4[CL].GRNumArrAmount3) ...}
                {  ... (EDI) in Am3P }
 Mov   RC3,CL           { Salva RC (CL) in RC3 }

  (* ======================================== *)
  (* = Ricerca del record TGRData2  ========= *)
  (* ======================================== *)

 Mov   AL,RndN3

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr3[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData3.GRNumArr3-TYPE(TGRData2) { EDI <- OFFSET ... }
                { ... TGRData3.GRNumArr3-SizeOf(TGRData2) }

  (* ---------------------------------------- *)

@@L3:Add   EDI,TYPE(TGRData2)   { EDI += SizeOf(TGRData2) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr3[CL].GRNumArrAmount2<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L3         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   Am2P,EDI         { Salva OFFS(GRNumArr3[CL].GRNumArrAmount2) ...}
                {  ... (EDI) in Am2P }
 Mov   RC2,CL           { Salva RC (CL) in RC2 }

  (* ======================================== *)
  (* = Ricerca del record TGRData1  ========= *)
  (* ======================================== *)

 Mov   AL,RndN2

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr2[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData2.GRNumArr2-TYPE(TGRData1) { EDI <- OFFSET ... }
                { ... TGRData2.GRNumArr2-SizeOf(TGRData1) }

  (* ---------------------------------------- *)

@@L2:Add   EDI,TYPE(TGRData1)   { EDI += SizeOf(TGRData1) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr2[CL].GRNumArrAmount1<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L2         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   Am1P,EDI         { Salva OFFS(GRNumArr2[CL].GRNumArrAmount1) ...}
                {  ... (EDI) in Am1P }
 Mov   RC1,CL           { Salva RC (CL) in RC1 }

  (* ======================================== *)
  (* = Ricerca del record TGRData0  ========= *)
  (* ======================================== *)

 Mov   AL,RndN1

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{EDI: GRNumArr1[CL].
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Add   EDI,OFFSET TGRData1.GRNumArr1-TYPE(TGRData0) { EDI <- OFFSET ... }
                { ... TGRData1.GRNumArr1-SizeOf(TGRData0) }

  (* ---------------------------------------- *)

@@L1:Add   EDI,TYPE(TGRData0)   { EDI += SizeOf(TGRData0) }
 Inc   CL           { RC += 1 }

 Cmp   Byte Ptr [EDI],1     { Se GRNumArr1[CL].GRNumArrAmount0<>0, ... }
 CmC                { ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L1         { Se VC<>0, ripete il ciclo }

  (* ---------------------------------------- *)

 Mov   RC0,CL           { Salva RC (CL) in RC0 }

  (* ======================================== *)
  (* = Ricerca del Bit selezionato  ========= *)
  (* ======================================== *)

 Mov   AL,RndN0

  (* ---------------------------------------- *)

 Mov   AH,[EDI]         { AH <- GRConfig^.GRNumArrAmount6 (amount) }

{in:127=out:amount-1
 out<-in*amount/128}

 Mul   AH           { AX <- in*amount }
 ShR   AX,7         { AL <- in*amount/128 }
 Inc   AL           { AL <- in*amount/128+1 }

  (* ---------------------------------------- *)

{ DX: GRNumArr0.
  AL: VC.
  CL: RC.
  CH: Temp=0}

 Mov   CX,255           { RC <- -1; Temp <- 0}

 Mov   DL,[EDI+OFFSET TGRData0.GRNumArr0] { DL <- TGRData0.GRNumArr0 }

  (* ---------------------------------------- *)

@@L0:Inc   CL           { RC += 1 }

 ShR   DL,1         { GRNumArr0>>1 }
 CmC                { Se FCarry=0 ... }
 SbB   AL,CH            { ... VC -= 1 }

 JNE   @@L0         { Se VC<>0, ripete il ciclo }

  (* ======================================== *)

 Mov   DL,1         { ... }
 ShL   DL,CL            { ... DL <- 1<<RC }

 Or    [EDI+OFFSET TGRData0.GRNumArr0],DL { Marca il num. come già estratto}

  (* ---------------------------------------- *)

 Mov   EDX,GRData8Ptr       { Carica GRConfig in EDX }

 Dec   Byte Ptr [EDI]       { TGRData0.GRNumArrAmount0 -= 1 }
 JNE   @@01         { Se TGRData0.GRNumArrAmount0<>0, salta }

 Mov   EDI,Am1P         { Carica OFFS(TGRData1.GRNumArrAmount1) in EDI }
 Dec   Byte Ptr [EDI]       { TGRData1.GRNumArrAmount1 -= 1 }
 JNE   @@01         { Se TGRData1.GRNumArrAmount1<>0, salta }

 Mov   EDI,Am2P         { Carica OFFS(TGRData2.GRNumArrAmount2) in EDI }
 Dec   Byte Ptr [EDI]       { TGRData2.GRNumArrAmount2 -= 1 }
 JNE   @@01         { Se TGRData2.GRNumArrAmount2<>0, salta }

 Mov   EDI,Am3P         { Carica OFFS(TGRData3.GRNumArrAmount3) in EDI }
 Dec   Byte Ptr [EDI]       { TGRData3.GRNumArrAmount3 -= 1 }
 JNE   @@01         { Se TGRData3.GRNumArrAmount3<>0, salta }

 Mov   EDI,Am4P         { Carica OFFS(TGRData4.GRNumArrAmount4) in EDI }
 Dec   Byte Ptr [EDI]       { TGRData4.GRNumArrAmount4 -= 1 }
 JNE   @@01         { Se TGRData4.GRNumArrAmount4<>0, salta }

 Mov   EDI,Am5P         { Carica OFFS(TGRData5.GRNumArrAmount5) in EDI }
 Dec   Byte Ptr [EDI]       { TGRData5.GRNumArrAmount5 -= 1 }
 JNE   @@01         { Se TGRData5.GRNumArrAmount5<>0, salta }

 Mov   EDI,Am6P         { Carica OFFS(TGRData6.GRNumArrAmount6) in EDI }
 Dec   Byte Ptr [EDI]       { TGRData6.GRNumArrAmount6 -= 1 }
 JNE   @@01         { Se TGRData6.GRNumArrAmount6<>0, salta }

 Mov   EDI,Am7P         { Carica OFFS(TGRData7.GRNumArrAmount7) in EDI }
 Dec   Byte Ptr [EDI]       { TGRData7.GRNumArrAmount7 -= 1 }
 JNE   @@01         { Se TGRData7.GRNumArrAmount7<>0, salta }

 Dec   Byte Ptr [EDX]       { GRConfig^.GRNumArrAmount8 -= 1 }

  (* ---------------------------------------- *)

@@01:MovZX EAX,RC7          { EAX <- pos. ("Real Count.") r. TGRData7 trov.}

 ShL   Al,3         { EAX <<= 3 }
 Or    AL,RC6           { EAX |= pos. ("Real Count.") r. TGRData6 trov.}

 ShL   AX,3         { EAX <<= 3 }
 Or    AL,RC5           { EAX |= pos. ("Real Count.") r. TGRData5 trov.}

 ShL   AX,3         { EAX <<= 3 }
 Or    AL,RC4           { EAX |= pos. ("Real Count.") r. TGRData4 trov.}

 ShL   AX,3         { EAX <<= 3 }
 Or    AL,RC3           { EAX |= pos. ("Real Count.") r. TGRData3 trov.}

 ShL   EAX,3            { EAX <<= 3 }
 Or    AL,RC2           { EAX |= pos. ("Real Count.") r. TGRData2 trov.}

 ShL   EAX,3            { EAX <<= 3 }
 Or    AL,RC1           { EAX |= pos. ("Real Count.") r. TGRData1 trov.}

 ShL   EAX,3            { EAX <<= 3 }
 Or    AL,RC0           { EAX |= pos. ("Real Count.") r. TGRData0 trov.}

 ShL   EAX,3            { EAX <<= 3 }
 Or    AL,CL            { EAX |= pos. Bit selezionato }

  (* ---------------------------------------- *)

 Add   EAX,[EDX+OFFSET TGRData8.GRNumMin8] { Somma GRConfig^.GRNumMin8 ... }
                { ... al numero cas. gen. }

  (* ======================================== *)

@@00:Pop   EDI          { Ripristina il registro EDI dallo STACK }

End;

end.

Answer 4

If you do not have to generate numbers of a particular length, then you can generate unique random numbers as follows:

• Divide the number space into a unique part and a random part.
• The unique part is simply a sequentially assigned number, starting at 0. The unique number generation fails when the last number has already been generated.
• The random part is a random number generated using a cryptographic RNG. Since the unique part already ensures uniqueness, there is no worry about the risk of generating duplicate random parts.

For the purposes of this answer, the sizes of the unique part and the random part are arbitrary. For most practical purposes, the unique part should be at least 64 bits long and the random part should be at least 128 bits long.

Answer 5

A well-known algorithm is to use some sequence of values in the number-space -- for a range of a power of two, you could use a linear congruential sequence, for example -- and then encrypt the values. Since an encryption function must be an isomorphism -- otherwise accurate decryption wouldn't be possible -- this cannit repeat until the base sequence wraps around.

Of course, you'll want to protect your encryption key, and also whatever parameters you're using for the underlying sequence, and the difficulty of maintaining these secrets is an issue. But the output values are certainly going to look random. You will have to balance the possible security issues with the needs of your real problem domain.

Some cyclic generators can be advanced by k generations in O(1). If you choose one of these, you can parallelise the "random" number generation by handing each parallel process with an appropriate seed. If a process runs through all k of its values, it just asks a master server for a new range allocation or does it itself if it can access the persistent storage.

Answer 6

This is a theoretical answer.

Since No number should be generated more than once, forever, within this number space, the algorithm effectively generates some permutation of the number space. This hints that it should pick a certain permutation, and generate it sequentially.

If the space size is N, there are N! possible permutations. Given the permutation index, it is pretty easy to generate it, one element at a time. Select a permutation randomly, and do generate it.

It is possible that a selected permutation would be an identity (producing a 0, 1, 2, ... sequence of IDs). It doesn't look very random, but the attacker still is not able to predict it.

Answer 7

I presume that you know in advance how many random numbers you want.

I would suggest using the scalable approach with a Bloom filter for your optimized lookup. Note that a Bloom filter does not store the actual values, and has a chance of thinking it has seen a value that it hasn't. Neither is a significant detriment in this case, and it is virtually impossible to predict which numbers will be falsely accused of having been seen when they haven't.

You can size the filter to trade off memory and how many random numbers you need. Sizing it so that at the end your false positive rate is 10% will make generating numbers slower, but will take less memory, than having the false positive rate be 1%. For very large data sets, a Bloom filter can easily be parallelized to run across multiple machines. For very large data sets that you want to produce very quickly, you can even have a two-level hash where the top level determines which subset of hash functions will be checked, and the second runs against the saved data. This design lets you parallelize both checks across machines, with load balancing at the first. This will allow insane throughput.

The one important drawback is that you have to decide in advance how big the final pool of random numbers is. Because once the filter is clogged with too much data, you can't readily resize it.