Random number generation on a VIC

[Victragic]

Hi,

apologies if this has been raised before...

I'm looking for a quick way to fill the screen with random characters between a certain limit.. say 0-7..

I find I can create 'randomness' if I slow things down and generate a number based on the Raster beam location, but surely there's a quicker and easier way? What is the internal random function RND based on?

If someone can help out, I'd be mighty obliged

-Glen

[Mike]

What is the internal random function RND based on?

RND(0) uses TI, RND(1) is based on a linear-congruential generator (seeded with RND(-x)). However, Commodore tried to "improve" upon that, by swapping some bytes, and thus broke the RND() function. It already loops after ~60000 calls, even though it would loop only after 4 billion numbers if it were not broken.

I'm looking for a quick way to fill the screen with random characters between a certain limit.. say 0-7.. [...] generate a number based on the Raster beam location, but surely there's a quicker and easier way?

In ML, you might try a linear-feedback-shift generator, something like:

Code: Select all

LSR $FA
ROR $FB
BCC skip
LDA $FA
EOR #$AA  ; most significant bit *must* be set
STA $FA
LDA $FB
EOR #$2B  ; least significant bit should be set
STA $FB
.skip

It gives single pseudo-random bits in the C flag, which you can rotate into another value. Use a non-0 value to seed.

Greetings,

Michael

[Bacon]

The Fridge at Stephen L. Judd's ffd2.com site has some good stuff, like this random routine. And this.

[Victragic]

Very cool, that's exactly what I needed..

[nbla000]

Take a look to this old thread too.

I've used Carlsson/Nippur72 solutions for my works, the last was a random game selection inside the Mega-Cart Menu.

[Jeff-20]

A random game is a great idea! It's like a Vic iPod. "Shuffle Games"

[Victragic]

A random game is a great idea! It's like a Vic iPod. "Shuffle Games"

I had an MP3 player that couldn't manage to randomly shuffle the tunes -- selecting 'Random' made them play out of order, but it was always the same sequence..

-Good old Taiwanese knockoffs..

[Jeff-20]

I once had an MP3 player with a "Random" mode and no Shuffle mode. This meant that the songs could be played in any order, but it could play the same song two or three times in a row and never get to another song for days. I hated that.

[carlsson]

Yep, I call the broken ROM routine for a random number, but implementing your own small integer RNG seems like a better approach!

[WillKemp]

This thread's a bit old, but i thought i'd add a comment from what i've rediscovered disassembling River Rescue (which i wrote 25 years ago).

If there's no human intervention, random number generation is fairly tricky, but once human input comes into it, it becomes quite easy, i think.

After a bit of experimenting (in the 80s), the way i implemented a random number generator was with three counters - one incremented every time the NMI handler was called, one incremented by the IRQ handler, and one which was incremented every time round the main control loop.

The random number generator takes the raster value and XORs it with each of those counters, one after the other. The result's returned as the "random" number.

That random number generator is used in the intro routine and in demo mode - but it's certainly not very random in the intro or the first run of the demo mode. In fact, if it's allowed to run into the demo mode after start up, it repeats the same pattern each time. I'm using Vice, so the raster scan timing's probably rock solid, but the raster timing of the Vic hardware might be a different matter altogether. Athough i guess the timing of everything would fluctuate together. However, i can't remember it being so predictable in the pre-play state when i wrote it.

As soon as you hit a key though, it starts to become a lot more random. That's because a fraction of a second difference in the time you hit the start key, or move the joystick, press the fire button, etc, makes a significant difference to the generated random number.

It's pretty random, i think, but it must respond to the way it's played - in some intangible way - i reckon!

[Kweepa]

The Fridge at Stephen L. Judd's ffd2.com site has some good stuff, like this random routine.

I found a bug in the LCG in rand1.s (by comparing with the output from a C version): the carry bit should be cleared before adding $3611. So the code should be:

Code: Select all

GETRAND                   
         LDA RANDOM+1     
         STA TEMP1        
         LDA RANDOM       
         ASL              
         ROL TEMP1        
         ASL              
         ROL TEMP1        
         CLC              
         ADC RANDOM       
         PHA              
         LDA TEMP1        
         ADC RANDOM+1     
         STA RANDOM+1     
         PLA              
         CLC             ; added this instruction - kweepa
         ADC #$11         
         STA RANDOM       
         LDA RANDOM+1     
         ADC #$36         
         STA RANDOM+1     
         RTS 

This should make the generator cycle through all 65536 values without repeats. Sorry about adding a byte!

[EDIT]
I ran some tests on the old code vs. the new code using "ent" to ensure correct behaviour. For the statistical tests, I used the top 8 bits.

Code: Select all

TEST                  NEW       OLD
Entropy              8.00      6.35  bits per byte - good random # generator should be 8
ChiSquare Dist       0.00      2.36  value - good random # generator should be 0
ChiSquare rand      50.00      0.96  % - good random # generator should be 50
Mean               127.50    124.78  good random # generator should be 127.5
Monte Carlo pi       3.13      3.12  good random # generator will approach 3.14 slowly
Serial correlation   0.00     -0.03  good random # generator will be 0

I also checked for premature looping. The new code looped after 65536 numbers as expected. The old code when seeded with 0 looped after 358 numbers to the 263rd number and repeated this 95 number sequence.

[carlsson]

Nice spotted! Did you message Steve, in case he still maintains The Fridge actively?

[Kweepa]

My randomly wandering creatures were behaving distinctly non-randomly, so it was easy to see

It doesn't look like he's updated his website in a couple of years, but I'll send him an email.