Thread: Random numbers
View Single Post
Old 15 November 2020, 21:39   #7
Thomas Richter
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 968
Originally Posted by sparhawk View Post
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".

Originally Posted by sparhawk View Post
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:

        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)
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.
Thomas Richter is offline  
Page generated in 0.07655 seconds with 11 queries