Quote:
Originally Posted by sparhawk
I was looking for some algorithm how to create random numbers.
|
Donald Knuth, "The Art of Programming", Vol. II: "Numerical and Semi-numerical algorithms". Contains everything you ever wanted to know about random generators and you never dared to ask.
The quick morale: Do not pick the algorithm to generate random numbers at random. In particular, do not accept "home made" algorithms. About the simplest random number generators are "linear congruence random generators", which use a multiply-add approach. Depending on the numbers you pick, the results are "ok".
Quote:
Originally Posted by sparhawk
When I look at the glibc source, it looks extremly complicated and expensive.
|
For a reason. Better quality requires more complexity. The linear congruence generators are not too good. A simple one is this one:
Code:
saveregs a2/a6
lea _Seed(a4),a2
move.l (a2),d0
move.l _UtilityBase(a4),a6
move.l #1664525,d1 ;Knuth's algorithm
jsr -$90(a6) ;UMul
add.l #1013904223,d0
move.l d0,(a2)
loadregs
rts
[/QUOTE]
This is Knuth's linear congruence algorithm with a modulo value of 2^32. It is well researched and well understood. Do not exchange the multiplication with anything else, neither its constant.
Note that if you use the output of this algorithm: Always use data from the MSBs on, do not generate random numbers by "masking", as the LSBs have a much smaller period.