User Tools

Site Tools


base:basic_rnd_routine

Differences

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

Link to this comparison view

base:basic_rnd_routine [2015-04-17 04:30] (current)
Line 1: Line 1:
 +<​code>​
 +Newsgroups: comp.sys.cbm
 +Subject: Re: C64 Random Generator?
 +Summary: ​
 +Expires: ​
 +References: <​Pine.GSO.3.95.980424085552.16245A-100000@wartburg.kom.auc.dk>​ <​Pine.SOL.3.95.980424134847.17282G-100000@hobbes.dai.ed.ac.uk>​ <​6hq9sp$ok7@news.acns.nwu.edu>​ <​6hqisi$qg6@examiner.concentric.net>​
 +Sender: ​
 +Followup-To: ​
 +Reply-To: sjudd@nwu.edu (Stephen Judd)
 +Distribution: ​
 +Organization:​ Northwestern University, Evanston, IL
 +Keywords: ​
 +Cc: 
  
 +In article <​6hqisi$qg6@examiner.concentric.net>,​
 +Cameron Kaiser ​ <​cdkaiser@delete.these.four.words.concentric.net>​ wrote:
 +>​judd@merle.acns.nwu.edu (Stephen Judd) writes:
 +>
 +>>​Another method I have seen is the "​middle-squares"​ process: if x is
 +>>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 "​it"​ above refers to any random number generation algorithm, btw.
 +
 +>>is a deterministic process, and if you start from the same initial
 +>>​value (the "​seed"​),​ then you will generate the same sequence. ​ This
 +>>​isn'​t a bad thing, btw -- it means you can reproduce results, initial
 +>>​conditions,​ etc.
 +>
 +>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
 +>​generator is effectively useless.
 +
 +I read about this method in the paper "​Equation of State Calculations by 
 +Fast Computing Machines",​ by Nick Metropolis, Edward Teller, Marshall
 +Rosenbluth, Arianna Rosenbluth, and Augusta Teller (Journal Chem Phys.,
 +v21 No. 6, June 1953). ​ "​Useless"​ is a very strong adjective; therefore
 +I strongly disagree with it.
 +
 +>>​Also,​ RND(-X) swaps bytes in the random number ($61<​->​$64 and 
 +>>​$62<​->​$63 I believe) -- silly.
 +>
 +>IIRC RND(-X) puts X as the seed. So RND(-TI) works well, provided you
 +>​consider the time a random number (but since it always starts at zero when
 +>you turn the computer on it's less random than you think).
 +
 +Not quite. ​ Let's have a look-see:
 +
 +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   ​C8 ​        INY
 +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   ​C8 ​        INY
 +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 ;​Normalize result (remove leading zeroes)
 +E0F2   A2 8B      LDX #$8B ;(mark another correction in Mapping the 64...)
 +E0F4   A0 00      LDY #$00
 +E0F6   4C D4 BB   JMP $BBD4 ;​Store number at $008B
 +
 +As you can see, this is a pretty nutty algorithm.
 +
 +>>​Now,​ what is relevant here is that some sequences are better than
 +>>​others! ​ The choice of a and m in a*x mod m affects the calculation
 +>>​quite significantly. ​ Ideally you want to generate every number
 +>>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'​ to say that
 +>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. ​ I for one don't think
 +x=1 is a particularly good random number generator, and I'm not even
 +sure what the last "​it"​ of the last sentence refers to.  Moreover,
 +all random number generators use an iterative method. ​ I will try 
 +another explanation.
 +
 +First, an anecdote from "​Numerical Recipies"​. ​ One of the authors had 
 +found that the IBM "​RANDU"​ random number generator didn't work very well.
 +He called customer support, and they said he had misused their generator:
 +"We guarantee that each number is random individually,​ but we don'​t ​
 +guarantee that more than one of them is random."​
 +
 +There'​s an important moral here: "​random"​ is really a relative quantity.
 +That is, the important thing is the _sequence_ of numbers that a
 +random generator produces. ​ The sequence should be very long, and be
 +totally uncorrelated.
 +
 +So now consider a generator like x=f(x), and for simplicity consider x to
 +be an 8-bit number. ​ Eventually the generator will hit a number it has
 +already generated, at which point the sequence will repeat. ​ Naturally one
 +would like the sequence to be as long as possible -- 23 233 23 233 ...
 +isn't a very useful sequence. ​ Since x is an 8-bit number, the longest
 +possible sequence has all 256 numbers. ​ This is one reason to generate
 +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. ​ For example, numbers between 20 and 30 shouldn'​t be more
 +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. ​ The sequence ​ 0 1 2 3 ...
 +is uniform and has a long period, but certainly isn't random. ​ Here's
 +another sequence: ​
 +
 + 142 3 84 242 198 30 34 204 239 77 ...
 +
 +It looks reasonably random. ​ In fact, I generated it using a=a+2*pi/​4.321
 +x=128*(1+cos(a)). ​ So it takes some real work to ensure that a sequence
 +really is random. ​ Much of this falls under the broad rubric of "Time
 +Series Analysis"​ -- you've got a sensor sending numbers to you, and want
 +to know if the resulting time series is chaotic, nonlinear, deterministic,​
 +correlated, etc.  This is also a subject I don't know much about. ​ For
 +random numbers, though, there are several tests available. ​ Knuth has
 +one in vol. 2 of "The Art of Computer Programming",​ and I'm sure that
 +Numerical Recipies references some of the more recent schemes.
 +
 +It is worth emphasizing that what is important here is that the _sequence_
 +is random. ​ Making sure that "each number is random individually"​ doesn'​t
 +mean anything. ​ This is why doing things like swapping bytes is such
 +a bad idea -- it doesn'​t make the number "more random",​ but it does
 +wreck the sequence. ​ It's also why doing things like reading from
 +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? ​ For most computer science applications,​
 +it isn'​t. ​ For most scientific applications,​ it is terribly important.
 +Cute tricks like swapping bytes can be absolutely devastating to e.g.
 +a Monte-Carlo integrator. ​ Unless that sequence has the right properties,
 +you just aren't simulating nature. ​ A computer jock without any 
 +mathematical or scientific background is to be distrusted absolutely!  ​
 +(For scientific applications anyways. ​ If it makes you feel better,
 +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,​ but death for any Real application :).
 +
 +BTW, looks like you're on a Sun -- those ps options have different
 +meanings on different computers.
 + 
 +>​F-Secure ssh for Windows has you move your mouse around in circular motion
 +>and measures the eccentricity;​ a lot of PGP implementations just have you bang
 +>on the keyboard.
 +
 +It would be interesting to see if these pass the tests. ​ I also wonder
 +what effect generators have on the underlying security. ​ I have zero
 +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'​t give as good of a result.
 +
 + evetS-
 +</​code>​
base/basic_rnd_routine.txt ยท Last modified: 2015-04-17 04:30 (external edit)