User Tools

Site Tools



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:
 +Newsgroups: comp.sys.cbm
 +Subject: Re: C64 Random Generator?
 +References: <> <> <6hq9sp$> <6hqisi$>
 +Reply-To: (Stephen Judd)
 +Organization: Northwestern University, Evanston, IL
 +In article <6hqisi$>,
 +Cameron Kaiser  <> wrote:
 +> (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'
 +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
 +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-
base/basic_rnd_routine.txt ยท Last modified: 2015-04-17 04:30 (external edit)