;----------------------------- ; From: Mitch Ames ; Subject: Random # Generator LINEAR CONGRUENTIAL METHOD -------------------------- X' = (X * M + I) mod D where the multiplier M, the increment I and the divisor D are chosen so as to let the sequence "jump around" within the range 0..(D-1) in a random-like fashion for as long as possible without repeating. Some good numbers (from Grogono, PROGRAMMING IN PASCAL) are: M=25173d, I=13849d, D=65536 (This produces a sequence of period 65536, ie all possibilities in included.) ; Code returns random number in AX, changes DX mov ax,seed mov dx,25173d mul dx add ax,13849d mov seed,ax Refer to code below for seed generation. BIT SHIFT METHOD - Written and placed in the public domain by Mitch Ames ---------------- GENERATING PSEUDO-RANDOM BIT STREAMS IN HARDWARE Pseudo-random bit streams may be generated with hardware using a bit shift register and a multi-input XOR gate. The input bit for the shift register is formed by XORing several of the existing bits from the register. B0 is the output bit. Eg using an 8 bit register, and XORing bits 0, 2 and 4 we get: Bit shift register +----+----+----+----+----+----+----+----+ +-->| b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 +---+--> Output | +----+----+----+--+-+----+--+-+----+----+ | | | | | | <+ | | +--------------< XOR <----------+ | <--------------------------+ The bit values after the shift (t+1) are dependent on those before the shift (n): b0(t+1) = b1(t) b1(t+1) = b2(t) b2(t+1) = b3(t) b3(t+1) = b4(t) b4(t+1) = b5(t) b5(t+1) = b6(t) b6(t+1) = b7(t) b7(t+1) = b0(t) XOR b2(t) XOR b4(t) The output (b0) is a pseudo-random bit stream which repeats every N bits, where N may be anywhere between 1 and 2^8-1, depending on the bits XOR'd (the filter) and the starting bits (seed value). Taking each 8 consecutive bits from the stream produces a pseudo-random byte sequence, with up to 2^8-1 bytes before repetition. (Since 2^8-1 is not a multiple of 8, the repetition of bytes will only occur after 8 repetitions of the bit sequence). Obviously the more bits/bytes before repetition, the better; so the bits XOR'd must be chosen carefully. It can be determined fairly easily that if all the bits are zero initially, the output bit will always be zero (this is the case where the cycle repeats after one bit/byte), so the seed value must not be zero. Trial and error shows that there are many filters which produce an output stream which will repeat only after the maximum cycle, ie 255 for 8 bits, (65535 for 16 bits). In each case a different bit sequence is output. SOFTWARE IMPLEMENTATION Conversion of the above algorithm into assembly language software is not difficult - the rotate instructions provide a convenient bit shift, the OR instruction allows only specific bits to be extracted and the parity flag acts as the XOR gate. The assembly source code contains three parts; the first is only run once and initializes the seed value from the 8253 timer (making sure that it is not zero), the second part generates the random sequences and is called once for each random number required. The third part is used to generate filters. Note that in this case, a 16 bit shift register is used to generate 8 bit values. This ensures multiple occurrence of output values within a single cycle and hence less predictability, ie one specific 8 bit value will not always follow another specific value, which would be the case where the output value has the same number of bits as the shift register. It also allows an output value of zero, but note that it is impossible to get two (8 bit) zero's in a row. The register may be shifted 16 bits between outputs to provide 16 bit values, but these will be predictable - ie any specific value will always be followed by another specific value. This algorithm can be extended to 32, 48 or more bits if necessary by carrying bits from one 8086 register to another, or using larger registers in later model processors. This allows "non-predictable" 16, 24 or more bit random numbers. If random numbers are required over a smaller range than 0 - 255, a smaller range (0 - N) can be obtained by dividing the 8 bit number by N+1 and using the remainder. DETERMINING WHICH BITS TO XOR As mentioned above, for any random number generator there are many combinations of bits which can be XORed to give the feedback bit. The third section of RANDOM.ASM will try every bit combination for a 16 bit shift register and list those which give an optimum bit cycle, ie with a length of 65535. It does this by starting with a seed of 0001h and then generating pseudo random numbers until the seed value returns to 0001h. Checks are made for a seed of zero (which would never change in subsequent shifts) and for a number count of 65536, the latter implying that the generator will never return to 0001h since there is a maximum cycle length of 65535. Each successful filter is displayed on the screen (in binary) and counted. If the program is allowed to run to completion, it takes several hours (on a 10 MHz 8088) and counts several thousand successful filters. "RANDOMNESS", DISTRIBUTIONS, ETC It should be obvious that if you analyse the complete output set of the generator, it will be almost normally distributed (with a marginally smaller probability of getting zero). However, I have performed NO tests on these algorithms as to how "random" the output values are if only a subset of values are used. .radix 16 ; -------------------------------------------------------------------- ; INITIALIZE SEED cli mov al,00000000b ;latch timer 0 out 43,al in al,40h ;read seed from 8253 count (16 bits) mov ah,al ;which changes 1,193,180 times per sec in al,40h sti and ax,ax ;check for zero jnz save ;OK if not zero inc ax ;cannot use 0, use 1 instead save: mov [seed],ax ;save as seed ; End of initialization code ; -------------------------------------------------------------------- ; 8 BIT PSEUDO-RANDOM NUMBER GENERATOR ; Returns number in AL ; Changes AX, BX, CX filter equ 002Dh ;bit filter random: mov ax,[seed] ;get seed mov cx,8 ;set counter for 8 bits newbit: mov bx,ax ;put bit stream in BX and bx,filter ;extract appropriate bits xor bh,bl ;determine parity of BX clc ;clear carry flag jpe shift ;new bit = 0 stc ;new bit = 1 shift: rcr ax,1 ;shift AX right, bringing in carry bit loop newbit ;repeat 8 times mov [seed],ax ;store new seed ret ; To return a number in the range 0-N, divide AL by N+1 ; and return the remainder, ie: mov ah,0 mov bl,N+1 div bl mov al,ah ret ; End of random number generator code ; -------------------------------------------------------------------- ; GENERATE FILTERS mov bx,0001 ;filter = 1 seed1: mov ax,0001 ;seed = 1 mov cx,0 ;count = 0 ; 8 bit pseudo-random number generator random: mov dx,ax ;copy current value to DX and dx,bx ;extract appropriate bits xor dl,dh ;determine parity of filtered bits clc ;clear carry flag jpe shift ;new bit = 0 stc ;new bit = 1 shift: rcr ax,1 ;shift AX right, bringing in carry bit inc cx ;increment count jz disp ;count cannot exceed FFFFh cmp ax,1 ;check for repetition of cycle jne random ;if not, go again ; Display filter in binary disp: cmp cx,0FFFF ;ideal filter ? je disp1 ;yes, display it jmp repeat ;else, try again disp1: mov di,offset output ;point to output string mov cx,10 ;16 bits in filter disp2: rcl bx,1 ;rotate bit to carry mov [di],byte ptr "0" ;display 0 if bit clear jnb disp3 inc byte ptr [di] ;display 1 if bit set disp3: inc di ;shift pointer loop disp2 ;repeat for 16 bits rcl bx,1 ;17th rotation restores original value push bx ;save filter ; Convert count into ASCII string, and display inc [count] ;increment filter count mov di,offset out2 ;point past end of number string mov ax,count ;put count to accumulator mov bx,10d ;divide by ten to convert to decimal mov cl,5 ;5 digits digit: mov dx,0 ;DX is two MSBs for 16 bit division div bx ;divide by 10 add dl,"0" ;DX contains least significant digit dec di ;point to next most significant digit mov [di],dl ;put in output string loop digit ;repeat for 5 digits mov dx,offset output ;point to output string mov ah,9 ;display string int 21 ; Repeat for all filters pop bx ;restore filter repeat: inc bx ;increment it twice inc bx cmp bx,1 ;done all? je quit ;yes, finish jmp seed1 ;no, try again ; Data storage seed dw 0 count dw 0000h output db "0000000000000000 00000" out2 db 13d,10d,"$" ; End of filter generation code