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


Quote:
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:


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