I have put together a series of Assembly programs along with their outputs. The results are stunning, though my original BASIC program is still able to produce a more random pattern compared to the results you will see.
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
call setup
.loop
call rnd
call sht4
ld a,(rslt)
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
and a
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
and a
sbc hl,de
jr nz,loop
call keywait
ret
.rnd
ld a,(seed)
ld b,a
add a,a
add a,a
add a,b
inc a
ld (seed),a
ret
.sht4
srl a
srl a
srl a
srl a
inc a
ld (rslt),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
.seed defb 0
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
Output:
[attachimg=1]
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
call setup
.loop
call rnd
call sht4
ld a,(rslt)
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
and a
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
and a
sbc hl,de
jr nz,loop
call keywait
ret
.rnd
push hl
ld a,(RandomPtr)
inc a
ld (RandomPtr),a
ld hl,RandTable
add a,l
ld l,a
jr nc,skip
inc h
.skip ld a,(hl)
pop hl
ret
.sht4
srl a
srl a
srl a
srl a
inc a
ld (rslt),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
.RandTable
defb &3B,&02,&B7,&6B,&08,&74,&1A,&5D,&21,&99,&95,&66,&D5,&59,&05,&42
defb &F8,&03,&0F,&53,&7D,&8F,&57,&FB,&48,&26,&F2,&4A,&3D,&E4,&1D,&D9
defb &9D,&DC,&2F,&F5,&92,&5C,&CC,&00,&73,&15,&BF,&B1,&BB,&EB,&9E,&2E
defb &32,&FC,&4B,&CD,&A7,&E6,&C2,&10,&11,&80,&52,&B2,&DA,&77,&4F,&EC
defb &13,&54,&64,&ED,&94,&8C,&C6,&9A,&19,&9F,&75,&FA,&AA,&8D,&FE,&91
defb &01,&23,&07,&C1,&40,&18,&51,&76,&3C,&BD,&2A,&88,&2D,&F1,&8A,&72
defb &F6,&98,&35,&97,&68,&93,&B3,&0C,&82,&4E,&CB,&39,&D8,&5F,&C7,&D4
defb &CE,&AE,&6D,&A3,&7C,&6A,&B8,&A6,&6F,&5E,&E5,&1B,&F4,&B5,&3A,&14
defb &78,&FD,&D0,&7A,&47,&2C,&A8,&1E,&EA,&2B,&9C,&86,&83,&E1,&7B,&71
defb &F0,&FF,&D1,&C3,&DB,&0E,&46,&1C,&C9,&16,&61,&55,&AD,&36,&81,&F3
defb &DF,&43,&C5,&B4,&AF,&79,&7F,&AC,&F9,&37,&E7,&0A,&22,&D3,&A0,&5A
defb &06,&17,&EF,&67,&60,&87,&20,&56,&45,&D7,&6E,&58,&A9,&B0,&62,&BA
defb &E3,&0D,&25,&09,&DE,&44,&49,&69,&9B,&65,&B9,&E0,&41,&A4,&6C,&CF
defb &A1,&31,&D6,&29,&A2,&3F,&E2,&96,&34,&EE,&DD,&C0,&CA,&63,&33,&5B
defb &70,&27,&F7,&1F,&BE,&12,&B6,&50,&BC,&4D,&28,&C8,&84,&30,&A5,&4C
defb &AB,&E9,&8E,&E8,&7E,&C4,&89,&8B,&0B,&24,&85,&3E,&38,&04,&D2,&90
.RandomPtr
defb 0
Output:
[attachimg=2]
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
call setup
.loop
call rnd
ld l,a
ld h,0
ld bc,14
.mod_loop
or a
sbc hl,bc
jp p,mod_loop
add hl,bc
ld bc,1
add hl,bc
ld a,l
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
and a
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
and a
sbc hl,de
jr nz,loop
call keywait
ret
.rnd
ld a,(seed)
ld b,a
add a,a
add a,a
add a,b
inc a
ld (seed),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
.seed defb 0
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
Output:
[attachimg=3]
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
call setup
.loop
call rnd
ld l,a
ld h,0
ld bc,14
.mod_loop
or a
sbc hl,bc
jp p,mod_loop
add hl,bc
ld bc,1
add hl,bc
ld a,l
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
and a
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
and a
sbc hl,de
jr nz,loop
call keywait
ret
.rnd
push hl
ld a,(RandomPtr)
inc a
ld (RandomPtr),a
ld hl,RandTable
add a,l
ld l,a
jr nc,skip
inc h
.skip ld a,(hl)
pop hl
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
.RandTable
defb &3B,&02,&B7,&6B,&08,&74,&1A,&5D,&21,&99,&95,&66,&D5,&59,&05,&42
defb &F8,&03,&0F,&53,&7D,&8F,&57,&FB,&48,&26,&F2,&4A,&3D,&E4,&1D,&D9
defb &9D,&DC,&2F,&F5,&92,&5C,&CC,&00,&73,&15,&BF,&B1,&BB,&EB,&9E,&2E
defb &32,&FC,&4B,&CD,&A7,&E6,&C2,&10,&11,&80,&52,&B2,&DA,&77,&4F,&EC
defb &13,&54,&64,&ED,&94,&8C,&C6,&9A,&19,&9F,&75,&FA,&AA,&8D,&FE,&91
defb &01,&23,&07,&C1,&40,&18,&51,&76,&3C,&BD,&2A,&88,&2D,&F1,&8A,&72
defb &F6,&98,&35,&97,&68,&93,&B3,&0C,&82,&4E,&CB,&39,&D8,&5F,&C7,&D4
defb &CE,&AE,&6D,&A3,&7C,&6A,&B8,&A6,&6F,&5E,&E5,&1B,&F4,&B5,&3A,&14
defb &78,&FD,&D0,&7A,&47,&2C,&A8,&1E,&EA,&2B,&9C,&86,&83,&E1,&7B,&71
defb &F0,&FF,&D1,&C3,&DB,&0E,&46,&1C,&C9,&16,&61,&55,&AD,&36,&81,&F3
defb &DF,&43,&C5,&B4,&AF,&79,&7F,&AC,&F9,&37,&E7,&0A,&22,&D3,&A0,&5A
defb &06,&17,&EF,&67,&60,&87,&20,&56,&45,&D7,&6E,&58,&A9,&B0,&62,&BA
defb &E3,&0D,&25,&09,&DE,&44,&49,&69,&9B,&65,&B9,&E0,&41,&A4,&6C,&CF
defb &A1,&31,&D6,&29,&A2,&3F,&E2,&96,&34,&EE,&DD,&C0,&CA,&63,&33,&5B
defb &70,&27,&F7,&1F,&BE,&12,&B6,&50,&BC,&4D,&28,&C8,&84,&30,&A5,&4C
defb &AB,&E9,&8E,&E8,&7E,&C4,&89,&8B,&0B,&24,&85,&3E,&38,&04,&D2,&90
.RandomPtr
defb 0
Output:
[attachimg=5]
And this is my original BASIC Output:
[attachimg=4]
I've used variations of the Random number generators from the Wiki pages and also used some code Kev posted which lets you select a Range for the specific Random numbers, though for this kind of program, I need something a bit more unpredictable to make up something that looks totally Random. At the moment I haven't looked into Random number generators which use the R register or the Firmware to return from the clock function, I wasn't sure how they would go.
Can the R register be used for (pseudo)random generation purposes? I'm interested what visual pattern it would yield.
Quote from: Singaja on 13:01, 07 November 15
Can the R register be used for (pseudo)random generation purposes? I'm interested what visual pattern it would yield.
It's not something I've played with, due to the nature of the Assembly book, though I've been told the R register can only be loaded into the Accumulator. @redbox (http://www.cpcwiki.eu/forum/index.php?action=profile;u=229) posted a 16bit solution for it in this thread (http://www.cpcwiki.eu/forum/programming/random-number-generator-in-machine-code/msg16894/#msg16894).
Unfortunately I totally forgot about this thread (http://www.cpcwiki.eu/forum/programming/pseudo-random-number-generation/), which might have a solution for me in there.
I modifed your first code snippet .rnd part to this uber complicated approach
.rnd
ld a,r
ret
Got this:
(http://s23.postimg.org/qb9f5d2cr/small.png)
[UPDATED x 2] I also found this:
//X ABC Algorithm Random Number Generator for 8-Bit Devices:
//This is a small PRNG, experimentally verified to have at least a 50 million byte period
//by generating 50 million bytes and observing that there were no overapping sequences and repeats.
//This generator passes serial correlation, entropy , Monte Carlo Pi value, arithmetic mean,
//And many other statistical tests. This generator may have a period of up to 2^32, but this has
//not been verified.
//
// By XORing 3 bytes into the a,b, and c registers, you can add in entropy from
//an external source easily.
//
//This generator is free to use, but is not suitable for cryptography due to its short period(by //cryptographic standards) and simple construction. No attempt was made to make this generator
// suitable for cryptographic use.
//
//Due to the use of a constant counter, the generator should be resistant to latching up.
//A significant performance gain is had in that the x variable is nly ever incremented.
//
//Only 4 bytes of ram are needed for the internal state, and generating a byte requires 3 XORs , //2 ADDs, one bit shift right , and one increment. Difficult or slow operations like multiply, etc
//were avoided for maximum speed on ultra low power devices.
init_rng(s1,s2,s3) //Can also be used to seed the rng with more entropy during use.
{
//XOR new entropy into key state
a ^=s1;
b ^=s2;
c ^=s3;
x++;
a = (a^c^x);
b = (b+a);
c = (c+(b>>1)^a);
}
unsigned char randomize()
{
x++; //x is incremented every round and is not affected by any other variabl
a = (a^c^x); //note the mix of addition and XOR
b = (b+a); //And the use of very few instructions
c = (c+(b>>1)^a); //the right shift is to ensure that high-order bits from b can affect
return(c) //low order bits of other variables
}
I actually exchanged a & c on register level in my implementation attempt.
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
run start
start
call setup
call rndInit
jp firstEntry
.loop
call rnd
.firstEntry
call sht4
ld a,(rslt)
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
and a
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
and a
sbc hl,de
jr nz,loop
call keywait
ret
.rndInit
ld l,a
;b ^=s2;
ld a,r
ld b,a
xor a
xor b
ld b,a
;a ^=s3;
ld a,r
ld c,a
xor a
xor c
ld (aVal),a
;c ^=s1
ld a,r
ld c,a
xor a
xor c
ld c,a
;x++
ld a,(x)
inc a
ld (x),a
ld l,a
;c = (c^a^x);
ld a,(aVal)
ld a,c
xor l
ld c,a
;b = (b+c);
ld a,b
add c
ld b,a
;a = (a+(b>>1)^c);
ld a,(aVal)
srl b
add b
xor c
ld (aVal),a
ld (x),hl
ret
.rnd
push hl
;x++
ld a,(x)
inc a
ld (x),a
ld l,a
;c = (c^a^x);
ld a,(aVal)
ld a,c
xor l
ld c,a
;b = (b+c);
ld a,b
add c
ld b,a
;a = (a+(b>>1)^c);
ld a,(aVal)
srl b
add b
xor c
ld (aVal),a
pop hl
ret
.sht4
srl a
srl a
srl a
srl a
inc a
ld (rslt),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
;.seed defb 0
.x db 0
.aVal db 0
.rslt defb 0
.xcount defw 0
.checkx defw 640.checky defw 0
Not sure if there are no bugs in implementation,but I got this:
(http://s9.postimg.org/9e1jy3epb/skinszot4.png)
It would be interesting to see how performs the SDCC rand function:
Small Device C Compiler suite / Code / [r9392] /trunk/sdcc/device/lib/rand.c (http://sourceforge.net/p/sdcc/code/HEAD/tree/trunk/sdcc/device/lib/rand.c)
That would translate into something like the following:
_rand::
; next = next * 1103515245UL + 12345;
ld hl,(_next + 2)
push hl
ld hl,(_next)
push hl
ld hl,#0x41C6
push hl
ld hl,#0x4E6D
push hl
call __mullong
pop af
pop af
pop af
pop af
ld c,l
ld b,h
ld a,c
ld hl,#_next
add a, #0x39
ld (hl),a
ld a,b
adc a, #0x30
inc hl
ld (hl),a
ld a,e
adc a, #0x00
inc hl
ld (hl),a
ld a,d
adc a, #0x00
inc hl
ld (hl),a
; return (unsigned int)(next/65536) % (RAND_MAX + 1U);
push af
ld iy,#_next
ld l,0 (iy)
ld iy,#_next
ld h,1 (iy)
ld iy,#_next
ld e,2 (iy)
ld iy,#_next
ld d,3 (iy)
pop af
ld b,#0x10
00103$:
srl d
rr e
rr h
rr l
djnz 00103$
res 7, h
ret
_srand::
; next = seed;
ld hl, #2+0
add hl, sp
ld a, (hl)
ld (#_next + 0),a
ld hl, #2+1
add hl, sp
ld a, (hl)
ld (#_next + 1),a
ld hl,#_next + 2
ld (hl), #0x00
ld hl,#_next + 3
ld (hl), #0x00
ret
_next:
.ds 4
EDIT: well, that's SDCC assembler syntax so it may not be straightforward to assemble. Also that __mullong is a quite a piece of code. So meh.
Quote from: Singaja on 16:21, 07 November 15
Not sure if there are no bugs in implementation,but I got this:
xor a ; a is always 0 ;D
Quote from: Urusergi on 20:50, 07 November 15
xor a ; a is always 0 ;D
Thanks. I made some corrections, looks better but it is still a repeatable pattern :-[
I found a bug, but when I corrected it, it looks even worse :picard2:
Thanks for your replies folks. I've gone back to my original program and made some alterations to it.
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
.timeplease equ &bd0d
call setup
.newseed
call timeplease
ld a,l
ld (seed),a
.loop
call rnd
call sht4
ld a,(rslt)
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
;; and a <- Not sure why this was needed, but works without it.
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
;; and a <- Not sure why this was needed, but works without it.
sbc hl,de
jr nz,newseed
call keywait
ret
.rnd
ld a,(seed)
ld b,a
add a,a
add a,a
add a,b
inc a
ld (seed),a
ret
.sht4
srl a
srl a
srl a
srl a
inc a
ld (rslt),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
.seed defb 0
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
This was about as Random as I could get it, there were some defined vertical lines, but the rest looks scrambled, only thing I could come up with regarding those lines was the clock cycle ticking over. I've used "l" register from Timeplease which gives the most random due to it being the least significant bit.
I was using "and a" which I've removed because I didn't know what it was doing and seems to work without it. I originally had it there based on some code from my assembly book which looked like this:
ld hl,(first)
ld de,(second)
and a
sbc hl,de
jr nz,over
...
...
...
.over
which branches to over if first double byte number is not equal to second double byte number.
But I altered that so I'm only using HL.
So what happens in my code above is when it reaches the Y position loop, it loops back to obtain a new seed which addresses the pattern from occurring all over again.
Here's the result:
[attachimg=1]
I was also getting some other unusual patterns when playing around with the code:
[attachimg=1]
[attachimg=2]
Quote from: reidrac on 16:47, 07 November 15
It would be interesting to see how performs the SDCC rand function:
Small Device C Compiler suite / Code / [r9392] /trunk/sdcc/device/lib/rand.c (http://sourceforge.net/p/sdcc/code/HEAD/tree/trunk/sdcc/device/lib/rand.c)
EDIT: well, that's SDCC assembler syntax so it may not be straightforward to assemble. Also that __mullong is a quite a piece of code. So meh.
I've only played around with Small-C myself. One of the libraries for that had a Random Number Generator for it, unsure how it fared in regard to how random the numbers were.
I could also possibly experiment the last Assembly routine. In a way it works similarly to how BASIC does with RANDOMIZE TIME being initiated. The assembly just needs something to set another seed when it starts looping another line to prevent a patterned effect.
Slightly exhausted by my attempts to fix the previous one I went for something new with more experimental approach. The result is surprisingly good.
.rnd
ld a,r
ld b,a
ld a,r
ld c,a
ld a,r
ld d,a
ld a,r
ld e,a
ld a,(x)
add b
xor c
add d
xor e
add c
xor b
add e
ld (x),a
ret
(http://s30.postimg.org/dmo4r14sh/skinszot5.png)
I've produced a similar sort of outcome when I've used the Refresh Register (R) when acquiring a new seed
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
call setup
.newseed
ld a,r
ld (seed),a
.loop
call rnd
call sht4
ld a,(rslt)
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
sbc hl,de
jr nz,newseed
call keywait
ret
.rnd
ld a,(seed)
ld b,a
add a,a
add a,a
add a,b
inc a
ld (seed),a
ret
.sht4
srl a
srl a
srl a
srl a
inc a
ld (rslt),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
.seed defb 7
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
In terms of writing a routine to generate random numbers having a routine to solely handle that has more practical application.
I was still dancing around the idea of using the Refresh Register, while it produces good Random Results, my Assembly book & Thomas Scherrer's website advise caution when using it in one way or another. Thomas Scherrer's site describes the "R" register as:
Quote
The Z-80 CPU contains a memory refresh counter to enable dynamic memories to be used with the same ease as static memories. Seven bits of this 8 bit register are automatically incremented after each instruction fetch. The eight bits will remain as programmed with the LD R,A instruction. The data in the refresh counter is sent out on the lower portion of the address bus along with a refresh control signal while the CPU is decoding and executing the instruction. The programmer can load the R register for testing purposes, but this register is normally NOT used by the programmer. During refresh, the contents of the I register are placed on the upper
8 bits of the address bus.
What I don't know is what sort of Risk is there in using the Refresh Register, is it bad for the hardware to use it a lot in your code for example?
Quote from: AMSDOS on 09:48, 09 November 15
What I don't know is what sort of Risk is there in using the Refresh Register, is it bad for the hardware to use it a lot in your code for example?
I'm inclined to think it won't damage the hardware, but I don't know.
I'm using rand() from SDCC, but I play with R to set the seed (expects a 16-bit number):
void
setup_srand()
{
__asm
di
ld a, r
ld l, a
ld a, (_tick)
xor l
ld h, l
push hl
call _srand
pop af
ei
__endasm;
}
("tick" is a 8-bit number that gets increased every interrupt; that's how I measure time)
I only call this once per game though.
Quote from: AMSDOS on 09:48, 09 November 15
What I don't know is what sort of Risk is there in using the Refresh Register, is it bad for the hardware to use it a lot in your code for example?
At this point some proper mathematical tools would be helpful to evaluate the distribution that is generated. Which is good :)
Anyway my understanding is that author meant that the register shouldn't be used like "normal" general purpose register (analogously to F).Z80 down to logic gates is reversed engineered here:http://www.righto.com/2014/10/how-z80s-registers-are-implemented-down.htmlOur hardware experts could shed some light, but it seems pretty safe to me.
The R register is a Z80 refresh dedicated register. It is used during refresh cycle (on instruction fetch) for refreshing DRAM.
This feature is not used on the CPC. The DRAM refresh is done by the screen data fetching.
On a computer that uses the Z80 refresh feature, writing to the R register may compromise the DRAM refresh and lead to memory corruption.
Quote from: Singaja on 10:41, 08 November 15
.rnd
ld a,r
ld b,a
ld a,r
ld c,a
ld a,r
ld d,a
ld a,r
ld e,a
Did you know this is equivalent to
.rnd
ld a,r
ld b,a
ld c,(a+3) & 0x7F
ld d,(a+6) & 0x7F
ld e,(a+9) & 0x7F
While at work I'm thinking about this distribution evaluation, proper mathematical tool is the Kolmogorov test , but that seems like an overkill.
My simpler idea is to reserve 256bytes of memory for [0..255] and than each random result would increase the relevant memory cell.
After the screen run the memory should be filled number of occurrences , which can be easily copied from WinApe to something like an Excel or some other spreadsheet tool to make a plot.
That of course will flip for more than 255 instances but for the screen size it should be ok. if not , 2bytes per result should do the trick.
Rough estimate :screen size 320 x 200 = 64000 vs ideal distribution 256*255 = 65280
Quote from: AMSDOS on 09:48, 09 November 15
What I don't know is what sort of Risk is there in using the Refresh Register, is it bad for the hardware to use it a lot in your code for example?
If you're just reading it, there's no problem.
If you're writing it, and you're on a CPC, then there's still no problem, because as far as I know the CPC relies on the CRTC to refresh the DRAM. Other Z80 systems may suffer memory rot if you constrain R too much.
I have made a modified version which tracks the number of occurences in memory:
(http://s21.postimg.org/e80s927xj/distribution.png)
With this tool evaluating results became much easier. This lead me to an approach very similar to one Amsdos is using.
ld a,r
ld b,a
ld a,(myA)
add b
add b
add b
add a
ld (myA),a
Result is quite nice:
(http://s7.postimg.org/xbio8ionv/noiz.png)
Full code:
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
run start
start
call setup
.loop
call rnd
call sht4
ld a,(rslt)
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
and a
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
and a
sbc hl,de
jr nz,loop
call keywait
ret
.rnd
ld a,r
ld b,a
ld a,(myA)
add b
add b
add b
add a
ld (myA),a
ld b,a
ld hl,buffer256
ld a,l
adc b
ld l,a
ld a,b
jp nc,notcarry
inc h
.notCarry
ld b,(hl)
inc b
ld (hl),b
;pop hl
ret
.sht4
srl a
srl a
srl a
srl a
inc a
ld (rslt),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
;.seed defb 0
.myA db 0
.X db 0
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
.padding defs 2+8+7,#CC
.buffer256 defs 256,0
Quote from: pelrun on 15:10, 09 November 15
If you're just reading it, there's no problem.
If you're writing it, and you're on a CPC, then there's still no problem, because as far as I know the CPC relies on the CRTC to refresh the DRAM. Other Z80 systems may suffer memory rot if you constrain R too much.
Yeah I don't know why I'm all cautious about this register, the z80 website made it sound like you could change the state of your system. I guess if did it would only go as far as the emulator bounds.
More likely to do some harm with an OUT command I would of thought.
Quote from: Singaja on 00:01, 10 November 15
I have made a modified version which tracks the number of occurences in memory:
(http://s21.postimg.org/e80s927xj/distribution.png)
With this tool evaluating results became much easier. This lead me to an approach very similar to one Amsdos is using.
ld a,r
ld b,a
ld a,(myA)
add b
add b
add b
add a
ld (myA),a
Result is quite nice:
(http://s7.postimg.org/xbio8ionv/noiz.png)
Full code:
org &4000
.mode equ &bc0e
.border equ &bc38
.inks equ &bc32
.plot equ &bbea
.grapen equ &bbde
.keywait equ &bb18
run start
start
call setup
.loop
call rnd
call sht4
ld a,(rslt)
call grapen
ld hl,(xp)
ex hl,de
ld hl,(yp)
call plot
ld hl,(xp)
inc hl
inc hl
inc hl
inc hl
ld (xp),hl
ld hl,(checkx)
ex hl,de
ld hl,(xp)
and a
sbc hl,de
jr nz,loop
ld hl,0
ld (xp),hl
ld hl,(yp)
dec hl
dec hl
ld (yp),hl
ld hl,(checky)
ex hl,de
ld hl,(yp)
and a
sbc hl,de
jr nz,loop
call keywait
ret
.rnd
ld a,r
ld b,a
ld a,(myA)
add b
add b
add b
add a
ld (myA),a
ld b,a
ld hl,buffer256
ld a,l
adc b
ld l,a
ld a,b
jp nc,notcarry
inc h
.notCarry
ld b,(hl)
inc b
ld (hl),b
;pop hl
ret
.sht4
srl a
srl a
srl a
srl a
inc a
ld (rslt),a
ret
.setup xor a
call mode
ld a,14
ld c,9
ld b,c
call inks
ld a,15
ld c,11
ld b,c
call inks
ld c,26
ld b,c
call border
ret
.xp defw 0
.yp defw 398
;.seed defb 0
.myA db 0
.X db 0
.rslt defb 0
.xcount defw 0
.checkx defw 640
.checky defw 0
.padding defs 2+8+7,#CC
.buffer256 defs 256,0
This looks great, but I don't understand what the data is about, I presume this is an alternative to the earlier 8bit Random Number Generator which had a Buffer, so the Bytes Highlighted from &40B0 to &41AF is the Information you used to create that Random Effect?
Quote from: AMSDOS on 08:38, 10 November 15
This looks great, but I don't understand what the data is about, I presume this is an alternative to the earlier 8bit Random Number Generator which had a Buffer, so the Bytes Highlighted from &40B0 to &41AF is the Information you used to create that Random Effect?
Highlighted bytes are used for debugging only. Each byte cell at given index is increased when a number is generated with the same value. The smaller differences between the cells the more uniform the distribution is.
I made a little BASIC program to count through the INK colours individually, in case anyone was interested, though the colourful results speak for themselves. I just wanted to see if the results gave a good spread.
10 CALL &4000
20 FOR p%=0 TO 15
30 INK p%,0
40 NEXT p%
50 col%=26
60 FOR p%=1 TO 15
70 INK p%,col%
80 INK p%-1,0
90 CALL &BB18
100 NEXT p%
110 PEN 1:CALL &BC02:MODE 2
I made a xor variant with one less instruction and more uniform distribution.
.rnd
ld a,r
ld b,a
ld a,(myA)
xor b
add a
xor b
ld (myA),a
(http://s18.postimg.org/9fggdmat5/xor_skrinszot.png)
Quote from: Singaja on 13:35, 15 November 15
I made a xor variant with one less instruction and more uniform distribution.
.rnd
ld a,r
ld b,a
ld a,(myA)
xor b
add a
xor b
ld (myA),a
This example of code would make a nice alternative for producing 8bit numbers if you don't mind having it posted on the Wiki (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator), I could probably just alter myA to Seed I guess?
Quote from: AMSDOS on 09:20, 17 November 15
This example of code would make a nice alternative for producing 8bit numbers if you don't mind having it posted on the Wiki (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator), I could probably just alter myA to Seed I guess?
I agree, this is a very nice example (being myA the seed). I've used a similar approach in my current project instead the more code-lengthy SDCC approach and it works great!
Quote from: AMSDOS on 09:20, 17 November 15
This example of code would make a nice alternative for producing 8bit numbers if you don't mind having it posted on the Wiki (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator), I could probably just alter myA to Seed I guess?
I will be delighted :)
Quote from: Singaja on 12:30, 17 November 15
I will be delighted :)
Done (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator#8-bit_random_number_generator_using_Refresh_Register_.28R.29) :)
I'm sorry to tell you that the functions you are creating are not so random as your tests say. You are ploting pixels with colors ranging from 0 to 15. Therefore, you are testing randomness for last 4 bits only, not for the full 8 bits. If you test the full 8-bits, results are different. I made a testing program using 2 different graphs: a color stream graph (similar to graphs you were using, but using 8 bits to plot instead of 4), and a 2D spare points plot (most useful to test randomness). Here is the code:
#include <cpctelera.h>
#define VMEM (u8*)0xC000
typedef u8(*TRandFunction)(void);
typedef void(*TDrawFunction)(TRandFunction);
///////////////////////////////////////////////////////////////////
/// Singaja's Random generator 1
u8 randgen() __naked {
__asm
ld a,r
ld b,a
ld a,(seed)
xor b
add a
xor b
ld (seed),a
ld l, a
ret
seed: .db 0x55
__endasm;
}
///////////////////////////////////////////////////////////////////
/// Singaja's Random generator 2
u8 randgen2() __naked {
__asm
ld a,r
ld b,a
ld a,(seed2)
add b
add b
add b
add a
ld (seed2),a
ld l, a
ret
seed2: .db 0x55
__endasm;
}
///////////////////////////////////////////////////////////////////
/// Initialization for CPCtelera's random generators
void initializeRandomGenerators() {
cpct_setRandomSeedUniform_u8(0x55);
cpct_setSeed_glfsr16(0x1120);
cpct_setTaps_glfsr16(GLFSR16_TAPSET_0512);
}
///////////////////////////////////////////////////////////////////
/// CPCtelera's mixed random number generator
u8 mixedRandomGenerator() {
return cpct_getRandomUniform_u8_f( cpct_getRandomu8_glfsr16() );
}
///////////////////////////////////////////////////////////////////
/// CPCtelera's wrapper for simple Random Uniform Generator
u8 getRandomUniform_u8() {
return cpct_getRandomUniform_u8_f(0);
}
///////////////////////////////////////////////////////////////////
/// Put a pixel in Mode 2
void putpixel_m2(u16 x, u8 y, u8 val) {
u8* vram = cpct_getScreenPtr(VMEM, x >> 3, y + 8);
u8 byte = *vram;
u8 pen = val << (7 - (x & 7));
*vram = byte & (pen ^ 0xFF) | pen;
}
///////////////////////////////////////////////////////////////////
/// Fill up the screen with random bytes
void fillUpScreen_colors(TRandFunction randfunc) {
u8* mem = (u8*) 0xC000;
cpct_setVideoMode(0);
cpct_clearScreen(0);
while(mem < (u8*)0xFFFF) {
*mem = randfunc();
++mem;
}
}
///////////////////////////////////////////////////////////////////
/// Fill up the screen with a 2D-pixel plot
void fillUpScreen_pixels(TRandFunction randfunc) {
u16 i;
u8 last_y = 0;
cpct_setVideoMode(2);
cpct_clearScreen(0);
for(i=0; i < 32000; i++) {
u8 y = randfunc();
putpixel_m2(last_y, y>>1, 1);
last_y = y;
cpct_scanKeyboard();
if (cpct_isAnyKeyPressed())
break;
}
}
///////////////////////////////////////////////////////////////////
/// Main function for testing
void main(void) {
TDrawFunction draw = fillUpScreen_colors;
cpct_disableFirmware();
cpct_setVideoMode(0);
initializeRandomGenerators();
// Loop forever
while(1) {
cpct_scanKeyboard();
if (cpct_isKeyPressed(Key_1)) draw(randgen);
else if (cpct_isKeyPressed(Key_2)) draw(randgen2);
else if (cpct_isKeyPressed(Key_3)) draw(cpct_getRandomu8_glfsr16);
else if (cpct_isKeyPressed(Key_4)) draw(getRandomUniform_u8);
else if (cpct_isKeyPressed(Key_5)) draw(mixedRandomGenerator);
else if (cpct_isKeyPressed(Key_C)) draw=fillUpScreen_colors;
else if (cpct_isKeyPressed(Key_P)) draw=fillUpScreen_pixels;
}
}
You can compile it with CPCtelera.
These are the results:
[attach=2]
[attach=3]
Algorithms used, from left to right:
- Singaja's XOR-based random generator
- Singaja's ADD-based random generator
- CPCtelera's implementation of Galois Linear-Feedback Shift Register
- CPCtelera's basic random uniform
- CPCtelera's mixed random generator
Attached you have the full CPCtelera project, including DSK and CDT. Keys are: 1-5 to test one of these algorithms, P for 2D point graph, C for Color Stream Graph.
Coincidentally I need less than 4 bits (get a random block from 7 available).
Singaja's XOR-based random generator is just tiny, if I needed properly randomness I would use SDCC's code. rand is like crypto: it is a very bad idea to make your own, so... don't do it!
EDIT: also, Singaja's code depends on R, that may change more than in these tests depending on how you use the function. In my game there's some variability because user input, but I need from 7 to 16 random numbers in a row (with little R change between them). That might mean I need a slightly better generator ;)
ANOTHER EDIT: I probably need to run my own tests for my use case, but looks like Singaja's code (or the variation I was using) can be useful if I want to provide different difficulty levels. Worst random numbers allow more repeated blocks in a row, which makes easier to "match 3".
Btw, slightly off-topic: why is cpctelera not using stdint.h? (u8 instead uint8_t, part of Standard C)
Quote from: ronaldo on 23:11, 18 November 15
I'm sorry to tell you that the functions you are creating are not so random as your tests say.
Well your more than welcome to submit your Random Number Generator onto the Wiki (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator#8-bit_random_number_generator_using_Refresh_Register_.28R.29).
@AMSDOS (http://www.cpcwiki.eu/forum/index.php?action=profile;u=330), @reidrac (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1504): I may have explained myself bad. I'm not critizising @Singaja (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1284), nor anyone contributing with different ideas to this community. Even the most minimum of the ideas is always worthy. It wasn't my intention to bother anyone of you. Sorry about that.
What I'm telling you is that the method used for measuring randomness is not valid for 8-bit integers. It doesn't have anything to be with special cases. I'm just trying to highlight this part, as I think it is important for this conversation. I think it is important to correctly measure randomness, to fairly compare different methods and have better understanding of them.
@Singaja (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1284)'s methods may be useful in many contexts. But the user has to be conscious of the properties of the algorithm in order to properly use it; The same argument is valid for any other method. @reidrac (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1504): If you are councious of the way it works and it is fine for you, that's nice. The point is not about you, it is about all of us having better understanding of the algorithms and their properties.
Off-topic: CPCtelera (http://lronaldo.github.io/cpctelera) does not use stdint.h because it has been conceived independent and centred only on the CPC: It doesn't have to support different platforms (at least, right now). However, it's always up to the user: CPCtelera (http://lronaldo.github.io/cpctelera) doesn't prevent the user from including stdint.h and using it. Anyway, if you want to discuss these matters, I think it's preferably to use CPCtelera (http://lronaldo.github.io/cpctelera)'s main thread.
Oi m8s :) I'm really happy ronaldo you did properly evaluate my 2 last approaches and keep an eye on not giving false confidence in what is generated. I didn't have proper time yet to grasp the idea of this plot with one color dots but it seems a really reliable measure of randomness. Anyway I'm glad your evaluation is consistent with mine measurements that the xor-variant is much better than the add-variant I made. Clearly it's not trivial, but I hope there's still room for improvement so I'll dive into it in the evening CET (I hope). Since my xor-variant seems to work mostly on 4 least significant bits (if I got that correct) throwing in some bit shifts might improve it.
Quote from: ronaldo on 10:10, 19 November 15
@AMSDOS (http://www.cpcwiki.eu/forum/index.php?action=profile;u=330), @reidrac (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1504): I may have explained myself bad. I'm not critizising @Singaja (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1284), nor anyone contributing with different ideas to this community. Even the most minimum of the ideas is always worthy. It wasn't my intention to bother anyone of you. Sorry about that.
Critizise? Wasn't suggesting you critizise on the Wiki, though any corrected errors or Random Number Generators that could be included on that page would be great.
You'll need to Register to be able to Edit I think, talk to @Gryzor (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1) if you need help.
Quote from: ronaldo on 10:10, 19 November 15
@reidrac (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1504): If you are councious of the way it works and it is fine for you, that's nice. The point is not about you, it is about all of us having better understanding of the algorithms and their properties.
I didn't think you were making a point about me ;D That's clear enough! I shared my use case because it might be useful, not as a counter-example of your evaluation.
Relevant: Dilbert Comic Strip on 2001-10-25 | Dilbert by Scott Adams (http://dilbert.com/strip/2001-10-25)
Quote from: ronaldo on 10:10, 19 November 15
Off-topic: CPCtelera (http://lronaldo.github.io/cpctelera) does not use stdint.h because it has been conceived independent and centred only on the CPC: It doesn't have to support different platforms (at least, right now). However, it's always up to the user: CPCtelera (http://lronaldo.github.io/cpctelera) doesn't prevent the user from including stdint.h and using it. Anyway, if you want to discuss these matters, I think it's preferably to use CPCtelera (http://lronaldo.github.io/cpctelera)'s main thread.
It was just curiosity, thanks. I thought I could learn something specific about SDCC ;)
I found this one written by Joe Wingbermuehle here: http://wikiti.brandonw.net/index.php?title=Z80_Routines:Math:Random
;-----> Generate a random number
; ouput a=answer 0<=a<=255
; all registers are preserved except: af
random:
push hl
push de
ld hl,(randData)
ld a,r
ld d,a
ld e,(hl)
add hl,de
add a,l
xor h
ld (randData),hl
pop de
pop hl
ret
Seems much better than the xor-one.
I've added it to the test.
As they say in their webpage, it's simple and fast, but randomness is worse than yours, as you'll easily see here:
[attachimg=1][attachimg=2]
Attached you'll find the updated CPCtelera (http://lronaldo.github.io/cpctelera) project to test all algorithms.
EDIT: I made a mistake and wasn't correctly returning the genarated value. I've fixed it and randomness is far better than expected. It may be improved, but it is really good for such a small sized algorithm. However, as you see in the 2D-scatter plot, there are some clear square patterns. Depending on the use, that should be taken into account.
Attached file is now updated.
Quote from: Singaja on 10:24, 19 November 15
Oi m8s :) I'm really happy ronaldo you did properly evaluate my 2 last approaches and keep an eye on not giving false confidence in what is generated. I didn't have proper time yet to grasp the idea of this plot with one color dots but it seems a really reliable measure of randomness. Anyway I'm glad your evaluation is consistent with mine measurements that the xor-variant is much better than the add-variant I made. Clearly it's not trivial, but I hope there's still room for improvement so I'll dive into it in the evening CET (I hope). Since my xor-variant seems to work mostly on 4 least significant bits (if I got that correct) throwing in some bit shifts might improve it.
Creating a high quality random number generator is not a trivial matter. The proper test for checking quality is the diehard test for randomness, which runs a battery of statistical programs looking for correlations in the numbers generated. You can grab a copy on the web if you're really interested in this. Using the R register will tie the sequence to time between calls modulo 128 cycles and this itself can create patterns in the numbers generated. But there can be such a thing as "good enough" and maybe that's the argument here.
SDCC provides an LCG-type random number generator copied out of the C standard. It's ok but it's very expensive in computation involving a 32-bit multiply. There are better alternatives: the marsaglia xor generators and a very high quality cmwc generator both of which have already been implemented on the z80. These are designed by the mathematical community and surprisingly have short and fast implementations on the z80. They were mentioned already in another thread but here are some links again:
CMWC
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_cmwc_8.asm?revision=1.2&content-type=text%2Fplain (http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_cmwc_8.asm?revision=1.2&content-type=text%2Fplain)
Marsaglia XOR
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_xor_32.asm?revision=1.2&content-type=text%2Fplain (http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_xor_32.asm?revision=1.2&content-type=text%2Fplain)
Relevant: TIFU by using Math.random() — Medium (https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.ibhrvaelt)
Quote from: Alcoholics Anonymous on 06:48, 20 November 15
But there can be such a thing as "good enough" and maybe that's the argument here.
The argument here initially, was the 8bit random number generators posted on the Wiki (http://www.cpcwiki.eu/index.php/Programming:Random_Number_Generator), were coming back with lovely Patterns :-*
All these screenshots keeps reminding me that I still have a old TV that I need to fix for someone!
Looks like analogue hardware is better at doing random than software :D
Bryce.
@Alcoholics Anonymous (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1116): Oh man! You've spoiled the fun :D . All the algorithms considered here won't pass a single Marsaglia test (diehard tests were created by him). These algorithms have difficulties to pass a simple congruential-sequence test (like 2D-scatter plots), so no need to consider more serius tests. However, I assume that algorithms here are to be used on simple games and similar applications, and they should be "just right" for those tasks. Of course, any serious application will have to consider diehard tests firsts.
However, one of the interesting things here is that really small and fast algorithms may give a "just right" random output for non-critical applications. Marsaglia's CMWC is wonderful and not very expensive, but these algorithms are smaller and cheaper, so they could be consireded for games.
Anyway, if someone wants to know results from Marsaglia test, they are easy to perform using R.
Quote from: ronaldo on 10:29, 20 November 15
@Alcoholics Anonymous (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1116): Oh man! You've spoiled the fun :D . All the algorithms considered here won't pass a single Marsaglia test (diehard tests were created by him). These algorithms have difficulties to pass a simple congruential-sequence test (like 2D-scatter plots), so no need to consider more serius tests. However, I assume that algorithms here are to be used on simple games and similar applications, and they should be "just right" for those tasks. Of course, any serious application will have to consider diehard tests firsts.
Heh heh yeah sorry :) The point is the proper generators are in fact very fast and very small. When Patrik looked into this a few years ago I think we were all very surprised at how small and fast the z80 implementations turned out to be. Up to that point the reason for settling on using R or sequences of bytes in the ROM to generate numbers was that games didn't need anything high quality whereas they did need something small and fast. Now there is something high quality that also happens to be small and fast :)
The R generator that Singaja posted above is similar to what a lot of people have been using. It is definitely fast and small -- 76 (z80) cycles not including register preservation and 15 bytes including seed. Compare that to the high quality 8-bit CMWC: 146 cycles and 42 bytes. The Marsaglia XOR comes to 165 cycles and 44 bytes. There's not much between those in terms of speed and size but there is a huge difference in the quality of numbers generated. If you do write a program that does nothing but generate random numbers, Singaja's version will be twice as fast but then the program will be generating streams of numbers that don't look very random anyway :) OTH if you really need to save those 30 bytes well maybe Singaja's version makes sense if you can get away with using it. And I'm not being facetious here -- desperately searching for a few bytes at the end of a project is quite a common problem.
The Marsaglia XOR generator gets a mention in the article reidrac posted; apparently if you multiply its output by a constant it can pass hard tests for randomness.
I proudly present Joe Wingbermuehle's and my own "xor and xor" hybrid:
;-----> Generate a random number
; ouput a=answer 0<=a<=255
ld hl,(seed_ion)
ld a,r
ld d,a
ld e,a
add hl,de
xor l
add a
xor h
ld l,a
ld (seed_ion),hl
ret
seed_ion: .dw 0x0
(http://s13.postimg.org/o8b9o5ht3/hybrid.png)
@Alcoholics Anonymous (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1116): Yes, man. I completely agree with you. I've been myself reading Marsaglia's works and I'm definitely including several versions of his algorithms in CPCtelera (http://lronaldo.github.io/cpctelera). I'm also looking for some other small generators to include, to let the user select the one that best fits concrete project needs (Mainly some simple LCG, a G-LFSR and some R generator like Singaja's). I think most people will prefer "just right" random quality if they save some bytes and cycles. It is also interesting to consider combinations of them for some applications (like a R-generator with an initial entropy source for seeding CMWC, for instance).
In any case, thank you very much for your considerations and contribution to this discussion. I think we all have the opportunity to learn a lot in this matter :D.
@Singaja (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1284):
Don't know exactly what happens, or where is the difference, but your last proposal shows a much different pattern on my tests:(Note: This test is using 0x5555 as seed. Using 0x0000 as seed results are worse).EDIT: Fixed typo in my code. It now works perfectly :). Updated attached ZIP file.
Attached you'll find this latest implementation. I've also added some new characteristics to the tests:
- Now 2D scatter plots draw 65000 points instead of 32000.
- There is a nice progress bar down the plot that may be hidden (O = progress bar ON, F = progressbar OFF).
It is interesting that, as pointed out previously, with different intermediate code, R-based algorithms behave differently. Up to now, best behaving one is the first version of Ion algorithm. It turns out to improve its quality in this version of the code, when progress bar is drawn. The additional code affects the period of the sequence, that seems to traverse greater part of the space.
I have also run some diehard tests. As expected, none of these algoritms pass a single diehard test. Only G-LFSR does pass 2 out of 64 tests, which is not a big deal though. So, conclusion remains the same: for good randomness quality, other algorithms like CMWC should be considered.
I'm using WinApe for testing and the result is reproducible. My modified Ion function is under 6.
Btw I noticed you have a typo in your code and in one place you're using seed and in the other seed2.
Seed 0 is fine.
You're right. I didn't change that value and it was using incorrect values. Now my test show similar results as yours. In fact, these results seem really better than Ion. Haven't passed diehard tests yet (it probably won't pass, like the others), but this result seems really useful for general needs in games. Nice work :D
[attachimg=1]
Be very, very careful with R-based RNG. Since R follows the number of opcodes executed, its "randomness" solely depends on the context it is used (no matter the amount of bit-shuffling applied to it). It gets somewhat better when the program often go through many different execution paths. But your tight test loop is actually the worst case usage scenario: R will very quickly follow an equally short pattern and the randomness won't be any better than in the Dilbert strip :)
As mentioned before, R is best used once, eg. to generate the seed of a proper PRNG. Finally, it should be noted that one of the best source of entropy, are human input events. Works especially well in games.
Quote from: Grim on 21:48, 20 November 15
... Finally, it should be noted that one of the best source of entropy, are human input events. Works especially well in games.
Isn't is fascinating that the highest degree of order (biological life) can be the source of perfect chaos. :laugh:
Quote from: ronaldo on 20:27, 20 November 15
In any case, thank you very much for your considerations and contribution to this discussion. I think we all have the opportunity to learn a lot in this matter :D .
It's one of those things that's fun to think about too. Incidentally for entropy I also tend to use time spent in the menu screen for the seed. I have used the quick-and-dirty R register to measure that time in the past but then realized you can't get more than 128 different seeds that way and in reality probably much less depending on the length of the code path. That means possibly much less than 128 different games. A counter is better.
Not to derail the discussion but I've also snuck in use of R to generate "random" events inside a quicksort implementation (shocker!!):
; enable equality dispersal
jp m, right_squeeze_0 ; if item[lo=pivot] < item[i]
or a
jr nz, left_squeeze_0 ; if item[lo=pivot] > item[i]
; item and pivot are equal
ld a,r ; instruction count
and 31 ; use prime number
jp pe, left_squeeze_0 ; if parity is even (random event)
The problem being solved here is if quicksort gets an array of equal elements it can degrade to a bubble sort so this is supposed to disperse equal elements randomly to the left and right partitions. I've taken R, ANDed with a small mask (it's modulo 32 cycles of execution time now) and used parity to decide if the element should go left or right. The value of R will not be very random because it will depend on a finite number of code paths spiced up a bit by the user comparison function and the data that determines when swaps are necessary. I still haven't tested this yet but will be doing so when I do some sorting benchmarks.
@Alcoholics Anonymous (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1116): if balance between both sets is the goal, why not send alternatively to one then the other?
Quote from: ronaldo on 23:17, 20 November 15
@Alcoholics Anonymous (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1116): if balance between both sets is the goal, why not send alternatively to one then the other?
I'm out of registers to remember that information. There's even a parameter on the top of the stack so adding another one there would lead to some contorted gymnastics to access both. I'm also trying to avoid using EXX or index registers in the implementation. If the R thing works, it will be a simple fast solution. I can already see that "AND 31" was a bad choice because it leads to execution length mod 32 cycles. The z80 has a lot of instructions that are a multiple of four length so this probably causes cycles shorter than 32 to appear from the AND. Something relatively prime with z80 cycle lengths and maybe mixing in some bits from the top of R would be better I think.