Random numbers
I was looking for some algorithm how to create random numbers. When I look at the glibc source, it looks extremly complicated and expensive. Another approach I became aware of was, to use a Murmur2 hash value. This works quite nice, but it also looks computationally expensive. From guts feeling I think it's not as expensive as the glibc code, but still. So I was wondering if there is some better approach which is also fast.
At least the Murmur2 code looks much easier to translate to asm, so if there is no better alternative I will take that one. As a nice side effect, I have then a hashing algorithm as well. :D 
If you search the Coders forum for "random" you get some threads that should give several solutions for fast and cheap random generators. There is also a long discussion I remember with code examples.

I once looked at the algorithm used by C64 Basic. It's really simple: it takes the 32bit seed, EORs it by a large random number (probably a prime number) and orders the bytes backward.
The seed was then interpreted as a float and normalized to be between 0 and 1. But that's not necessary, you already get quite good results if you divide the seed by the desired range and use the remainder as result. Something like this for random numbers between 1 and 6: Code:
move.l seed,d0 
Thanks. :D I tried to search, but I didn't find much. Maybe the wrong search phrase.
That algorithm looks nice and simple. :) 
Code:
;;; EAB simple random generator 
Code:
move.l seed,d0 there is only swap 
Quote:
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 multiplyadd approach. Depending on the numbers you pick, the results are "ok". Quote:
Code:
saveregs a2/a6 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. 
Quote:
This will not, however, fix the problem with the short period of the algorithm (for a 32bit seed, it's in the thousands). 
1. short
2. fast 3. accurate Pick two :P. This is a quick&dirty one that works for me: Code:
Init: move.l #<seed>,d7 ; large prime numbers 
Quote:

Quote:

The one I posted? That one, as stated, works for me, to generate a few thousand random 16bit numbers very quickly (6 bytes inline, 20 cycles on a 68000).
Xorshift? Yeah, there are many variants that pass the bigcrush tests. Look up xorshift and xoshiro. But most importantly, read the first 4 lines (and pick two) :P. That's the point. 
The question is not "whether it works for you", but whether it is a good random generator and passes a couple of tests, for example the spectral test. See again Knuth II for a lot of tests and a lot of material on random generators, and in particular why homemade generators are not a good idea.

moveq #ohhowilovearguingwithinternetstrangersaboutnothing,d0
... not.l d0 Again, you are missing the point. Taking a step back, xorshift is not some mumbo jumbo, and as i said it passes the bigcrush test which is a few hours long test. Now, back to code I posted... You should stop looking at this from your point of view only, especially in a coders/asm forum.  Original poster said, in a general manner, that he needs a fast algorithm but doesn't specify how fast is fast enough for his definition of fast in this fast moving thread.  Apply 2outof3 rule.  Different people present different options. 01 choice 0$ff better choice 0$ffff betterer choice 0$ffffffff bettererer choice So what's the problem? Need better accuracy (*again*, 2outof3 rule)? 1. pick a better seed/modifier 2. use shift/ror instead of a swap 3. use 2x32 bits ... 9. use the "fullblown" xorshift algorithm, which is still plenty fast, if you still like this type of rng 10. use something else that you like more or that works better in your, and unknown to us, scenario 
The numbers should be sufficiently random for a game. they don't need to hold against a scientific test. :) So in a game, speed is important, but I think if I have the choice between a bad generator and a little bit slower one, then I might take the slower one. If it starts to get a performance issue, then a less "random" algorithm might be acceptable. I thought of adding a few of them and then compare how the perform vs. how they "feel" regarding randomness.

Quote:

Quote:

Quote:

I suggest using RANDU just to irritate PRNG algorithm snobs. ;)

Now I've been looking for a random number algorithm generator as well and it looks like something like xorshift would be good enough for my purpose. Assuming I'd use xorshift, what would be good initial seed (or state) values for 32 bit signed/unsiged random numbers?
See, to me it seems to me that getting the seed right is the critical part for using this type of algorithm properly. 
All times are GMT +2. The time now is 13:30. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, vBulletin Solutions Inc.