Re: not enough real programmers?

[pbwh@ix.netcom.spamfree.com (Paul)]

Eric Smith <eric-no-spam-for-me@brouhaha.com> wrote:
>> prs@gol.com (Peter Stephenson) suggests the job interview task:
>> 4.  "Write a program to perform a "perfect shuffle" on an array of 52
>> numbers." 

>I don't see why that should be a big problem.  The program would simply
>use the provided RNG (Random Number Generator).  :-)


If you want a *true* random number generator then you have to
introduce randomness into the algorithm for selecting the numbers. As
we all know, digital computers do nothing at random. But if you have
the computer running through the states 1 thru 52 (or any number) many
times per second, and a person (who has no knowledge of what state the
computer is in) pushes a key which causes a recording of the state of
the computer, then the result will be a random number between 1 and
52. I think the slot machines in Vegas probably use such an algorithm:
the slot machine cycles thru the states many times per second, and the
gambler pushes a button or pulls a lever thereby "selecting" a state.
Since all states are equally likely, and the gambler has no knowlege
of the state when he pushes the button, the result is a random number
between 1 and 52.

Here's my code for such a random number generator which I created a
couple weeks ago. I've tested this, and it does seem to produce random
numbers between 1 and "numrange". Set numrange to 52 for the above
example. "numlist" is the number of random numbers between 1 and
numrange to be generated in a given session.

The last number displayed when you execute the program is the "sum" of
all the numbers generated. The column on the right shows how many
times the computer cycled thru the states (1 thru numrange) between
key presses.

The test of randomness is this: As numlist becomes large, the value of
sum / numlist should approach

(1+2+3+ ... + numrange) / numrange = (1/2) * (numrange + 1)


For numrange = 52,  sum/numlist should approach
(1/2) * (52 + 1) = 26.5



This program displays the generated random numbers as you press the
ascii keys:
*************************
title   Generates random numbers from 1 to numrange.   Rand.asm
; Paul White    7-27-1999

..model small
..stack 100h
..386

..data
   sum dw 0
   string3 db " numbers)",0
   string2 db "Start:  (",0
   string1 db ".  ",0
   spaces1 db "         ",0
      
..code
main proc
   mov ax,@data
   mov ds,ax
       
   extrn writeint:proc
   extrn crlf:proc
   extrn readchar:proc
   extrn writestring:proc
   
   numlist = 20
   numrange = 10
   mov dx,offset string2
   call writestring
   mov bx,10
   mov ax,numlist
   call writeint
   mov dx,offset string3
   call writestring   
   call crlf
   
   mov si,0   ;***
   mov cx,numlist
L1:
   inc si
   mov dx,0
L2:
   inc dx
   LAHF
   or ah,40h
   SAHF               ;sets the zero flag
   call readchar
   LAHF      
   and ah,40h
   jz L3   	      ;jumps to L3 if zero flag is clear
   mov ax,dx
   sub ax,numrange+1
   jz L1              ;jumps to L1 if dx = numrange
   Jmp L2
   
L3:
   add dx,0
   jz L2         ;jumps to L2 if dx = 0
   mov bx,dx
   sub bx,numrange+1
   jz L1         ;jumps to L1 if dx = numrange + 1
   mov bx,10        ;sets radix for writeint
   mov ax,numlist
   sub ax,cx
   inc ax
   call crlf
   call writeint   ;displays (numlist - cx)+1 = turn
   push dx
   mov dx,offset string1
   call writestring   ;puts period and 2 spaces after 'turn'
   
   pop dx
   mov ax,dx
   call writeint   ;displays generated number
   add sum,dx
   
   push dx ; ***
   mov dx,offset spaces1 ;***
   call writestring ;***  puts spaces in place
   pop dx    ;***
   mov bx,10 ;***
   mov ax,si ;***
   call writeint ;***  displays si
   
   mov si,0     ;***      
   Loop L2
   
   call crlf
   call crlf   
   mov ax,sum
   call writeint   ;displays sum
   
      
   mov ax,4c00h
   int 21h   
main endp
end main
*******************************



This is the same program as above, except it's more efficient because
it only displays stuff at the end. This allows the computer to cycle
thru more states between key presses.
*******************************
title   Generates random numbers from 1 to numrange.  Randc.asm
;   Paul White     Wed 7-28-1999

..model small
..stack 100h
..386

   numlist = 20
   numrange = 2

..data
   sum dw 0
   string3 db " numbers)",0
   string2 db "Start:  (",0
   string1 db ".  ",0
   spaces1 db "    ",0
   array dw 2*numlist dup(0)
      
..code
main proc
   mov ax,@data
   mov ds,ax
       
   extrn writeint:proc
   extrn crlf:proc
   extrn readchar:proc
   extrn writestring:proc
   
   mov dx,offset string2
   call writestring
   mov bx,10
   mov ax,numlist
   call writeint
   mov dx,offset string3
   call writestring      ;prints Start info
   call crlf
   
   mov di,0
   mov si,0
   mov cx,numlist
L1:
   inc si
   mov dx,0
L2:
   inc dx
   LAHF
   or ah,40h
   SAHF               ;sets the zero flag
   call readchar
   LAHF      
   and ah,40h
   jz L3   	      ;jumps to L3 if zero flag is clear
   mov ax,dx
   sub ax,numrange+1
   jz L1              ;jumps to L1 if dx = numrange
   Jmp L2
   
L3:
   add dx,0
   jz L2         ;jumps to L2 if dx = 0
   mov bx,dx
   sub bx,numrange+1
   jz L1         ;jumps to L1 if dx = numrange + 1
   
   mov bx,offset array
   mov [bx+di],dx   ;store dx in array
   add di,2
   mov [bx+di],si   ;store si in array
   mov si,0
   add di,2
   add sum,dx
   Loop L2
   
   mov di,offset array
   mov bx,10        ;sets radix for writeint
   mov cx,numlist

L4:
   mov ax,numlist
   sub ax,cx
   inc ax          ;ax = turn
   call writeint   ;displays (numlist - cx)+1 = turn = ax

   mov dx,offset string1
   call writestring   ;puts period and 2 spaces after 'turn'
   
   mov ax,[di]
   call writeint   ;displays generated number
   
   mov dx,offset spaces1
   call writestring  ;puts spaces in place
   
   add di,2   
   mov ax,[di]
   call writeint   ;displays stored si
   add di,2
   call crlf
   Loop L4
   
   call crlf   
   mov ax,sum
   call writeint   ;displays sum
         
   mov ax,4c00h
   int 21h   
main endp
end main
****************************************



---
[To reply by email, remove .spamfree from the address above]