Random Numbers

Boriel, I know the compiler's pseudorandom number generator is better than the one in the ROM.

Seen this:

http://www.worldofspectrum.org/forums/s ... hp?t=23070

?

If it's smaller, faster or better, you might want to consider

For posterity, an 8 bit result with 32 bit seed that passes diehard test for 32 bit entropy:

  Code:

rnd     ld  hl,0xA280   ; xz -> yw
        ld  de,0xC0DE   ; yw -> zt
        ld  (rnd+1),de  ; x = y, z = w
        ld  a,e         ; w = w ^ ( w << 3 )
        add a,a
        add a,a
        add a,a
        xor e
        ld  e,a
        ld  a,h         ; t = x ^ (x << 1)
        add a,a
        xor h
        ld  d,a
        rra             ; t = t ^ (t >> 1) ^ w
        xor d
        xor e
        ld  h,l         ; y = z
        ld  l,a         ; w = t
        ld  (rnd+4),hl
        ret


[boriel]

The random number generator I used is taken from C Numerical Recipes and is, in fact nearly the same this one (maybe my implementation is not that good I converted from C to Z80 asm by hand ). It should pass the same test this one.
Anyway we should consider them.

I was thinking other basics such QBasic or VBasic allows SUBS to be called without parenthesis. This way,

  Code:

SUB mysub(a, b)
...
END SUB


Can be called with

  Code:

mysub a, b


This will allow the user to effectively redefine a complete set of DRAW, RANDOMIZE, INK, etc... routines and will allow ZXBASIC to be more universal and no so speccy-oriented!
This way, ZX Spectrum users will have an implicit #include <spectrum.h> at the beginning (like when the --spectrum flag is used) and all will remain the same. But programs for other platform might not use such include, but other ones.

Well, that is just an idea.

We haven't looked at this in a while.

Here's some test code:

  Code:

FUNCTION FASTCALL randomBase () as uByte
ASM
random: ld  hl,$A280       ; xz -> yw
        ld  de,$C0DE       ; yw -> zt
        ld  (random+1),de   ; x = y, z = w
        ld  a,e             ; w = w ^ ( w << 3 )
        add a,a
        add a,a
        add a,a
        xor e
        ld  e,a
        ld  a,h             ; t = x ^ (x << 1)
        add a,a
        xor h
        ld  d,a
        rra                 ; t = t ^ (t >> 1) ^ w
        xor d
        xor e
        ld  h,l             ; y = z
        ld  l,a             ; w = t
        ld  (random+4),hl
        ret
END ASM
END FUNCTION

FUNCTION FASTCALL randomFixed() as FIXED
ASM
call random
push AF
call random
ld l,A
POP AF
ld h,a
ld d,0
ld e,d
END ASM
END FUNCTION

FUNCTION t() as uLong
asm
    DI
    LD DE,(23674)
    LD D,0
    LD HL,(23672)
    EI
end asm
end function

DIM time,endtime as uLong

REM Print the base random 8 bits:
print randomBase()

REM print as a decimal, like basic's random number:
print randomFixed()

REM Works the same way:
print int(randomFixed()*10)

pause 1
pause 0
cls
dim n as uInteger

REM how does this look as a random dot spread?
time=t()
for n=1 to 30000
plot rnd*255,rnd*192
'print at 0,0;INT(rnd)
next n
REM (it looks good)
endtime=t()

print endtime-time;" Frames"

pause 1
pause 0
cls

REM how does this look as a random dot spread?
time=t()

for n=1 to 30000
plot randomFixed()*255,randomFixed()*192
'print at 0,0;INT( randomFixed() )
next n
REM (it looks good)
endtime=t()

print endtime-time;" Frames"



Basically, more than twice as fast in all cases.

I think the clincher, for me, is that even

  Code:

print at 0,0;INT(CAST(FLOAT,randomFixed()))


- which forces a full floating point result, like rnd has, comes back 50% faster.

I also tried it with my planet proggy - bug-reports/byte-loops-solved-t757.html#p3229 - it comes out over twice as fast.

[boriel]

I was talking about attach two snapshots (one for each run), to compare the scatter plots and see if they are really random (e.g. Sinclair BASIC RND used to show diagonal patterns).

Did you try it?

I tweaked it here to do 10,000 on rnd and time it, then do 10,000 on random and time it.

I recommend turning emulator up to full speed!

random.tzx

(2.57 KiB) Downloaded 14 times

[boriel]

Did you try it?
I tweaked it here to do 10,000 on rnd and time it, then do 10,000 on random and time it.
I recommend turning emulator up to full speed!

random.tzx

Sorry, I've been away (now back!).
This is exactly the test I was suggesting.

1. The RND stream is MUCH faster! (Ideal for games)
2. ZX Basic RND generator I know is really "random" (well distributed). Visually "Comparing" both images, they seem really well distributed

I agree we could replace RANDOMIZE/RND generator with this one, then RND is used very often in games, and the memory footprint looks not very significant Also, for compatibility's sake, we should consider RND returning Float (yes, should be a bit slower)

RND is used very often in games, and the memory footprint looks not very significant Also, for compatibility's sake, we should consider RND returning Float (yes, should be a bit slower)

True! My current games "Earthraid" and "U-Boot Hunt" both use random numbers, but while "U-Boot Hunt" use few of them at initialisation of a new game and therefor it is not critical, "Earthraid" must calculate many randoms each round and for calculating the landscape for each new game. Should I wait for the version with fast randoms?
Most games (in fact all of them) need integers, so why not add a RANDOM(max) function for fast integer randoms calculation?

It's pretty fast to make the stream function do a decimal using the method I did - grab 16 bits (two stream function calls) and express them as the last half of a fixed type number.

It's also pretty easy to have it make a result in the realms of (0-2^n-1) since that is just a binary limit. E.g. 0-255 is 8 bits of data. 0-65535 is 16 bits.

An arbitrary integer is harder, and is going to mean multiplying by n. Even then, as pointed out on the WOS boards, at least you should generate more bits than you need if you are going to multiply. E.g. the 16 bits version above is probably good for numbers into the tens of thousands, but getting pretty rough above that.

Still, even here, doing it with fixed numbers seems to be a win, speed wise.