Jim McKeeth's Entry for the Unique Random Numbers Generator

Question: Jim McKeeth'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 Jim McKeeth (USA):

 procedure Randomizer_Jim_McKeeth(const maxValue: Int64; var values: array of Int64) ;
 var
   valuesNeeded: Integer;
   count: Integer;
   position: Integer;
   newVal, this, prev: Int64;
 
 function RanomizerSafe(const maxValue : int64; var values : array of int64): Boolean;
 var
   valuesNeeded: Int64;
   lowRange: Int64;
   position: Int64;
 begin
   Result := True;
   valuesNeeded := Length(values) ;
   if valuesNeeded > maxValue then
     raise Exception.Create('Array too large!') ;
   if valuesNeeded = maxValue then
   begin
     lowRange := Low(values) ;
     valuesNeeded := High(Values) ;
     position := lowRange;
     while position <= valuesNeeded do
     begin
       values[position] := position - lowRange + 1;
       inc(position) ;
     end;
     result := false;
     Exit;
   end;
 end;
 
   procedure Insert(const index: Integer; const value: Int64; var values: array of Int64) ;
   begin
     Move(values[Index], values[Index + 1], (Length(values) - Index - 1) * 8) ;
     values[Index] := value;
   end;
 
   function RandomInt64(const ARange: Int64): Int64;
   begin
     if ARange < MaxInt then
     begin
       result := Random(ARange) ;
       Exit;
     end;
     repeat
       Result := Trunc(ARange * Random) ;
     until Result >= 0;
   end;
 
   function RandomRangeInt64(const AFrom, ATo: Int64): Int64;
   begin
     if AFrom > ATo then
       Result := RandomInt64(AFrom - ATo) + ATo
     else
       Result := RandomInt64(ATo - AFrom) + AFrom;
   end;
 
 begin
   if not RanomizerSafe(maxValue, values) then Exit;
 
   valuesNeeded := Length(values) ;
 
   this := RandomInt64(maxValue) ;
   repeat
     newVal := RandomInt64(maxValue) ;
   until this <> newVal;
 
   if this > newVal then
   begin
     values[0] := newVal;
     values[1] := this;
   end
   else
   begin
     values[1] := newVal;
     values[0] := this;
   end;
 
   count := 2;
   while count < valuesNeeded do
   begin
     position := Random(Count + 1) ;
     if position = 0 then
     begin
       this := values[position];
       prev := 0;
     end
     else if position >= count then
     begin
       position := count;
       this := maxValue + 1;
       prev := values[position - 1];
     end
     else
     begin
       this := values[position];
       prev := values[position - 1];
     end;
     if this - 1 = prev then Continue;
     newVal := RandomRangeInt64(prev + 1, this) ;
     if position <> count then
       Insert(position, newVal, values)
     else
       values[position] := newVal;
     Inc(Count) ;
   end;
 end;
 

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

Jim's speed result: 125 milliseconds

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