Random Numbers

[Blestan]

Hi!
I have to generate several milions of random numbers without repeating them ... any idea of a fast e efficient algorithm?

[Ocye]

How about this?

Code: Pascal  [Select][+][-]

1. uses ..., fgl;
2.  
3. type
4.   TIntegerList = specialize TFPGList<Integer>;
5.   TForm1 = class(TForm)
6.   private
7.     procedure CreateRandomList(const aNumber: longword; var aintList:TIntegerList);
8.   ...
9. end;
10.  
11. ...
12.  
13. function DoRandomize(const Item1, Item2: integer): Integer;
14. begin
15.   Result:=-1+Random(3);
16. end;
17.  
18. procedure TForm1.CreateRandomList(const aNumber: longword;
19.   var aIntList: TIntegerList);
20. var
21.   i:integer;
22. begin
23.   for i:=0 to aNumber-1 do
24.     aIntList.Add(i);
25.   aIntList.Sort(@DoRandomize);
26. end;

[wp]

To me, the random generator shipped with fpc always has been enough, but I don't know about its performance. It it is not sufficient you could try the one provided with AMRandom (http://www.esbconsult.com.au/download.htm); according to its docs it has a cycle length of 3E47.

As a test I would create as many random numbers as you need, store them either in memory or on file, and compare if there are any duplicates.

[User137]

Code: Pascal  [Select][+][-]

1. type
2.   TRandomType = integer;
3.  
4.   TForm1 = class(TForm)
5.     btnGenerate: TButton;
6.     Memo1: TMemo;
7.     procedure btnGenerateClick(Sender: TObject);
8.     procedure FormCreate(Sender: TObject);
9.   private
10.     rnd: array of TRandomType;
11.   public
12.   end;

Code: Pascal  [Select][+][-]

1. procedure TForm1.FormCreate(Sender: TObject);
2. begin
3.   randomize;
4. end;
5.  
6. procedure TForm1.btnGenerateClick(Sender: TObject);
7. var i, j, l: integer; tmp: TRandomType;
8. begin
9.   l:=10000000;
10.   setlength(rnd, l);
11.   for i:=0 to l-1 do rnd[i]:=i;
12.   for i:=0 to l-1 do begin
13.     j:=random(l); // Swap
14.     tmp:=rnd[i];
15.     rnd[i]:=rnd[j];
16.     rnd[j]:=tmp;
17.   end;
18.   // Print results (just first 1000...)
19.   memo1.Lines.Clear;
20.   for i:=0 to 999 do memo1.Lines.Add(inttostr(rnd[i]));
21. end;

It took about 1 second to generate array, but way too long to actually print 10 million of them. Test with 3 or 4 numbers to see that they really are randomized.

[howardpc]

What is a series of 'random' numbers?
Surely it is not a series of numbers in which there can never ever be a repeated number?
Without wanting to start an off-topic debate, by some  criteria of randomness, if you have a set of some millions of numbers none of which is allowed to be a duplicate of another, then you have lost randomness by imposing some order on that set.
But perhaps you are not after 'truly' random numbers per se, but just gathering a well-distributed set of non-identical numbers?

[Thaddy]

To me, the random generator shipped with fpc always has been enough, but I don't know about its performance. It it is not sufficient you could try the one provided with AMRandom (http://www.esbconsult.com.au/download.htm); according to its docs it has a cycle length of 3E47.

As a test I would create as many random numbers as you need, store them either in memory or on file, and compare if there are any duplicates.

The question is about a random set that has no duplicates... In other words a set list with random distribution. Random is not directly suitable for that.
The most efficient algorithm (but deterministic, because the standard  random is deterministic) is generating a sequential list and swap Index[0] with Index [random(x)-1] for x times.  Which is O(n).

Code: Pascal  [Select][+][-]

1. {$APPTYPE CONSOLE}
2.  
3. procedure SwapInt(var a,b:integer);
4. var
5.   t:integer;
6. begin
7.   t:= a;a:=b;b:=t;
8. end;
9.  
10. var
11.   A:array[0..999999] of integer;
12.   i,x:Integer;
13. begin
14. for i := Low(a) to high(a) do
15.   A[i] := i;
16. for i := Low(a) to high(a) do
17.   SwapInt(a[0],a[Random(High(a))]);
18. end.
19.  

[molly]

The most efficient algorithm (but deterministic, because the standard  random is deterministic) is generating a sequential list and swap Index[0] with Index [random(x)-1] for x times.  Which is O(n)

Please do forgive my ignorance on the subject, but isn't that highly inefficient ?.

Can't you (better) use a prng for that ?

[Thaddy]

Can't you (better) use a prng for that ?

Do you know anything about mathematics? See my example that crossed your entry. The only way is O(n) since it is sequential because it needs to be unrepeatable: for the brain deaf, you can't have two occurrences of the same number... Sigh, but anyway Look at my example. That is the most efficient.

The fpc algorithm IS a prng, btw.... YOU SHOULD KNOW BETTER, MOLLY! Shame! (teacher speak )

[molly]

Do you know anything about mathematics?

Not much, that's why i started with excusing myself.

See my example that crossed your entry. The only way is O(n) since it is sequential because it needs to be unrepeatable: for the brain deaf, you can't have two occurrences of the same number... Sigh, but anyway Look at my example. That is the most efficient.

Yes, i understand that each generated number cannot be repeated again... that's why PRNG LCG can be used using a special seed that guarantees for the generated number to be non repetitive _unless_ you managed to 'flip' around the max numbers that can be generated as then indeed the algorithm starts to repeat itself.

I am not an expert, nor do i have the mathematical skills to proof wrong or right. I did come across this article that perhaps explains better what i meant.

See also: In OpenBSD, we designed a non-repeating pseudo-random number generator that was very fast and did not require additional resources.

Ah i noticed to late you added some additional stuff ;-)

The fpc algorithm IS a prng, btw.... YOU SHOULD KNOW BETTER, MOLLY! Shame! (teacher speak )

Yes, i am aware of that ;-)

Please feel free to educate with regards to the links i posted.

Can or can't it be used as a quick alternative for what you proposed (given that the sequence repeats itself when the max generated unique numbers is reached).

[Thaddy]

See also: In OpenBSD, we designed a non-repeating pseudo-random number generator that was very fast and did not require additional resources.

Yes. Look at the implementation. I just did. It is the same algorithm I used....

What I wrote up is the most efficient non-repeating algorithm that is mathematically proven.
It may or not be the most efficient in pascal but it is close.

[wp]

A stupid comment of another non-mathematician: You assume that the floating point random number generator produces repeating results which certainly is true. But how can you be sure that the integer random number generator that you use for swapping the indexes does not produce repeating results as well? Therefore I doubt that your algorithm is "non-repeating" in a strict sense.

[molly]

See also: In OpenBSD, we designed a non-repeating pseudo-random number generator that was very fast and did not require additional resources.

Yes. Look at the implementation. I just did. It is the same algorithm I used....

Oh dear 

Seems i indeed needed the correction so thank you for that. My Bad, attempting to argue with Knuth 

What I wrote up is the most efficient non-repeating algorithm that is mathematically proven.
It may or not be the most efficient in pascal but it is close.

Yes, i agree on that.

Problem is (or at least i assume it is for OP) that using such huge arrays is usually not very practice friendly.

A stupid comment of another non-mathematician: You assume that the floating point random number generator produces repeating results which certainly is true. But how can you be sure that the integer random number generator that you use for swapping the indexes does not produce repeating results as well? Therefore I doubt that your algorithm is "non-repeating" in a strict sense.

I can relate to that, but at the same time i wonder if it really matters ?

I guess it depends on what your definition of random is ? e.g. when a particular index was already swapped before and it will be swapped again, do we really care (unless it is continuously swapping the same index) ?

[Blestan]

i think that i found a good solution .. pretty compact and linear in time. all you need is x×y matrix . where x is the digits needed (length) and y is the alphabet (00..9 or 0 to F or a to z )...i need a very fast  random function in the range of powers of 2 ..lets say 0..16 to 0.128 max. ideas?

[Thaddy]

i think that i found a good solution .. pretty compact and linear in time. all you need is x×y matrix . where x is the digits needed (length) and y is the alphabet (00..9 or 0 to F or a to z )...i need a very fast  random function in the range of powers of 2 ..lets say 0..16 to 0.128 max. ideas?

Which is exactly what I gave as an example.
You can plug in any faster random you can find, but the algorithm is the same. And may I say very short and efficent in Pascal...

[Nitorami]

The fastest generator I am aware of is George Marsaglia's MWC256.

Code: Pascal  [Select][+][-]

1. function MWC256: dword;
2. // MWC256 from Usenet posting by G. Marsaglia - Period 2^8222
3. var t : qword;
4. begin
5.   i := (i+1) AND $FF;
6.   t := qword (809430660) * Q[i] + c;
7.   c      := hi (t);
8.   Q[i]   := lo (t);
9.   result := lo (t);
10. end;
11.  

where Q : array [0..$FF] of dword;
i, c: dword;
Q needs to be seeded once e.g. by FPC's own generator.

Linear Congruential generators may be faster but they have poor statistical quality. Or try

Code: Pascal  [Select][+][-]

1. function xor32: dword ; inline;
2. var r32: dword;
3. begin
4.   r32 := r32 xor (r32 shl 13);
5.   r32 := r32 xor (r32 shr 17);
6.   r32 := r32 xor (r32 shl 5);
7.   exit (r32);
8. end;
9.  

r32 must be seeded with a numer not equal zero.