Cycle detection: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(add RPL) |
||
Line 1: | Line 1: | ||
{{ |
{{Draft task}} |
||
;Task: |
;Task: |
||
Line 2,985: | Line 2,985: | ||
/*-------------------------------------------------------------------*/ |
/*-------------------------------------------------------------------*/ |
||
f: Return (arg(1)**2+1)// 255; /*define the function F*/</syntaxhighlight> |
f: Return (arg(1)**2+1)// 255; /*define the function F*/</syntaxhighlight> |
||
=={{header|RPL}}== |
|||
Translation of the Brent algorithm given in Wikipedia. |
|||
{{works with|HP|48}} |
|||
≪ 1 1 0 → f x0 power lam mu |
|||
≪ x0 DUP f EVAL <span style="color:grey">@ Main phase: search successive powers of two</span> |
|||
'''WHILE''' DUP2 ≠ '''REPEAT''' |
|||
'''IF''' power lam == '''THEN''' <span style="color:grey">@ time to start a new power of two?</span> |
|||
SWAP DROP DUP |
|||
2 'power' STO* |
|||
0 'lam' STO |
|||
'''END''' |
|||
f EVAL |
|||
1 'lam' STO+ |
|||
'''END''' |
|||
DROP2 x0 DUP <span style="color:grey">@ Find the position of the first repetition of length λ</span> |
|||
0 lam 1 - '''START''' |
|||
f EVAL '''NEXT''' <span style="color:grey">@ distance between the hare and tortoise is now λ</span> |
|||
'''WHILE''' DUP2 ≠ '''REPEAT''' <span style="color:grey">@ the hare and tortoise move at same speed until they agree</span> |
|||
f EVAL SWAP |
|||
f EVAL SWAP |
|||
1 'mu' STO+ |
|||
'''END''' |
|||
DROP2 lam mu |
|||
≫ ≫ '<span style="color:blue">CYCLEB</span>' STO |
|||
≪ SQ 1 + 255 MOD ≫ 0 <span style="color:blue">CYCLEB</span> |
|||
{{out}} |
|||
<pre> |
|||
2: 6 |
|||
1: 2 |
|||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |