Fibonacci sequence: Difference between revisions
Content added Content deleted
No edit summary |
m (→{{header|RPL}}: text formatting) |
||
Line 11,974: | Line 11,974: | ||
===Iterative=== |
===Iterative=== |
||
≪ 0 1 |
≪ 0 1 |
||
0 4 ROLL START |
0 4 ROLL '''START''' |
||
OVER + SWAP |
OVER + SWAP |
||
NEXT |
'''NEXT''' SWAP DROP |
||
≫ '<span style="color:blue">→FIB</span>' STO |
|||
SWAP DROP |
|||
´→FIB´ STO |
|||
≪ { } 0 20 FOR j j →FIB + NEXT ≫ EVAL |
≪ { } 0 20 FOR j j →FIB + NEXT ≫ EVAL |
||
===Recursive=== |
===Recursive=== |
||
≪ '''IF''' DUP 2 > '''THEN''' |
≪ '''IF''' DUP 2 > '''THEN''' |
||
DUP 1 - →FIB |
DUP 1 - <span style="color:blue">→FIB</span> |
||
SWAP 2 - →FIB + |
SWAP 2 - <span style="color:blue">→FIB</span> + |
||
'''ELSE''' |
'''ELSE''' SIGN '''END''' |
||
≫ '<span style="color:blue">→FIB</span>' STO |
|||
SIGN |
|||
'''END''' |
|||
≫ |
|||
´→FIB´ STO |
|||
≪ { } 0 20 FOR j j →FIB + NEXT ≫ EVAL |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 11,996: | Line 11,992: | ||
</pre> |
</pre> |
||
===Fast recursive=== |
===Fast recursive=== |
||
A much better recursive approach, based on the formulas: F(2k) = |
A much better recursive approach, based on the formulas: <code>F(2k) = [2*F(k-1) + F(k)]*F(k)</code> and <code>F(2k+1) = F(k)² + F(k+1)²</code> |
||
≪ '''IF''' DUP 2 ≤ |
≪ '''IF''' DUP 2 ≤ '''THEN''' SIGN '''ELSE''' |
||
'''THEN''' SIGN |
|||
'''ELSE''' |
|||
'''IF''' DUP 2 MOD |
'''IF''' DUP 2 MOD |
||
'''THEN''' 1 - 2 / DUP →FIB SQ SWAP 1 + →FIB SQ + |
'''THEN''' 1 - 2 / DUP <span style="color:blue">→FIB</span> SQ SWAP 1 + <span style="color:blue">→FIB</span> SQ + |
||
'''ELSE''' 2 / DUP →FIB DUP ROT 1 - →FIB 2 * + * |
'''ELSE''' 2 / DUP <span style="color:blue">→FIB</span> DUP ROT 1 - <span style="color:blue">→FIB</span> 2 * + * |
||
'''END''' |
'''END END''' |
||
≫ '<span style="color:blue">→FIB</span>' STO |
|||
≫ |
|||
'→FIB' STO |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |