Patrick van Logchem's Entry for the Unique Random Numbers Generator

Question: Patrick van Logchem's Entry for the Unique Random Numbers Generator

Challenge: a custom Delphi function, Randomizer, takes an open integer array and should fill it with unique random numbers as fast as possible.

The code is submitted for the Unique Random Numbers Delphi Challenge

Answer: Unique random number generator entry by Patrick van Logchem (The Netherlands):

 unit PatrickvanLogchem_Randomizer;
 
 interface
 
 
 (*
 The algorithm used is based on the
 "Galois Linear Feedback Shift Register (LFSR)". This algorithm
 generates a unique non-repeating sequence of numbers, which
 avoids the need to check for duplicate elements. A special case
 is available for a MaxValue that fits in a 32-bit variable.
 
 Sources :
 http://en.wikipedia.org/wiki/Linear_feedback_shift_register
 http://tog.acm.org/GraphicsGems/gems/Dissolve.c
 http://www.mactech.com/articles/mactech/Vol.06/06.12/SafeDissolve/index.html
 *)
 procedure Randomizer(const MaxValue: Int64; var Values: array of Int64) ;
 
 implementation
 
 // Disables loop-unrolling; shortens code, slows down a little.
 {$DEFINE RANDOMIZER_UseLoopUnrolling}
 
 {$INLINE ON}
 {$RANGECHECKS OFF}
 {$OPTIMIZATION ON}
 {$OVERFLOWCHECKS OFF}
 
 // Note : If the compiler complains about UInt64,
 // uncomment the next line:
 // type UInt64 = Int64;
 
 // No bits set returns 0, left-most bit returns 32, right-most bit returns 1
 function GetLeftmostBitNr(const aValue: Cardinal): Integer;
 asm
   CMP EAX, 0
   JE @@1
 
   BSR EAX, EAX
   INC EAX
 @@1:
 end;
 
 procedure Randomizer(const MaxValue: Int64; var Values: array of Int64) ;
 const
   // Masks to generate the pseudo-random sequence.
   // The table runs 0..32, but only elements 2..32 are valid.
   SeqMasks32: array [0..32] of Cardinal = ($00000000,
     $00000000, $00000003, $00000006, $0000000C, $00000014, $00000030, $00000060, $000000B8,
     $00000110, $00000240, $00000500, $00000CA0, $00001B00, $00003500, $00006000, $0000B400,
     $00012000, $00020400, $00072000, $00090000, $00140000, $00300000, $00400000, $00D80000,
     $01200000, $03880000, $07200000, $09000000, $14000000, $32800000, $48000000, $A3000000) ;
   // Masks 32..64
   SeqMasks64: array [1..32] of UInt64 = (
     $0000000100080000, $0000000204000003, $0000000500000000, $0000000801000000,
     $000000100000001F, $0000002000000031, $0000004400000000, $000000A000140000,
     $0000012000000000, $00000300000C0000, $0000063000000000, $00000C0000030000,
     $00001B0000000000, $0000300003000000, $0000420000000000, $0000C00000180000,
     $0001008000000000, $0003000000C00000, $0006000C00000000, $0009000000000000,
     $0018003000000000, $0030000000030000, $0040000040000000, $00C0000600000000,
     $0102004000000000, $0200004000000000, $0600003000000000, $0C00000000000000,
     $1800300000000000, $3000000000000030, $6000000000000000, $D800000000000000) ;
 
   procedure _Randomizer32(const MaxValue: Cardinal) ;
   var
     Mask: Cardinal;
     Current: Cardinal;
     ValuePtr: PAnsiChar;
     k: Integer;
   begin
     Mask := SeqMasks32[GetLeftmostBitNr(MaxValue)];
     Current := 0;
     ValuePtr := @(Values[0]) ;
     k := Length(Values) ;
 {$IFDEF RANDOMIZER_UseLoopUnrolling}
     while k > 4 do
     begin
       repeat
         Current := (Current shr 1) xor (Mask and Cardinal(-1+(Current and 1))) ;
       until Current < MaxValue;
       PCardinal(ValuePtr+(0 * SizeOf(Cardinal)))^ := 1 + Current;
       PCardinal(ValuePtr+(1 * SizeOf(Cardinal)))^ := 0;
 
       repeat
         Current := (Current shr 1) xor (Mask and Cardinal(-1+(Current and 1))) ;
       until Current < MaxValue;
       PCardinal(ValuePtr+(2 * SizeOf(Cardinal)))^ := 1 + Current;
       PCardinal(ValuePtr+(3 * SizeOf(Cardinal)))^ := 0;
 
       repeat
         Current := (Current shr 1) xor (Mask and Cardinal(-1+(Current and 1))) ;
       until Current < MaxValue;
       PCardinal(ValuePtr+(4 * SizeOf(Cardinal)))^ := 1 + Current;
       PCardinal(ValuePtr+(5 * SizeOf(Cardinal)))^ := 0;
 
       repeat
         Current := (Current shr 1) xor (Mask and Cardinal(-1+(Current and 1))) ;
       until Current < MaxValue;
       PCardinal(ValuePtr+(6 * SizeOf(Cardinal)))^ := 1 + Current;
       PCardinal(ValuePtr+(7 * SizeOf(Cardinal)))^ := 0;
 
       Inc(ValuePtr, 8 * SizeOf(Cardinal)) ;
 
       Dec(k, 4) ;
     end;
 {$ENDIF RANDOMIZER_UseLoopUnrolling}
 
     while k > 0 do
     begin
       repeat
         Current := (Current shr 1) xor (Mask and Cardinal(-1+(Current and 1))) ;
       // Until we're within range :
       until Current < MaxValue;
 
       PCardinal(ValuePtr + (0 * SizeOf(Cardinal)))^ := 1 + Current;
       PCardinal(ValuePtr + (1 * SizeOf(Cardinal)))^ := 0;
       Inc(ValuePtr, 2 * SizeOf(Cardinal)) ;
 
       Dec(k) ;
     end;
   end;
 
 begin
   if Cardinal(MaxValue shr 32) = 0 then
     _Randomizer32(Cardinal(MaxValue))
   else
     _Randomizer64;
 end;
 
 end.
 

Download Patrick's Unique Randomizer code.

Test data:
- array size: 10 000
- number range: 1 - 100 000

Patrick's speed result: 99 microseconds !!

Explore the list of all accepted entries for the Fastest Unique Random Number Generator Delphi challenge.