6502.org

That definitely deserves some caveats

You have to keep in mind that the randomness comes from
the timing, not the timer.
eg you wouldn't want to seed from the timer as part of an
initialization at power on, you might as well use a constant.

But choice and use of some external event takes some care too.

IF you've carefully constructed you're PRNG with a long
sequence of which you will use only a small part,
you're not going to want to settle for a 16 bit value as
the seed just cause that's the length of the timer, you would
have just thrown away most of your PRNGs "randomness"

If your PRNG uses 32 bit values, a 32 bit timer might help,
but if you eg seed from timing of the first keystroke
after power on, and that usually comes in a relatively small
range of values, it might not help much.
ie if your timer takes 8 seconds to cycle through the possible
seeds but you usually hit the first key within 1-3 seconds
you might not be much better off.

If you were simulating the flip of a coin, you might be ok,
but if you're trying to do monte carlo, calculations maybe not.

The lower bits of the timer might look a lot more random
than the higher bits. If you were simulating the flip of a
coin, the lowest bit of the timer might be good enough by
its self (forget the PRNG).

If you're seeding you're PRNG by timing keystrokes you
could be better off composing a 32 bit seed from two 16 bit
timer values, as opposed to a single 32 bit timer value,
but you might be a LOT better off using four eight bit
values (from the lower eight timer bits)

that was, of course, my point
And, of course, I deliberately chose bad but not (I hope) implausible examples.

I suppose the classic example would be if your timer is running a real
time clock you probably don't want to use the current time as a seed.

If the timer were initialized at power-up and you always read it for the first seed the same number of cycles into an embedded application for example, then of course the timer value will always be the same.  But since the timer value changes at least once per instruction executed, any subsequent branching on a variable condition will change the timing so the next read is not exactly predictable, even if it's soon after the first reading.

Some people have tried to use the random values in RAM upon power-up for random numbers, but many RAMs are actually quite consistent in their "random" power-up values; ie, each power-up of a particular RAM IC will produce the same values as the last.

I'm no expert in random-number generation, and will definitely be referring to Bruce's article in the future when the need arises.  So far I have had no serious need for random numbers in my particular work and projects; but the little I have done followed the simple ideas I've seen before except that I also used the timer reading.

The type of generator to use and how to seed it depends on the application. In a game, especially a game with fast-paced action, you can get away with just about anything. Something more substantial in terms of both generator and seed is needed for things like encryption or Monte Carlo type calculations. Rather than debate the merits of LC vs. LFSR (Linear Feedback Shift Register) vs. lagged Fibonacci sequence, etc. type generators, I just provided routines for an LC type generator for those who wish to use that type of generator. I tailored them specifically to the 6502, with an eye toward efficient multiplication -- the typical bottleneck in an LC type generator.

Lee Davison has routines and information for LFSR type generators on his website for those who wish to use that type of generator. EhBASIC uses an LFSR type generator.

The Apple II timed keypresses, but did it in entirely in software. While waiting for keypresses, it incremented a 16-bit counter every few microseconds, which gave an unpredictable number unless the auto-repeat was in effect (from holding down the key, or, on early Apples, using the REPT key). Applesoft BASIC kept its random number seed separate from this counter, but "Integer" BASIC, the earlier BASIC dialect, used that counter as the random number seed. Integer BASIC used a 15-bit LFSR type generator (with provisions to avoid an all zero seed), which meant that the sequence length was only 32767. It could be used for games (Steve Wozniak, who wrote Integer BASIC, would sometimes refer to it as "game BASIC" back in the day), but there are other applications where this wouldn't be an adequate generator.

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin"

I hope I haven't made it sound like I'm disparaging the idea of using a timer to get some randomness.

It's a great idea, and indeed might be the only thing available that offers any possibility of injecting
anything like true randomness in to software.

I just definitely think that it needs to be mentioned (probably with the next breath) that there could be gotchas
(particualrly if one were going to write it up as a "tip of the day")

I wasn't calling for an elaborate analysis of pros and cons or whys and wherefores,
although, an example or two wouldn't be out of place.
That wasn't meant as an plausible example, more as an argument " reductio ad absurdum"
Like, 'you obviously wouldn't want to do this, but if you're not careful you could do something less obvious
but almost as bad'

But my whole point was just that it should be mentioned that you need to be careful


(as an aside)
I can't imagine that anyone's going to do many 80 bit floating point monte carlo calculations or, you know,
128 bit crytography with a 6502 but..

One of the first things I tried when I got my C64 (or maybe it was the VIC20) was calculating pi by
monte carlo methods

And apparently that's a lot more common than (I would have) guessed,
'cause I've heard several people mention doing exactly the same thing and
having exactly the same problems I had.

I didn't see that could you give me a hint where to look (I didn't go through his whole site)

And I went to all that trouble with the baking section, pah! 8^)=
Here ..
http://www.themotionstore.com/leeedavis ... /prng.html
.. or here, same thing but with adverts ..
http://members.lycos.co.uk/leeedavison/ ... /prng.html
.. both of which have been updated recently.

I've re written the RND() function in EhBASIC to use the Galois LFSR which with taking every 17th result makes the sequence fairly good for sets with less than 32768 distinct elements. This will all be in EhBASIC 2.xx as soon as I get all the undocumented features ironed out.

Cheers,

Lee.

Maybe he was just feeling guilty that the middle square method didn't turn out to be so hot.
You're right. There is plenty of subtlety with random number generation, so just blindly applying any old approach is usually not a good idea. My LC routines are just one option; they're what I use. There are far too many broken RNGs out there as it is. Between the bugs and design flaws, the RNG in Applesoft and SYM 1 BASIC (there is a disassembly of the latter on Lee's web site) is an excellent example of how NOT to write an RNG.
No, I use RNGs mainly for games. My routines were intended to be a decent "middleweight" approach, and they are certainly not the be all, end all of 6502 RNGs. I use the middle RAND routine, but the fast RAND routine is under 100 cycles if speed is an issue.

Well, actually, I have looked at the baking section
You don't say, but assuming you're still using a maiximal 32 bit PRNG,
with a cycle length of 65535, won't that just be a complicated 3855 length
PRNG? (in so far as 65535/17=3855)

ack!
let me rephrase that..

You don't say, but assuming you're still using a maiximal 32 bit PRNG,
with a cycle length of 4294967295, won't that just be a complicated 252645135 length
PRNG? (in so far as 4294967295/17=252645135)



ps I usually use Primus for whuppin' eggs and stuff

Since 17 and 2^32 are co-prime (because 17 is itself prime) RND will still take 4 294 967 296 calls before repeating a value. However I think the same randomness could be achieved in less time by XORing a smaller number (7 or maybe 5) of outputs together. This also means the raw output of the shift register is not exposed, I don't have proof but believe the shift register can be cloned from a single word of output if the polynomial (tap points) is known.

Of course, the Galois PRNG is exactly the same as a CRC generator, so if you already have one it can be re-used. As long as the first word is non-zero, you can checksum the seed followed by zeroes, repeat the seed endlessly, or feed in whatever volatile data you have to hand.

well, again, he didn't say (that I recall) but unless he's taking special pains
the cycle length will be 2^32-1

After lots of testing I've settled on a maximal length 32 bit Galois LFSR with a single byte feedback that returns every 19 number from the sequence.

I've chosen this for a number of reasons. The single feedback byte makes this as easy to implement on a 6502 as a 680x0, both versions of EhBASIC now generate the same sequence.

You get 2^32-1 numbers in sequence before it all starts again. This would take over 49hours to cycle at one result per milisecond, which I can live with.

Taking every 19th number removes any obvious pattern that I can see in up to four dimensions over relatively short runs. This was done by taking 512k byte values and plotting them as x,y,z,colour points in a cube.

Chi square and serial correlation coefficient results are good for a number of 65536 byte sample runs that were tried.

I've now done quite a bit of experimenting with number generation and this seems to me to be the best all round solution for size, speed and randomness. It's by no means perfect but if you really need better random numbers then BASIC on a 6502, or 680x0, is probably not the best place to start. If you insist there's always the USR() function to let you run your own, hand crafted, PRNG routines.

Lee.

i'd say just xor'ing it with another counter -running at a different frequency- -preferably in the other direction- (although that is easily solved by in turn substracting that or inverting that, but that requires more cpu registers)... such as oh eh. the current lowest 8 bits of the raster counter, kinda fixes all 'it's not truely random' problems.

something like this where only the one for the pet is not actually, really, random but time dependent.
GETRANDOM:
.IF PRODUCT=264
PUSHAY
LDY #$05
LDA $FF1D ; TED RASTER COUNTER
:
EOR $FF00,Y ; TED FREE RUNNING COUNTERS
DEY
BPL :-
STA RANDOMBYTE
PULLAY
.ENDIF
.IF PRODUCT=64
PHA
LDA $D41B ; SID OSCILLATOR SID VOICE-3
EOR $D41C ; SID OSCILLATOR SID VOICE-3
EOR $D012 ; VIC-II RASTER COUNTER
STA RANDOMBYTE
PLA
.ENDIF
.IF PRODUCT=20
PHA
LDA $9004 ; VIC-I RASTER COUNTER
; ADD EOR WITH 6522 FREE RUNNING COUNTERS
ORA VIA+$04
ORA VIA+$05
STA RANDOMBYTE
PLA
.ENDIF
.IF PRODUCT=8032||PRODUCT=4032
PHA
; MUST FIND SOME ADDITIONAL RANDOM SOURCE FOR THE PET AS THIS COUNTS DOWN
LDA VIA+$04
ORA VIA+$05
STA RANDOMBYTE
PLA
.ENDIF
RTS

note that out of these the pet lacks any 'other source' of 'random' user-independent data (can't read out the current scanline for all i know) and as such there we'll just have to live with the only source being the via. and 'whatever time it just so happened to be queried upon'