13 August 2016, 23:45 | #1 |
Join Date: Jul 2008
Location: Sweden
Posts: 2,269
|
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 Last edited by Leffmann; 18 August 2016 at 20:52. |
17 August 2016, 23:17 | #2 |
Glastonbridge Software
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,243
|
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!!)
|
18 August 2016, 19:42 | #3 | |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,866
|
Quote:
|
|
18 August 2016, 21:03 | #4 |
Join Date: Jul 2008
Location: Sweden
Posts: 2,269
|
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.
|
18 August 2016, 21:23 | #5 |
Glastonbridge Software
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,243
|
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 |
18 August 2016, 22:29 | #6 | ||
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,866
|
Quote:
Quote:
Xorgens is for when you need something really good with a large period. |
||
18 August 2016, 22:49 | #7 |
Glastonbridge Software
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,243
|
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! |
19 August 2016, 08:33 | #8 |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,365
|
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. |
19 August 2016, 11:18 | #9 |
Glastonbridge Software
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,243
|
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. |
20 August 2016, 04:33 | #10 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,866
|
Xorgens4096 + Sha 1 or Sha 256 for seeding.
|
20 August 2016, 10:20 | #11 |
Glastonbridge Software
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,243
|
are we going for cryptographic level strength now?
|
20 August 2016, 13:26 | #12 |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,365
|
A little bit overkill for a game indeed.
|
20 August 2016, 13:30 | #13 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,866
|
|
20 August 2016, 13:36 | #14 |
Glastonbridge Software
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,243
|
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!
|
20 August 2016, 14:02 | #15 | |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,365
|
Quote:
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 |
|
20 August 2016, 17:29 | #16 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,866
|
So, it passes BigCrush from testu01?
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 |
20 August 2016, 17:34 | #17 |
Registered User
Join Date: Sep 2007
Location: Stockholm
Posts: 4,357
|
Isn't just reading $dff006 enough for most game purposes?
|
20 August 2016, 18:15 | #18 |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,365
|
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). Yes it's obviously for key gen. For the encryption itself it wouldn't be decipherable again |
20 August 2016, 19:32 | #19 | ||
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,866
|
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:
Quote:
Yeah, I know. The hardware registers don't behave in the same way as on hardware. |
||
20 August 2016, 20:13 | #20 |
Glastonbridge Software
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,243
|
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.
|
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 |
|
|