base:basic_rnd_routine

This shows you the differences between two versions of the page.

— |
base:basic_rnd_routine [2015-04-17 04:30] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | < | ||

+ | Newsgroups: comp.sys.cbm | ||

+ | Subject: Re: C64 Random Generator? | ||

+ | Summary: | ||

+ | Expires: | ||

+ | References: < | ||

+ | Sender: | ||

+ | Followup-To: | ||

+ | Reply-To: sjudd@nwu.edu (Stephen Judd) | ||

+ | Distribution: | ||

+ | Organization: | ||

+ | Keywords: | ||

+ | Cc: | ||

+ | In article < | ||

+ | Cameron Kaiser | ||

+ | > | ||

+ | > | ||

+ | >> | ||

+ | >>an m-digit random number, then the next number is given by the middle | ||

+ | >>m digits of x^2 (which is of size 2m). Anyways, as you can see it | ||

+ | |||

+ | The " | ||

+ | |||

+ | >>is a deterministic process, and if you start from the same initial | ||

+ | >> | ||

+ | >> | ||

+ | >> | ||

+ | > | ||

+ | >I think this is the one proposed by von Neumann, and someone demonstrated a | ||

+ | >seed that when plugged into the von Neumann generator will devolve to zero | ||

+ | >after only a few cycles. Apparently there are many such seeds, so this | ||

+ | > | ||

+ | |||

+ | I read about this method in the paper " | ||

+ | Fast Computing Machines", | ||

+ | Rosenbluth, Arianna Rosenbluth, and Augusta Teller (Journal Chem Phys., | ||

+ | v21 No. 6, June 1953). | ||

+ | I strongly disagree with it. | ||

+ | |||

+ | >> | ||

+ | >> | ||

+ | > | ||

+ | >IIRC RND(-X) puts X as the seed. So RND(-TI) works well, provided you | ||

+ | > | ||

+ | >you turn the computer on it's less random than you think). | ||

+ | |||

+ | Not quite. | ||

+ | |||

+ | E097 20 2B BC JSR $BC2B ;Get sign of function argument | ||

+ | E09A 30 37 BMI $E0D3 | ||

+ | E09C D0 20 BNE $E0BE | ||

+ | |||

+ | E09E 20 F3 FF JSR $FFF3 ;If zero, initialize from CIA timers | ||

+ | E0A1 86 22 STX $22 | ||

+ | E0A3 84 23 STY $23 | ||

+ | E0A5 A0 04 LDY #$04 | ||

+ | E0A7 B1 22 LDA ($22),Y | ||

+ | E0A9 85 62 STA $62 | ||

+ | E0AB | ||

+ | E0AC B1 22 LDA ($22),Y | ||

+ | E0AE 85 64 STA $64 | ||

+ | E0B0 A0 08 LDY #$08 | ||

+ | E0B2 B1 22 LDA ($22),Y | ||

+ | E0B4 85 63 STA $63 | ||

+ | E0B6 | ||

+ | E0B7 B1 22 LDA ($22),Y | ||

+ | E0B9 85 65 STA $65 | ||

+ | E0BB 4C E3 E0 JMP $E0E3 | ||

+ | |||

+ | E0BE A9 8B LDA #$8B ;If positive, copy iterate to FAC1 (from $8B) | ||

+ | E0C0 A0 00 LDY #$00 | ||

+ | E0C2 20 A2 BB JSR $BBA2 | ||

+ | E0C5 A9 8D LDA #$8D ;Then multiply by num at $E08D (= 11879546) | ||

+ | E0C7 A0 E0 LDY #$E0 | ||

+ | E0C9 20 28 BA JSR $BA28 ;Your favorite routine :) | ||

+ | E0CC A9 92 LDA #$92 ;And add number at $E092 (= 3.927677739e-8) | ||

+ | E0CE A0 E0 LDY #$E0 | ||

+ | E0D0 20 67 B8 JSR $B867 | ||

+ | ;Entry point for RND(-X) | ||

+ | E0D3 A6 65 LDX $65 ;Do something dumb like reverse all the bytes | ||

+ | E0D5 A5 62 LDA $62 | ||

+ | E0D7 85 65 STA $65 | ||

+ | E0D9 86 62 STX $62 | ||

+ | E0DB A6 63 LDX $63 | ||

+ | E0DD A5 64 LDA $64 | ||

+ | E0DF 85 63 STA $63 | ||

+ | E0E1 86 64 STX $64 | ||

+ | E0E3 A9 00 LDA #$00 ;Make positive | ||

+ | E0E5 85 66 STA $66 | ||

+ | E0E7 A5 61 LDA $61 ;Do something dumb like use old exponent | ||

+ | E0E9 85 70 STA $70 ;as extra bits | ||

+ | E0EB A9 80 LDA #$80 ;Set exponent to -1 | ||

+ | E0ED 85 61 STA $61 | ||

+ | E0EF 20 D7 B8 JSR $B8D7 ; | ||

+ | E0F2 A2 8B LDX #$8B ;(mark another correction in Mapping the 64...) | ||

+ | E0F4 A0 00 LDY #$00 | ||

+ | E0F6 4C D4 BB JMP $BBD4 ; | ||

+ | |||

+ | As you can see, this is a pretty nutty algorithm. | ||

+ | |||

+ | >> | ||

+ | >> | ||

+ | >> | ||

+ | >>in an interval (i.e. all numbers between 0 and 1 that the computer | ||

+ | >>can represent), and you want the sequence to be evenly distributed. | ||

+ | > | ||

+ | >I disagree with this definition. I read 'even distribution' | ||

+ | >no number *should* appear more frequently than any other, but I consider it | ||

+ | >random and acceptable for a random number generator to continually return 1, | ||

+ | >as long as the generator depends nothing on the numbers before it. One has | ||

+ | |||

+ | I'm really unclear about what you are saying. | ||

+ | x=1 is a particularly good random number generator, and I'm not even | ||

+ | sure what the last " | ||

+ | all random number generators use an iterative method. | ||

+ | another explanation. | ||

+ | |||

+ | First, an anecdote from " | ||

+ | found that the IBM " | ||

+ | He called customer support, and they said he had misused their generator: | ||

+ | "We guarantee that each number is random individually, | ||

+ | guarantee that more than one of them is random." | ||

+ | |||

+ | There' | ||

+ | That is, the important thing is the _sequence_ of numbers that a | ||

+ | random generator produces. | ||

+ | totally uncorrelated. | ||

+ | |||

+ | So now consider a generator like x=f(x), and for simplicity consider x to | ||

+ | be an 8-bit number. | ||

+ | already generated, at which point the sequence will repeat. | ||

+ | would like the sequence to be as long as possible -- 23 233 23 233 ... | ||

+ | isn't a very useful sequence. | ||

+ | possible sequence has all 256 numbers. | ||

+ | every number in the interval -- it makes sure the sequence has a long | ||

+ | period. | ||

+ | |||

+ | Moreover, the sequence should be uniformly distributed throughout the | ||

+ | interval -- not only should no single number be more probable than | ||

+ | any other, but no group of numbers should be more probable than | ||

+ | any other. | ||

+ | probable than numbers between 241 and 251. Note that sometimes you | ||

+ | do want a non-uniform distribution -- say, a Gaussian distribution | ||

+ | of random numbers -- but these are invariably generated from a | ||

+ | uniform distribution. | ||

+ | |||

+ | Finally, the sequence should be uncorrelated. | ||

+ | is uniform and has a long period, but certainly isn't random. | ||

+ | another sequence: | ||

+ | |||

+ | 142 3 84 242 198 30 34 204 239 77 ... | ||

+ | |||

+ | It looks reasonably random. | ||

+ | x=128*(1+cos(a)). | ||

+ | really is random. | ||

+ | Series Analysis" | ||

+ | to know if the resulting time series is chaotic, nonlinear, deterministic, | ||

+ | correlated, etc. This is also a subject I don't know much about. | ||

+ | random numbers, though, there are several tests available. | ||

+ | one in vol. 2 of "The Art of Computer Programming", | ||

+ | Numerical Recipies references some of the more recent schemes. | ||

+ | |||

+ | It is worth emphasizing that what is important here is that the _sequence_ | ||

+ | is random. | ||

+ | mean anything. | ||

+ | a bad idea -- it doesn' | ||

+ | wreck the sequence. | ||

+ | SID four times to make a new floating point number never work well. | ||

+ | In fact, even reading from SID is probably a bad idea, in terms of | ||

+ | generating a sequence with the above properties (and at worst, you | ||

+ | might sample at some period of the random number generator -- of | ||

+ | course it's very improbable :), but it gives a flavor of the problems). | ||

+ | |||

+ | Why is all of this important? | ||

+ | it isn' | ||

+ | Cute tricks like swapping bytes can be absolutely devastating to e.g. | ||

+ | a Monte-Carlo integrator. | ||

+ | you just aren't simulating nature. | ||

+ | mathematical or scientific background is to be distrusted absolutely! | ||

+ | (For scientific applications anyways. | ||

+ | don't trust me to write a database :). | ||

+ | |||

+ | >Someone (Larry Wall?) likes this as a good source of random numbers: | ||

+ | > | ||

+ | >% ps -auxww | compress | compress > random | ||

+ | > | ||

+ | >Read random bytes from the file random, and run again to re-seed. Hope | ||

+ | >you have a busy system ;-) | ||

+ | |||

+ | Looks neat, but I bet it fails the spectral tests -- i.e. probably | ||

+ | fine for CS applications, | ||

+ | |||

+ | BTW, looks like you're on a Sun -- those ps options have different | ||

+ | meanings on different computers. | ||

+ | |||

+ | > | ||

+ | >and measures the eccentricity; | ||

+ | >on the keyboard. | ||

+ | |||

+ | It would be interesting to see if these pass the tests. | ||

+ | what effect generators have on the underlying security. | ||

+ | experience in this area -- it's a serious question! | ||

+ | |||

+ | S/KEY uses a phrase typed in from the keyboard, so my guess is | ||

+ | "not much". | ||

+ | |||

+ | >>Any other questions? :) | ||

+ | > | ||

+ | >Why is the earth round? :-) | ||

+ | |||

+ | Because a truncated earth wouldn' | ||

+ | |||

+ | evetS- | ||

+ | </ |

base/basic_rnd_routine.txt ยท Last modified: 2015-04-17 04:30 (external edit)