Генерация огромного количества уникальных случайных чисел (теоретическое)

Question

Это теоретический вопрос;Это то, о чем я думал как энтузиаст информатики и пытаюсь понять логику и методологию, которые могут (или используются) использоваться для решения этой проблемы.

Проблема: Предположим, у вас есть номерное пространство длябродить вокруг для какого-то значения идентификатора.Вам нужно генерировать СЛУЧАЙНЫЕ номера в этом пространстве.

Требования:

• Ни одно число не должно генерироваться более одного раза, навсегда, в этом числовом пространстве. Это нормально, если ваш алгоритм "генерирования" не работает, когдавсе числа исчерпаны.Лучше потерпеть неудачу, чем тихо генерировать дубликаты, но по крайней мере он должен исчерпать все числа, прежде чем делать дубли.Сгенерированные числа будут использоваться как уникальные значения идентификатора.
• Локальный набор сгенерированных чисел должен быть как можно более случайным.Например:
  • Если за одну секунду генерируется 100 чисел, а затем генерируются еще 100 чисел с частотой один раз в день, то обнаруживаемая разница в «случайности» набора должна быть незначительной или не обнаруживаться.
  • Учитывая число или даже набор чисел, должно быть "как можно более невозможным" статистический анализ этих чисел для определения характеристик, таких как время, когда они были сгенерированы, как быстро и т. Д.
• Для этого мысленного эксперимента предположим, что перекрывающийся идентификатор - это НАИБОЛЕЕ сценарий случая, и его нельзя допустить.(Например, предположим, что перекрывающийся идентификатор может привести к серьезному нарушению безопасности, что приведет к судебному иску, в результате которого ваша организация окажется в общеизвестной картонной коробке в дождливый день.) Однако статистически анализируемые строки чисел также могут оказаться вредными - пример:если кто-то может выяснить схему, он может угадать идентификаторы и получить доступ к личным данным других.

Существует четыре подхода, которые я рассмотрел для генерации этих огромных наборов уникальных чисел:

• Наивный подход: просто используйте большое числовое пространство и используйте генератор чисел на основе криптографического алгоритма.Идея состоит в том, что теоретически пространство ключей должно быть настолько большим, чтобы при хорошем алгоритме "маловероятно", чтобы два значения могли перекрываться.Этого МОЖЕТ быть достаточно, если вы можете использовать достаточно большое числовое пространство для своих идентификаторов, например, 256 бит.Но если вам нужно ограничить свои идентификаторы до 64 бит, вероятность совпадения становится слишком большой.
• Ужасно невероятный подход: каждый раз, когда число генерируется, ищите его в списке уже сгенерированных чисел,Это прекрасно работает для небольших наборов данных, но представьте, что у вас было сгенерировано 50 триллионов идентификаторов, и теперь вам приходилось каждый раз сканировать этот список, чтобы убедиться, что только что созданный вами идентификатор не используется.
• The "масштабируемый подход: такой же, как и в предыдущей идее, но создать оптимизированную базу данных, способную выполнять быстрые запросы к огромным наборам данных.Упрощенный подход, который фактически используется, состоит в том, чтобы, скажем, создать 100 таблиц - все числа, заканчивающиеся цифрами 00, заканчиваются на первом, 01 на следующем и т. Д. - и тогда вы можете сузить и оптимизировать свой запрос к БД.быстро.
• Используйте алгоритм, такой как алгоритм GUID, для генерации гарантированных уникальных чисел.Это неуместно, потому что GUID имеет «структуру», и большинство генераторов будут следовать ей, поэтому его данные не случайные , а просто уникальные.

Конечно, я попал тудане является «лучшим» вариантом для этого без учета фактического варианта использования.Меня больше интересует только мысленно-логический эксперимент, над которым меня заводит такая проблема, и мне интересно узнать, использовал ли кто-то другой метод или хотя бы подумал о других для решения такой проблемы.Вы видите что-то хотя бы частично похожее на это, скажем, на YouTube с идентификаторами видео.Конечно, Google - это компания, которая может «искать вас в Интернете» менее чем за секунду, поэтому их подход может не подходить для «всех остальных».

Answer 1

Если вам не нужно генерировать числа определенной длины, вы можете сгенерировать уникальных случайных чисел следующим образом:

• Разделите пространство чисел на уникальная часть и случайная часть.
• уникальная часть представляет собой просто последовательно назначенный номер, начиная с 0. Генерация уникального номера завершается неудачно, когда последнийномер уже сгенерирован.
• random - это случайное число, сгенерированное с использованием криптографического RNG.Поскольку уникальная часть уже обеспечивает уникальность, нет риска беспокоиться о возможности создания дубликатов случайных частей.

Для целей этого ответа размеры уникальной части и случайной части являются произвольными.В большинстве практических целей уникальная часть должна иметь длину не менее 64 бит, а произвольная часть должна быть длиной не менее 128 бит.

Answer 2

Используя масштабируемый подход, помимо использования памяти, происходит замедление извлечения.Тем не менее, предполагая наличие пространства из N чисел, если оно представлено одномерным массивом, для извлечения некоторого числа таких пространств мне придется выполнить в среднем величину (N / 2)итераций;но если это пространство является квадратной матрицей, например, для каждого числа, которое я извлекаю, у меня будет в среднем количество (Sqrt (N) / 2 + Sqrt (N) / 2) итераций;это поиск по строке и по столбцу: меньше итераций.С 3-мерной матрицей число итераций еще меньше: (N ^ (1/3) / 2 + N ^ (1/3) / 2 + N ^ (1/3) / 2) и т. Д.,При увеличении числа измерений структуры, связанной с пространством чисел, количество полных итераций всегда меньше.Очевидно, что для каждого измерения выше первого, я должен принимать во внимание количество доступных элементов сразу меньшего измерения векторного пространства.

Например, я сообщаю об этом модуле, написанном на ассемблере (защищенный режим) под Delphi.Чтобы извлечь 2 ^ 27 чисел, функция GetRndGRNum () на старом ноутбуке ACER TravelMate 4220 занимает 37 секунд:

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 3

Это теоретический ответ.

Поскольку Никакое число не должно генерироваться более одного раза, навсегда, в этом числовом пространстве , алгоритм эффективно генерирует некоторую перестановкучислового пространства.Это намекает на то, что он должен выбрать определенную перестановку и сгенерировать ее последовательно.

Если размер пространства равен N, существует N! возможных перестановок.Учитывая индекс перестановки, довольно просто сгенерировать его , по одному элементу за раз.Выберите случайную перестановку и сгенерируйте ее.

Возможно, что выбранная перестановка была бы идентичностью (производя последовательность 0, 1, 2, ... идентификаторов). не выглядит очень случайным, но злоумышленник все еще не может его предсказать.

Answer 4

Хорошо известный алгоритм состоит в том, чтобы использовать некоторую последовательность значений в числовом пространстве - для диапазона степеней два, например, вы можете использовать линейную конгруэнтную последовательность - и затем зашифровать значения.Поскольку функция шифрования должна быть изоморфизмом - в противном случае точное дешифрование было бы невозможным - это невозможно повторить, пока базовая последовательность не обернется.

Конечно, вы захотите защитить свой ключ шифрования, итакже любые параметры, которые вы используете для основной последовательности, и сложность сохранения этих секретов является проблемой.Но выходные значения будут выглядеть случайными.Вам придется сбалансировать возможные проблемы безопасности с потребностями вашей реальной проблемной области.

Некоторые циклические генераторы могут быть усовершенствованы на k поколений в O (1).Если вы выберете один из них, вы можете распараллелить генерацию «случайных» чисел, передав каждому параллельному процессу соответствующее начальное число.Если процесс выполняет все k своих значений, он просто запрашивает у главного сервера новое распределение диапазона или делает это сам, может ли он получить доступ к постоянному хранилищу.

Answer 5

Я предполагаю, что вы заранее знаете, сколько случайных чисел вы хотите.

Я бы предложил использовать масштабируемый подход с фильтром Блума для оптимизированного поиска.Обратите внимание, что фильтр Блума не хранит фактические значения и может думать, что он видел значение, которого у него нет.В этом случае также нет существенного вреда, и практически невозможно предсказать, какие цифры будут ложно обвинены в том, что они были замечены, когда их не было.случайные числа вам нужны.Если изменить размер так, чтобы в конце ваш уровень ложных срабатываний составлял 10%, генерирование чисел замедлялось, но занимало меньше памяти, чем если бы уровень ложных срабатываний составлял 1%.Для очень больших наборов данных фильтр Блума может быть легко распараллелен для работы на нескольких машинах.Для очень больших наборов данных, которые вы хотите создать очень быстро, вы можете даже иметь двухуровневый хеш, где верхний уровень определяет, какое подмножество хеш-функций будет проверяться, а второй - для сохраненных данных.Эта конструкция позволяет распараллеливать обе проверки на разных машинах, сначала с балансировкой нагрузки.Это обеспечит безумную пропускную способность.

Один важный недостаток заключается в том, что вы должны заранее решить, насколько велик конечный пул случайных чисел.Потому что, как только фильтр забит слишком большим количеством данных, вы не сможете легко изменить его размер.