-
-
Save raxoft/c074743ea3f926db0037 to your computer and use it in GitHub Desktop.
; 8-bit Xor-Shift random number generator. | |
; Created by Patrik Rak in 2008 and revised in 2011/2012. | |
; See http://www.worldofspectrum.org/forums/showthread.php?t=23070 | |
org 40000 | |
call rnd ; BASIC driver | |
ld c,a | |
ld b,0 | |
ret | |
rnd ld hl,0xA280 ; yw -> zt | |
ld de,0xC0DE ; xz -> yw | |
ld (rnd+4),hl ; x = y, z = w | |
ld a,l ; w = w ^ ( w << 3 ) | |
add a,a | |
add a,a | |
add a,a | |
xor l | |
ld l,a | |
ld a,d ; t = x ^ (x << 1) | |
add a,a | |
xor d | |
ld h,a | |
rra ; t = t ^ (t >> 1) ^ w | |
xor h | |
xor l | |
ld h,e ; y = z | |
ld l,a ; w = t | |
ld (rnd+1),hl | |
ret |
As shown in the paper, the direction of the shift is your choice. You can choose any of the 8 combinations, and then you look for the triplets for that particular combination. In this case, I wanted 2 left and one right, as shifting left fast is somewhat easier than shifting right.
As for the triplets, yes, it uses the same (a,b,c)
notation as the paper does. As for slightly better, if you run the Diehard tests, IIRC, those two triples fail few less tests than the (1,1,3). However, it's still far from perfect so it doesn't matter much. This class of generators is bound to fail some of them anyway. If you want/need something really robust in this regard, use my CMWC Z80 generator instead.
I was hoping to use an adapted version of this code in my gameboy game. Is this possible? I'd love to know what its license is :)
Absolutely. You can consider this snippet to be part of Public Domain.
Thanks for asking and good luck with the game.
Thanks for sharing this! I am also hoping to adapt this code for use in a Game Boy game. I am relatively new to programming and was wondering whether you would be willing to proofread my attempt to adapt your code for gbZ80. It is based on the 16th post of the World of Spectrum thread that you linked:
rnd:
; ld bc,(seed) ; xz -> yw
ld hl,random
ld a,[hli] ; hl = random+1
ld c,a
ld a,[hli] ; hl = random+2
ld b,a
; ld de,(seed+2) ; yw -> zt
ld a,[hli] ; hl = random+3
ld e,a
ld a,[hld] ; hl = random+2
; ld (seed),de ; x = y, z = w
dec hl ; hl = random+1
ld [hld],a ; hl = random
ld a,e
ld [hli],a ; hl = random+1
; ld a,e ; w = w ^ ( w << 3 )
add a,a
add a,a
add a,a
xor e
ld e,a
ld a,b ; t = x ^ (x << 1)
add a,a
xor b
ld d,a
rra ; t = t ^ (t >> 1) ^ w
xor d
xor e
; ld b,c ; y = z
; ld c,a ; w = t
; ld (seed+2),bc
inc hl ; hl = random+2
ld [hli],a ; hl = random+3
ld a,c
ld [hl],a
; ld b,0
ret
My understanding is that the label "random" should point to a 4-byte range and that at least one of these bytes should be initialised to a non-zero value before calling the function for the first time. It will then generate a random 8-bit number which I can retrieve from random+2 after the function has returned. Is this correct?
Yes, and looks like the code is correct, too, AFAICT, but I think it can be optimized further... Essentially, in xorshift, you are having n words, in our case 4 bytes, xyzw, but only the first and last (x and w) are used in the computation, the rest is merely moved/shifted (y to x, z to y, and w to z). So I think the last store of the C register which you do at the end could be actually moved to the opening sequence, as you really need just to store the result from A to w at the end (the result also serves as the feedback for the next round). This would have the advantage that the result remains in A once the routine returns, which was the idea in the first place (puting it to BC is done just for Sinclair Basic).
Thank you very much for taking the time to check this! I think I get what you mean about the last store of the C register and I think I now understand this code enough that I've been able to optimise it accordingly by loading out of RAM specifically, rather than using HLI/HLD commands:
rnd:
; ld bc,(seed) ; xz -> yw
; ld de,(seed+2) ; yw -> zt
; ld (seed),de ; x = y, z = w
ld a,[random+1]
ld b,a ; b = random+1
ld a,[random+3]
ld [random+1],a ; random+3 -> random+1
ld a,[random]
ld [random+3],a ; random -> random+3
ld a,[random+2]
ld [random],a ; random+2 -> random
ld e,a ; e = random+2
; ld a,e ; w = w ^ ( w << 3 )
add a,a
add a,a
add a,a
xor e
ld e,a
ld a,b ; t = x ^ (x << 1)
add a,a
xor b
ld d,a
rra ; t = t ^ (t >> 1) ^ w
xor d
xor e
; ld b,c ; y = z
; ld c,a ; w = t
; ld (seed+2),bc
ld [random+2],a
; ld b,0
ret
The complication that I didn't mention before is that I am trying to improve the random number generator in a hack of an existing game and calling the function involves bank switching, so the result in the A register is lost by the time the code returns to the point that it called for a random number in the first place anyway. I suppose I could possibly move the function, but I am opting for retrieving the result for now. This does mean spending another byte of code on the retrieval process, but this revision is six bytes less than the original adaption (bringing the total to twenty-four bytes once the random value has been retrieved).
Thank you for the code, and the insights in that worldofspectrum thread. I have a couple of questions (apologies in advance if they turn out to be "obvious" but it's been a really long time since I wrote Z80 assembly last, or did any serious math for that matter).
First off, Marsaglia's pseudo-C-code in the Xorshift RNGs paper
t=(xˆ(x<<a)); x=y; y=z; z=w; return w=(wˆ(w>>c))ˆ(tˆ(t>>b));
has thew
shifted right rather than left. I reckon that it's an entirely different context there vs. the 8-bit case here, yet I was wondering if/how it matters.Secondly, the code here is using the
(1,1,3)
triplet, but since the first two parameters are numerically equal it is not obvious which is which. Does it follow Marsaglia's notation for(a,b,c)
wherea
is the shift count forx
,b
fort
andc
forw
? Somewhat related, I was wondering how doesslightly better
quantify in this line:(3,3,2) and (5,3,2) seem to get slightly better results in the Diehard tests
.