Random Numbers

[Thaddy]

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.

Well:
1. I am schooled in mathematics
2. You are introducing an issue that is not at hand. The repeatability of the swaps is not important here. Just uniqueness of single elements.
3. I am sure it is repeatable (at least I hope so, otherwise my statistics models become untestable ) . That is the point of a prng. You have to seed otherwise.......

Not a clue, that is ....

[Blestan]

@thady :nope!!!! you use 0.999999 aray this is not lets say for a 10 digits decimal 10x10 matrix (100 cells)  help me for a fast 0...128 random generator

[Nitorami]

As said above, the MWC256 is the fastest on two machines I tested. Other choices:

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

1. function XorShift1024star: dword;
2. var    s0, s1: qword;
3. begin
4.   s0 := s[i];
5.   i := (i+1) and $F;
6.   s1 := s[i];
7.   s1 := s1 xor (s1 shl 31);
8.   s[i] := s1 xor s0 xor (s1 shr 11) xor (s0 shr 30);
9.   result := s[i];
10. end;
11.  

where s: array [0..$F] of qword;
i: dword;

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

1. function XorShift128plus: dword;
2. var x,y: qword;
3. begin
4.   x := s[0];
5.   y := s[1];
6.   s[0] := y;
7.   x := x xor (x shl 23);
8.   s[1] := x xor y xor (x shr 17) xor (y shr 26);
9.   result := s[1] + y;
10. end;
11.  

where s: array [0..1] of qword;
i: dword;

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

1. function lfsr113: dword;
2. var b: dword;
3. { VERY IMPORTANT : The initial seeds z1, z2, z3, z4  MUST be larger than
4.   1, 7, 15, and 127 respectively.}
5. begin
6.   b    := ( z[1] xor (z[1] shl 6)) shr 13;
7.   z[1] := ((z[1] and 4294967294) << 18) xor b;
8.   b    := ( z[2] xor (z[2] shl 2)) shr 27;
9.   z[2] := ((z[2] AND 4294967288) shl 2) xor b;
10.   b    := ( z[3] xor (z[3] shl 13)) shr 21;
11.   z[3] := ((z[3] AND 4294967280) shl 7) xor b;
12.   b    := ( z[4] xor (z[4] shl 3)) shr 12;
13.   z[4] := ((z[4] AND 4294967168) shl 13) xor b;
14.   result := z[1] xor z[2] xor z[3] xor z[4];
15. end;
16.  

where Z: array [1..4] of dword;

[Blestan]

so all of these returns a random in the range 0..128?

[Nitorami]

No, all of these return a dword. You need to limit the range but need to be careful. It is easy for ranges 0..127, but 0...128 may be tricky.

I think hi(lo(output)*128) should do, but no guarantee.

[Blestan]

my mistake 00..127 (128 values) 00..63 00..31 00..15 ranges

[Thaddy]

@thady :nope!!!! you use 0.999999 aray this is not lets say for a 10 digits decimal 10x10 matrix (100 cells)  help me for a fast 0...128 random generator

you mean a range of 129? do you? My range is an exact fit for 1.000.000
Ate you a BASIC programmer?

[Blestan]

00...127 ... 128 values or 00..31 (32 values) 00..0f (16 values)

[Thaddy]

00...127 ... 128 values or 00..31 (32 values) 00..0f (16 values)

So then admit you were wrong in the first place.....

[Blestan]

oooo please!

[Nitorami]

You can limit the range using mod:

r := MWC256 mod 128 gives you numbers 0..127.

Just DO not use this trick for ranges not a power of 2 !

You may get several values out of one random dword (which is 32 bit while you need only 7):

x := MWC256;
r := x mod 128;
x := x shr 7;
r := x mod 128;
x := x shr 7;
r := x mod 128;
(... until x is depleted)

[Blestan]

ok! thanks! i will put my algo together i will post it for tests.
basicly in concist in the following :
if we need and 16 digits random number of digits form 0 to f we create and matrix of 16x16 of booleans ( i will bits and use bsr and bsf  to scan for speeed) then  find a random  "spot" of uniqunesness to generate the digit for the given order... im mot sure if im explaining it verry well but i will show the code soon

[Nitorami]

No I don't get what you try to say but let's wait for the code.

BTW do not overstimate microoptimisations such as BSRDword. First, it may not be portable (which may not matter to you), but second, it is not necessarily faster in the context of a real-world program.

I tried it for the bit-reversal algorithm required in the fast fourier transform, but on program level it proved to be no more efficient than the plain pascal code  repeat l := l shr 1 until (k + l) <= nn; on no machine.

[knuckles]

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.

You can speed up this part by stopping the paint messages been sent to the memo whilst adding the lines, eg:

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

1. memo1.Lines.BeginUpdate;
2. try
3.   memo1.Lines.Clear;
4.   for i:=0 to 999 do memo1.Lines.Add(inttostr(rnd[i]));
5. finally
6.   memo1.Lines.EndUpdate;
7. end;