English Amiga Board Amiga Lore


Go Back   English Amiga Board > Coders > Coders. General > Coders. Tutorials

 
 
Thread Tools
Old 13 August 2016, 23:45   #1
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,017
Post Fast floating-point random numbers

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

Code:
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)

Last edited by Leffmann; 18 August 2016 at 20:52.
Leffmann is offline  
AdSense AdSense  
Old 17 August 2016, 23:17   #2
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
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!!)
Mrs Beanbag is offline  
Old 18 August 2016, 19:42   #3
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,964
Quote:
Originally Posted by Mrs Beanbag View Post
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.
Thorham is offline  
Old 18 August 2016, 21:03   #4
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,017
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.
Leffmann is offline  
Old 18 August 2016, 21:23   #5
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
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
Mrs Beanbag is offline  
Old 18 August 2016, 22:29   #6
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,964
Quote:
Originally Posted by Mrs Beanbag View Post
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.

Quote:
Originally Posted by Mrs Beanbag View Post
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.
Thorham is offline  
Old 18 August 2016, 22:49   #7
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
Quote:
Originally Posted by Thorham View Post
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!
Mrs Beanbag is offline  
Old 19 August 2016, 08:33   #8
meynaf
68k wisdom
meynaf's Avatar
 
Join Date: Nov 2007
Location: Lyon (France)
Age: 44
Posts: 2,381
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.
meynaf is offline  
Old 19 August 2016, 11:18   #9
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
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.
Mrs Beanbag is offline  
Old 20 August 2016, 04:33   #10
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,964
Xorgens4096 + Sha 1 or Sha 256 for seeding.
Thorham is offline  
Old 20 August 2016, 10:20   #11
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
are we going for cryptographic level strength now?
Mrs Beanbag is offline  
Old 20 August 2016, 13:26   #12
meynaf
68k wisdom
meynaf's Avatar
 
Join Date: Nov 2007
Location: Lyon (France)
Age: 44
Posts: 2,381
A little bit overkill for a game indeed.
meynaf is offline  
Old 20 August 2016, 13:30   #13
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,964
Quote:
Originally Posted by Mrs Beanbag View Post
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.
Thorham is offline  
Old 20 August 2016, 13:36   #14
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
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!
Mrs Beanbag is offline  
Old 20 August 2016, 14:02   #15
meynaf
68k wisdom
meynaf's Avatar
 
Join Date: Nov 2007
Location: Lyon (France)
Age: 44
Posts: 2,381
Quote:
Originally Posted by Mrs Beanbag View Post
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 :
Code:
 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 !).
meynaf is offline  
Old 20 August 2016, 17:29   #16
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,964
Quote:
Originally Posted by meynaf View Post
On real hardware it passes all randomness tests
So, it passes BigCrush from testu01?

Quote:
Originally Posted by meynaf View Post
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:
Code:
;
; 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.
Thorham is offline  
Old 20 August 2016, 17:34   #17
idrougge
Registered User
 
Join Date: Sep 2007
Location: Stockholm
Posts: 3,020
Isn't just reading $dff006 enough for most game purposes?
idrougge is offline  
Old 20 August 2016, 18:15   #18
meynaf
68k wisdom
meynaf's Avatar
 
Join Date: Nov 2007
Location: Lyon (France)
Age: 44
Posts: 2,381
Quote:
Originally Posted by Thorham View Post
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).


Quote:
Originally Posted by Thorham View Post
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
meynaf is offline  
Old 20 August 2016, 19:32   #19
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,964
Quote:
Originally Posted by idrougge View Post
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.

Quote:
Originally Posted by meynaf View Post
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.

Quote:
Originally Posted by meynaf View Post
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.

Quote:
Originally Posted by meynaf View Post
(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.
Thorham is offline  
Old 20 August 2016, 20:13   #20
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
 
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
Quote:
Originally Posted by Thorham View Post
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.
Mrs Beanbag is offline  
AdSense AdSense  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Important Facts about Floating Point Numbers Mrs Beanbag Coders. General 2 13 August 2016 21:14
Floating point without FPU oRBIT Coders. Asm / Hardware 13 18 March 2015 23:11
Help needed!!Random octal numbers generator(asm) sheryn88 Coders. General 6 01 August 2010 07:19
A nice quick small random numbers routine? Photon Coders. General 2 20 December 2004 21:56
Floating menus? Mojo2000 New to Emulation or Amiga scene 6 30 January 2003 14:35

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 12:11.


Powered by vBulletin® Version 3.8.8 Beta 1
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Page generated in 0.23245 seconds with 12 queries