More random questions

[Victragic]

Okay programming wizards,

I'm looking for a simple 'random' routine in assembly that will select the numbers 0 to 255, only *once*, in a seemingly random order when the routine is called 256 times.

I had a look on The Fridge and at 6502.org, but don't even know what I'm looking for is called..

Once again, thanks in advance..

-Glen

[TMR]

Do you have a spare page of RAM you can give over to this? If so, fill it with the values $00 to $ff, then spend a little time picking two random numbers of any value and swapping the numbers in those positions in your table. Do it enough and it'll appear random but not repeat the values until all 256 have gone past.

[MacbthPSW]

If you want a different set of randoms every time the program is run (or more often) then TMR's suggestion is the best I know of.

If you want the same "random" sequence every time, then an 8-bit Linear Feedback Shift Register is what you want.

I used the same one for both Splatform and (on the C-64) Minima and its sequels:

Code: Select all

random
         lda blah
         asl
         eor blah
         asl
         eor blah
         asl
         asl
         eor blah
         asl
         rol blah
         lda blah
         rts

Two things:

1) You have to make sure that "blah" is never set to zero, or it'll get stuck endlessly outputting zeros. So, initialize blah to anything but zero.

2) The sequence will repeat after 255 calls, not 256; zero is not part of the sequence.

LFSRs were probably most famously used in early Atari 2600 games. If you ever wondered how 4k of ROM and 128 bytes of RAM allowed for the 256 "room" world of Pitfall! or the seemingly endless scrolling world in River Raid, now you (sort of) know.

[Victragic]

Thanks for both responses -

I don't have 256 bytes to play with (otherwise TMR's recommendation would be perfect - I had come to similar conclusions in trying to work out how to achieve this) and it doesn't have to be a different sequence each time it is run, so I'll go with a linear feedback shift register..

Cheers
-G

[carlsson]

Can't you feed the linear feedback shift register with different values to get random sequences every time you run the program?

I tried the code above, but I only get a 32 byte "random" sequence, not 255 bytes?

Code: Select all

rng  equ $fd

     ldx #0
ol$: lda $a2
     sta rng
il$: lda rng
     asl
     eor rng
     asl
     eor rng
     asl
     asl
     eor rng
     asl
     ror rng
     lda rng
     sta $1e00,x
     inx
     bne il$
wk$: lda 197
     cmp #64
     beq wk$
     bne ol$

[Victragic]

Well it worked for me..

[carlsson]

Bah. Spot the typo. I used ROR instead of ROL. Interesting how one instruction can make that great difference.

[Jeff-20]

I was just wondering what the ROR and ROL commands could be used for. I had imagined they could only be useful to me for scrolling user graphics (or some other kind of visual effect) I don't know.

[MacbthPSW]

Can't you feed the linear feedback shift register with different values to get random sequences every time you run the program?

Yes, you can seed it with a different non-zero value to enter the sequence at a different point. But the sequence is the same every time.

Bah. Spot the typo. I used ROR instead of ROL. Interesting how one instruction can make that great difference.

Another instruction, like BRK, would make an even bigger difference

[MacbthPSW]

I was just wondering what the ROR and ROL commands could be used for. I had imagined they could only be useful to me for scrolling user graphics (or some other kind of visual effect) I don't know.

I think that's the first thing I thought of too, when I was first learning assembly. I made the beginnings of a scrolling shoot-em-up on the C-64, with some sort of grass pattern repeated full screen. I was very proud of it, but then I realized how boring it looked, and that I couldn't scroll anything else on to the screen with the same trick, so I gave up on that

For Splatform, I used ROR/ROL/LSR/ASL to generate the shifted graphics to make the scrolling look smooth. In hindsight, it may have been quicker just to have shifted all the graphics myself manually; I think the code to do the shifting is longer than the data it generates! But anyway, here's a little snippet from Splatform:

Code: Select all

	    ;make copy of platform shifted by 1 bit for smooth scrolling
	    ldy #7
.loop7 lda char+plat_mid*8,y
	    cmp #$80
	    rol
	    sta char+plat_mid*8+8,y
	    dey
	    bpl .loop7

But ROR and ROL (and their partners LSR and ASL) are especially useful for quickly multiplying and dividing by 2 at a time.

[Kweepa]

Since I didn't find anything on the internet, I just did an exhaustive search of the a and c parameters for a mod 256 Linear Congruential Generator, feeding the results into Monte Carlo Pi (PI) and Serial Correlation Coefficient (SCC) tests from "ent" (http://www.fourmilab.ch/random/).
There were a number that produced almost identical results (3.143 and 0.0004), the simplest being R = (9*R + 193)%256.

Code: Select all

random
    lda blah
    asl
    asl
    asl
    clc
    adc blah
    clc ; added this after johncl noticed the code was wrong!
    adc #193
    sta blah
    rts

This will do exactly what Glen asked for, cycling through all 256 numbers (including 0). It's also 5 bytes smaller (13/18) and 10 cycles faster (20/30 excluding the jsr/rts) than the LFSR posted above.

The LFSR does well on the PI test (3.143) but badly on the SCC test (0.5). However, any single bit from the LFSR does well in the SCC test, whereas the less significant bits of this LCG do badly.

If for some reason you don't like the sequence of numbers generated, you could try any of these multipliers (a) and constants (c).

Code: Select all

a = 13 c = 211
a = 29 c = 143
a = 33 c = 169
a = 41 c = 123
a = 65 c = 73
a = 69 c = 33
a = 69 c = 35
a = 81 c = 119
a = 93 c = 73
a = 101 c = 181
a = 109 c = 211
a = 113 c = 247
a = 117 c = 37
a = 145 c = 25
a = 149 c = 133
a = 153 c = 7
a = 169 c = 71
a = 173 c = 61
a = 177 c = 187
a = 185 c = 177
a = 201 c = 129
a = 209 c = 123
a = 229 c = 65
a = 245 c = 35

This is probably more info than you need, but you never know - this is the info I was looking for.

[MacbthPSW]

Since I didn't find anything on the internet, I just did an exhaustive search of the a and c parameters for a mod 256 Linear Congruential Generator...

...This is probably more info than you need, but you never know - this is the info I was looking for.

Cool, I was unaware of these. I'll try one next time I've got a project where I would have used the old trusty LFSR and let you all know how it goes. And no, that's exactly how much info I'd need if I was to use it

More reading here (don't know why I hadn't thought to look before):
http://en.wikipedia.org/wiki/Linear_con ... _generator
http://en.wikipedia.org/wiki/Pseudorand ... _generator

[johncl]

Since I didn't find anything on the internet, I just did an exhaustive search of the a and c parameters for a mod 256 Linear Congruential Generator, feeding the results into Monte Carlo Pi (PI) and Serial Correlation Coefficient (SCC) tests from "ent" (http://www.fourmilab.ch/random/).
There were a number that produced almost identical results (3.143 and 0.0004), the simplest being R = (9*R + 193)%256.

Code: Select all

random
    lda blah
    asl
    asl
    asl
    clc
    adc blah
    adc #193
    sta blah
    rts

This will do exactly what Glen asked for, cycling through all 256 numbers (including 0). It's also 5 bytes smaller (13/18) and 10 cycles faster (20/30 excluding the jsr/rts) than the LFSR posted above.

This code above does not work. Sat for an hour last night and wondered if I had done something wrong when I integrated it, only to test the algorithm on its own and found out it gives me these these values: $c1, $8a, $9b, $35, $9e - and then onto these - $50, $91, $db, $75, $df, $99, $23, $fc, $9e, $50... endless loop...

Here is the one I have used before (but are open to alternatives). I believe I found this on codebase64:

Code: Select all

//---------------------------------------------------------
// Simple RND function using ASL and EOR
seed:	.byte 0
rnd: {
           lda seed
           beq doEor
           clc
           asl
           beq noEor    // if the input was $80, skip the EOR
           bcc noEor
doEor:     eor #$1d
noEor:     sta seed
	 rts
}

If you start this at $0 for the seed it will generate 255 unique values, but the whole set ends in a clear bitshifting pattern: $01, $02, $04, $08, $10, $20, $40, $80. This is basically how it works, as long as the asl did not result in carry being set it will just shift the bits left until it does. So the numbers will often have a clear "next number is bigger than the last" pattern really, especially for the low numbers you know it will grow gradually. But still it worked in my game Rocket Smash, so I am trying it in my VICRPG (working title).

[Kweepa]

Oh jeez, you're right. Here's the corrected code:

Code: Select all

random
    lda blah
    asl
    asl
    asl
    clc
    adc blah
    clc ; note this second clc.
    adc #193
    sta blah
    rts

I tested its output against the C version I wrote before when testing the randomness, and it worked this time.
Sorry about that!
(I'll also edit the code up above so there isn't a wrong version in the thread.)