Fast floating-point random numbers

[Leffmann]

Here's a very fast way of generating FP random numbers in [0.0, 1.0) based on the XORShift PRNG:

move.l   state, d0
move.l   d0, d1
lsl.l    #7, d1
eor.l    d1, d0
move.l   d0, d1
lsr.l    #2, d1
eor.l    d1, d0
move.l   d0, d1
lsr.l    #7, d1
eor.l    d1, d0
move.l   d0, state

lsr.l    #2, d0
or.l     #127<<23, d0
fmove.s  d0, fp0
fsub.s   #1.0, fp0

It has a period of 2^32-1, uniform distribution, and very good randomness. (you can omit the latter part and just use it for integers as well)

[Mrs Beanbag]

now this i can really use! i have something similar in my own code, but it was a bit of a bodge and randomness isn't very good. will try this instead at earliest opportunity. (but keep my current one in the sound effects generation so it doesn't change the sound!!)

[Thorham]

Originally Posted by Mrs Beanbag

now this i can really use! i have something similar in my own code, but it was a bit of a bodge and randomness isn't very good. will try this instead at earliest opportunity. (but keep my current one in the sound effects generation so it doesn't change the sound!!)

Xorshift is a reasonable prng, but if you want something better (passes the Bigcrush test, for example), check out xorgens: https://maths-people.anu.edu.au/~brent/random.html. Xorgens is also easy to implement in 68k.

[Leffmann]

Pretty much any PRNG will work fine.. the main idea here was just to construct the number in a faster way than by using division or multiplication, it doesn't matter where the random bits come from really.

[Mrs Beanbag]

i used a simple LCG to generate the restart codes from world map co-ordinates, that should be pretty good for randomness but doesn't need to be fast.

my in-game random used rotates and xor iirc, randomness however was not very good, resulting often in enemies firing shots in bursts for some reason

[Thorham]

Originally Posted by Mrs Beanbag

i used a simple LCG to generate the restart codes from world map co-ordinates, that should be pretty good for randomness but doesn't need to be fast.

It's probably better to use xorgens for things like that.

Originally Posted by Mrs Beanbag

my in-game random used rotates and xor iirc, randomness however was not very good, resulting often in enemies firing shots in bursts for some reason

Xorshift seems fine for that.

Xorgens is for when you need something really good with a large period.

[Mrs Beanbag]

Originally Posted by Thorham

It's probably better to use xorgens for things like that.

it might be, but i can't change it now or all the codes wouldn't work anymore!

also, needs to be perfectly reversible. LCG is easy to implement and easy to invert. that was why i used it. i will read the Xorgens paper though!

[meynaf]

The best randomness is achieved when you use several RNG and mix their results together.
LCG has problems with the lower bits of the output ; xorshift has problems with seeds containing many '0'. But if you mix both together you'll get very good results, especially if you also mix that with values read from hardware counters (like cia timers).

So you can just keep your LCG for level code generation and use a more sophisticated RNG for the game itself.

[Mrs Beanbag]

hey LCG could even stand for "Level Code Generation", well fancy that

something occurred to me, which is that i'm not typically using loads of random numbers per frame, so i could just generate a stack of them in advance to use when needed, replenishing it whenever there's spare time, then performance wouldn't be so much of an issue.

[Thorham]

Xorgens4096 + Sha 1 or Sha 256 for seeding.

[Mrs Beanbag]

are we going for cryptographic level strength now?

[meynaf]

A little bit overkill for a game indeed.

[Thorham]

Originally Posted by Mrs Beanbag

are we going for cryptographic level strength now?

Sha is nice for mixing bytes read from the Amiga chip set. Makes for a great seeder.

[Mrs Beanbag]

i did see a talk about tool-assisted speed runs at EMFcamp that explained how people sort of cheat the game by exploiting the random number sequence and it did set me wondering about techniques to thwart this sort of thing. Using, for instance, beam position XOR onto the State value might make things a little harder to predict. At least on real hardware... or might make it highly dependent on exactly which emulator is being used!

[meynaf]

Originally Posted by Mrs Beanbag

i did see a talk about tool-assisted speed runs at EMFcamp that explained how people sort of cheat the game by exploiting the random number sequence and it did set me wondering about techniques to thwart this sort of thing. Using, for instance, beam position XOR onto the State value might make things a little harder to predict. At least on real hardware... or might make it highly dependent on exactly which emulator is being used!

This is the kind of thing i use in my random routine, as follows :

 move.l seed,d0
 move.w $dff006,d2
 swap d2
 move.b $bfe801,d2
 lsl.w #8,d2
 move.b $bfd800,d2
 add.l d2,d0
 mulu.l #$59fa769f,d2:d0
 add.l d2,d0
 addi.l #$4a5be021,d0
 ror.l #6,d0
 move.l d0,seed

On real hardware it passes all randomness tests ; for me it's even good enough for cryptographic uses (but i don't want to go into this discussion again !).

[Thorham]

Originally Posted by meynaf

On real hardware it passes all randomness tests

So, it passes BigCrush from testu01?

Originally Posted by meynaf

for me it's even good enough for cryptographic uses

You can only use this to generate keys.

I use this to generate data to be used by an external mixer:

;
; a0 = output buffer
; d0 = number of bytes
;
getHardwareBytes
    movem.l d0-d2/a0,-(sp)
.loop
    move.b  $dff006,d1
    move.b  $dff007,d2
    eor.b   d2,d1
    move.b  $bfe601,d2
    eor.b   d2,d1
    move.b  $bfe701,d2
    eor.b   d2,d1
    move.b  $bfe801,d2
    eor.b   d2,d1
    move.b  $bfe901,d2
    eor.b   d2,d1
    move.b  $bfd800,d2
    eor.b   d2,d1
    move.b  $bfd900,d2
    eor.b   d2,d1

    move.b  d1,(a0)+

    subq.l  #1,d0
    bne     .loop

    movem.l (sp)+, d0-d2/a0
    rts

You can also just xor all hardware bytes together, of course.

[idrougge]

Isn't just reading $dff006 enough for most game purposes?

[meynaf]

Originally Posted by Thorham

So, it passes BigCrush from testu01?

Haven't made the full big crush test (too long). However I extracted all the toughest tests from several test suits, including testu01. It passed them all. Xorshift didn't fare so well (i especially liked the linear complexity test, on which mersenne twisters also fail).

If you want to do that huge test, then just do it
(However be awared that the tests fill fail if you extract megabytes of rnd data per second on an emulator).

Originally Posted by Thorham

You can only use this to generate keys.

Yes it's obviously for key gen. For the encryption itself it wouldn't be decipherable again

[Thorham]

Originally Posted by idrougge

Isn't just reading $dff006 enough for most game purposes?

Seems a little weak. It's really easy to write something simple and think it's okay, while the output is really bad. Randomness is a topic that must not be underestimated.

Originally Posted by meynaf

Haven't made the full big crush test (too long). However I extracted all the toughest tests from several test suits, including testu01. It passed them all.

Sounds good, but I'd test it using the full suite. Shouldn't take that long on your laptop.

Originally Posted by meynaf

Xorshift didn't fare so well (i especially liked the linear complexity test, on which mersenne twisters also fail).

Indeed. Xorshift is nice for when you need something simple and reasonable that's also fast. I prefer Xorgens4096, because it's pretty fast, has a huge period and passes all of Big Crush.

Originally Posted by meynaf

(However be awared that the tests fill fail if you extract megabytes of rnd data per second on an emulator).

Yeah, I know. The hardware registers don't behave in the same way as on hardware.

[Mrs Beanbag]

Originally Posted by Thorham

Seems a little weak. It's really easy to write something simple and think it's okay, while the output is really bad. Randomness is a topic that must not be underestimated.

true but i really don't think it needs to pass all of these rigorous statistical tests to be good enough to decide which item an enemy drops when you kill it.