Stern-Brocot sequence: Difference between revisions
Content deleted Content added
Not a robot (talk | contribs) Add Miranda |
Not a robot (talk | contribs) Add MACRO-11 |
||
Line 4,016: | Line 4,016: | ||
Task 5: PASS</pre> |
Task 5: PASS</pre> |
||
=={{header|MACRO-11}}== |
|||
<syntaxhighlight lang="macro11"> .TITLE STNBRC |
|||
.MCALL .TTYOUT,.EXIT |
|||
AMOUNT = ^D1200 |
|||
STNBRC::JSR PC,GENSEQ |
|||
; PRINT FIRST 15 |
|||
MOV #FST15,R1 |
|||
JSR PC,PRSTR |
|||
MOV #STERN+2,R3 |
|||
MOV #^D15,R4 |
|||
1$: MOV (R3)+,R0 |
|||
JSR PC,PR0 |
|||
SOB R4,1$ |
|||
MOV #NEWLINE,R1 |
|||
JSR PC,PRSTR |
|||
; PRINT FIRST OCCURRENCE OF 1..10 AND 100 |
|||
MOV #FSTOCC,R1 |
|||
JSR PC,PRSTR |
|||
MOV #1,R3 |
|||
2$: JSR PC,PRFST |
|||
INC R3 |
|||
CMP R3,#^D10 |
|||
BLE 2$ |
|||
MOV #^D100,R3 |
|||
JSR PC,PRFST |
|||
MOV #NEWLIN,R1 |
|||
JSR PC,PRSTR |
|||
; CHECK GCDS OF ADJACENT PAIRS UP TO 1000 |
|||
MOV #CHKGCD,R1 |
|||
JSR PC,PRSTR |
|||
MOV #STERN+2,R2 |
|||
MOV #^D999,R5 |
|||
MOV (R2)+,R3 |
|||
3$: MOV R3,R4 |
|||
MOV (R2)+,R3 |
|||
MOV R3,R0 |
|||
MOV R4,R1 |
|||
JSR PC,GCD |
|||
DEC R0 |
|||
BNE 4$ |
|||
SOB R5,3$ |
|||
MOV #ALL1,R1 |
|||
BR 5$ |
|||
4$: MOV #NOTAL1,R1 |
|||
5$: JSR PC,PRSTR |
|||
.EXIT |
|||
FST15: .ASCIZ /FIRST 15: / |
|||
FSTOCC: .ASCIZ /FIRST OCCURRENCES:/<15><12> |
|||
ATWD: .ASCIZ /AT / |
|||
CHKGCD: .ASCIZ /CHECKING GCDS OF ADJACENT PAIRS... / |
|||
NOTAL1: .ASCII /NOT / |
|||
ALL1: .ASCIZ /ALL 1./ |
|||
NEWLIN: .BYTE 15,12,0 |
|||
.EVEN |
|||
; GENERATE STERN-BROCOT SEQUENCE |
|||
GENSEQ: MOV #1,R0 |
|||
MOV R0,STERN+2 |
|||
MOV R0,STERN+4 |
|||
MOV #STERN+<2*AMOUNT>,R5 |
|||
MOV #STERN+2,R0 |
|||
MOV #STERN+6,R1 |
|||
MOV (R0)+,R2 |
|||
1$: MOV R2,R3 |
|||
MOV (R0)+,R2 |
|||
MOV R2,R4 |
|||
ADD R3,R4 |
|||
MOV R4,(R1)+ |
|||
MOV R2,(R1)+ |
|||
CMP R1,R5 |
|||
BLT 1$ |
|||
RTS PC |
|||
; LET R0 = FIRST OCCURRENCE OF R3 IN SEQUENCE |
|||
FNDFST: MOV #STERN,R0 |
|||
1$: CMP (R0)+,R3 |
|||
BNE 1$ |
|||
SUB #STERN+2,R0 |
|||
ASR R0 |
|||
RTS PC |
|||
; PRINT FIRST OCC. OF <R3> |
|||
PRFST: MOV R3,R0 |
|||
JSR PC,PR0 |
|||
MOV #ATWD,R1 |
|||
JSR PC,PRSTR |
|||
JSR PC,FNDFST |
|||
JSR PC,PR0 |
|||
MOV #NEWLIN,R1 |
|||
JMP PRSTR |
|||
; LET R0 = GCD(R0,R1) |
|||
GCD: CMP R0,R1 |
|||
BLT 1$ |
|||
BGT 2$ |
|||
RTS PC |
|||
1$: SUB R0,R1 |
|||
BR GCD |
|||
2$: SUB R1,R0 |
|||
BR GCD |
|||
; PRINT NUMBER IN R0 AS DECIMAL |
|||
PR0: MOV #4$,R1 |
|||
1$: MOV #-1,R2 |
|||
2$: INC R2 |
|||
SUB #12,R0 |
|||
BCC 2$ |
|||
ADD #72,R0 |
|||
MOVB R0,-(R1) |
|||
MOV R2,R0 |
|||
BNE 1$ |
|||
3$: MOVB (R1)+,R0 |
|||
.TTYOUT |
|||
BNE 3$ |
|||
RTS PC |
|||
.ASCII /...../ |
|||
4$: .ASCIZ / / |
|||
.EVEN |
|||
; PRINT STRING IN R1 |
|||
PRSTR: MOVB (R1)+,R0 |
|||
.TTYOUT |
|||
BNE PRSTR |
|||
RTS PC |
|||
; STERN-BROCOT BUFFER |
|||
STERN: .BLKW AMOUNT+1 |
|||
.END STNBRC</syntaxhighlight> |
|||
{{out}} |
|||
<pre>FIRST 15: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 |
|||
FIRST OCCURRENCES: |
|||
1 AT 1 |
|||
2 AT 3 |
|||
3 AT 5 |
|||
4 AT 9 |
|||
5 AT 11 |
|||
6 AT 33 |
|||
7 AT 19 |
|||
8 AT 21 |
|||
9 AT 35 |
|||
10 AT 39 |
|||
100 AT 1179 |
|||
CHECKING GCDS OF ADJACENT PAIRS... ALL 1.</pre> |
|||
=={{header|MAD}}== |
=={{header|MAD}}== |