Delphi BigInt Random без дубликатов
Я использую устройство uBigIntsV4 с компонентом TIntegerК счастью, он имеет встроенный random процедура, которая позволяет вам выбрать очень высокое случайное число и вернуть его в виде строки.
Но я не могу найти способ разработать функцию, которая позволяет мне выбрать большое случайное число из x в n без повторения.
Создание списка или массива невозможно из-за диапазона собственных целых чисел без знака, чтобы охватить все случаи.
Как бы я мог решить это?
2 ответа
Извините, я не знаком с uBigIntsV4. Я надеюсь, что он обладает всеми необходимыми функциями для реализации основных аритметических операций (*, +, мод). Если это так, вы можете использовать следующую формулу для вычисления следующего псевдослучайного числа
и есть только 3 ограничения на значения a, c и m
- m и c относительно простые,
- а-1 делится на все простые множители м
- a-1 делится на 4, если m делится на 4
Смотрите линейный конгруэнтный генератор вики для деталей.
У меня не было много времени, чтобы прокомментировать мой ответ, однако эта библиотека Delphi, которую я создал, позволит вам извлекать случайные числа в диапазоне min-max, всегда отличающиеся от ранее извлеченных, до тех пор, пока их не станет больше. Позже я мог бы расширить, при необходимости, объяснения для этого ответа.
Примечания: Вы должны включить опцию оптимизации компилятора; с помощью GetRndGVNum () вы можете извлечь числа в диапазоне выше 65535, просто увеличив константу 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.