home *** CD-ROM | disk | FTP | other *** search
- TITLE 'HATGIRL2.ALC - CALCULATE VALUE OF E FOR N HATS'
- * PGMID. HATGIRL2.ALC
- * AUTHOR. DON HIGGINS.
- * 6365 - 32 AVENUE NORTH
- * ST. PETERSBURG, FL 33710
- *
- * DATE. 09/07/85.
- * REMARKS. THIS PROGRAM CALCULATES VALUE OF E (BASE OF NATUARAL
- * LOGRITHMS) USING THE CARELESS HAT CHECK GIRL ALGORITHM
- * DESCRIBED BY ROBERT T. KUROSAKA IN 9/85 BYTE. HE
- * SHOWS THAT E IS EQUAL TO N! DIVIDED BY THE NUMBER OF
- * WAYS THAT N HATS CAN BE DISTRIBUTED SUCH THAT NO ONE
- * GETS THE CORRECT HAT.
- *
- * THIS ALGORITHM IS WRITTEN IN IBM 370 ASSEMBLER TO BE
- * RUN ON AN IBM PC USING THE PC/370 ASSEMBLER AND
- * EMULATOR. THIS PROGRAM DIFFERS FROM THE BASIC PROGRAM
- * SHOWN IN BYTE, IN THAT IT IS DETERMINISTIC RATHER THAN
- * USING A RANDOM SAMPLE OF DISTRIBUTIONS TO APPROXIMATE
- * THE ANSWER FOR A GIVEN N. THIS PROGRAM CALCULATES THE
- * EXACT ANSWER FOR A GIVEN N. THE LARGER THE VALUE OF N,
- * THE MORE ACCURATE THE ANSWER IS.
- *
- * PC/370 IS A FREEWARE PACKAGE AVAILABLE ON MANY PC USER
- * GROUP ELECTRONIC BULLETIN BOARDS.
- *
- HATGIRL2 CSECT
- LR BASE,ENTRY
- USING HATGIRL2,BASE
- LA N,2
- LA ONE,1
- LA BADCOMB,0
- L ENTRY,=V(TIMER)
- BALR LINK,ENTRY SAVE STARTING TIME IN 100TH SECONDS
- ST R0,TIME
- MAINLOOP EQU *
- BAL LINK,CALCBAD COUNT BAD COMBINATIONS FOR CURRENT N
- BAL LINK,CALCE CALCULATE N! AND E FOR CURRENT N
- L ENTRY,=V(TIMER)
- BALR LINK,ENTRY
- L R1,TIME
- ST R0,TIME SAVE NEW TIME
- SR R0,R1
- CVD R0,PWORK
- MVC DS,DSMASK
- ED DS,PWORK+4 EDIT SECONDS
- LA R2,MSGLINE
- SVC WTO DISPLAY RESULTS FOR CURRENT N
- AR N,ONE
- CH N,=AL2(MAXN)
- BNH MAINLOOP
- SVC EXIT
- TITLE 'CALCBAD - CALCULATE NUMBER OF BAD COMBINATIONS FOR N'
- CALCBAD EQU * CALCULATE BADCOMB = TOTAL BAD COMBINATIONS
- *
- * INCREMENT COMBINATION COUNTER D(N) TO NEXT BAD COMBINATION
- * INCREMENT BADCOMB
- * EXIT WHEN COUNTER OVERFLOWS
- *
- XR BADCOMB,BADCOMB
- MVC D,DINIT
- MVC DP,DPINIT
- LA I,1
- XR R1,R1
- XR R2,R2
- LR NM1,N
- BCTR NM1,0 SET NM1 = N - 1
- INCDI EQU * INCREMENT D(I) TO NEXT BAD DIGIT
- IC J,D-1(I)
- FINDD EQU * SEARCH DP(J) TO DP(N) FOR NEXT DIGIT
- AR J,ONE
- CLR J,N
- BH NOTFOUND NO BAD DIGITS FOUND, GO INCR PREV DIGIT
- IC R1,DP-1(J)
- CLR I,R1 IS NEXT HIGHEST DIGIT AVAILABLE
- BNL FINDD NO, GO TO NEXT LARGER DIGIT
- CLR J,I IS NEXT DIGIT BAD
- BE FINDD NO, GO TO NEXT LARGER DIGIT
- FOUND EQU * SWAP LARGER DIGIT WITH D(I)
- IC R1,D-1(I) SAVE OLD DIGIT
- IC R2,DP-1(J) SAVE OLD POSITION OF NEW DIGIT
- STC J,D-1(I) STORE NEW DIGIT
- STC I,DP-1(J) SET POSITION OF NEW DIGIT
- STC R1,D-1(R2) STORE OLD DIGIT
- STC R2,DP-1(R1) SET POSITION OF OLD DIGIT
- SORT EQU *
- *
- * SORT D(I+1) TO D(N) IN ASCENDING ORDER
- *
- XR J,J
- LR K,I
- NEXTDK EQU * SEARCH DP(J) FOR NEXT DIGIT FOR D(K)
- AR K,ONE
- CLR K,N
- BNL CHKLAST GO CHECK IF LAST SORTED DIGIT D(N) IS BAD
- NEXTDPJ EQU * FIND NEXT HIGHEST DIGIT FOR D(K)
- AR J,ONE
- IC R1,DP-1(J)
- CLR K,R1 IS THIS DIGIT AVAILABLE
- BH NEXTDPJ
- BE CHKDIGIT IF ALREADY AT K, SKIP SWAP
- IC R1,D-1(K) SAVE OLD DIGIT
- IC R2,DP-1(J) SAVE OLD POSITION OF NEW DIGIT
- STC J,D-1(K) STORE NEW DIGIT
- STC K,DP-1(J) SET POSITION OF NEW DIGIT
- STC R1,D-1(R2) STORE OLD DIGIT
- STC R2,DP-1(R1) SET POSITION OF OLD DIGIT
- CHKDIGIT EQU *
- CLR J,K IS SORT DIGIT BAD
- BNE NEXTDK YES, CONTINUE SORT
- LR I,K NO, GO INCR GOOD DIGIT
- B INCDI
- CHKLAST EQU *
- IC R1,D-1(K)
- CLR K,R1 IS LAST DIGIT BAD
- BNE SORTOK YES, SORT DONE
- LR I,NM1 NO, GO INCR D(N-1)
- B INCDI
- SORTOK EQU *
- AR BADCOMB,ONE COUNT BAD COMBINATION
- LR I,NM1 GO INCR D(N-1)
- B INCDI
- NOTFOUND EQU *
- BCTR I,0 DECREMENT I
- IC R1,D-1(I)
- LTR R1,R1 IF NOT OVERFLOW
- BNE INCDI THEN GO INCREMENT NEW D(I)
- BR LINK ELSE EXIT WITH BAD COMBINATION COUNT
- TITLE 'CALCE - CALCULATE N! AND E FOR GIVEN N'
- CALCE EQU * CALCULATE AND FORMAT RESULTS
- CVD N,PWORK
- MVC DNN,DNMASK
- ED DNN,PWORK+6 N
- LR R1,N
- LR R2,N
- BCTR R2,0
- NFAC EQU *
- MR R0,R2 GENERATE N!
- BCT R2,NFAC
- CVD R1,PWORK
- MVC DT,DTMASK
- ED DT,PWORK+4 N!
- ZAP PT,PWORK
- CVD BADCOMB,PWORK
- MVC DB,DBMASK
- ED DB,PWORK+4 BAD COMBINATIONS
- MP PT,=P'100000000'
- DP PT,PWORK+4(4)
- MVC DE,DEMASK
- ED DE,PT+7 E
- BR LINK
- *
- * REGISTER ASSIGNMENTS
- *
- R0 EQU 0 WORK
- R1 EQU 1 WORK
- R2 EQU 2 WORK
- N EQU 3 NUMBER OF HATS
- BADCOMB EQU 4 BAD COMBINATION COUNTER
- I EQU 5 INDEX FOR DIGITS D(I) AND DP(I)
- J EQU 6 INDEX FOR DIGITS D(J) AND DP(J)
- K EQU 7 INDEX FOR DIGITS D(K) AND DP(K)
- ONE EQU 10 FREQUENTLY USED CONSTANT
- NM1 EQU 11 FREQUENTLY USED CONSTANT N-1
- BASE EQU 12 BASE
- LINK EQU 14 LINK
- ENTRY EQU 15 ENTRY
- *
- * PC/370 SYSTEM SVC'S
- *
- WTO EQU 209 WRITE TO OPERATOR (R2 = ADDRESS OF TEXT FOLLOWED BY $)
- EXIT EQU 0 RETURN TO MSDOS
- *
- * DATA AREAS
- *
- MAXN EQU 12 MAX NUMBER OF COMBINATIONS (HATS)
- DINIT DC (MAXN)AL1(*-DINIT+1) COMBINATION REGISTER WITH DIGITS
- DPINIT DC (MAXN)AL1(*-DPINIT+1) POSITION OF VALUE IN D(I)
- DC C'*** D REG ***'
- DC X'00' FORCE OVERFLOW ON CARRY OUT
- D DC XL(MAXN)'00' BAD COMBINATION REGISTER
- DC C'*** DP REG ***'
- DP DC XL(MAXN)'00' DIGIT POSITION INDEX REGISER
- PWORK DC D'0' WORK AREA FOR CVD
- PT DC PL16'0' WORK AREA TO CALC TOTCOMB/BADCOMP
- TIME DC F'0'
- MSGLINE EQU *
- DC C' N='
- DNN DC C' ZZZ',C' N!='
- DT DC C' Z,ZZZ,ZZZ',C' BAD='
- DB DC C' Z,ZZZ,ZZZ',C' E='
- DE DC C' 9.99999999',C' SEC='
- DS DC C' ZZ,ZZZ',C'$'
- DNMASK DC X'40202020'
- DTMASK DC X'4020',C',',X'202020',C',',X'202020'
- DBMASK DC X'4020',C',',X'202020',C',',X'202020'
- DEMASK DC X'4021',C'.',8X'21'
- DSMASK DC X'402020',C',',X'202121'
- END HATGIRL2
-
