Rnd
From Maze
5. Randomness
Among other things, the program being discussed is a display of (near) randomness, which is often mentioned in digital media discussions but seldom explored in depth. The “pseudo-random” capability of the computer far exceeds a human’s randomization ability and is core to many areas of computing, including graphics (Perlin noise) and communication (random backoff for Ethernet).
Contents[hide] |
The Random Function (RND) as used in Commodore 64 BASIC
with particular regard to: 10 print chr$(79+int(rnd(0)*2));:goto 10=
C64-specific:
rnd(1) is a deterministic sequence of random numbers Rnd(0) means use the timer as the random number generator
This is a commented disassembly of the C64 ROM. Elsewhere, I've quoted the relevant code to perform RND() in C64 Basic.
C64 prog. ref. manual (zero page addresses)
This is a reference to assist in interpretation the the above disassembly.
C64 Floating-Point
The native number format of Commodore BASIC, like that of its parent MS BASIC, was floating point. Most of the contemporary BASIC implementations used one byte for the characteristic (exponent) and three bytes for the mantissa. This led to problems in business applications since the accuracy of a floating point number using a three-byte mantissa is only about 6.5 decimal digits, and round-off error is common. Commodore, however, used MS BASIC's four-byte mantissa, which made their BASIC much more adapted for business than most other BASICs of the era. (reference: http://en.wikipedia.org/wiki/Commodore_BASIC)
Dartmouth BASIC
Dartmouth BASIC source code in assembly
Dartmouth BASIC manual/specification
The original BASIC manual shows that Dartmouth Basic (the first BASIC), had a similar specification for the RND(x) function. It generated a single stream of pseudorandom numbers. Interestingly, it recommends throwing away the first "115" or so numbers. (reference: BASIC_Oct64.pdf, page 45 of PDF, page -39- of original document)
Survey of Random Number Algorithms
These are rather technical in nature, but can be used to contextualize the "quality" of the random number generator used in the C64 by comparing it with those used today in languages like Java and Python (need more lingos?).
Good technical overview with links to many papers on RNG
Specific LCG algorithms and quality
classic random algorithms, e.g. in Fortran
(Java) The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.)
Python uses the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of 2**19937-1. The underlying implementation in C is both fast and threadsafe. The Mersenne Twister is one of the most extensively tested random number generators in existence. However, being completely deterministic, it is not suitable for all purposes, and is completely unsuitable for cryptographic purposes.
Article:Mathematica-PRNG-Eval.pdf
Etymology of the Word "Random"
"having no definite aim or purpose," 1650s, from at random (1560s), "at great speed" (thus, "carelessly, haphazardly"), alteration of M.E. randon "impetuosity, speed" (c.1300), from O.Fr. randon "rush, disorder, force, impetuosity," from randir "to run fast," from Frankish *rant "a running," from P.Gmc. *randa (cf. O.H.G. rennen "to run," O.E. rinnan "to flow, to run"). In 1980s college student slang, it began to acquire a sense of "inferior, undesirable." Random access in ref. to computer memory is recorded from 1953. (reference: http://www.etymonline.com/index.php?term=random)
The latest buzzword used amongst mindless teenagers as a way of showing just so utterly irreverent their predictable sense of humour is. Particularly dominant among English teens and University students, the word "random" or the act of being "random" is a desperate plea for others to recognise how totally against the grain of the norm you are and that you're really crazy and out there. Trouble is, being "random" is predictable, boring, moronic and extremely sad indeed. (reference: http://www.urbandictionary.com/define.php?term=random)
To most of the rest of us something that is random has no predictable pattern. But 700 years ago when this word came to English from French it meant “to rush headlong” so that the lack of predictability was more a sense of being out of control due to speed.
The French were thought to have gotten the word from a Germanic word.
In French the word was randon with an N not an M and has since developed into randonnee which means a long outing or a hike. So in French there isn’t the sense so much of unpredictability, but wandering is still retained. (reference: Charles Hodgson, http://podictionary.com/?p=32)
Technical and Philosophical Definitions of Randomness
C64 Rnd(0) Disassembly
- This an excerpt of the relevant parts of the C64 BASIC and Kernal ROMs which implement the RND(1) function in the titular program.
perhaps we can depict this function somehow.
- I would like to depict it, but I don't fully understand it yet. I can't quite find the portion where the floating-point mantissa is manipulated. I can see parts where it is shifted by one byte, but I can't see where it folds in the constants located at $E08D-$E094. Can anyone help?
(most disassembly from http://www.ffd2.com/fridge/docs/c64-diss.html)
; float numbers for RND E08D .BY $98,$35,$44,$7A,$00 E092 .BY $68,$28,$B1,$46,$00 (http://www.devili.iki.fi/Computers/Commodore/C64/Programmers_Reference/page_iii.html) ; FACEXP 0061 97 Floating-Point Accumulator #1: Exponent ; FACHO 0062-0065 98-101 Floating Accum. #1: Mantissa ; FACSGN 0066 102 Floating Accum. #1: Sign ; FACOV 0070 112 Floating Accum. #1. Low-Order (Rounding) ; RND function ; With RND(0) the C64 generates the random number with the internal clock. (http://www.c64-wiki.com/index.php/RND) E097 20 2B BC JSR $BC2B ; get sign of accumulator E09A 30 37 BMI $E0D3 ; do negative E09C D0 20 BNE $E0BE ; positive ; rnd(0) E09E 20 F3 FF JSR $FFF3 ; read base address of I/O device E0A1 86 22 STX $22 ; INDEX 0022-0025 34-37 Utility Pointer Area 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 ; positive number, e.g. rnd(1) E0BE A9 8B LDA #$8B ; E0C0 A0 00 LDY #$00 E0C2 20 A2 BB JSR $BBA2 ; retrieve float accu from index XY E0C5 A9 8D LDA #$8D ; load generator seeds E0C7 A0 E0 LDY #$E0 E0C9 20 28 BA JSR $BA28 ; move float indexed by AY into second float accu E0CC A9 92 LDA #$92 ; load more generator seeds E0CE A0 E0 LDY #$E0 E0D0 20 67 B8 JSR $B867 ; add float indexed by AY to float accu ; negative operand, e.g. rnd(-1) E0D3 A6 65 LDX $65 ; swap $65 and $62 E0D5 A5 62 LDA $62 E0D7 85 65 STA $65 E0D9 86 62 STX $62 E0DB A6 63 LDX $63 ; swap $63 and $64 E0DD A5 64 LDA $64 E0DF 85 63 STA $63 E0E1 86 64 STX $64 ; common entry point for rnd E0E3 A9 00 LDA #$00 ; clear sign of float acc #1 E0E5 85 66 STA $66 E0E7 A5 61 LDA $61 ; more float acc #1 stuff (exponent and rounding) E0E9 85 70 STA $70 E0EB A9 80 LDA #$80 E0ED 85 61 STA $61 E0EF 20 D7 B8 JSR $B8D7 ; a floating-point routine E0F2 A2 8B LDX #$8B E0F4 A0 00 LDY #$00 E0F6 4C D4 BB JMP $BBD4 ; store float accu in index XY ; add float indexed by AY to float accu B867 20 8C BA JSR $BA8C ; a floating-point routine B8D7 A0 00 LDY #$00 B8D9 98 TYA B8DA 18 CLC B8DB A6 62 LDX $62 B8DD D0 4A BNE $B929 B8DF A6 63 LDX $63 B8E1 86 62 STX $62 B8E3 A6 64 LDX $64 B8E5 86 63 STX $63 B8E7 A6 65 LDX $65 B8E9 86 64 STX $64 B8EB A6 70 LDX $70 B8ED 86 65 STX $65 B8EF 84 70 STY $70 B8F1 69 08 ADC #$08 B8F3 C9 20 CMP #$20 B8F5 D0 E4 BNE $B8DB B8F7 A9 00 LDA #$00 B8F9 85 61 STA $61 B8FB 85 66 STA $66 B8FD 60 RTS BA28 20 8C BA JSR $BA8C ; move float indexed by AY into second float accu BA8C 85 22 STA $22 BA8E 84 23 STY $23 BA90 A0 04 LDY #$04 BA92 B1 22 LDA ($22),Y BA94 85 6D STA $6D BA96 88 DEY BA97 B1 22 LDA ($22),Y BA99 85 6C STA $6C BA9B 88 DEY BA9C B1 22 LDA ($22),Y BA9E 85 6B STA $6B BAA0 88 DEY BAA1 B1 22 LDA ($22),Y BAA3 85 6E STA $6E BAA5 45 66 EOR $66 BAA7 85 6F STA $6F BAA9 A5 6E LDA $6E BAAB 09 80 ORA #$80 BAAD 85 6A STA $6A BAAF 88 DEY BAB0 B1 22 LDA ($22),Y BAB2 85 69 STA $69 BAB4 A5 61 LDA $61 BAB6 60 RTS ; retrieve float accu from index XY BBA2 85 22 STA $22 BBA4 84 23 STY $23 BBA6 A0 04 LDY #$04 BBA8 B1 22 LDA ($22),Y BBAA 85 65 STA $65 BBAC 88 DEY BBAD B1 22 LDA ($22),Y BBAF 85 64 STA $64 BBB1 88 DEY BBB2 B1 22 LDA ($22),Y BBB4 85 63 STA $63 BBB6 88 DEY BBB7 B1 22 LDA ($22),Y BBB9 85 66 STA $66 BBBB 09 80 ORA #$80 BBBD 85 62 STA $62 BBBF 88 DEY BBC0 B1 22 LDA ($22),Y BBC2 85 61 STA $61 BBC4 84 70 STY $70 BBC6 60 RTS ; store float accu in index XY BBD4 20 1B BC JSR $BC1B ; round float accu according to guard bit BBD7 86 22 STX $22 BBD9 84 23 STY $23 BBDB A0 04 LDY #$04 BBDD A5 65 LDA $65 BBDF 91 22 STA ($22),Y BBE1 88 DEY BBE2 A5 64 LDA $64 BBE4 91 22 STA ($22),Y BBE6 88 DEY BBE7 A5 63 LDA $63 BBE9 91 22 STA ($22),Y BBEB 88 DEY BBEC A5 66 LDA $66 BBEE 09 7F ORA #$7F BBF0 25 62 AND $62 BBF2 91 22 STA ($22),Y BBF4 88 DEY BBF5 A5 61 LDA $61 BBF7 91 22 STA ($22),Y BBF9 84 70 STY $70 BBFB 60 RTS ; round float accu according to guard bit BC1B A5 61 LDA $61 BC1D F0 FB BEQ $BC1A BC1F 06 70 ASL $70 BC21 90 F7 BCC $BC1A BC23 20 6F B9 JSR $B96F BC26 D0 F2 BNE $BC1A BC28 4C 38 B9 JMP $B938 ; get sign of float accu in A BC2B A5 61 LDA $61 BC2D F0 09 BEQ $BC38 BC2F A5 66 LDA $66 BC31 2A ROL BC32 A9 FF LDA #$FF BC34 B0 02 BCS $BC38 BC36 A9 01 LDA #$01 BC38 60 RTS FFF3 4C 00 E5 JMP $E500 ; read base address of I/O devices ; read base address of I/O device into XY ; D000-DFFF 53248-57343 Input/Output Devices and Color RAM or Character Generator ROM or RAM - 4096 Bytes ; DC00 56320 Data Port A (Keyboard, Joystick, Paddles, Light-Pen) 7-0 Write Keyboard Column Values for Keyboard Scan 7-6 Read Paddles on Port A / B (01 = Port A, 10 = Port B) 4 Joystick A Fire Button: 1 = Fire 3-2 Paddle Fire Buttons 3-0 Joystick A Direction (0-15) E500 A2 00 LDX #$00 ; low DC00 E502 A0 DC LDY #$DC ; high DC00 E504 60 RTS
On May 4, 2010, at 2:43 PM, Ian Bogost wrote:
Yes, Randomness is a good area to consider here. It brings up all sorts of issues of encapsulation in programming and expression. A random number generator is a powerful and nontrivial piece of engineering compared to the function one invokes in "10 print."
The smallest effective 8-bit RND I know of in 6502 assembly is 9 bytes long, and considerably longer than the entire "10 print" program when typed in:
Rand8 lda random ; get seed (must be non-zero) asl ; shift byte bcc Rand8.no_eor ; branch if carry flag not set after left shift eor #$CF ; otherwise EOR with literal $CF Rand8.no_eor sta random ; save number as next seed Although it's interesting to note that in "10 print" the BASIC RND (which generates a number between 0 and 1) is actually less efficient than simply ORing the C64 TOD clock's tenth-of-seconds register with $01 — although that clock outputs in binary-coded decimal (BCD), so it's less truly random. The need to do the RND(1)*2 is sort of an artifact of this process. Incidentally, the BASIC RND function on the C64 is at ROM address $E09A, so it's possible just to jump there to generate a random number into the 6502's accumulator: jsr $E09A I think it was possible on the C64 to get random values from the Sound Interface Device (SID) chip. Does anyone remember how? reading from register 27 (decimal) returns the current value of oscillator 3. If it's set to noise, you get a random number generator. (http://www.waitingforfriday.com/index.php/Commodore_SID_6581_Datasheet#SID_Control_Registers)
