Delphi BigInt Random without Duplicates

Question

I am using the unit uBigIntsV4 with the component TInteger Fortunately it has a built in random procedure, which let's you choose a very high random number and return it as a string.

But I can't find a way to develop a function which lets me pic a high random number from x to n without being repeated.

Creating a list or an array is not possible due to native unsigned integers's range to cover all cases.

How would I be able to solve this?

But how? Many numbers require large arrays or lists to be stored... I can't just allocate an array that is larger than an unsigned integer. — Ben, Dec 10 '16 at 22:28
OK, I picked the wrong dupe. But if you search you will find an accurate one. Clearly you are the first person to face this problem. Search for sampling without replacement. That's the key phrase. Don't worry about language. It's the algorithm that matters. — David Heffernan, Dec 10 '16 at 22:34
But I guess since the prospect of collision is rare your best bet is to simply sample and discard any duplicates. — David Heffernan, Dec 10 '16 at 22:48
Maybe not the best but you could generate random nums, sort the array and you can easily find duplicates now looking at the previous item in the list — Alberto Miola, Dec 11 '16 at 01:15
As a variation on a theme of previous comments, since the number is returned as a string, perhaps a TStringList with duplicates prohibited, setting the Duplicates property to dupIgnore and checking the count after an attempted assignment, or setting it to dupError and catching the exception raised. — Dsm, Dec 11 '16 at 15:48
And if the range is small enough then you can do the ring work in plain integers and shift later to the true range — David Heffernan, Dec 11 '16 at 15:54

score 2 · Answer 1 · answered Dec 14 '16 at 22:14

Sorry I'm not familiar with uBigIntsV4. I hope it has all the required functionality to implement basic arythmetic operations (*, +, mod). If so you may use the folowing formula to calculate the next pseudo random number

and there are anly 3 restictions on the a, c and m values

m and c are relatively prime,
a-1 is divisible by all prime factors of m
a-1 is divisible by 4 if m is divisible by 4

See Linear congruential generator wiki for details.

Paolo Fassin · Answer 2 · 2018-11-17T10:18:53.637

I did not have much time to comment on my answer, however this Delphi library that I created, will allow you to extract random numbers, in a range min-max, always different from those previously extracted, until until there are more. Later I could expand, if required, the explanations for this answer.

Notes: You must enable the compiler optimization option; with GetRndGVNum () you can extract numbers in a range higher than 65535, simply increasing the constant DefGVNumArrSize (range = DefGVNumArrSize * 8).

Unit so;

{$A-}
{$B-}
{$U+}
{$W-}

interface

Const DefGVNumArrSize=8192;

      MinCellValue=-1 ShL 31;

      MaxDeltaNum=DefGVNumArrSize*8-1;

Type TGVNumArr=Array[0..DefGVNumArrSize-1] Of Byte;

     TGVConfig=Record
      {0} GVNumArrAmount,
      {4} GVNumArrMin:Integer;
      {8} GVNumArr:TGVNumArr;
     End;

Var MyRandSeed:Integer=0;

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

{ Similar to the System.FillChar (), but faster.

  NOTE: it is written entirely IN ASSEMBLER.

        Skip not required (CALL, JMP or conditional jump),
        and it's very fast.

        To set the VAR to 0. A
        (of type BYTE, WORD, SMALLINT or INTEGER):

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

        To set the VAR to 0. A
        (type T = RECORD):

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

Function  CopyInt            (IntIn:Integer;
                              IntPtrOut:Pointer):Integer;

{Set the BOOLEAN parameter to IntPtrOut ^ with IntIn e
 returns IntIn.

 NOTE: It is written IN ASSEMBLER.

 RESTRICTIONS: None}

Procedure MyInitRand;

{Initialize the glob. VAR. MyRandSeed for the function MyRandInt ().

 RESTRICTIONS: None}

Function  MyRandInt          (Min,Max:Integer):Integer;

{Returns a random number between MIN and MAX (inclusive).

 RESTRICTIONS: None.

 NOTES: Permitted MIN> MAX.

        Allow integer values with 32-bit SIGN for MIN and MAX.

        Use a 32-bit conversion of Turbo-PASCAL System.RandInt ()}

Procedure ReSetGVConfig      (Var GVConfig:TGVConfig;
                              Min,Max:Integer);

(* (Re) initializes the extraction of random numbers,
    between Min and Max, with GetRndGVNum (GVConfig).

    The values allowed for Min and Max
    range from -2147483647 to +2147483647,
    but the maximum number of numbers
    which can be extracted is 65536.

    If Min and Max constitute a too wide range,
    the aforementioned range e will be restricted
    the minimum value will be raised.

    you can specify Min> Max *)

Function  GetRndGVNum        (Var GVConfig:TGVConfig):Integer;

(* Extracts a random number in the Min-Max range at all times
   different from those previously extracted.

   Return to MinCellValue (-2147483648)
   if there are no other numbers to extract.

   Initialize the extraction with ReSetGVConfig (GVConfig, Min, Max) *)

Procedure RndGVNum_Test      (GVMin,GVMax:Integer);

(* Test program of this library *)

implementation

Uses Math,SysUtils;

Function CopyInt(IntIn:Integer;IntPtrOut:Pointer):Integer; Assembler;
(* EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
   Can freely modify the EAX, ECX, AND EDX REGISTERs *)
Asm

     Mov   EAX,IntIn

     Mov   [EDX],EAX

End;

Procedure MyFillChar(M:Pointer;S,V:Cardinal); Assembler;
(* EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
   Can freely modify the EAX, ECX, AND EDX REGISTERs. *)
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 MyInitRand;

Begin
 MyRandSeed:=Round(Frac(Time)*4294967295);
End;

Function NextRand:Cardinal; Assembler;
{ EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
  Can freely modify the EAX, ECX, AND EDX REGISTERs. }
Asm

     Push  EDI

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

     LEA   EDI,MyRandSeed

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

     MovZX EAX,Word Ptr [EDI]   { RandSeed.w0 }
     Mov   CX,8405H

     Mul   CX                   { New = Old.w0 * 8405H }

     Mov   CX,[EDI]

     ShL   CX,3                 { New.w2 += Old.w0 * 808H }

     Add   Ch,CL
     Add   DX,CX

     Mov   CX,[EDI+2]

     Add   DX,CX                { New.w2 += Old.w2 * 8405H }

     ShL   CX,2

     Add   DX,CX
     Add   DH,CL

     ShL   CX,5

     Add   DH,CL

     Add   AX,1
     AdC   DX,0                 { New += 1 }

     ShL   EDX,16
     Or    EAX,EDX              { EDX= DX:AX }

     Mov   [EDI],EAX

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

     Pop   EDI

End;

Function MyRandInt(Min,Max:Integer):Integer; Assembler;
{ EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
  Can freely modify the EAX, ECX, AND EDX REGISTERs. }
Asm

     Push   ESI
     Push   EDI

     Mov    ESI,Max        {A}
     Mov    EDI,Min        {B}

    {$IFDEF Delphi_7_Plus}

     Mov    ECX,EDI
     Cmp    EDI,ESI

     CMovGE EDI,ESI        {MIN}
     CMovGE ESI,ECX        {MAX}

    {$ELSE}

     XOr    ECX,ECX
     Sub    EDI,ESI
     Mov    EAX,EDI
     SetGE  CL
     Dec    ECX

     And    EDI,ECX
     Add    EDI,ESI

     Not    ECX

     And    EAX,ECX
     Add    ESI,EAX

    {$ENDIF}

     Sub    ESI,EDI
     Inc    ESI            {ESI= MAX-MIN+1}

     Call   NextRand       {EAX= 32 Bit Random number}

     Mul    ESI            {EDX:EAX= EAX*(MAX-MIN+1)}

     Add    EDX,EDI
     Mov    EAX,EDX        {@RESULT= EAX*(MAX-MIN+1)/(65536*65536)+MIN}

     Pop    EDI
     Pop    ESI

End;

Procedure ReSetGVConfig(Var GVConfig:TGVConfig;
                        Min,Max:Integer);

Var Diff:Integer;

Begin

 With GVConfig Do
  Begin

   Inc(Min,Integer(Min=MinCellValue));
   Diff:=Max-Min+
         Integer(Max=MinCellValue);
   Dec(Diff,
       Integer(Abs(Diff)>MaxDeltaNum)*
               (Diff-Sign(Diff)*MaxDeltaNum));

   GVNumArrAmount:=Abs(Diff)+1;
   GVNumArrMin:=Max-Diff*Integer(Diff>=0);

   MyFillChar(@GVNumArr,SizeOf(GVNumArr),0);

  End;

End;

Function GetRndGVNum(Var GVConfig:TGVConfig):Integer; Assembler;
{ EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
  Can freely modify the EAX, ECX, AND EDX REGISTERs. }
Asm

     Push  EBX
     Push  ESI
     Push  EDI

     Mov   EDI,GVConfig

     Mov   EAX,MinCellValue
     Mov   EDX,[EDI+OFFSET TGVConfig.GVNumArrAmount]

     Or    EDX,EDX
     JE    @@00

     Mov   EAX,1

     Call  MyRandInt

    {EDI: GRConfig.GRNumArr[I].
     EAX: VC.
     EBX: I.
     ECX: RC.
      DH: Mask}

     Mov   DH,128                          {Mask}
     Mov   EBX,OFFSET TGVConfig.GVNumArr-1 {I}
     Mov   ECX,-1                          {RC}

     XOr   ESI,ESI

    {-----------}

@@01:RoL   DH,1
     AdC   EBX,ESI

     Inc   ECX

     Mov   DL,[EDI+EBX]
     And   DL,DH
     Sub   DL,DH
     SbB   EAX,ESI

     JNE   @@01

    {-----------}

     Or    [EDI+EBX],DH

     Dec   DWord Ptr [EDI+OFFSET TGVConfig.GVNumArrAmount]

     Add   ECX,[EDI+OFFSET TGVConfig.GVNumArrMin]
     Mov   EAX,ECX

@@00:Pop   EDI
     Pop   ESI
     Pop   EBX

End;

Procedure RndGVNum_Test(GVMin,GVMax:Integer);

Var Num,Max,Count:Integer;
    GVConfig:TGVConfig;

Begin

 MyInitRand;

 Count:=0;

 ReSetGVConfig(GVConfig,GVMin,GVMax);

 Max:=GVConfig.GVNumArrMin+
      GVConfig.GVNumArrAmount-1;

 WriteLn;

 While (CopyInt(GetRndGVNum(GVConfig),@Num)<>MinCellValue) Do
  Begin
   Write(Num,#9);
   Inc(Count);
  End;

 WriteLn;
 WriteLn;

 WriteLn('Minimum value:');
 WriteLn(GVMin);

 WriteLn('Maximum value:');
 WriteLn(GVMax);

 WriteLn('New minimum value:');
 WriteLn(GVConfig.GVNumArrMin);

 WriteLn('New maximum value:');
 WriteLn(Max);

 WriteLn('Maximum allowed value:');
 WriteLn(GVConfig.GVNumArrMin+MaxDeltaNum);

 WriteLn('Maximum extraction width:');
 WriteLn(MaxDeltaNum+1);

 WriteLn('Total number of numbers generated:');
 WriteLn(Count);

 WriteLn;

 WriteLn('ALL NUMBERS HAVE BEEN EXTRACTS!');
 WriteLn('Try extraction of other 3 numbers:');

 WriteLn;

 WriteLn(GetRndGVNum(GVConfig));
 WriteLn(GetRndGVNum(GVConfig));
 WriteLn(GetRndGVNum(GVConfig));

 WriteLn;
 Write('Press ENTER to exit ... ');

 ReadLn;

End;

End.

Delphi BigInt Random without Duplicates

2 Answers2