Cycle detection: Difference between revisions
Add PL/M
Not a robot (talk | contribs) (Add FOCAL) |
Not a robot (talk | contribs) (Add PL/M) |
||
Line 1,605:
{101,2,5,26,167,95}
</pre>
=={{header|PL/M}}==
<lang plm>100H:
/* CP/M CALLS */
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
/* THIS IS A HACK TO CALL A FUNCTION GIVEN ITS ADDRESS */
APPLY: PROCEDURE (FN, ARG) ADDRESS;
DECLARE (FN, ARG) ADDRESS;
INNER: PROCEDURE (X) ADDRESS; /* THIS SETS UP THE ARGUMENTS IN MEMORY */
DECLARE X ADDRESS;
GO TO FN; /* THEN WE JUMP TO THE ADDRESS GIVEN */
END INNER;
RETURN INNER(ARG);
END APPLY;
/* THIS IS ANOTHER HACK - THE SINGLE 0 (WHICH IS AN 8080 NOP) WILL BE
STORED AS A CONSTANT RIGHT BEFORE THE FUNCTION.
PL/M-80 DOES NOT ALLOW THE PROGRAMMER TO DIRECTLY GET THE ADDRESS
OF A FUNCTION, BUT THE ADDRESS OF THIS CONSTANT WILL BE RIGHT IN
FRONT OF IT AND CAN BE USED INSTEAD. */
DECLARE F$ADDR DATA (0);
/* F(X) FROM THE TASK */
F: PROCEDURE (X) ADDRESS;
DECLARE X ADDRESS;
RETURN (X*X + 1) MOD 255;
END F;
/* PRINT A NUMBER */
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (7) BYTE INITIAL ('..... $');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUMBER;
/* PRINT F^M(X0) TO F^N(X0) */
PRINT$RANGE: PROCEDURE (FN, X0, M, N);
DECLARE (FN, X0, M, N, I) ADDRESS;
DO I=0 TO N-1;
IF I>=M THEN CALL PRINT$NUMBER(X0);
X0 = APPLY(FN,X0);
END;
CALL PRINT(.(13,10,'$'));
END PRINT$RANGE;
/* BRENT'S ALGORITHM */
BRENT: PROCEDURE (FN, X0, MU$A, LAM$A);
DECLARE (FN, X0, MU$A, LAM$A) ADDRESS;
DECLARE (MU BASED MU$A, LAM BASED LAM$A) ADDRESS;
DECLARE (TORT, HARE, POW, I) ADDRESS;
POW, LAM = 1;
TORT = X0;
HARE = APPLY(FN,X0);
DO WHILE TORT <> HARE;
IF POW = LAM THEN DO;
TORT = HARE;
POW = SHL(POW, 1);
LAM = 0;
END;
HARE = APPLY(FN,HARE);
LAM = LAM + 1;
END;
TORT, HARE = X0;
DO I=1 TO LAM;
HARE = APPLY(FN,HARE);
END;
MU = 0;
DO WHILE TORT <> HARE;
TORT = APPLY(FN,TORT);
HARE = APPLY(FN,HARE);
MU = MU + 1;
END;
END BRENT;
DECLARE (MU, LAM) ADDRESS;
/* PRINT THE FIRST 20 VALUES IN THE SEQUENCE */
CALL PRINT$RANGE(.F$ADDR, 3, 0, 20);
/* FIND THE CYCLE */
CALL BRENT(.F$ADDR, 3, .MU, .LAM);
CALL PRINT(.'LENGTH: $');
CALL PRINT$NUMBER(LAM);
CALL PRINT(.'START: $');
CALL PRINT$NUMBER(MU);
CALL PRINT(.(13,10,'$'));
/* PRINT THE CYCLE */
CALL PRINT$RANGE(.F$ADDR, 3, MU, MU+LAM);
CALL EXIT;
EOF</lang>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
LENGTH: 6 START: 2
101 2 5 26 167 95 </pre>
=={{header|Python}}==
| |||