Fibonacci sequence: Difference between revisions
m
Fibonacci sequence page fix highlighting...
(added 32 bit version) |
GordonBGood (talk | contribs) m (Fibonacci sequence page fix highlighting...) |
||
Line 38:
=={{header|0815}}==
<
%<:0D:>~$<:01:~%>=<:a94fad42221f2702:>~>
}:_s:{x{={~$x+%{=>~>x~-x<:0D:~>~>~^:_s:?
</syntaxhighlight>
=={{header|11l}}==
{{trans|Python}}
<
I n < 2
R n
Line 57:
L(i) 1..20
print(fib_iter(i), end' ‘ ’)
print()</
{{out}}
Line 67:
For maximum compatibility, programs use only the basic instruction set.
===using fullword integers===
<
* integer (31 bits) = 10 decimals -> max fibo(46)
FIBONACC CSECT
Line 117:
WTOBUF DC CL80'fibo(12)=1234567890'
REGEQU
END FIBONACC</
{{out}}
<pre>
Line 129:
</pre>
===using packed decimals===
<
* packed dec (PL8) = 15 decimals => max fibo(73)
FIBOWTOP CSECT
Line 176:
WTOBUF DC CL80'fibo(12)=123456789012345 '
REGEQU
END FIBOWTOP</
{{out}}
<pre>
Line 192:
The results are calculated and stored, but are not output to the screen or any other physical device: how to do that would depend on the hardware and the operating system.
<
STA $F0 ; LOWER NUMBER
LDA #1
Line 207:
CPX #$0A ; STOP AT FIB(10)
BMI LOOP
RTS ; RETURN FROM SUBROUTINE</
=={{header|68000 Assembly}}==
{{trans|ARM Assembly}}
Input is in D0, and the output is also in D0. There is no protection from 32-bit overflow, so use at your own risk. (I used this [https://godbolt.org/ C compiler] to create this in ARM Assembly and translated it manually into 68000 Assembly. It wasn't that difficult since both CPUs have similar architectures.)
<
MOVEM.L D4-D5,-(SP)
MOVE.L D0,D4
Line 231:
ADD.L D4,D0
MOVEM.L (SP)+,D4-D5
RTS</
=={{header|8080 Assembly}}==
This subroutine expects to be called with the value of <math>n</math> in register <tt>A</tt>, and returns <math>f(n)</math> also in <tt>A</tt>. You may want to take steps to save the previous contents of <tt>B</tt>, <tt>C</tt>, and <tt>D</tt>. The routine only works with fairly small values of <math>n</math>.
<
DCR C ; decrement, because we know f(1) already
MVI A, 1
Line 244:
DCR C
JNZ LOOP ; jump if not zero
RET ; return from subroutine</
=={{header|8086 Assembly}}==
Line 251:
The max input is 24 before you start having 16-bit overflow.
<
; WRITTEN IN C WITH X86-64 CLANG 3.3 AND DOWNGRADED TO 16-BIT X86
; INPUT: DI = THE NUMBER YOU WISH TO CALC THE FIBONACCI NUMBER FOR.
Line 280:
pop BX
pop BP
ret</
===Using A Lookup Table===
Line 291:
For the purpose of this example, assume that both this code and the table are in the <code>.CODE</code> segment.
<
;input: BX = the desired fibonacci number (in other words, the "n" in "F(n)")
; DS must point to the segment where the fibonacci table is stored
Line 321:
dword 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269
dword 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986
dword 102334155 </
=={{header|8th}}==
An iterative solution:
<
: fibon \ n -- fib(n)
>r 0 1
Line 334:
dup 1 n:= if 1 ;; then
fibon nip ;
</syntaxhighlight>
=={{header|ABAP}}==
===Iterative===
<
CHANGING number_fib TYPE i.
DATA: lv_old type i,
Line 351:
lv_cur = number_fib.
enddo.
ENDFORM.</
===Impure Functional===
{{works with|ABAP|7.4 SP08 Or above only}}
<
n TYPE string
x = `0`
Line 363:
fibnm = VALUE #( BASE fibnm ( n ) )
x = y
y = n ) ).</
=={{header|ACL2}}==
Fast, tail recursive solution:
<
(if (or (zp n) (zp (1- n)))
b
Line 383:
(defun first-fibs (n)
(first-fibs-r n 0))</
{{out}}
Line 393:
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach has been proposed.
<
INT curr,prev,tmp
Line 440:
FI
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Fibonacci_sequence.png Screenshot from Atari 8-bit computer]
Line 470:
=={{header|ActionScript}}==
<
{
if (n < 2)
Line 476:
return fib(n - 1) + fib(n - 2);
}</
=={{header|Ada}}==
===Recursive===
<
procedure Fib is
Line 499:
Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
Ada.Text_IO.Put_Line(Integer'Image(Fib(X)));
end Fib;</
===Iterative, build-in integers===
<
procedure Test_Fibonacci is
Line 521:
Put_Line (Positive'Image (Fibonacci (N)));
end loop;
end Test_Fibonacci;</
{{out}}
<pre>
Line 541:
Using the big integer implementation from a cryptographic library [https://github.com/cforler/Ada-Crypto-Library/].
<
procedure Fibonacci is
Line 573:
Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
Ada.Text_IO.Put_Line(LN.Utils.To_String(Fib(X)));
end Fibonacci;</
{{out}}
Line 581:
===Fast method using fast matrix exponentiation===
<
with ada.text_io;
use ada.text_io;
Line 630:
-- calculate instantly F_n with n=10^15 (modulus 2^64 )
put_line (Big_Int_Fibo (10**15)'img);
end fast_fibo; </
=={{header|AdvPL}}==
===Recursive===
<
#include "totvs.ch"
User Function fibb(a,b,n)
return(if(--n>0,fibb(b,a+b,n),a))
</syntaxhighlight>
===Iterative===
<
#include "totvs.ch"
User Function fibb(n)
Line 651:
end while
return(fnext)
</syntaxhighlight>
=={{header|Aime}}==
<
fibs(integer n)
{
Line 679:
return w;
}
</syntaxhighlight>
=={{header|ALGOL 60}}==
{{works with|A60}}
<
comment Fibonacci sequence;
integer procedure fibonacci(n); value n; integer n;
Line 701:
integer i;
for i := 0 step 1 until 20 do outinteger(1,fibonacci(i))
end </
{{out}}
<pre>
Line 714:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
<
LONG REAL sqrt 5 = long sqrt(5);
LONG REAL p = (1 + sqrt 5) / 2;
Line 726:
print(", ")
OD;
print(new line)</
{{out}}
<pre>
Line 736:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
<
CASE n+1 IN
0, 1, 1, 2, 3, 5
Line 752:
print(", ")
OD;
print(new line)</
{{out}}
<pre>
Line 761:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
<
( n < 2 | n | fib(n-1) + fib(n-2));</
===Generative===
{{trans|Python|Note: This specimen retains the original [[Prime decomposition#Python|Python]] coding style.}}
Line 768:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
<
PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (
Line 785:
# OD # ));
print(new line)
)</
{{out}}
<pre>
Line 797:
This uses a pre-generated list, requiring much less run-time processor usage, but assumes that INT is only 31 bits wide.
<
-701408733, 433494437, -267914296, 165580141, -102334155,
63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
Line 826:
print(", ")
OD;
print(new line)</
{{out}}
<pre>
Line 833:
=={{header|ALGOL W}}==
<
% return the nth Fibonacci number %
integer procedure Fibonacci( integer value n ) ;
Line 851:
for i := 0 until 10 do writeon( i_w := 3, s_w := 0, Fibonacci( i ) )
end.</
{{out}}
<pre>
Line 860:
Note that the 21st Fibonacci number (= 10946) is the largest that can be calculated without overflowing ALGOL-M's integer data type.
====Iterative====
<
BEGIN
INTEGER M, N, A, I;
Line 872:
END;
FIBONACCI := N;
END;</
====Naively recursive====
<
BEGIN
IF X < 3 THEN
Line 881:
ELSE
FIBONACCI := FIBONACCI( X - 2 ) + FIBONACCI( X - 1 );
END;</
=={{header|Alore}}==
<
if n < 2
return 1
end
return fib(n-1) + fib(n-2)
end</
=={{header|Amazing Hopper}}==
Analitic, Recursive and Iterative mode.
<
#include <hbasic.h>
Line 937:
Next
Return(B)
</syntaxhighlight>
{{out}}
<pre>
Line 947:
=={{header|AntLang}}==
<
fib:{<0;1> {x,<x[-1]+x[-2]>}/ range[x]}
/nth
fibn:{fib[x][x]}</
=={{header|Apex}}==
<
/*
author: snugsfbay
Line 998:
}
</syntaxhighlight>
=={{header|APL}}==
Line 1,005:
{{works with|Dyalog APL}}
<
fib←{⍵≤1:⍵ ⋄ (∇ ⍵-1)+∇ ⍵-2}
</syntaxhighlight>
Read this as: In the variable "fib", store the function that says, if the argument is less than or equal to 1, return the argument. Else, calculate the value you get when you recursively call the current function with the argument of the current argument minus one and add that to the value you get when you recursively call the current function with the argument of the current function minus two.
Line 1,020:
:<math>\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.</math>
In APL:
<
↑+.×/N/⊂2 2⍴1 1 1 0
</syntaxhighlight>
Plugging in 4 for N gives the following result:
:<math>\begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix}</math>
Line 1,029:
The ''First'' removes the shell from the ''Enclose''.
At this point we're basically done, but we need to pick out only <math>F_n</math> in order to complete the task. Here's one way:
<
↑0 1↓↑+.×/N/⊂2 2⍴1 1 1 0
</syntaxhighlight>
====Analytic====
Line 1,037:
{{works with|GNU APL}}
An alternative approach, using Binet's formula (which was apparently known long before Binet):
<
=={{header|AppleScript}}==
Line 1,044:
===Imperative===
<
set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3"))
set x to x as integer
Line 1,054:
end if
end repeat
return item x of fibs</
Line 1,062:
The simple recursive version is famously slow:
<
if n < 1 then
0
Line 1,070:
fib(n - 2) + fib(n - 1)
end if
end fib</
but we can combine '''enumFromTo(m, n)''' with the accumulator of a higher-order '''fold/reduce''' function to memoize the series:
Line 1,076:
{{Trans|JavaScript}} (ES6 memoized fold example)
{{Trans|Haskell}} (Memoized fold example)
<
-- fib :: Int -> Int
Line 1,137:
end script
end if
end mReturn</
{{Out}}
<pre>2178309</pre>
Line 1,157:
=={{header|ARM Assembly}}==
Expects to be called with <math>n</math> in R0, and will return <math>f(n)</math> in the same register.
<
push {r1-r3}
mov r1, #0
Line 1,172:
mov r0, r2
pop {r1-r3}
mov pc, lr</
=={{header|ArnoldC}}==
<
HEY CHRISTMAS TREE f1
Line 1,206:
CHILL
YOU HAVE BEEN TERMINATED</
=={{header|Arturo}}==
Line 1,212:
===Recursive===
<
if? x<2 [1]
else [(fib x-1) + (fib x-2)]
Line 1,219:
loop 1..25 [x][
print ["Fibonacci of" x "=" fib x]
]</
=={{header|AsciiDots}}==
<
/--#$--\
Line 1,235:
. .
</syntaxhighlight>
=={{header|ATS}}==
===Recursive===
<
fun fib_rec(n: int): int =
if n >= 2 then fib_rec(n-1) + fib_rec(n-2) else n
</syntaxhighlight>
===Iterative===
<
(*
** This one is also referred to as being tail-recursive
Line 1,255:
then (fix loop (i:int, r0:int, r1:int): int => if i > 1 then loop (i-1, r1, r0+r1) else r1)(n, 0, 1)
else 0
</syntaxhighlight>
===Iterative and Verified===
<
(*
** This implementation is verified!
Line 1,286:
loop {0} (FIB0 (), FIB1 () | n, 0, 1)
end // end of [fibats]
</syntaxhighlight>
===Matrix-based===
<
(* ****** ****** *)
//
Line 1,369:
//
} (* end of [main0] *)
</syntaxhighlight>
=={{header|AutoHotkey}}==
Line 1,376:
===Iterative===
{{trans|C}}
<
MsgBox % fib(A_Index)
Return
Line 1,393:
}
Return this
}</
===Recursive and iterative===
Source: [http://www.autohotkey.com/forum/topic44657.html AutoHotkey forum] by Laszlo
<
Important note: the recursive version would be very slow
without a global or static array. The iterative version
Line 1,413:
c := b, b += a, a := c
Return n=0 ? 0 : n>0 || n&1 ? b : -b
}</
=={{header|AutoIt}}==
===Iterative===
<
$n0 = 0
$n1 = 1
Line 1,444:
Return $febo
EndFunc
</syntaxhighlight>
===Recursive===
<
$n0 = 0
$n1 = 1
Line 1,465:
EndIf
EndFunc
</syntaxhighlight>
=={{header|AWK}}==
As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout.
<
10
fib(10)=55</
=={{header|Axe}}==
Line 1,478:
Iterative solution:
<
r₁→N
0→I
Line 1,488:
End
J
Return</
=={{header|Babel}}==
In Babel, we can define fib using a stack-based approach that is not recursive:
<
foo x < puts x in foo. In this case, x is the code list between the curly-braces. This is how you define callable code in Babel. The definition works by initializing the stack with 0, 1. On each iteration of the times loop, the function duplicates the top element. In the first iteration, this gives 0, 1, 1. Then it moves down the stack with the <- operator, giving 0, 1 again. It adds, giving 1. then it moves back up the stack, giving 1, 1. Then it swaps. On the next iteration this gives:
Line 1,505:
And so on. To test fib:
<
{{out}}
Line 1,512:
=={{header|bash}}==
===Iterative===
<
$ fib=1;j=1;while((fib<100));do echo $fib;((k=fib+j,fib=j,j=k));done
</syntaxhighlight>
<pre>
1
Line 1,530:
===Recursive===
<
{
if [ $1 -le 0 ]
Line 1,546:
fi
}
</syntaxhighlight>
=={{header|BASIC}}==
Line 1,556:
==={{header|BASIC256}}===
<
# Basic-256 ver 1.1.4
# iterative Fibonacci sequence
Line 1,581:
print " "
print n + chr(9) + c
</syntaxhighlight>
==={{header|Commodore BASIC}}===
<
110 INPUT "MIN, MAX"; N1, N2
120 IF N1 > N2 THEN T = N1: N1 = N2: N2 = T
Line 1,599:
230 : PRINT ","; STR$(A);
240 NEXT I
250 PRINT</
{{Out}}
Line 1,612:
==={{header|Integer BASIC}}===
Only works with quite small values of <math>n</math>.
<
20 A=0
30 B=1
Line 1,621:
80 NEXT I
90 PRINT B
100 END</
==={{header|IS-BASIC}}===
<
110 FOR I=0 TO 20
120 PRINT "F";I,FIB(I)
Line 1,635:
190 NEXT
200 LET FIB=A
210 END DEF</
==={{header|QBasic}}===
Line 1,641:
{{works with|FreeBASIC}}
====Iterative====
<
n1 = 0
n2 = 1
Line 1,654:
itFib = n1
END IF
END FUNCTION</
Next version calculates each value once, as needed, and stores the results in an array for later retreival (due to the use of <code>REDIM PRESERVE</code>, it requires [[QuickBASIC]] 4.5 or newer):
<
REDIM SHARED fibNum(1) AS LONG
Line 1,695:
ERROR 6 'overflow
END SELECT
END FUNCTION</
{{out}} (unhandled error in final input prevents output):
Line 1,707:
This example can't handle n < 0.
<
IF (n < 2) THEN
recFib = n
Line 1,713:
recFib = recFib(n - 1) + recFib(n - 2)
END IF
END FUNCTION</
====Array (Table) Lookup====
Line 1,719:
This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.)
<
DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309
DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711
Line 1,739:
NEXT
PRINT
'*****sample inputs*****</
===={{header|QB64}}====
Line 1,745:
Fibonacci from Russia
<
F(1) = 0: F(2) = 1
'OPEN "FibRus.txt" FOR OUTPUT AS #1
Line 1,758:
f$ = n$ + f$
PRINT i, f$: ' PRINT #1, i, f$
NEXT i</
{{out}}
<pre>1 0
Line 1,794:
==={{header|Sinclair ZX81 BASIC}}===
====Analytic====
<
20 PRINT INT (0.5+(((SQR 5+1)/2)**N)/SQR 5)</
====Iterative====
<
20 LET A=0
30 LET B=1
Line 1,806:
70 LET A=C
80 NEXT I
90 PRINT B</
====Tail recursive====
<
20 LET A=0
30 LET B=1
Line 1,821:
110 LET N=N-1
120 GOSUB 70
130 RETURN</
=={{header|Batch File}}==
Recursive version
<
@echo off
if "%1" equ "" goto :eof
Line 1,845:
set r2=%errorlevel%
set /a r0 = r1 + r2
exit /b !r0!</
{{out}}
Line 1,866:
<!--- works with C syntax highlighting --->
<syntaxhighlight lang=c>
// Fibonacci sequence, recursive version
fun fibb
Line 1,910:
// vim: set syntax=c ts=4 sw=4 et:
</syntaxhighlight>
=={{header|BBC BASIC}}==
<
PRINT FNfibonacci_r(13), FNfibonacci_i(13)
PRINT FNfibonacci_r(26), FNfibonacci_i(26)
Line 1,932:
NEXT
= F
</syntaxhighlight>
{{out}}
<pre> 1 1
Line 1,940:
=={{header|bc}}==
=== iterative ===
<
define fib(x) {
Line 1,954:
}
fib(1000)
quit</
=={{header|BCPL}}==
<
let fib(n) = n<=1 -> n, valof
Line 1,971:
let start() be
for i=0 to 10 do
writef("F_%N*T= %N*N", i, fib(i))</
{{out}}
<pre>F_0 = 0
Line 1,987:
=={{header|beeswax}}==
<
_`Enter n: `TN`Fib(`{`)=`X~P~K#{;
#>~P~L#MM@>+@'q@{;
b~@M<</
Example output:
Line 1,996:
Notice the UInt64 wrap-around at <code>Fib(94)</code>!
<
Enter n: i0
Line 2,024:
Fib(94)=1293530146158671551
Program finished!</
=={{header|Befunge}}==
<
^ .:\/*8"@"\%*8"@":\ <</
=={{header|BlitzMax}}==
<
n = int(input( "Enter n: "))
Line 2,048:
n = n - 1
wend
print c</
=={{header|Blue}}==
<
: fib ( nth:ecx -- result:edi ) 1 0
: compute ( times:ecx accum:eax scratch:edi -- result:edi ) xadd latest loop ;
: example ( -- ) 11 fib drop ;
</syntaxhighlight>
=={{header|BQN}}==
Line 2,063:
=== Recursive ===
A primitive recursive can be done with predicates:
<
Or, it can be done with the Choose(<code>◶</code>) modifier:
<
=== Iterative ===
An iterative solution can be made with the Repeat(<code>⍟</code>) modifier:
<
=={{header|Bracmat}}==
===Recursive===
<
fib$30
Line 2,079:
===Iterative===
<
last i this new
. !arg:<2
Line 2,091:
)
& !this
)</
fib$777
Line 2,099:
{{works with|Brainf***|implementations with unbounded cell size}}
The first cell contains ''n'' (10), the second cell will contain ''fib(n)'' (55), and the third cell will contain ''fib(n-1)'' (34).
<
>>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]</
The following generates n fibonacci numbers and prints them, though not in ascii.
It does have a limit due to the cells usually being 1 byte in size.
<
>> + Init #2 to 1
<<
Line 2,140:
]
<<<< Back to #0
]</
=={{header|Brat}}==
===Recursive===
<
true? x < 2, x, { fibonacci(x - 1) + fibonacci(x - 2) }
}</
===Tail Recursive===
<
true? x == 0,
result,
Line 2,157:
fibonacci = { x |
fib_aux x, 1, 0
}</
===Memoization===
<
fibonacci = { x |
Line 2,166:
{ cache[x] }
{true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}
}</
=={{header|Burlesque}}==
<
{0 1}{^^++[+[-^^-]\/}30.*\[e!vv
</syntaxhighlight>
<
0 1{{.+}c!}{1000.<}w!
</syntaxhighlight>
=={{header|C}}==
===Recursive===
<
return (--n>0)?(fibb(b, a+b, n)):(a);
}</
===Iterative===
<
int fnow = 0, fnext = 1, tempf;
while(--n>0){
Line 2,193:
}
return fnext;
}</
===Analytic===
<
#define PHI ((1 + sqrt(5))/2)
long long unsigned fib(unsigned n) {
return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );
}</
===Generative===
{{trans|Python}}
{{works with|gcc|version 4.1.2 20080704 (Red Hat 4.1.2-44)}}
<
typedef enum{false=0, true=!0} bool;
typedef void iterator;
Line 2,242:
OD;
printf("...\n");
}</
{{out}}
<pre>
Line 2,249:
===Fast method for a single large value===
<
#include <stdio.h>
#include <gmp.h>
Line 2,322:
}
return 0;
}</
{{out}}
<pre>
Line 2,339:
=== Recursive ===
<
public static ulong Fib(uint n) {
return (n < 2)? n : Fib(n - 1) + Fib(n - 2);
}
</syntaxhighlight>
=== Tail-Recursive ===
<
public static ulong Fib(uint n) {
return Fib(0, 1, n);
Line 2,354:
return (n < 1)? a :(n == 1)? b : Fib(b, a + b, n - 1);
}
</syntaxhighlight>
=== Iterative ===
<
public static ulong Fib(uint x) {
if (x == 0) return 0;
Line 2,371:
return next;
}
</syntaxhighlight>
=== Eager-Generative ===
<
public static IEnumerable<long> Fibs(uint x) {
IList<ulong> fibs = new List<ulong>();
Line 2,389:
return fibs;
}
</syntaxhighlight>
=== Lazy-Generative ===
<
public static IEnumerable<ulong> Fibs(uint x) {
ulong prev = -1;
Line 2,403:
}
}
</syntaxhighlight>
=== Analytic ===
This returns digits up to the 93<sup>rd</sup> Fibonacci number, but the digits become inaccurate past the 71<sup>st</sup>. There is custom rounding applied to the result that allows the function to be accurate at the 71<sup>st</sup> number instead of topping out at the 70<sup>th</sup>.
<
static ulong fib(uint n) {
if (n > 71) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 72.");
double r = Math.Pow(Phi, n) / r5;
return (ulong)(n < 64 ? Math.Round(r) : Math.Floor(r)); }</
do { t = x / g; lg = g; g = (t + g) / 2M; } while (lg != g);
return g; }
Line 2,427:
if (n > 93) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 94.");
decimal r = Pow_dec(Phi, n) / r5;
return (ulong)(n < 64 ? Math.Round(r) : Math.Floor(r)); }</
do { t = x / g; lg = g; g = (t + g) / 2M; } while (lg != g);
return g; }
Line 2,442:
if (n > 128) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 129.");
decimal r = Pow_dec(Phi, n) / r5;
return n < 64 ? Math.Round(r) : Math.Floor(r); }</
=== Matrix ===
Line 2,450:
Needs <code>System.Windows.Media.Matrix</code> or similar Matrix class.
Calculates in <math>O(n)</math>.
<
public static ulong Fib(uint n) {
var M = new Matrix(1,0,0,1);
Line 2,457:
return (ulong)M[0][0];
}
</syntaxhighlight>
Needs <code>System.Windows.Media.Matrix</code> or similar Matrix class.
Calculates in <math>O(\log{n})</math>.
<
private static Matrix M;
private static readonly Matrix N = new Matrix(1,1,1,0);
Line 2,477:
if (n % 2 == 0) M *= N;
}
</syntaxhighlight>
=== Array (Table) Lookup ===
<
private static int[] fibs = new int[]{ -1836311903, 1134903170,
-701408733, 433494437, -267914296, 165580141, -102334155,
Line 2,498:
return fibs[n+46];
}
</syntaxhighlight>
===Arbitrary Precision===
{{libheader|System.Numerics}}
This large step recurrence routine can calculate the two millionth Fibonacci number in under 1 / 5 second at tio.run. This routine can generate the fifty millionth Fibonacci number in under 30 seconds at tio.run. The unused conventional iterative method times out at two million on tio.run, you can only go to around 1,290,000 or so to keep the calculation time (plus string conversion time) under the 60 second timeout limit there. When using this large step recurrence method, it takes around 5 seconds to convert the two millionth Fibonacci number (417975 digits) into a string (so that one may count those digits).
<
using System.Collections.Generic;
using BI = System.Numerics.BigInteger;
Line 2,546:
Console.Write("partial: {0}...{1}", v / BI.Pow(10, vlen - digs), v % BI.Pow(10, digs));
}
}</
{{out}}
<pre>137.209 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975
Line 2,554:
=={{header|C++}}==
Using unsigned int, this version only works up to 48 before fib overflows.
<
int main()
Line 2,569:
return 0;
}</
Line 2,575:
This version does not have an upper bound.
<
#include <gmpxx.h>
Line 2,595:
}
return 0;
}</
Version using transform:
<
#include <vector>
#include <functional>
Line 2,610:
// "v" now contains the Fibonacci sequence from 0 up
return v[n];
}</
Far-fetched version using adjacent_difference:
<
#include <vector>
#include <functional>
Line 2,625:
return v[n-1];
}
</syntaxhighlight>
Version which computes at compile time with metaprogramming:
<
template <int n> struct fibo
Line 2,651:
std::cout<<fibo<46>::value<<std::endl;
return 0;
}</
The following version is based on fast exponentiation:
<
inline void fibmul(int* f, int* g)
Line 2,688:
std::cout << fibonacci(i) << " ";
std::cout << std::endl;
}</
{{out}}
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
===Using Zeckendorf Numbers===
The nth fibonacci is represented as Zeckendorf 1 followed by n-1 zeroes. [[Zeckendorf number representation#Using a C++11 User Defined Literal|Here]] I define a class N which defines the operations increment ++() and comparison <=(other N) for Zeckendorf Numbers.
<
// Use Zeckendorf numbers to display Fibonacci sequence.
// Nigel Galloway October 23rd., 2012
Line 2,709:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,717:
===Using Standard Template Library===
Possibly less "Far-fetched version".
<
// Use Standard Template Library to display Fibonacci sequence.
// Nigel Galloway March 30th., 2013
Line 2,729:
return 0;
}
</syntaxhighlight>
{{out}}
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
=={{header|Cat}}==
<
dup 1 <=
[]
[dup 1 - fib swap 2 - fib +]
if
}</
=={{header|Chapel}}==
<
var a = 0, b = 1;
Line 2,749:
(a, b) = (b, b + a);
}
}</
=={{header|Chef}}==
<
An unobfuscated iterative implementation.
Line 2,782:
Pour contents of the 4th mixing bowl into baking dish.
Serves 1.</
=={{header|Clio}}==
Line 2,788:
Clio is pure and functions are lazy and memoized by default
<
if n < 2: n
else: (n - 1 -> fib) + (n - 2 -> fib)
[0:100] -> * fib -> * print</
=={{header|Clojure}}==
Line 2,798:
===Lazy Sequence===
This is implemented idiomatically as an infinitely long, lazy sequence of all Fibonacci numbers:
<
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))</
Thus to get the nth one:
<syntaxhighlight lang
So long as one does not hold onto the head of the sequence, this is unconstrained by length.
The one-line implementation may look confusing at first, but on pulling it apart it actually solves the problem more "directly" than a more explicit looping construct.
<
(map first ;; throw away the "metadata" (see below) to view just the fib numbers
(iterate ;; create an infinite sequence of [prev, curr] pairs
(fn [[a b]] ;; to produce the next pair, call this function on the current pair
[b (+ a b)]) ;; new prev is old curr, new curr is sum of both previous numbers
[0 1]))) ;; recursive base case: prev 0, curr 1</
A more elegant solution is inspired by the Haskell implementation of an infinite list of Fibonacci numbers:
<
Then, to see the first ten,
<
(0 1 1 2 3 5 8 13 21 34)</
===Iterative===
Here's a simple interative process (using a recursive function) that carries state along with it (as args) until it reaches a solution:
<
;; n is which fib number you're on for this call (0th, 1st, 2nd, etc.)
;; j is the nth fib number (ex. when n = 5, j = 5)
Line 2,838:
(if (< max 2)
max
(fib-iter max 1 0N 1N)))</
"defn-" means that the function is private (for use only inside this library). The "N" suffixes on integers tell Clojure to use arbitrary precision ints for those.
Line 2,844:
Based upon the doubling algorithm which computes in O(log (n)) time as described here https://www.nayuki.io/page/fast-fibonacci-algorithms
Implementation credit: https://stackoverflow.com/questions/27466311/how-to-implement-this-fast-doubling-fibonacci-algorithm-in-clojure/27466408#27466408
<
(defn fib [n]
(letfn [(fib* [n]
Line 2,856:
[d (+' c d)]))))]
(first (fib* n))))
</syntaxhighlight>
===Recursive===
Line 2,862:
A naive slow recursive solution:
<
(case n
0 0
1 1
(+ (fib (- n 1))
(fib (- n 2)))))</
This can be improved to an O(n) solution, like the iterative solution, by memoizing the function so that numbers that have been computed are cached. Like a lazy sequence, this also has the advantage that subsequent calls to the function use previously cached results rather than recalculating.
<
(memoize
(fn [n]
Line 2,878:
1 1
(+ (fib (- n 1))
(fib (- n 2)))))))</
=== Using core.async ===
<
(require '[clojure.core.async
:refer [<! >! >!! <!! timeout chan alt! go]])
Line 2,897:
(for [i (range 10)]
(println (<!! c))))))
</syntaxhighlight>
=={{header|CLU}}==
<
fib = iter () yields (int)
a: int := 0
Line 2,940:
|| int$unparse(nth[int](fib, n)))
end
end start_up</
{{out}}
<pre>F(0) = 0
Line 2,964:
Iteration uses a while() loop. Memoization uses global properties.
<
set_property(GLOBAL PROPERTY fibonacci_1 1)
set_property(GLOBAL PROPERTY fibonacci_next 2)
Line 2,991:
get_property(answer GLOBAL PROPERTY fibonacci_${n})
set(${var} ${answer} PARENT_SCOPE)
endfunction(fibonacci)</
<
set(s "")
foreach(i RANGE 0 9)
Line 3,004:
set(s "${s} ${f}")
endforeach(i)
message(${s})</
<pre> 0 1 1 2 3 5 8 13 21 34 ... 75025 121393 196418 317811 514229 832040</pre>
Line 3,010:
=={{header|COBOL}}==
===Iterative===
<
Data Division.
Working-Storage Section.
Line 3,049:
Move INTERM-RESULT to FORMATTED-RESULT.
Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT.
Display FORMATTED-RESULT.</
===Recursive===
{{works with|GNU Cobol|2.0}}
<
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci-main.
Line 3,097:
END-EVALUATE
.
END PROGRAM fibonacci.</
=={{header|CoffeeScript}}==
===Analytic===
<
sqrt = Math.sqrt
phi = ((1 + sqrt(5))/2)
Math.round((Math.pow(phi, n)/sqrt(5)))</
===Iterative===
<
return n if n < 2
[prev, curr] = [0, 1]
[prev, curr] = [curr, curr + prev] for i in [1..n]
curr</
===Recursive===
<
if n < 2 then n else fib_rec(n-1) + fib_rec(n-2)</
=={{header|Comefrom0x10}}==
Line 3,122:
===Iterative===
<
a = 1
i = 1 # start
Line 3,136:
b = next_b
comefrom fib if i > stop</
=={{header|Common Lisp}}==
Note that Common Lisp uses bignums, so this will never overflow.
===Iterative===
<
(case n
(0 f0)
Line 3,148:
for a = f0 then b and b = f1 then result
for result = (+ a b)
finally (return result)))))</
Simpler one:
<
(let ((a 0) (b 1) (c n))
(loop for i from 2 to n do
Line 3,157:
a b
b c))
c))</
Not a function, just printing out the entire (for some definition of "entire") sequence with a <code>for var = </code> loop:<
===Recursive===
<
(if (< n 2)
n
(+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))</
<
(if (= n 0)
a
(fibonacci-tail-recursive (- n 1) b (+ a b))))</
Tail recursive and squaring:
<
(if (= n 1) (+ (* b p) (* a q))
(fib (ash n -1)
Line 3,182:
(+ (* q q) (* 2 p q))))) ;p is Fib(2^n-1), q is Fib(2^n).
(print (fib 100000))</
=== Alternate solution ===
I use [https://franz.com/downloads/clp/survey Allegro CL 10.1]
<
;; Project : Fibonacci sequence
Line 3,200:
(write(+ n 1)) (format t "~a" ": ")
(write (fibonacci n)) (terpri))
</syntaxhighlight>
Output:
<pre>
Line 3,217:
=== Solution with methods and eql specializers ===
<
(defmethod fib (n)
(declare ((integer 0 *) n))
Line 3,226:
(defmethod fib ((n (eql 1))) 1)
</syntaxhighlight>
=== List-based iterative ===
This solution uses a list to keep track of the Fibonacci sequence for 0 or a
positive integer.
<
(cond ((< n 0) nil)
((< n 2) n)
Line 3,239:
(second leo))
leo))
finally (return (first leo)))))))</
{{out}}
Line 3,271:
we reverse it back when we return it).
<
;;; Helper functions
Line 3,303:
(fibo (1+ lower))
(fibo lower))
(1+ (- upper lower))))))</
{{out}}
<pre>> (fibo 100)
Line 3,318:
=={{header|Computer/zero Assembly}}==
To find the <math>n</math>th Fibonacci number, set the initial value of <tt>count</tt> equal to <math>n</math>–2 and run the program. The machine will halt with the answer stored in the accumulator. Since Computer/zero's word length is only eight bits, the program will not work with values of <math>n</math> greater than 13.
<
STA temp
ADD x ; lower No.
Line 3,339:
x: 1
y: 1
temp: 0</
=={{header|Corescript}}==
<
var previous = 1
var number = 0
Line 3,356:
:kill
stop</
=={{header|Cowgol}}==
<
sub fibonacci(n: uint32): (a: uint32) is
Line 3,379:
i := i + 1;
end loop;
print_nl();</
{{out}}
Line 3,388:
===Recursive===
<
n < 2 ? n : fib(n - 1) + fib(n - 2)
end</
===Iterative===
<
return n if n < 2
Line 3,401:
prevFib
end</
===Tail Recursive===
<
n == 0 ? prevFib : fibTailRecursive(n - 1, fib, prevFib + fib)
end</
===Analytic===
<
(((5 ** 0.5 + 1) / 2) ** n / 5 ** 0.5).round.to_i
end</
=={{header|D}}==
Here are four versions of Fibonacci Number calculating functions. ''FibD'' has an argument limit of magnitude 84 due to floating point precision, the others have a limit of 92 due to overflow (long).The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results. A Fibonacci Number generating function is added.
All functions have support for negative arguments.
<
long sgn(alias unsignedFib)(int n) { // break sign manipulation apart
Line 3,504:
foreach (i, f; fibG(-9))
writef("%d:%d | ", i, f);
}</
{{out}} for n = 85:
<pre>Fib( 85) =
Line 3,512:
0:0 | -1:1 | -2:-1 | -3:2 | -4:-3 | -5:5 | -6:-8 | -7:13 | -8:-21 | -9:34 | </pre>
===Matrix Exponentiation Version===
<
T fibonacciMatrix(T=BigInt)(size_t n) {
Line 3,541:
void main() {
10_000_000.fibonacciMatrix;
}</
===Faster Version===
For N = 10_000_000 this is about twice faster (run-time about 2.20 seconds) than the matrix exponentiation version.
<
// Algorithm from: Takahashi, Daisuke,
Line 3,588:
void main() {
10_000_000.fibonacci;
}</
=={{header|Dart}}==
<
if (n==0 || n==1) {
return n;
Line 3,610:
print(fib(11));
print(fibRec(11));
}</
=={{header|Datalog}}==
Simple recurive implementation for Souffle.
<
Fib(0, 0).
Fib(1, 1).
Fib(i+2,x+y) :- Fib(i+1, x), Fib(i, y), i+2<=40, i+2>=2.
Fib(i-2,y-x) :- Fib(i-1, x), Fib(i, y), i-2>=-40, i-2<0.</
=={{header|DBL}}==
<
; Fibonacci sequence for DBL version 4 by Dario B.
;
Line 3,654:
CLOSE 1
END</
=={{header|Dc}}==
This needs a modern Dc with <code>r</code> (swap) and <code>#</code> (comment).
It easily can be adapted to an older Dc, but it will impact readability a lot.
<
d - # 0
1 + # 1
Line 3,675:
] sF
33 lF x f</
{{out}}
<pre>
Line 3,684:
=== Iterative ===
<
function FibonacciI(N: Word): UInt64;
var
Line 3,703:
end;
end;
</syntaxhighlight>
=== Recursive ===
<
function Fibonacci(N: Word): UInt64;
begin
Line 3,714:
Result := Fibonacci(N - 1) + Fibonacci(N - 2);
end;
</syntaxhighlight>
=== Matrix ===
Algorithm is based on
:<math>\begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F(n+1)&F(n)\\F(n)&F(n-1)\end{pmatrix}</math>.
<
function fib(n: Int64): Int64;
Line 3,756:
fib := matrix[0,0];
end;
</syntaxhighlight>
=={{header|DIBOL-11}}==
<
START ;First 10 Fibonacci NUmbers
Line 3,802:
</syntaxhighlight>
=={{header|DWScript}}==
<
begin
if N < 2 then Result := 1
else Result := fib(N-2) + fib(N-1);
End;</
=={{header|Dyalect}}==
<
if n < 2 {
return n
Line 3,821:
}
print(fib(30))</
=={{header|E}}==
<
var s := [0, 1]
for _ in 0..!n {
Line 3,831:
}
return s[0]
}</
(This version defines <tt>fib(0) = 0</tt> because [http://www.research.att.com/~njas/sequences/A000045 OEIS A000045] does.)
Line 3,850:
.
call fib 36 r
print r</
Recursive (inefficient):
Line 3,864:
.
call fib 36 r
print r</
=={{header|EchoLisp}}==
Use '''memoization''' with the recursive version.
<
(define (fib n)
(if (< n 2) n
Line 3,877:
(for ((i 12)) (write (fib i)))
0 1 1 2 3 5 8 13 21 34 55 89
</syntaxhighlight>
=={{header|ECL}}==
Line 3,883:
===Analytic===
<
Line 3,911:
RETURN FibSeq;
END; }</
=={{header|EDSAC order code}}==
This program calculates the <i>n</i>th—by default the tenth—number in the Fibonacci sequence and displays it (in binary) in the first word of storage tank 3.
<
==================
Line 3,966:
[ 20 ] P0F [ used to clear a ]
EZPF [ begin execution ]</
{{out}}
<pre>00000000000110111</pre>
=={{header|Eiffel}}==
<
class
APPLICATION
Line 4,022:
end
</syntaxhighlight>
=={{header|Ela}}==
Tail-recursive function:
<
where fib' a b 0 = a
fib' a b n = fib' b (a + b) (n - 1)</
Infinite (lazy) list:
<
where fib' x y = & x :: fib' y (x + y)</
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA 5.0 :
<
fibu(n)
Line 4,064:
console.printLine(fibu(i))
}
}</
{{out}}
<pre>
Line 4,081:
=== Alternative version using yieldable method ===
<
public FibonacciGenerator
Line 4,114:
console.readChar()
}</
=={{header|Elixir}}==
<
def fib(0), do: 0
def fib(1), do: 1
Line 4,129:
end
IO.inspect Enum.map(0..10, fn i-> Fibonacci.fib(i) end)</
Using Stream:
<
Stream.unfold({0,1}, fn {a,b} -> {a,{b,a+b}} end) |> Enum.take(10)
</syntaxhighlight>
{{out}}
Line 4,143:
=={{header|Elm}}==
Naïve recursive implementation.
<
fibonacci n = if n < 2 then
n
else
fibonacci(n - 2) + fibonacci(n - 1)</
=={{header|Emacs Lisp}}==
Line 4,153:
===version 1===
<
(cond
((< c n) (fib n b (+ a b) (+ 1 c)))
Line 4,162:
(if (< n 2)
n
(fib n 0 1 1)))</
===version 2===
<
(let (vec i j k)
(if (< n 2)
Line 4,180:
j (1+ j)
k (1+ k)))
(elt vec n))))</
<b>Eval:</b>
<
(mapconcat (lambda (n) (format "%d" (fibonacci n)))
(number-sequence 0 15) " "))</
{{out}}
Line 4,194:
=={{header|Erlang}}==
===Recursive ===
<
-module(fib).
-export([fib/1]).
Line 4,201:
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
</syntaxhighlight>
===Iterative ===
<
-module(fiblin).
-export([fib/1])
Line 4,218:
fib(N, A, B) -> if N < 1 -> B; true -> fib(N-1, B, A+B) end.
</syntaxhighlight>
<b> Evaluate:</b>
<
io:write([fiblin:fib(X) || X <- lists:seq(1,10) ]).
</syntaxhighlight>
<b> Output:</b>
Line 4,231:
===Iterative 2===
<
fib(N) -> fib(N, 0, 1).
Line 4,237:
fib(Iter, Result, Next) -> fib(Iter-1, Next, Result+Next).
</syntaxhighlight>
=={{header|ERRE}}==
<
! derived from my book "PROGRAMMARE IN ERRE"
! iterative solution
Line 4,267:
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 4,277:
==='Recursive' version===
{{works with|Euphoria|any version}}
<
function fibor(integer n)
if n<2 then return n end if
return fibor(n-1)+fibor(n-2)
end function
</syntaxhighlight>
==='Iterative' version===
{{works with|Euphoria|any version}}
<
function fiboi(integer n)
integer f0=0, f1=1, f
Line 4,297:
return f
end function
</syntaxhighlight>
==='Tail recursive' version===
{{works with|Euphoria|4.0.0}}
<
function fibot(integer n, integer u = 1, integer s = 0)
if n < 1 then
Line 4,312:
-- example:
? fibot(10) -- says 55
</syntaxhighlight>
==='Paper tape' version===
{{works with|Euphoria|4.0.0}}
<
include std/mathcons.e -- for PINF constant
Line 4,396:
end while
</syntaxhighlight>
=={{header|Excel}}==
Line 4,405:
{{Works with|Office 365 Betas 2021}}
<
=LAMBDA(n,
APPLYN(n - 2)(
Line 4,416:
)
)({1;1})
)</
And assuming that the following names are also bound to reusable generic lambdas in the Name manager:
<
=LAMBDA(xs,
LAMBDA(ys,
Line 4,475:
)
)
)</
{{Out}}
Line 4,543:
Or as a fold, obtaining just the Nth term of the Fibonacci series:
<
=LAMBDA(n,
INDEX(
Line 4,557:
1
)
)</
Assuming the following generic bindings in the Excel worksheet Name manager:
<
=LAMBDA(xs,
LAMBDA(ys,
Line 4,621:
SEQUENCE(1, COLUMNS(xs))
)
)</
{{Out}}
{| class="wikitable"
Line 4,647:
=={{header|F_Sharp|F#}}==
This is a fast [tail-recursive] approach using the F# big integer support:
<
let fibonacci n : bigint =
let rec f a b n =
Line 4,656:
f (bigint 0) (bigint 1) n
> fibonacci 100;;
val it : bigint = 354224848179261915075I</
Lazy evaluated using sequence workflow:
<
for (a,b) in Seq.zip fib (Seq.skip 1 fib) -> a+b}</
The above is extremely slow due to the nested recursions on sequences, which aren't very efficient at the best of times. The above takes seconds just to compute the 30th Fibonacci number!
Lazy evaluation using the sequence unfold anamorphism is much much better as to efficiency:
<
fibonacci |> Seq.nth 10000
</syntaxhighlight>
Approach similar to the Matrix algorithm in C#, with some shortcuts involved.
Since it uses exponentiation by squaring, calculations of fib(n) where n is a power of 2 are particularly quick.
Eg. fib(2^20) was calculated in a little over 4 seconds on this poster's laptop.
<
open System
open System.Diagnostics
Line 4,715:
iter1 1 1I 1I 0I
|> iter2
</syntaxhighlight>
=={{header|Factor}}==
===Iterative===
<
dup 2 < [
[ 0 1 ] dip [ swap [ + ] keep ] times
drop
] unless ;</
===Recursive===
<
dup 2 < [
[ 1 - fib ] [ 2 - fib ] bi +
] unless ;</
===Tail-Recursive===
<
dup 1 <
[ 2drop ]
[ [ swap [ + ] keep ] dip 1 - fib2 ]
if ;
: fib ( n -- m ) [ 0 1 ] dip fib2 ;</
===Matrix===
{{trans|Ruby}}
<
: fib ( n -- m )
Line 4,747:
[ { { 0 1 } { 1 1 } } ] dip 1 - m^n
second second
] unless ;</
=={{header|Falcon}}==
===Iterative===
<
if n < 2: return n
Line 4,763:
end
return fib
end</
===Recursive===
<
if n < 2 : return n
return fib_r(n-1) + fib_r(n-2)
end</
===Tail Recursive===
<
return fib_aux(n,0,1)
end
Line 4,778:
default: return fib_aux(n-1,a+b,a)
end
end</
=={{header|FALSE}}==
<
20n: {First 20 numbers}
0 1 n;f;!%%44,. {Output: "0,1,1,2,3,5..."}</
=={{header|Fancy}}==
<
def fib {
match self -> {
Line 4,799:
x fib println
}
</syntaxhighlight>
=={{header|Fantom}}==
Line 4,805:
Ints have a limit of 64-bits, so overflow errors occur after computing Fib(92) = 7540113804746346429.
<
class Main
{
Line 4,827:
}
}
</syntaxhighlight>
=={{header|Fermat}}==
<
Array fib[n+1];
fib[1] := 0;
Line 4,840:
fi;
fi;
.</
=={{header|Fexl}}==
<
# (fib n) = the nth Fibonacci number
\fib=
Line 4,861:
# Now test it:
for 0 20 (\n say (fib n))
</syntaxhighlight>
{{out}}
Line 4,890:
=={{header|Fish}}==
Outputs Fibonacci numbers until stopped.
<
=={{header|FOCAL}}==
<
01.20 ASK "N =", N
01.30 SET A=0
Line 4,903:
02.10 SET T=B
02.20 SET B=A+B
02.30 SET A=T</
{{out}}
<pre>FIBONACCI NUMBERS
Line 4,910:
=={{header|Forth}}==
<
0 1 rot 0 ?do over + swap loop drop ;</
Or, for negative-index support:
<
rot dup 0 = if drop drop exit then
dup 0 > if 1 - rot rot dup rot +
else 1 + rot rot over - swap then
again ;</
Since there are only a fixed and small amount of Fibonacci numbers that fit in a machine word, this FORTH version creates a table of Fibonacci numbers at compile time. It stops compiling numbers when there is arithmetic overflow (the number turns negative, indicating overflow.)
<
: F-next, over + swap
dup 0> IF dup , true ELSE false THEN ;
Line 4,939:
16 fibonacci . 987 ok
#F/64 . 93 ok
92 fibonacci . 7540113804746346429 ok \ largest number generated.</
=={{header|Fortran}}==
===FORTRAN IV===
<
NN=46
DO 1 I=0,NN
Line 4,964:
5 IFN=IFNM1+IFNM2
9 IFIBO=IFN
END</
{{out}}
<pre>
Line 4,983:
</pre>
===FORTRAN 77===
<
FUNCTION IFIB(N)
IF (N.EQ.0) THEN
Line 5,008:
IFIB=ITEMP0
END
</syntaxhighlight>
Test program
<
EXTERNAL IFIB
CHARACTER*10 LINE
Line 5,022:
901 FORMAT(3(X,I10))
END
</syntaxhighlight>
{{out}}
<pre>
Line 5,042:
===Recursive===
In ISO Fortran 90 or later, use a RECURSIVE function:
<
contains
recursive function fibR(n) result(fib)
Line 5,053:
case default; fib = fibR(n-1) + fibR(n-2)
end select
end function fibR</
===Iterative===
In ISO Fortran 90 or later:
<
integer, intent(in) :: n
integer, parameter :: fib0 = 0, fib1 = 1
Line 5,075:
end select
end function fibI
end module fibonacci</
Test program
<
use fibonacci
Line 5,084:
print *, fibr(i), fibi(i)
end do
end program fibTest</
{{out}}
Line 5,103:
=={{header|Free Pascal}}==
''See also: [[#Pascal|Pascal]]''
<
/// domain for Fibonacci function
/// where result is within nativeUInt
Line 5,142:
// assign to previous, bc f[current] = f[next] for next iteration
fibonacci := f[previous];
end;</
=={{header|FreeBASIC}}==
Extended sequence coded big integer.
<
'Freebasic version 24 Windows
Dim Shared ADDQmod(0 To 19) As Ubyte
Line 5,228:
print
print fibonacci(500)
Sleep</
{{out}}
<pre>THE SEQUENCE TO 10:
Line 5,251:
=={{header|Frink}}==
All of Frink's integers can be arbitrarily large.
<
fibonacciN[n] :=
{
Line 5,264:
return a
}
</syntaxhighlight>
=={{header|FRISC Assembly}}==
To find the nth Fibonacci number, call this subroutine with n in register R0: the answer will be returned in R0 too. Contents of other registers are preserved.
<
PUSH R2
PUSH R3
Line 5,290:
POP R1
RET</
=={{header|FunL}}==
=== Recursive ===
<
fib( 0 ) = 0
fib( 1 ) = 1
fib( n ) = fib( n - 1 ) + fib( n - 2 )</
=== Tail Recursive ===
<
def
_fib( 0, prev, _ ) = prev
Line 5,306:
_fib( n, prev, next ) = _fib( n - 1, next, next + prev )
_fib( n, 0, 1 )</
=== Lazy List ===
<
def _fib( a, b ) = a # _fib( b, a + b )
_fib( 0, 1 )
println( fib(10000) )</
{{out}}
Line 5,323:
=== Iterative ===
<
a, b = 0, 1
Line 5,329:
a, b = b, a+b
a</
=== Binet's Formula ===
<
def fib( n ) =
phi = (1 + sqrt( 5 ))/2
int( (phi^n - (-phi)^-n)/sqrt(5) + .5 )</
=== Matrix Exponentiation ===
<
res = array( a.length(), b(0).length() )
Line 5,357:
for i <- 0..10
println( fib(i) )</
{{out}}
Line 5,379:
=== Iterative ===
<
fun main(n: int): int =
loop((a,b) = (0,1)) = for _i < n do
(b, a + b)
in a
</syntaxhighlight>
=={{header|FutureBasic}}==
=== Iterative ===
<
local fn Fibonacci( n as long ) as long
Line 5,417:
print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000
HandleEvents</
Output:
<pre>
Line 5,466:
=== Recursive ===
Cost is a time penalty
<
local fn Fibonacci( n as NSInteger ) as NSInteger
NSInteger result
Line 5,485:
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Line 5,542:
=={{header|GAP}}==
<
local a;
a := [[0, 1], [1, 1]]^n;
return a[1][2];
end;</
GAP has also a buit-in function for that.
<syntaxhighlight lang
=={{header|Gecho}}==
<
Prints the first several fibonacci numbers...
Line 5,594:
ENDSELECT
ENDFUNC
</syntaxhighlight>
=={{header|GML}}==
<
//Returns the nth fibonacci number
Line 5,622:
}
return numb;</
=={{header|Go}}==
=== Recursive ===
<
if a < 2 {
return a
}
return fib(a - 1) + fib(a - 2)
}</
=== Iterative ===
<
"math/big"
)
Line 5,647:
}
return b
}</
=== Iterative using a closure ===
<
fib1, fib2 := 0, 1
return func() int {
Line 5,664:
}
return fib
}</
=== Using a goroutine and channel ===
<
a, b := 0, 1
for {
Line 5,681:
}
}
</syntaxhighlight>
=={{header|Groovy}}==
Line 5,687:
=== Recursive ===
A recursive closure must be ''pre-declared''.
<
rFib = {
it == 0 ? 0
Line 5,694:
/*it < 0*/: rFib(it+2) - rFib(it+1)
}</
=== Iterative ===
<
it == 0 ? 0
: it == 1 ? 1
: it > 1 ? (2..it).inject([0,1]){i, j -> [i[1], i[0]+i[1]]}[1]
/*it < 0*/: (-1..it).inject([0,1]){i, j -> [i[1]-i[0], i[0]]}[0]
}</
=== Analytic ===
<
def aFib = { (φ**it - (-φ)**(-it))/(5**(1/2)) as BigInteger }</
Test program:
<
def start = System.currentTimeMillis()
def result = c()
Line 5,724:
fibList.each { printf ' %3d', it }
println()
}</
{{out}}
Line 5,735:
=={{header|Harbour}}==
===Recursive===
<
#include "harbour.ch"
Function fibb(a,b,n)
return(if(--n>0,fibb(b,a+b,n),a))
</syntaxhighlight>
===Iterative===
<
#include "harbour.ch"
Function fibb(n)
Line 5,752:
end while
return(fnext)
</syntaxhighlight>
=={{header|Haskell}}==
Line 5,758:
{{Works with|exact-real|0.12.5.1}}
Using Binet's formula and [https://hackage.haskell.org/package/exact-real-0.12.5.1/docs/Data-CReal.html exact real arithmetic] library we can calculate arbitrary Fibonacci number '''exactly'''.
<
import Data.CReal
Line 5,765:
fib :: (Integral b) => b -> CReal 0
fib n = (phi^^n - (-phi)^^(-n))/sqrt 5
</syntaxhighlight>
Let's try it for large numbers:
<
λ> fib 10 :: CReal 0
55
Line 5,780:
-55
(0.01 secs, 138,408 bytes)
</syntaxhighlight>
===Recursive===
Simple definition, very inefficient.
<
if x < 1
then 0
else if x < 2
then 1
else fib (x - 1) + fib (x - 2)</
===Recursive with Memoization===
Very fast.
<
if x < 1
then 0
Line 5,801:
else fibs !! (x - 1) + fibs !! (x - 2)
where
fibs = map fib [0 ..]</
===Recursive with Memoization using memoized library===
Even faster and simpler is to use a defined memoizer (e.g. from MemoTrie package):
<
fib :: Integer -> Integer
fib = memo f where
f 0 = 0
f 1 = 1
f n = fib (n-1) + fib (n-2)</
You can rewrite this without introducing f explicitly
<
fib :: Integer -> Integer
fib = memo $ \x -> case x of
0 -> 0
1 -> 1
n -> fib (n-1) + fib (n-2)</
Or using LambdaCase extension you can write it even shorter:
<
import Data.MemoTrie
fib :: Integer -> Integer
Line 5,825:
0 -> 0
1 -> 1
n -> fib (n-1) + fib (n-2)</
The version that supports negative numbers:
<
import Data.MemoTrie
fib :: Integer -> Integer
Line 5,834:
1 -> 1
n | n>0 -> fib (n-1) + fib (n-2)
| otherwise -> fib (n+2) - fib (n+1)</
===Iterative===
<
where
go n a b
| n == 0 = a
| otherwise = go (n - 1) b (a + b)</
==== With lazy lists ====
This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:
<
Or alternatively:
<
The ''n''th Fibonacci number is then just <code plang="haskell">fib !! n</code>. The above is equivalent to
<
Also
<
==== As a fold ====
Accumulator holds last two members of the series:
<
fib :: Integer -> Integer
Line 5,869:
(\(a, b) _ -> (b, a + b))
(0, 1)
[1 .. n]</
=== With matrix exponentiation ===
Line 5,875:
we can simply write:
<
fib
Line 5,918:
-- TEST ----------------------------------------------------------------------
main :: IO ()
main = (print . take 10 . show . fib) (10 ^ 5)</
So, for example, the hundred-thousandth Fibonacci number starts with the digits:
Line 5,926:
=== With recurrence relations ===
Using <code>Fib[m=3n+r]</code> [http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities recurrence identities]:
<
fibstep :: (Integer, Integer) -> (Integer, Integer)
Line 5,960:
main :: IO ()
main = print $ (length &&& take 20) . show . fst $ fibN2 (10 ^ 2)</
{{Out}}
<pre>(21,"35422484817926191507")</pre>
<code>(fibN2 n)</code> directly calculates a pair <code>(f,g)</code> of two consecutive Fibonacci numbers, <code>(Fib[n], Fib[n+1])</code>, from recursively calculated such pair at about <code>n/3</code>:
<
(208988,"19532821287077577316")</
The above should take less than 0.1s to calculate on a modern box.
Other identities that could also be used are [http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form here]. In particular, for <i>(n-1,n) ---> (2n-1,2n)</i> transition which is equivalent to the matrix exponentiation scheme, we have
<
and for <i>(n,n+1) ---> (2n,2n+1)</i> (derived from d'Ocagne's identity, for example),
<
=={{header|Haxe}}==
=== Iterative ===
<
{
var current = 0;
Line 5,994:
}
handler(current);
}</
=== As Iterator ===
<
{
private var current = 0;
Line 6,015:
return ret;
}
}</
Used like:
<
Sys.println(i);</
=={{header|HicEst}}==
<
Fibonacci = ($==2) + Fibonacci($-1) + Fibonacci($-2)
WRITE(ClipBoard) Fibonacci ! 0 1 1 2 3 5 8 13 21 34</
=={{header|Hoon}}==
<
=/ a=@ud 0
=/ b=@ud 1
|-
?: =(n 0) a
$(a b, b (add a b), n (dec n))</
=={{header|Hope}}==
===Recursive===
<
--- f 0 <= 0;
--- f 1 <= 1;
--- f(n+2) <= f n + f(n+1);</
===Tail-recursive===
<
--- fib n <= l (1, 0, n)
whererec l == \(a,b,succ c) => if c<1 then a else l((a+b),a,c)
|(a,b,0) => 0;</
=== With lazy lists ===
This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers:
<
--- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs);</
The ''n''th Fibonacci number is then just <code plang="hope">fibs @ n</code>.
=={{header|Hy}}==
Recursive implementation.
<
(if (< n 2)
n
(+ (fib (- n 2)) (fib (- n 1)))))</
=={{header|Icon}} and {{header|Unicon}}==
Line 6,065:
computes fib(1000) if there is no integer argument.
<
write(fib(integer(!args) | 1000)
end
Line 6,078:
/fCache[n] := fib(n-1) + fib(n-2)
return fCache[n]
end</
{{libheader|Icon Programming Library}}
The above solution is similar to the one provided [http://www.cs.arizona.edu/icon/library/src/procs/memrfncs.icn fib in memrfncs]
Line 6,087:
This example computes fib(1000000) if there is no integer argument.
<
write(fib(integer(!args) | 1000000))
end
Line 6,103:
if n%2 = 1 then return [c+d, d]
else return [d, c]
end</
=={{header|IDL}}==
===Recursive===
<
if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)
end</
Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo.
===Iterative===
<
psum = (csum = 1uL)
if n lt 3 then return,csum
Line 6,123:
endfor
return,nsum
end</
Execution time O(n). Limited by size of uLong to fib(49)
===Analytic===
<
q=1/( p=(1+sqrt(5))/2 )
return,round((p^n+q^n)/sqrt(5))
end</
Execution time O(1), only limited by the range of LongInts to fib(48).
Line 6,138:
===Analytic===
<
fibAnalytic n =
floor $ ((pow goldenRatio n) - (pow (-1.0/goldenRatio) n)) / sqrt(5)
where goldenRatio : Double
goldenRatio = (1.0 + sqrt(5)) / 2.0</
===Recursive===
<
fibRecursive Z = Z
fibRecursive (S Z) = (S Z)
fibRecursive (S (S n)) = fibRecursive (S n) + fibRecursive n </
===Iterative===
<
fibIterative n = fibIterative' n Z (S Z)
where fibIterative' : Nat -> Nat -> Nat -> Nat
fibIterative' Z a _ = a
fibIterative' (S n) a b = fibIterative' n b (a + b) </
===Lazy===
<
fibLazy = 0 :: 1 :: zipWith (+) fibLazy (
case fibLazy of
(x::xs) => xs
[] => []) </
=={{header|J}}==
The [[j:Essays/Fibonacci_Sequence|Fibonacci Sequence essay]] on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number. Here is one:
<
'''Examples:'''
<
144
fibN i.31
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</
(This implementation is doubly recursive except that results are cached across function calls.)
Line 6,174:
=={{header|Java}}==
===Iterative===
<
{
if (n < 2)
Line 6,188:
}
return ans;
}</
<
/**
* O(log(n))
Line 6,219:
return a + b;
}
</syntaxhighlight>
===Recursive===
<
{
return (n < 2) ? n : recFibN(n - 1) + recFibN(n - 2);
}</
===Caching-recursive===
A variant on recursive, that caches previous results, reducing complexity from O(n<sup>2</sup>) to simply O(n). Leveraging Java’s Map.computeIfAbsent makes this thread-safe, and the implementation pretty trivial.
<
static final Map<Integer, Long> cache = new HashMap<>();
Line 6,246:
return cache.computeIfAbsent(n, k -> impl(k-1) + impl(k-2));
}
}</
===Analytic===
This method works up to the 92<sup>nd</sup> Fibonacci number. After that, it goes out of range.
<
{
double p = (1 + Math.sqrt(5)) / 2;
double q = 1 / p;
return (long) ((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5));
}</
===Tail-recursive===
<
{
return fibInner(0, 1, n);
Line 6,264:
{
return n < 1 ? a : n == 1 ? b : fibInner(b, a + b, n - 1);
}</
===Streams===
<
import java.util.function.LongUnaryOperator;
import java.util.stream.LongStream;
Line 6,285:
}
}
</syntaxhighlight>
=={{header|JavaScript}}==
Line 6,291:
====Recursive====
Basic recursive function:
<
return n<2?n:fib(n-1)+fib(n-2);
}</
Can be rewritten as:
<
if (n<2) { return n; } else { return fib(n-1)+fib(n-2); }
}</
One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion:
<
return function(n,a,b) {
return n>0 ? arguments.callee(n-1,b,a+b) : a;
}(n,0,1);
}</
===Iterative===
<
var a = 0, b = 1, t;
while (n-- > 0) {
Line 6,316:
}
return a;
}</
====Memoization====
Line 6,322:
With the keys of a dictionary,
<
return cache = cache || {}, function(n){
if (cache[n]) return cache[n];
Line 6,329:
};
})();
</syntaxhighlight>
with the indices of an array,
<
'use strict';
Line 6,349:
return fib(32);
})();</
Line 6,357:
====Y-Combinator====
<
return (function(fn) {
return fn(fn);
Line 6,373:
return fn(n - 1) + fn(n - 2);
};
});</
====Generators====
<
var prev = 0;
var curr = 1;
Line 6,385:
}
}
var fib = fibonacciGenerator();</
===ES6===
Line 6,394:
we can use an accumulating fold.
<
'use strict';
Line 6,428:
// --> 2178309
})();</
Otherwise, a simple fold will suffice.
Line 6,434:
{{Trans|Haskell}} (Memoized fold example)
<
'use strict';
Line 6,455:
// --> 2178309
})();</
{{Out}}
Line 6,462:
=={{header|Joy}}==
===Recursive===
<
===Iterative===
<
=={{header|jq}}==
Line 6,474:
so using it, the following algorithms only give exact answers up to fib(78). By contrast,
using the Go implementation of jq and the definition of nth_fib given below:
<syntaxhighlight lang=jq>
nth_fib(pow(2;20)) | tostring | [length, .[:10], .[-10:]]
</syntaxhighlight>
yields
<pre>
Line 6,488:
===Recursive===
<
if (n < 2) then n
else nth_fib_naive(n - 1) + nth_fib_naive(n - 2)
end;</
===Tail Recursive===
Recent versions of jq (after July 1, 2014) include basic optimizations for tail recursion, and nth_fib is defined here to take advantage of TCO. For example, nth_fib(10000000) completes with only 380KB (that's K) of memory. However nth_fib can also be used with earlier versions of jq.
<
# input: [f(i-2), f(i-1), countdown]
def fib: (.[0] + .[1]) as $sum
Line 6,502:
| fib end;
[-1, 1, n] | fib;
</syntaxhighlight>
Example:<
(range(0;5), 50) | [., nth_fib(.)]
</syntaxhighlight>
yields: <
[1,1]
[2,1]
[3,2]
[4,3]
[50,12586269025]</
===Binet's Formula===
<
(5|sqrt) as $rt
| ((1 + $rt)/2) as $phi
Line 6,521:
| (if 0 == (n % 2) then 1 else -1 end) as $sign
| ( ($phin - ($sign / $phin) ) / $rt ) + .5
| floor;</
===Generator===
The following is a jq generator which produces the first n terms of the Fibonacci sequence efficiently, one by one. Notice that it is simply a variant of the above tail-recursive function. The function is in effect turned into a generator by changing "( _ | fib )" to "$sum, (_ | fib)".<
def fibonacci(n):
# input: [f(i-2), f(i-1), countdown]
Line 6,531:
else $sum, ([ .[1], $sum, .[2] - 1 ] | fib)
end;
[-1, 1, n] | fib;</
=={{header|Julia}}==
===Recursive===
<
===Iterative===
<
x,y = (0,1)
for i = 1:n x,y = (y, x+y) end
x
end</
===Matrix form===
<
=={{header|K}}==
===Recursive===
<
===Recursive with memoization===
Using a (global) dictionary c.
<
===Analytic===
<
{_((phi^x)-((1-phi)^x))%_sqrt[5]}</
===Sequence to n===
<
<
=={{header|Kabap}}==
===Sequence to n===
<
// Calculate the $n'th Fibonacci number
Line 6,602:
// Return the sequence
return = "Fibonacci number " << $i << " is " << $a << " (" << $sequence << ")";
</syntaxhighlight>
=={{header|Klingphix}}==
Line 6,615:
msec print nl
"bertlham " input</
=={{header|Kotlin}}==
<
ITERATIVE {
override fun get(n: Int): Long = if (n < 2) {
Line 6,653:
println()
}
}</
{{out}}
<pre>ITERATIVE: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
Line 6,661:
=={{header|L++}}==
<
(main (prn (fib 30)))</
=={{header|LabVIEW}}==
Line 6,669:
=={{header|lambdatalk}}==
<
1) basic version
{def fib1
Line 6,753:
{fib5 1000} -> 4.346655768693743e+208 (CPU ~ 1ms)
</syntaxhighlight>
=={{header|Lang5}}==
<
__A -1 extract nip ; : nip swap drop ; : tuck swap over ;
: -rot rot rot ; : 0= 0 == ; : 1+ 1 + ; : 1- 1 - ; : sum '+ reduce ;
Line 6,762:
: fib dup 1 > if dup 1- fib swap 2 - fib + then ;
: fib dup 1 > if "1- fib" "2 - fib" bi + then ;</
=={{header|langur}}==
<
writeln map .fibonacci, series 2..20</
{{out}}
Line 6,773:
=={{header|Lasso}}==
<
define fibonacci(n::integer) => {
Line 6,797:
fibonacci(2) //->output 1
fibonacci(3) //->output 2
</syntaxhighlight>
=={{header|Latitude}}==
===Recursive===
<
takes '[n].
if { n <= 1. } then {
Line 6,809:
fibo (n - 1) + fibo (n - 2).
}.
}.</
===Memoization===
<
takes '[n].
cache := here cache.
Line 6,827:
;; Attach the cache to the method object itself.
#'self cache := Object clone.
}.</
Line 6,834:
It runs on Lean 3.4.2:
<
-- Our first implementation is the usual recursive definition:
def fib1 : ℕ → ℕ
Line 6,853:
-- Use #eval to check computations:
#eval fib1 20
#eval fib2 20</
It runs on Lean 4:
<
-- Naive version
def fib1 (n : Nat) : Nat :=
Line 6,878:
#eval fib1 20
#eval fib2 20
</syntaxhighlight>
=={{header|LFE}}==
Line 6,884:
===Recursive===
<
(defun fib
((0) 0)
Line 6,891:
(+ (fib (- n 1))
(fib (- n 2)))))
</syntaxhighlight>
===Iterative===
<
(defun fib
((n) (when (>= n 0))
Line 6,906:
(fib (- n 1) next (+ result next))))
</syntaxhighlight>
=={{header|Liberty BASIC}}==
===Iterative/Recursive===
<syntaxhighlight lang=lb>
for i = 0 to 15
print fiboR(i),fiboI(i)
Line 6,933:
fiboI = a
end function
</syntaxhighlight>
{{out}}
<pre>
Line 6,954:
</pre>
===Iterative/Negative===
<syntaxhighlight lang=lb>
print "Rosetta Code - Fibonacci sequence": print
print " n Fn"
Line 6,989:
end select
end function
</syntaxhighlight>
{{out}}
<pre>
Line 7,031:
===Recursive===
<
if n<2 then return n
return fib(n-1)+fib(n-2)
end</
===Iterative===
<
if n<2 then return n
fibPrev = 0
Line 7,048:
end repeat
return fib
end</
===Analytic===
<
sqrt5 = sqrt(5.0)
p = (1+sqrt5)/2
q = 1 - p
return integer((power(p,n)-power(q,n))/sqrt5)
end</
=={{header|Lisaac}}==
<
+ result : UINTEGER_64;
(n < 2).if {
Line 7,068:
};
result
);</
=={{header|LiveCode}}==
<
function fibi n
put 0 into aa
Line 7,090:
return fibr(n-1) + fibr(n-2)
end if
end fibr</
=={{header|LLVM}}==
<
; LLVM does not provide a way to print values, so the alternative would be
; to just load the string into memory, and that would be boring.
Line 7,162:
exit:
ret i32 0 ;-- return EXIT_SUCCESS
}</
{{out}}
<pre>0
Line 7,179:
=={{header|Logo}}==
<
if :n < 1 [output :a]
output (fib :n-1 :b :a+:b)
end</
=={{header|LOLCODE}}==
<
HAI 1.2
HOW DUZ I fibonacci YR N
Line 7,202:
IF U SAY SO
KTHXBYE
</syntaxhighlight>
=={{header|LSL}}==
Rez a box on the ground, and add the following as a New Script.
<
if(n<2) {
return n;
Line 7,220:
}
}
}</
Output:
<pre>
Line 7,262:
=={{header|Lua}}==
===Recursive===
<
--calculates the nth fibonacci number. Breaks for negative or non-integer n.
function fibs(n)
return n < 2 and n or fibs(n - 1) + fibs(n - 2)
end
</syntaxhighlight>
===Pedantic Recursive===
<
--more pedantic version, returns 0 for non-integer n
function pfibs(n)
Line 7,279:
end
end
</syntaxhighlight>
===Tail Recursive===
<
function a(n,u,s) if n<2 then return u+s end return a(n-1,u+s,u) end
function trfib(i) return a(i-1,1,0) end
</syntaxhighlight>
===Table Recursive===
<
fib_n = setmetatable({1, 1}, {__index = function(z,n) return n<=0 and 0 or z[n-1] + z[n-2] end})
</syntaxhighlight>
===Table Recursive 2===
<
-- table recursive done properly (values are actually saved into table;
-- also the first element of Fibonacci sequence is 0, so the initial table should be {0, 1}).
Line 7,303:
end
})
</syntaxhighlight>
===Iterative===
<
function ifibs(n)
local p0,p1=0,1
Line 7,312:
return p0
end
</syntaxhighlight>
=={{header|Luck}}==
<
let cache = {} in
let fibc x = if x<=1 then x else (
Line 7,323:
) in fibc(x)
);;
for x in range(10) do print(fib(x))</
=={{header|Lush}}==
<
(if (< n 2)
n
(+ (fib-rec (- n 2)) (fib-rec (- n 1)))))</
=={{header|M2000 Interpreter}}==
Return decimal type and use an Inventory (as closure) to store known return values. All closures are in scope in every recursive call (we use here lambda(), but we can use fib(), If we make Fib1=fib then we have to use lambda() for recursion.
<
Inventory K=0:=0,1:=1
fib=Lambda K (x as decimal)-> {
Line 7,346:
Print Fib(i)
}
</syntaxhighlight>
Here an example where we use a BigNum class to make a Group which hold a stack of values, and take 14 digits per item in stack. We can use inventory to hold groups, so we use the fast fib() function from code above, where we remove the type definition of Ret variable, and set two first items in inventory as groups.
<
Class BigNum {
Line 7,431:
</syntaxhighlight>
=={{header|M4}}==
<
`eval(fibo(decr($1)) + fibo(decr(decr($1))))')')')dnl
define(`loop',`ifelse($1,$2,,`$3($1) loop(incr($1),$2,`$3')')')dnl
loop(0,15,`fibo')</
=={{header|MAD}}==
<
INTERNAL FUNCTION(N)
Line 7,457:
SHOW PRINT FORMAT FNUM, I, FIB.(I)
VECTOR VALUES FNUM = $4HFIB(,I2,4H) = ,I4*$
END OF PROGRAM </
{{out}}
Line 7,484:
=={{header|Maple}}==
<
> f := n -> ifelse(n<3,1,f(n-1)+f(n-2));
> f(2);
Line 7,490:
> f(3);
2
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
The Wolfram Language already has a built-in function <tt>Fibonacci</tt>, but a simple recursive implementation would be
<
fib[1] = 1
fib[n_Integer] := fib[n - 1] + fib[n - 2]</
An optimization is to cache the values already calculated:
<
fib[1] = 1
fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]</
The above implementations may be too simplistic, as the first is incredibly slow for any reasonable range due to nested recursions and while the second is faster it uses an increasing amount of memory. The following uses recursion much more effectively while not using memory:
<
If[rm < 1, prvprv, fibi[prv, prvprv + prv, rm - 1]]
fib[n_Integer] := fibi[0, 1, n]</
However, the recursive approaches in Mathematica are limited by the limit set for recursion depth (default 1024 or 4096 for the above cases), limiting the range for 'n' to about 1000 or 2000. The following using an iterative approach has an extremely high limit (greater than a million):
<
For[i = 0, i < n, i++, tmp = prv; prv += prvprv; prvprv = tmp];
Return[prvprv]]</
If one wanted a list of Fibonacci numbers, the following is quite efficient:
<
fibList[n_Integer] := Map[Take[#, 1] &, NestList[fibi, {0, 1}, n]] // Flatten</
Output from the last with "fibList[100]":
<
1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, \
196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, \
Line 7,544:
19740274219868223167, 31940434634990099905, 51680708854858323072, \
83621143489848422977, 135301852344706746049, 218922995834555169026, \
354224848179261915075}</
The Wolfram Language can also solve recurrence equations using the built-in function <tt>RSolve</tt>
<
fib[1] == 1}, fib[n], n][[1]]</
which evaluates to the built-in function <tt>Fibonacci[n]</tt>
Line 7,555:
This function can also be expressed as
<
which evaluates to
<
and is defined for all real or complex values of n.
Line 7,568:
{{trans|Julia}}
<
f = [1 1 ; 1 0]^(n-1);
f = f(1,1);
end</
===Iterative===
<
Fn = [1 0]; %Fn(1) is F_{n-2}, Fn(2) is F_{n-1}
Line 7,591:
end
end</
===Dramadah Matrix Method===
The MATLAB help file suggests an interesting method of generating the Fibonacci numbers. Apparently the determinate of the Dramadah Matrix of type 3 (MATLAB designation) and size n-by-n is the nth Fibonacci number. This method is implimented below.
<
if n == 1
Line 7,608:
end
end</
===Tartaglia/Pascal Triangle Method===
<
function number = fibonacci(n)
%construct the Tartaglia/Pascal Triangle
Line 7,624:
number=trace(rot90(pt));
end
</syntaxhighlight>
=={{header|Maxima}}==
<
fib2(n) := (matrix([0, 1], [1, 1])^^n)[1, 2]$
Line 7,634:
fib2(-10);
-55</
=={{header|MAXScript}}==
===Iterative===
<
(
if n < 2 then
Line 7,656:
fib
)
)</
===Recursive===
<
(
if n < 2 then
Line 7,668:
fibRec (n - 1) + fibRec (n - 2)
)
)</
=={{header|Mercury}}==
Line 7,676:
===fib.m===
<
% The following code is derived from the Mercury Tutorial by Ralph Becket.
% http://www.mercury.csse.unimelb.edu.au/information/papers/book.pdf
Line 7,706:
write_int(fib(40), !IO),
write_string("\n", !IO).
</syntaxhighlight>
=== Iterative algorithm ===
Line 7,712:
The much faster iterative algorithm can be written as:
<
:- pred fib_acc(int::in, int::in, int::in, int::in, int::out) is det.
Line 7,728:
Res = Prev2 + Prev1
).
</syntaxhighlight>
This predicate can be called as <
It has several inputs which form the loop, the first is the current number, the second is a limit, ie when to stop counting. And the next two are accumulators for the last and next-to-last results.
Line 7,737:
But what if you want the speed of the fib_acc with the recursive (more declarative) definition of fib? Then use memoization, because Mercury is a pure language fib(N, F) will always give the same F for the same N, guaranteed. Therefore memoization asks the compiler to use a table to remember the value for F for any N, and it's a one line change:
<
:- pragma memo(fib/2).
:- pred fib(int::in, int::out) is det.
Line 7,744:
then X = 1
else fib(N - 1, A), fib(N - 2, B), X = A + B ).
</syntaxhighlight>
We've shown the definition of fib/2 again, but the only change here is the memoization pragma (see the reference manual). This is not part of the language specification and different Mercury implementations are allowed to ignore it, however there is only one implementation so in practice memoization is fully supported.
Line 7,751:
=={{header|Metafont}}==
<
if n=0: 0
elseif n=1: 1
Line 7,760:
for i=0 upto 10: show fibo(i); endfor
end</
=={{header|Microsoft Small Basic}}==
===Iterative===
<
n = 139
f1 = 0
Line 7,775:
f1 = f2
f2 = f3
EndFor</
{{out}}
<pre>
Line 7,781:
</pre>
===Binet's Formula===
<
n = 69
sq5=Math.SquareRoot(5)
Line 7,792:
phi2n=phi2n*phi2
TextWindow.Write(Math.Floor((phi1n-phi2n)/sq5)+" ")
EndFor</
{{out}}
<pre>
Line 7,800:
=={{header|min}}==
{{works with|min|0.19.3}}
<
(2 <)
((0 1 (dup rollup +)) dip pred times nip)
unless
) :fib</
=={{header|MiniScript}}==
An efficient solution (for n >= 0):
<
if n < 2 then return n
n1 = 0
Line 7,820:
end function
print fibonacci(6)</
And for comparison, a recursive solution (also for n >= 0):
<
if n < 1 then return 0
if n == 1 then return 1
Line 7,829:
end function
print rfib(6)</
=={{header|MiniZinc}}==
<
let {
array[0..n] of var int: fibonacci;
Line 7,845:
var int: fib = fibonacci(6);
solve satisfy;
output [show(fib),"\n"];</
=={{header|MIPS Assembly}}==
This is the iterative approach to the Fibonacci sequence.
<
.text
main: li $v0, 5 # read integer from input. The read integer will be stroed in $v0
Line 7,894:
li $v0, 10
syscall
</syntaxhighlight>
=={{header|Mirah}}==
<
return n if n < 2
fibPrev = 1
Line 7,916:
puts fibonacci 6
puts fibonacci 7
</syntaxhighlight>
=={{header|МК-61/52}}==
<lang>П0 1 lg Вx <-> + L0 03 С/П БП
03</
Instruction: ''n'' В/О С/П, where ''n'' is serial number of the number of Fibonacci sequence; С/П for the following numbers.
Line 7,928:
====Tail Recursion====
This version is tail recursive.
<
let
fun fib' (0,a,b) = a
Line 7,934:
in
fib' (n,0,1)
end</
====Recursion====
<
==={{header|MLite}}===
====Recursion====
Tail recursive.
<
(0, x1, x2) = x2
| (n, x1, x2) = fib (n-1, x2, x1+x2)
| n = fib (n, 0, 1)</
=={{header|ML/I}}==
<
"" Fibonacci - recursive
MCSKIP MT,<>
Line 7,962:
fib(3) is FIB(3)
fib(4) is FIB(4)
fib(5) is FIB(5)</
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 8,001:
ReadChar
END Fibonacci.</
=={{header|Modula-3}}==
===Recursive===
<
BEGIN
IF n < 2 THEN
Line 8,012:
RETURN Fib(n-1) + Fib(n-2);
END;
END Fib;</
=== Iterative (with negatives) ===
<
VAR
Line 8,051:
RETURN curr;
END IterFib;</
=={{header|Monicelli}}==
Recursive version. It includes a main that reads a number N from standard input and prints the Nth Fibonacci number.
<
# Main
Lei ha clacsonato
Line 8,068:
Necchi come se fosse brematurata la supercazzola bonaccia con antani meno 2 o scherziamo? vaffanzum
unchiamo più duechiamo! e velocità di esecuzione
</syntaxhighlight>
=={{header|MontiLang}}==
Reads number from standard input and prints to that number in the fibonacci sequence
<
1 VAR b .
INPUT TOINT
Line 8,080:
b VAR a .
c VAR b .
ENDFOR</
Forth-style solution
<
swap dup rot swap
enddef
Line 8,095:
. print
input
clear</
Simpler
<
0 1
FOR count
Line 8,106:
print
input /# wait until press ENTER #/
clear /# empties the stack #/</
=={{header|MUMPS}}==
===Iterative===
<
;Iterative version to get the Nth Fibonacci number
;N must be a positive integer
Line 8,120:
QUIT:N<2 F(N)
FOR I=2:1:N SET F(I)=F(I-1)+F(I-2)
QUIT F(N)</
<pre>
Line 8,129:
=={{header|Nanoquery}}==
===Iterative===
<
if (n < 2)
return n
Line 8,143:
return fib
end</
=={{header|Nemerle}}==
===Recursive===
<
using System.Console;
Line 8,164:
WriteLine("{0}: {1}", n, Fibonacci(n));
}
}</
===Tail Recursive===
<
{
match(x)
Line 8,178:
{
Fibonacci(x, 0, 1)
}</
=={{header|NESL}}==
===Recursive===
<
=={{header|NetRexx}}==
{{trans|REXX}}
<
options replace format comments java crossref savelog symbols
Line 8,223:
if n > 0 | na // 2 == 1 then return s /*if positive or odd negative... */
else return -s /*return a negative Fib number. */
</syntaxhighlight>
=={{header|NewLISP}}==
===Iterative===
<
(let (L '(0 1))
(dotimes (i n)
(setq L (list (L 1) (apply + L))))
(L 1)) )
</syntaxhighlight>
===Recursive===
<
(if (< n 2) 1
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))
</syntaxhighlight>
===Matrix multiplication===
<
(letn (f '((0 1) (1 1)) fib f)
(dotimes (i n)
Line 8,248:
(fib 0 1)) )
(print(fibonacci 10)) ;;89</
===With a stack ===
<
;;; Global variable (bigints); can be isolated in a namespace if need be
(setq stack '(0L 1L))
Line 8,267:
(println (length (fib 50000)))
;;; outputs 10450 (digits)
</syntaxhighlight>
=={{header|NGS}}==
===Iterative===
{{trans|Python}}
<
n < 2 returns n
local a = 1, b = 1
Line 8,282:
}
b
}</
=={{header|Nial}}==
Line 8,291:
single iteration with n=1,000,000 takes it about 15s.
<
if n<2 then
n
Line 8,302:
endfor;
x2
endif};</
Iterative using fold. Slightly faster, <1.6s:
<
Tacit verion of above. Slightly faster still, <1.4s:
<
===Recursive===
Line 8,316:
(Similar to time for recursive python version with n=37.)
<
...or tacit version. More than twice as fast (?) but still slow:
<
===Matrix===
Line 8,327:
Note that n>92 produces negative result.
<
Could it look a little more like J?
(Maybe 5% slower than above.)
<
~ is tr f op a b {b f a}; % Goes before verb, rather than after like in J;
_ is floor; % Not really J, but J-ish? (Cannot redefine "<.".);
fibm2 is _(0 1 pick reduce ip([2 2$1 1 1 0](~$)));</
Alternate, not involving replicating matrix n times, but maybe 50% slower
than the fastest matrix version above - similar speed to iterative:
<
=={{header|Nim}}==
===Analytic===
<
var fn = float64(n)
var p: float64 = (1.0 + sqrt(5.0)) / 2.0
var q: float64 = 1.0 / p
return int64((pow(p, fn) + pow(q, fn)) / sqrt(5.0))</
===Iterative===
<
var
first = 0
Line 8,361:
second += first
result = first</
===Recursive===
<
if n <= 2:
result = 1
else:
result = Fibonacci(n - 1) + Fibonacci(n - 2)</
===Tail-recursive===
<
if n == 0:
result = current
Line 8,377:
result = Fibonacci(n - 1, next, current + next)
proc Fibonacci(n: int): int64 =
result = Fibonacci(n, 0, 1)</
===Continuations===
<
var a = 0
var b = 1
Line 8,390:
var f = fib
for i in 0.. <10:
echo f()</
=={{header|Nix}}==
<
if n <= 1 then n else (fibonacci (n - 1) + fibonacci (n - 2));</
=={{header|Oberon-2}}==
{{Works with|oo2c Version 2}}
<
MODULE Fibonacci;
IMPORT
Line 8,458:
GenR(20);
END Fibonacci.
</syntaxhighlight>
{{out}}
<pre>
Line 8,473:
=={{header|Objeck}}==
===Recursive===
<
class Fib {
function : Main(args : String[]), Nil {
Line 8,489:
}
}
}</
=={{header|Objective-C}}==
===Recursive===
<
{
long result = 0;
Line 8,502:
}
return result;
}</
===Iterative===
<
long beforeLast = 0, last = 1;
while (index > 0) {
Line 8,512:
}
return last;
}</
=={{header|OCaml}}==
===Iterative===
<
if n < 2 then
n
Line 8,526:
fib_prev := temp
done;
!fib</
===Recursive===
<
if n < 2 then
n
Line 8,540:
| n -> if n > 0 then fib (n-1) + fib (n-2)
else fib (n+2) - fib (n+1)
</syntaxhighlight>
===Arbitrary Precision===
Using OCaml's [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Num.html Num] module.
<
let fib =
Line 8,564:
let n = int_of_string Sys.argv.(1) in
print_endline (string_of_num (fib n))
</syntaxhighlight>
compile with:
Line 8,582:
=== O(log(n)) with arbitrary precision ===
This performs log2(N) matrix multiplys. Each multiplication is not constant-time but increases sub-linearly, about O(log(N)).
<
let mul (a,b,c) (d,e,f) = let bxe = b*/e in
Line 8,597:
string_of_num y
;;
Printf.printf "fib %d = %s\n" 300 (fib 300)</
Output:<pre>fib 300 = 222232244629420445529739893461909967206666939096499764990979600</pre>
=={{header|Octave}}==
===Recursive===
<
function fibo = recfibo(n)
if ( n < 2 )
Line 8,609:
fibo = recfibo(n-1) + recfibo(n-2);
endif
endfunction</
'''Testing'''
<
for i = 0 : 20
printf("%d %d\n", i, recfibo(i));
endfor</
===Iterative===
<
function fibo = iterfibo(n)
if ( n < 2 )
Line 8,633:
fibo = f(2);
endif
endfunction</
'''Testing'''
<
for i = 0 : 20
printf("%d %d\n", i, iterfibo(i));
endfor</
===Analytic===
<
retval = round(((5 .^ 0.5 + 1) / 2) .^ n / 5 .^ 0.5);
endfunction</
===Tail Recursive===
<
if (n == 0)
retval = prevfib;
Line 8,653:
retval = fibtailrecursive(n - 1, fib, prevfib + fib);
endif
endfunction</
=={{header|Oforth}}==
<
=={{header|Ol}}==
Line 8,662:
=={{header|OPL}}==
<
REM Fibonacci sequence is generated to the Organiser II floating point variable limit.
REM CLEAR/ON key quits.
Line 8,674:
B=C
PRINT A,
UNTIL GET=1</
=={{header|Order}}==
===Recursive===
<
#define ORDER_PP_DEF_8fib_rec \
Line 8,687:
8fib_rec(8sub(8N, 2))))))
ORDER_PP(8fib_rec(10))</
Tail recursive version (example supplied with language):
<
#define ORDER_PP_DEF_8fib \
Line 8,702:
8fib_iter(8dec(8N), 8J, 8add(8I, 8J)))))
ORDER_PP(8to_lit(8fib(8nat(5,0,0))))</
===Memoization===
<
#define ORDER_PP_DEF_8fib_memo \
Line 8,729:
8print(8to_lit(8fib_memo(8N)) (,) 8space)),
1, 21)
)</
=={{header|Oz}}==
Line 8,735:
===Iterative===
Using mutable references (cells).
<
Temp = {NewCell 0}
A = {NewCell 0}
Line 8,746:
end
@A
end</
===Recursive===
Inefficient (blows up the stack).
<
if N < 2 then N
else {FibR N-1} + {FibR N-2}
end
end</
===Tail-recursive===
Using accumulators.
<
fun{Loop N A B}
if N == 0 then
Line 8,768:
in
{Loop N 1 0}
end</
===Lazy-recursive===
<
fun lazy {FiboSeq}
{LazyMap
Line 8,790:
end
in
{Show {List.take {FiboSeq} 8}}</
=={{header|PARI/GP}}==
===Built-in===
<syntaxhighlight lang
===Matrix===
<
===Analytic===
This uses the Binet form.
<
The second term can be dropped since the error is always small enough to be subsumed by the rounding.
<
===Algebraic===
Line 8,810:
and hence <code>real(quadgen(5)^n)</code> would give the (n-1)-th Fibonacci number.
<
A more direct translation (note that <math>\sqrt5=2\phi-1</math>) would be
<
===Combinatorial===
This uses the generating function. It can be trivially adapted to give the first n Fibonacci numbers.
<
===Binary powering===
<
if(n<=0,
if(n,(-1)^(n+1)*fib(n),0)
Line 8,837:
if(n,[v[1]^2+2,v[1]*v[2]+1],[v[1]^2-2,v[1]*v[2]-1])
)
};</
===Recursive===
<
if(n<2,
n
Line 8,846:
fib(n-1)+fib(n)
)
};</
===Anonymous recursion===
{{works with|PARI/GP|2.8.0+}}
This uses <code>self()</code> which gives a self-reference.
<
if(n<2,
n
Line 8,858:
s(n-2)+s(n-1)
)
};</
It can be used without being named:
<
gives
{{out}}
Line 8,867:
===Memoization===
<
fib(n)={
if(n>#F,
Line 8,879:
)
);
}</
===Iterative===
<
if(n<0,return((-1)^(n+1)*fib(n)));
my(a=0,b=1,t);
Line 8,892:
);
a
};</
===Chebyshev===
This solution uses Chebyshev polynomials of the second kind (Chyebyshev U-polynomials).
<
or
<
===Anti-Hadamard matrix===
Line 8,904:
R. L. Graham and N. J. A. Sloane, [http://www.math.ucsd.edu/~ronspubs/84_03_anti_hadamard.pdf Anti-Hadamard matrices], Linear Algebra Appl. 62 (1984), 113–137.</ref> matches this upper bound, and hence can be used as an inefficient method for computing Fibonacci numbers of positive index. These matrices are the same as Matlab's type-3 "Dramadah" matrices, following a naming suggestion of C. L. Mallows according to Graham & Sloane.
<
matrix(n,n,i,j,
my(t=j-i+1);
Line 8,910:
);
}
fib(n)=matdet(matantihadamard(n))</
===Testing adjacent bits===
The Fibonacci numbers can be characterized (for n > 0) as the number of n-bit strings starting and ending with 1 without adjacent 0s. This inefficient, exponential-time algorithm demonstrates:
<
{
my(g=2^(n+1)-1);
Line 8,921:
bitor(i,i<<1)==g
);
}</
===One-by-one===
This code is purely for amusement and requires n > 1. It tests numbers in order to see if they are Fibonacci numbers, and waits until it has seen ''n'' of them.
<
=={{header|Pascal}}==
===Analytic===
<
const
Sqrt5 = sqrt(5.0);
Line 8,945:
else
Fibdirekt := 0
end;</
===Recursive===
<
begin
if (n = 0) or (n = 1)
Line 8,955:
else
fib := fib(n-1) + fib(n-2)
end;</
===Iterative===
<
var
f0, f1, tmpf0, k: integer;
Line 8,979:
f1 := 0;
fib := f1;
end;</
===Analytic2===
<
begin
result:= (pow((1+SQRT5)/2,n)-pow((1-SQRT5)/2,n))/SQRT5
end;</
<
var tbig1, tbig2, tbig3: TInteger;
begin
Line 9,005:
tbig2.free;
tbig1.free;
end;</
writeln(floattoStr(FiboMax(555)))
Line 9,015:
=={{header|Perl}}==
===Iterative===
<
my $n = shift;
use bigint try => "GMP,Pari";
Line 9,021:
($v2,$v1) = ($v1,$v2+$v1) for 0..$n;
$v1;
}</
===Recursive===
<
my $n = shift;
$n < 2 ? $n : fibRec($n - 1) + fibRec($n - 2);
}</
===Modules===
Quite a few modules have ways to do this. Performance is not typically an issue with any of these until 100k or so. With GMP available, the first three are ''much'' faster at large values.
<
use Math::AnyNum qw/fibonacci/;
say fibonacci(10000);
Line 9,054:
# Perl, gives floating point *approximation*
use Math::Fibonacci qw/term/;
say term(10000);</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">fibonacci</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- iterative, works for -ve numbers</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>
Line 9,074:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 9,081:
Using native integers/atoms, errors creep in above 78, so the same program converted to use mpfr:
{{libheader|Phix/mpfr}}
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\fibonacci.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 9,127:
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 9,137:
=={{header|Phixmonti}}==
<
dup 0 < if
"Invalid argument: " print
Line 9,150:
10 Fibonacci pstack print nl
-10 Fibonacci print</
=={{header|PHP}}==
===Iterative===
<
if ($n < 2) {
return $n;
Line 9,164:
}
return $fib;
}</
===Recursive===
<
return $n < 2 ? $n : fibRec($n-1) + fibRec($n-2);
}</
=={{header|Picat}}==
===Function===
tabling for speed.
<
println([fib_fun(I) : I in 1..10]),
F1=fib_fun(2**10),
Line 9,182:
fib_fun(0) = 0.
fib_fun(1) = 1.
fib_fun(N) = fib_fun(N-1) + fib_fun(N-2).</
{{out}}
Line 9,189:
===Array===
<
fib_array(1,[0,1]).
fib_array(N,A) :-
Line 9,198:
foreach(I in 3..N)
A[I] = A[I-1] + A[I-2]
end.</
===Loop===
<
Curr = 0,
Prev = 1,
Line 9,208:
Curr := Curr + Prev,
Prev := Tmp
end.</
===Formula===
{{trans|Tcl}}
Works for n <= 70.
<
==="Lazy lists"===
{{trans|Prolog}}
<
A = new_list(15),
append(A,_,X),
Line 9,225:
ffib(0,1,X).
ffib(A,B,X) :-
freeze(X, (C is A+B, X=[C|Y], ffib(B,C,Y)) ).</
{{out}}
Line 9,232:
===Generators idiom===
{{trans|Prolog}}
<
take(15, $fib_gen(0,1), $T-[], _G),
println(T).
Line 9,241:
take( N1, Next1, $B-Z, NZ).
next( fib_gen(A,B), A, fib_gen(B,C)):- C is A+B.</
{{out}}
Line 9,257:
<
go =>
Line 9,283:
fib_rev(N1,F1),
fib_rev(N2,F2),
F #= F1+F2.</
{{out}}
Line 9,292:
=={{header|PicoLisp}}==
===Recursive===
<
(if (>= 2 N)
1
(+ (fibo (dec N)) (fibo (- N 2))) ) )</
Line 9,302:
===Recursive with Cache===
Using a recursive version doesn't need to be slow, as the following shows:
<
(cache '(NIL) N # Use a cache to accelerate
(if (>= 2 N)
Line 9,308:
(+ (fibo (dec N)) (fibo (- N 2))) ) ) )
(bench (fibo 1000))</
Output:
<
-> 43466557686937456435688527675040625802564660517371780402481729089536555417949
05189040387984007925516929592259308032263477520968962323987332247116164299644090
6533187938298969649928516003704476137795166849228875</
===Iterative===
<
(let (A 0 B 1)
(do N
(prog1 B (setq B (+ A B) A @)) ) ) )</
===Coroutines===
<
(let (A 0 B 1)
(yield 'ready)
Line 9,332:
(printsp (yield 'next 'fibo)) )
(prinl)
(yield NIL 'fibo)</
{{out}}
<pre>1 1 2 3 5 8 13 21 34 55 89 144 233 377 610</pre>
Line 9,339:
===Iterative===
<
fibIter(int n) {
int fibPrev, fib, i;
Line 9,353:
}
return fib;
}</
===Recursive===
<
fibRec(int n) {
if (n < 2) {
Line 9,362:
}
return( fib(n-2) + fib(n-1) );
}</
=={{header|PIR}}==
Recursive:
{{works with|Parrot|tested with 2.4.0}}
<
.param int n
.local int nt
Line 9,396:
DONE:
end
.end</
Iterative (stack-based):
{{works with|Parrot|tested with 2.4.0}}
<
.param int n
.local int counter
Line 9,449:
DONE:
end
.end</
=={{header|PL/I}}==
<
Fib: procedure (n) returns (fixed binary (31));
declare (i, n, f1, f2, f3) fixed binary (31);
Line 9,465:
end Fib;
</syntaxhighlight>
=={{header|PL/M}}==
<
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
Line 9,504:
END;
CALL EXIT;
EOF</
{{out}}
<pre>0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765</pre>
Line 9,511:
=== Recursive ===
<
BEGIN
IF (n < 2) THEN
Line 9,518:
RETURN fib(n - 1) + fib(n - 2);
END;
$$ LANGUAGE plpgsql;</
=== Calculated ===
<
BEGIN
RETURN round(pow((pow(5, .5) + 1) / 2, n) / pow(5, .5));
END;
$$ LANGUAGE plpgsql;</
=== Linear ===
<
DECLARE
prevFib INTEGER := 0;
Line 9,544:
RETURN fib;
END;
$$ LANGUAGE plpgsql;</
=== Tail recursive ===
<
RETURNS INTEGER AS $$
BEGIN
Line 9,555:
RETURN fibTailRecursive(n - 1, fib, prevFib + fib);
END;
$$ LANGUAGE plpgsql;</
=={{header|PL/SQL}}==
<
create or replace function fnu_fibonacci(p_num integer) return integer is
f integer;
Line 9,579:
end fnu_fibonacci;
/
</syntaxhighlight>
=={{header|Plain English}}==
<
Put 0 into a number.
Put 1 into another number.
Line 9,589:
Add the number to the other number.
Swap the number with the other number.
Repeat.</
=={{header|Pop11}}==
<
lvars a , b;
1 -> a;
Line 9,600:
endrepeat;
a;
enddefine;</
=={{header|PostScript}}==
Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:
<
% We want the 'n'th fibonacci number
Line 9,624:
(Fib\() show n (....) cvs show (\)=) show n fib (.....) cvs show
showpage</
=={{header|Potion}}==
Line 9,630:
===Recursive===
Starts with int and upgrades on-the-fly to doubles.
<
if (n <= 1): 1. else: recursive (n - 1) + recursive (n - 2)..
n = 40
("fib(", n, ")= ", recursive (n), "\n") join print</
<pre>
Line 9,642:
===Iterative===
<
curr = 0
prev = 1
Line 9,652:
.
curr
.</
===Matrix based===
<
# Based on the fact that
Line 9,674:
.
algorithm(n)(0)
.</
===Handling negative values===
Line 9,689:
.
.
.</
=={{header|PowerBASIC}}==
Line 9,702:
F(92) 7540113804746346429 7540113804746346430
<
DIM u AS LONG, a AS LONG, L0 AS LONG, outP AS QUAD
STATIC fibNum() AS QUAD
Line 9,749:
NEXT
CLOSE
END FUNCTION</
=={{header|PowerShell}}==
===Iterative===
<
function FibonacciNumber ( $count )
{
Line 9,763:
return $answer
}
</syntaxhighlight>
An even shorter version that eschews function calls altogether:
<
$count = 8
$answer = @(0,1)
0..($count - $answer.Length) | Foreach { $answer += $answer[-1] + $answer[-2] }
$answer
</syntaxhighlight>
===Recursive===
<
switch ($n) {
0 { return 0 }
Line 9,782:
default { return (fib ($n - 1)) + (fib ($n - 2)) }
}
}</
=={{header|Processing}}==
{{trans|Java}}
<
size(400, 400);
fill(255, 64);
Line 9,799:
int fibonacciNum(int n) {
return (n < 2) ? n : fibonacciNum(n - 1) + fibonacciNum(n - 2);
}</
On the nth frame, the nth Fibonacci number is printed to the console and a square of that size is drawn on the sketch surface. The sketch restarts to keep drawing within the window size.
Line 9,823:
{{works with|GNU Prolog}}
{{works with|YAP}}
<
fib(1, 1) :- !.
fib(0, 0) :- !.
Line 9,830:
B is N - 2, fib(B, B1),
Value is A1 + B1.
</syntaxhighlight>
This naive implementation works, but is very slow for larger values of N. Here are some simple measurements (in SWI-Prolog):
<
% 2 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 161943 Lips)
F = 0.
Line 9,851:
?- time(fib(40,F)).
% 496,740,421 inferences, 138.705 CPU in 140.206 seconds (99% CPU, 3581264 Lips)
F = 102334155.</
As you can see, the calculation time goes up exponentially as N goes higher.
Line 9,861:
The performance problem can be readily fixed by the addition of two lines of code (the first and last in this version):
<
:- dynamic(fib/2). % Not ISO, but works in SWI, YAP and GNU unlike the ISO declaration.
fib(1, 1) :- !.
Line 9,869:
B is N - 2, fib(B, B1),
Value is A1 + B1,
asserta((fib(N, Value) :- !)).</
Let's take a look at the execution costs now:
<
% 2 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 160591 Lips)
F = 0.
Line 9,891:
?- time(fib(40,F)).
% 41 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 543572 Lips)
F = 102334155.</
In this case by asserting the new N,Value pairing as a rule in the database we're making the classic time/space tradeoff. Since the space costs are (roughly) linear by N and the time costs are exponential by N, the trade-off is desirable. You can see the poor man's memoizing easily:
<
:- dynamic fib/2.
Line 9,945:
fib(C, F),
D is E+F,
asserta((fib(A, D):-!)).</
All of the interim N/Value pairs have been asserted as facts for quicker future use, speeding up the generation of the higher Fibonacci numbers.
Line 9,951:
===Continuation passing style===
Works with <b>SWI-Prolog</b> and module lambda, written by <b>Ulrich Neumerkel</b> found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
<
fib(N, FN) :-
cont_fib(N, _, FN, \_^Y^_^U^(U = Y)).
Line 9,964:
call(Pred, FNA, FNB, FN1, FN)
).
</syntaxhighlight>
===With lazy lists===
Works with <b>SWI-Prolog</b> and others that support <code>freeze/2</code>.
<
ffib(0,1,X).
ffib(A,B,X) :-
freeze(X, (C is A+B, X=[C|Y], ffib(B,C,Y)) ).</
The predicate <code>fib(Xs)</code> unifies <code>Xs</code> with an infinite list whose values are the Fibonacci sequence. The list can be used like this:
<
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]</
===Generators idiom===
<
take( N, Next, [A|B]-Z, NZ):- N>0, !, next( Next, A, Next1),
N1 is N-1,
Line 9,990:
%% usage: ?- take(15, fib(0,1), _X-[], G), writeln(_X).
%% [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
%% G = fib(610, 987)</
=== Yet another implementation ===
One of my favorites; loosely similar to the first example, but without the performance penalty, and needs nothing special to implement. Not even a dynamic database predicate. Attributed to M.E. for the moment, but simply because I didn't bother to search for the many people who probably did it like this long before I did. If someone knows who came up with it first, please let us know.
<
fib(C, [P,S], C, N) :- N is P + S.
fib(C, [P,S], Cv, V) :- succ(C, Cn), N is P + S, !, fib(Cn, [S,N], Cv, V).
Line 10,001:
fib(0, 0).
fib(1, 1).
fib(C, N) :- fib(2, [0,1], C, N). % Generate from 3rd sequence on</
Looking at performance:
<pre> ?- time(fib(30,X)).
Line 10,045:
=== Efficient implementation ===
<
% John Devou: 26-Nov-2021
% Efficient program to calculate n-th Fibonacci number.
Line 10,058:
fib(N,F):- b(N,[],Bs), f(Bs,0,1,2,F), !.
</syntaxhighlight>
{{out}}
<pre>
Line 10,080:
=={{header|Pure}}==
===Tail Recursive===
<
loop a b n = if n==0 then a else loop b (a+b) (n-1);
end;</
=={{header|PureBasic}}==
===Macro based calculation===
<
Int((Pow(((1+Sqr(5))/2),n)-Pow(((1-Sqr(5))/2),n))/Sqr(5))
EndMacro</
===Recursive===
<
If n<2
ProcedureReturn n
Line 10,097:
ProcedureReturn FibonacciReq(n-1)+FibonacciReq(n-2)
EndIf
EndProcedure</
===Recursive & optimized with a static hash table===
Line 10,108:
40 25847
46 1156741
<
Static NewMap Fib.i()
Protected FirstRecursion
Line 10,128:
EndIf
ProcedureReturn n
EndProcedure</
'''Example'''
Line 10,148:
The following takes a natural number and generates an initial segment of the Fibonacci sequence of that length:
<
data Fib1 = FoldNat
<
Line 10,154:
(uncurry Cons) . ((uncurry Add) . (Head, Head . Tail), id)
>
</syntaxhighlight>
This following calculates the Fibonacci sequence as an infinite stream of natural numbers:
<
type (Stream A?,,,Unfold) = gfix X. A? . X?
data Fib2 = Unfold ((outl, (uncurry Add, outl))) ((curry id) One One)
</syntaxhighlight>
As a histomorphism:
<
import Histo
Line 10,177:
> (outr $p1)) . UnmakeCofree
>
</syntaxhighlight>
=={{header|Python}}==
===Analytic===
Binet's formula:
<
def analytic_fibonacci(n):
Line 10,191:
for i in range(1,31):
print analytic_fibonacci(i),</
Output:
<pre>
Line 10,198:
===Iterative===
<
if n < 2:
return n
Line 10,205:
for _ in range(2, n):
fibPrev, fib = fib, fib + fibPrev
return fib</
====Iterative positive and negative====
<
for i in range(abs(n)-1): x=[x[1],sum(x)]
return x[1]*pow(-1,abs(n)-1) if n<0 else x[1] if n else 0
for i in range(-30,31): print fib(i),</
Output:
<pre>
Line 10,221:
===Recursive===
<
if n < 2:
return n
else:
return fibRec(n-1) + fibRec(n-2)</
===Recursive with Memoization===
<
pad = {0:0, 1:1}
def func(n):
Line 10,239:
fm = fibMemo()
for i in range(1,31):
print fm(i),</
Output:
Line 10,251:
The recursive code as written two sections above is incredibly slow and inefficient due to the nested recursion calls. Although the memoization above makes the code run faster, it is at the cost of extra memory use. The below code is syntactically recursive but actually encodes the efficient iterative process, and thus doesn't require memoization:
<
def fib(prvprv, prv, c):
if c < 1:
Line 10,257:
else:
return fib(prv, prvprv + prv, c - 1)
return fib(0, 1, n)</
However, although much faster and not requiring memory, the above code can only work to a limited 'n' due to the limit on stack recursion depth by Python; it is better to use the iterative code above or the generative one below.
===Generative===
<
a, b = 0, 1
while n>0:
yield a
a, b, n = b, a+b, n-1</
====Example use====
<
>>> [i for i in fibGen(11)]
[0,1,1,2,3,5,8,13,21,34,55]
</syntaxhighlight>
===Matrix-Based===
Translation of the matrix-based approach used in F#.
<
def prevPowTwo(n):
'Gets the power of two that is less than or equal to the given input'
Line 10,307:
return q
</syntaxhighlight>
===Large step recurrence===
This is much faster for a single, large value of n:
<
if n not in c:
x = n // 2
Line 10,317:
return c[n]
fib(10000000) # calculating it takes a few seconds, printing it takes eons</
===Same as above but slightly faster===
Putting the dictionary outside the function makes this about 2 seconds faster, could just make a wrapper:
<
def fib(n):
if n in F:
Line 10,328:
f2 = fib((n - 1) // 2)
F[n] = (f1 * f1 + f2 * f2 if n & 1 else f1 * f1 - f2 * f2)
return F[n]</
===Generative with Recursion===
This can get very slow and uses a lot of memory. Can be sped up by caching the generator results.
<
"""Yield fib[n+1] + fib[n]"""
yield 1 # have to start somewhere
Line 10,341:
f=fib()
print [next(f) for _ in range(9)]</
Output:
Line 10,347:
'''Another version of recursive generators solution, starting from 0'''
<
def fib():
Line 10,357:
yield next(a)+next(b)
print(tuple(islice(fib(), 10)))</
===As a scan or a fold ===
Line 10,363:
The Fibonacci series can be defined quite simply and efficiently as a scan or accumulation, in which the accumulator is a pair of the two last numbers.
{{Works with|Python|3.7}}
<
from itertools import accumulate, chain
Line 10,393:
fibs(20)
)
)</
{{Out}}
<pre>First twenty: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]</pre>
Line 10,401:
A fold can be understood as an amnesic scan, and functools.reduce can provide a useful and efficient re-write of the scanning version above, if we only need the Nth term in the series:
{{Works with|Python|3.7}}
<
from functools import reduce
Line 10,421:
nthFib(1000)
)
)</
{{Out}}
<pre>1000th term: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875</pre>
{{Works with|Python|3.9}}
<
def fib(n):
from functools import reduce
return reduce(lambda x, y: (x[1], x[0] + x[1]), range(n), (0, 1))[0]
</syntaxhighlight>
===Array and Range===
<
fiblength = 21
for x in range(1,fiblength-1):
xcount = fibseq[x-1] + fibseq[x]
fibseq.append(xcount)
print(xcount)</
{{Out}}
Line 10,445:
===Minimal from Russia===
<
for da in range(1, 88): # Danilin
print("."*(20-len(str(fi3))), end=' ')
Line 10,451:
fi3 = fi2+fi1
fi1 = fi2
fi2 = fi3</
{{Out}}
Line 10,468:
=={{header|QB64}}==
''CBTJD'': 2020/03/13
<
CLS
PRINT
Line 10,501:
END IF
END FUNCTION
</syntaxhighlight>
=={{header|Qi}}==
===Recursive===
<syntaxhighlight lang=qi>
(define fib
0 -> 0
Line 10,511:
N -> (+ (fib-r (- N 1))
(fib-r (- N 2))))
</syntaxhighlight>
===Iterative===
<syntaxhighlight lang=qi>
(define fib-0
V2 V1 0 -> V2
Line 10,520:
(define fib
N -> (fib-0 0 1 N))
</syntaxhighlight>
=={{header|Quackery}}==
<
100 fibo echo</
{{out}}
Line 10,534:
=={{header|R}}==
===Iterative positive and negative===
<
if (abs(n)>1) for (i in seq(abs(n)-1)) x=c(x[2],sum(x))
if (n<0) return(x[2]*(-1)^(abs(n)-1)) else if (n) return(x[2]) else return(0)
}
sapply(seq(-31,31),fib)</
Output:
<pre>
Line 10,551:
</pre>
===Other methods===
<
recfibo <- function(n) {
if ( n < 2 ) n
Line 10,589:
}
print.table(lapply(0:20, funcfibo))</
Note that an idiomatic way to implement such low level, basic arithmethic operations in R is to implement them C and then call the compiled code.
Line 10,599:
=={{header|Ra}}==
<syntaxhighlight lang=Ra>
class FibonacciSequence
**Prints the nth fibonacci number**
Line 10,645:
return a
</syntaxhighlight>
=={{header|Racket}}==
===Tail Recursive===
<
(define (fib n)
(let loop ((cnt 0) (a 0) (b 1))
Line 10,656:
a
(loop (+ cnt 1) b (+ a b)))))
</syntaxhighlight>
<
(define (fib n (a 0) (b 1))
(if (< n 2)
1
(+ a (fib (- n 1) b (+ a b)))))
</syntaxhighlight>
===Matrix Form===
<
#lang racket
Line 10,678:
(fibmat 1000)
</syntaxhighlight>
===Foldl Form===
<
(define (fib n)
(car (foldl (lambda (y x)
(let ((a (car x)) (b (cdr x)))
(cons b (+ a b)))) (cons 0 1) (range n))))
</syntaxhighlight>
=={{header|Raku}}==
Line 10,694:
This constructs the fibonacci sequence as a lazy infinite list.
<
If you really need a function for it:
<
To support negative indices:
<
sub fib ($n) { $n >= 0 ?? @fib[$n] !! @neg-fib[-$n] }</
===Iterative===
<
$n > 1 or return $n;
my ($prev, $this) = 0, 1;
($prev, $this) = $this, $this + $prev for 1 ..^ $n;
return $this;
}</
===Recursive===
<
multi fib (0) { 0 }
multi fib (1) { 1 }
multi fib ($n) { fib($n - 1) + fib($n - 2) }</
=={{header|Rapira}}==
===Iterative===
<
if n = 0 then
return 0
Line 10,727:
fi
return fibonacci(n - 1) + fibonacci(n - 2)
end</
=={{header|RASEL}}==
<lang>1&-:?v2\:2\01\--2\
>$.@</
=={{header|Red}}==
(unnecessarily, but pleasantly palindromic)
<
fibonacci: func [n][
fn-1: 0
fn: 1
loop n palindrome
]</
=={{header|Relation}}==
<
function fibonacci (n)
if n < 2
Line 10,759:
end if
end function
</syntaxhighlight>
=={{header|Retro}}==
===Recursive===
<
===Iterative===
<
[ 0 1 ] dip [ over + swap ] times drop ;</
=={{header|REXX}}==
Line 10,774:
This version of the REXX program can also handle ''negative'' Fibonacci numbers.
<
numeric digits 210000 /*be able to handle ginormous numbers. */
parse arg x y . /*allow a single number or a range. */
Line 10,796:
/* [↓] an//2 [same as] (an//2==1).*/
if n>0 | an//2 then return $ /*Positive or even? Then return sum. */
return -$ /*Negative and odd? Return negative sum*/</
{{out|output|text= when using the default inputs:}}
<pre style="height:150ex">
Line 10,891:
=={{header|Ring}}==
<
give n
x = fib(n)
Line 10,899:
if nr = 1 return 1 ok
if nr > 1 return fib(nr-1) + fib(nr-2) ok
</syntaxhighlight>
=={{header|Rockstar}}==
===Iterative (minimized)===
<
Fibonacci takes Number
FNow is 0
Line 10,914:
Say Fibonacci taking 1000 (prints out highest number in Fibonacci sequence less than 1000)
</syntaxhighlight>
===Iterative (idiomatic)===
<
Love takes Time
My love was addictions
Line 10,930:
Shout; Love taking 1000 (years, years)
</syntaxhighlight>
The semicolon and the comment <code>(years, years)</code> in this version are there only for poetic effect
===Recursive===
<
The Italian takes a lover, a kiss, a promise
love is population
Line 10,953:
your soul is opportunity
Whisper The Italian taking your heart, your mind, your soul
</syntaxhighlight>
=={{header|Ruby}}==
===Iterative===
<
if n < 2
n
Line 10,969:
end
p (0..10).map { |i| fib(i) }</
Output:
<pre>
Line 10,976:
===Recursive===
<
return sequence.last if n == 0
Line 10,984:
fib(n-1, sequence)
end
</syntaxhighlight>
===Recursive with Memoization===
<
# lazily calculate the Fibonacci numbers.
Line 10,999:
end
end
# examples: fib[10] => 55, fib[-10] => (-55/1)</
===Matrix===
<
# To understand why this matrix is useful for Fibonacci numbers, remember
Line 11,037:
return nil if matrix.row_size == 0
return matrix[matrix.row_size - 1, matrix.column_size - 1]
end</
===Generative===
<
f0, f1 = 0, 1
loop do
Line 11,046:
f0, f1 = f1, f0 + f1
end
end</
Usage:
Line 11,055:
"Fibers are primitives for implementing light weight cooperative concurrency in Ruby. Basically they are a means of creating code blocks that can be paused and resumed, much like threads. The main difference is that they are never preempted and that the scheduling must be done by the programmer and not the VM." [http://www.ruby-doc.org/ruby-1.9/classes/Fiber.html]
<
a,b = 0,1
loop do
Line 11,062:
end
end
9.times {puts fib.resume}</
using a lambda
<
a, b = 1, 1
lambda {ret, a, b = a, b, a+b; ret}
end</
<pre>
Line 11,087:
===Binet's Formula===
<
phi = (1 + Math.sqrt(5)) / 2
((phi**self - (-1 / phi)**self) / Math.sqrt(5)).to_i
end</
<pre>
1.9.3p125 :001 > def fib
Line 11,102:
=={{header|Run BASIC}}==
<
print i;" ";fibR(i);" ";fibI(i)
next i
Line 11,119:
next i
fibI = a
end function</
=={{header|Rust}}==
===Iterative===
<
let mut prev = 0;
// Rust needs this type hint for the checked_add method
Line 11,133:
println!("{}", n);
}
}</
===Recursive===
<
fn main() {
fibonacci(0,1);
Line 11,147:
fibonacci(prev, n);
}
}</
===Recursive (with pattern matching)===
<
match n {
0 => 0,
Line 11,156:
n => fib(n - 1) + fib(n - 2),
}
}</
===Tail recursive (with pattern matching)===
<
fn fib_tail_iter(n: usize, prev_fib: usize, fib: usize) -> usize {
match n {
Line 11,167:
}
fib_tail_iter(nth, 0, 1)
}</
===Analytic===
<
for num in fibonacci_sequence() {
println!("{}", num);
Line 11,182:
// The range is sufficient up to 70th Fibonacci number
(0..1).chain((1..70).map(move |n| ((p.powi(n) + q.powi(n)) / sqrt_5 + 0.5) as u64))
}</
===Using an Iterator===
Iterators are very idiomatic in rust, though they may be overkill for such a simple problem.
<
struct Fib {
Line 11,214:
println!("{}", num);
}
}</
====Iterator "Successors"====
<
std::iter::successors(Some((1u128, 0)), |&(a, b)| a.checked_add(b).map(|s| (b, s)))
.for_each(|(_, u)| println!("{}", u));
}</
=={{header|S-BASIC}}==
Note that the 23rd Fibonacci number (=28657) is the largest that can be generated without overflowing S-BASIC's integer data type.
<
rem - iterative function to calculate nth fibonacci number
function fibonacci(n = integer) = integer
Line 11,248:
end
</syntaxhighlight>
{{out}}
<pre> 0 1 1 2 3 5 8 13 21 34 55
Line 11,259:
This code builds a table <code>fib</code> holding the first few values of the Fibonacci sequence.
<
a=0;
b=1;
Line 11,269:
end;
keep n f;
run;</
=== Naive recursive ===
Line 11,275:
This code provides a simple example of defining a function and using it recursively. One of the members of the sequence is written to the log.
<
proc fcmp outlib=work.f.p;
Line 11,288:
x = fib(5);
put 'fib(5) = ' x;
run;</
=={{header|Sather}}==
The implementations use the arbitrary precision class INTI.
<
-- RECURSIVE --
Line 11,325:
end;
end;</
=={{header|Scala}}==
===Recursive===
<
case 0 => 0
case 1 => 1
case _ => fib(i - 1) + fib(i - 2)
}</
===Lazy sequence===
<
===Tail recursive===
<
@tailrec
final def fib(x: Int, prev: BigInt = 0, next: BigInt = 1): BigInt = x match {
case 0 => prev
case _ => fib(x - 1, next, next + prev)
}</
===foldLeft===
<
// Does not run out of memory for very large Fibonacci numbers
def fib(n: Int): BigInt = {
Line 11,360:
// result: 0 1 1 2 3 5 8 13 21 34 55 89 144 233
</syntaxhighlight>
===Iterator===
<
def fib(n: Int): Int = it.drop(n).next()
// example:
println(it.take(13).mkString(",")) // prints: 0,1,1,2,3,5,8,13,21,34,55,89,144</
=={{header|Scheme}}==
===Iterative===
<
(do ((num 2 (+ num 1))
(fib-prev 1 fib)
(fib 1 (+ fib fib-prev)))
((>= num n) fib)))</
===Recursive===
<
(if (< n 2)
n
(+ (fib-rec (- n 1))
(fib-rec (- n 2)))))</
This version is tail recursive:
<
(let loop ((a 0) (b 1) (n n))
(if (= n 0) a
(loop b (+ a b) (- n 1)))))
</syntaxhighlight>
===Recursive Sequence Generator===
Line 11,398:
The following procedure generates the sequence of Fibonacci numbers using a simplified version of a lazy list/stream - since no memoization is requried, it just implements future values by using a zero parameter lambda "thunk" with a closure containing the last and the pre-calculated next value of the sequence; in this way it uses almost no memory during the sequence generation other than as required for the last and the next values of the sequence (note that the test procedure does not generate a linked list to contain the elements of the sequence to show, but rather displays each one by one in sequence):
<
(define (fib)
(define (nxt lv nv) (cons nv (lambda () (nxt nv (+ lv nv)))))
Line 11,408:
(if (> n 1) (begin (display " ") (shw-nxt (- n 1) ((cdr strm)))) (display ")"))))
(begin (display "(") (shw-nxt n strm)))
(show-stream-take 30 (fib))</
{{output}}
Line 11,414:
===Dijkstra Algorithm===
<
;;; http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
Line 11,432:
q
(- count 1)))))
(fib-aux 1 0 0 1 n))</
=={{header|Scilab}}==
Line 11,445:
f1=f2
f2=f3
end</
{{out}}
<pre>...
Line 11,454:
=={{header|sed}}==
<
# First we need to convert each number into the right number of ticks
Line 11,493:
s/</|/g
t back
s/^$/0/</
=={{header|Seed7}}==
===Recursive===
<
result
var integer: result is 1;
Line 11,506:
result := 0;
end if;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#fib]
Line 11,513:
This funtion uses a bigInteger result:
<
result
var bigInteger: result is 1_;
Line 11,526:
result +:= c;
end for;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#iterative_fib]
Line 11,532:
=={{header|SequenceL}}==
===Recursive===
<
n when n < 2
else
fibonacci(n - 1) + fibonacci(n - 2);</
Based on: [https://www.youtube.com/watch?v=5JVC5dDtnyg]
===Tail Recursive===
<
fibonacciHelper(prev, next, n) :=
Line 11,546:
next when n = 1
else
fibonacciHelper(next, next + prev, n - 1);</
===Matrix===
<
fibonacciHelper(M(2), n) :=
Line 11,559:
fibonacciHelper(matmul(M, N), n - 1);
matmul(A(2), B(2)) [i,j] := sum( A[i,all] * B[all,j] );</
Based on the C# version: [http://rosettacode.org/wiki/Fibonacci_sequence#C.23]
Line 11,565:
=={{header|SETL}}==
<
$ This uses Set Builder Notation, it roughly means
$ 'collect fib(n) forall n in {0,1,2,3,4,5,6,7,8,9,10}'
Line 11,579:
end loop;
return C;
end proc;</
=={{header|Shen}}==
<
0 -> 0
1 -> 1
N -> (+ (fib (+ N 1)) (fib (+ N 2)))
where (< N 0)
N -> (+ (fib (- N 1)) (fib (- N 2))))</
=={{header|Sidef}}==
===Iterative===
<
var (a, b) = (0, 1)
{ (a, b) = (b, a+b) } * n
return a
}</
===Recursive===
<
n < 2 ? n : (__FUNC__(n-1) + __FUNC__(n-2))
}</
===Recursive with memoization===
<
n < 2 ? n : (__FUNC__(n-1) + __FUNC__(n-2))
}</
===Closed-form===
<
define S = (1.25.sqrt + 0.5)
define T = (-S + 1)
(S**n - T**n) / (-T + S) -> round
}</
===Built-in===
<
=={{header|Simula}}==
Straightforward iterative implementation.
<
INTEGER n;
BEGIN
Line 11,632:
END;
fibonacci := hi
END;</
=={{header|SkookumScript}}==
Line 11,640:
SkookumScript's <code>Integer</code> class has a fast built-in <code>fibonnaci()</code> method.
<syntaxhighlight lang
SkookumScript is designed to work in tandem with C++ and its strength is at the high-level stage-direction of things. So when confronted with [http://skookumscript.com/blog/2016/07-11-fibonacci/ benchmarking scripting systems] it is genrally better to make a built-in call. Though in most practical cases this isn't necessary.
Line 11,648:
Simple recursive method in same <code>42.fibonacci</code> form as built-in form above.
<
() Integer
[
if this < 2 [this] else [[this - 1].fibonacci + [this - 2].fibonacci]
]</
Recursive procedure in <code>fibonacci(42)</code> form.
<
(Integer n) Integer
[
if n < 2 [n] else [fibonacci(n - 1) + fibonacci(n - 2)]
]</
===Iterative===
Line 11,666:
Iterative method in <code>42.fibonacci</code> form.
<
() Integer
[
Line 11,684:
next
]
]</
Optimized iterative method in <code>42.fibonacci</code> form.
Though the best optimiation is to write it in C++ as with the built-in form that comes with SkookumScript.
<
// loop is faster than to_pre (which uses a closure)
() Integer
Line 11,712:
next
]
]</
=={{header|Slate}}==
<
[
n <= 0 ifTrue: [^ 0].
Line 11,723:
slate[15]> 10 fib = 55.
True</
=={{header|Smalltalk}}==
Line 11,733:
iterative (slow):
<
|aNMinus1 an t|
Line 11,743:
aNMinus1 := t.
].
^ an</
The recursive version although nice to read is the worst; it suffers from a huge stack requirement and a super poor performance (an anti-example for recursion):
<
(self > 1) ifTrue:[
^ (self - 1) fibR + (self - 2) fibR
].
^ self</
analytic (fast, but inexact, and limited to small n below 1475 if we use double precision IEEE floats):
<
|phi rPhi|
Line 11,758:
rPhi := 1 / phi.
^ (1 / 5 sqrt) * ((phi raisedTo:self) - (rPhi raisedTo:self))</
using more bits in the exponent, we can compute larger fibs (up to 23599 with x86 extended precision floats), but still inexact:
<
|phi rPhi|
Line 11,766:
rPhi := 1 / phi.
^ (1 / 5 sqrt) * ((phi raisedTo:self) - (rPhi raisedTo:self))</
<
(10 to:1e6 byFactor:10) do:[:n |
Transcript printCR:'----',n,'----'.
Line 11,792:
[ 1000000 fib ] benchmark:'1000000 fib (builtin)'.
[ 2000000 fib ] benchmark:'2000000 fib (builtin)'.
[ 10000000 fib ] benchmark:'10000000 fib (builtin)'</
{{out}}
<pre>----10----
Line 11,853:
</ul>
<
PRINT fibR(i),fibI(i),fibN(i)
NEXT i
Line 11,883:
lphi = .5 - SQR(5)/2
fibN = (uphi^n-lphi^n)/SQR(5)
END DEF</
=={{header|SNOBOL4}}==
===Recursive===
<
fib fib = lt(a,2) a :s(return)
fib = fib(a - 1) + fib(a - 2) :(return)
Line 11,895:
while a = trim(input) :f(end)
output = a " " fib(a) :(while)
end</
===Tail-recursive===
<
trfib trfib = eq(n,0) a :s(return)
trfib = trfib(n - 1, a + b, a) :(return)
trfib_end</
===Iterative===
<
ifib ifib = le(n,2) 1 :s(return)
f1 = 1; f2 = 1
if1 ifib = gt(n,2) f1 + f2 :f(return)
f1 = f2; f2 = ifib; n = n - 1 :(if1)
ifib_end</
===Analytic===
Line 11,916:
Note: Snobol4+ lacks built-in sqrt( ) function.
<
afib s5 = sqrt(5)
afib = (((1 + s5) / 2) ^ n - ((1 - s5) / 2) ^ n) / s5
afib = convert(afib,'integer') :(return)
afib_end</
Test and display all, Fib 1 .. 10
<
s1 = s1 fib(i) ' ' ; s2 = s2 trfib(i,0,1) ' '
s3 = s3 ifib(i) ' '; s4 = s4 afib(i) ' ' :(loop)
show output = s1; output = s2; output = s3; output = s4
end</
Output:
Line 11,940:
===Iterative===
<
fib\==>>+<<?!/>!\ ?/\
#<</?\!>/@>\?-<<</@>/@>/>+<-\
\-/ \ !\ !\ !\ ?/#</
===Recursive===
<
fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
| #+==/ fib(n-2)|+fib(n-1)|
\=====recursion======/!========/</
=={{header|Softbridge BASIC}}==
===Iterative===
<
Function Fibonacci(n)
x = 0
Line 11,972:
End Function
</syntaxhighlight>
=={{header|Spin}}==
Line 11,980:
{{works with|HomeSpun}}
{{works with|OpenSpin}}
<
_clkmode = xtal1 + pll16x
_clkfreq = 80_000_000
Line 12,001:
b := a := 1
repeat i
a := b + (b := a)</
{{out}}
<pre>1 1 2 3 5 8 13 21 34 55 89</pre>
Line 12,007:
=={{header|SPL}}==
=== Analytic ===
<
s5 = #.sqrt(5)
<= (((1+s5)/2)^n-((1-s5)/2)^n)/s5
.</
=== Iterative ===
<
? n<2, <= n
f2 = 0
Line 12,022:
<
<= f
.</
=== Recursive ===
<
? n<2, <= n
<= fibo(n-1)+fibo(n-2)
.</
=={{header|SQL}}==
=== Analytic ===
As a running sum:
<
select round ( exp ( sum (ln ( ( 1 + sqrt( 5 ) ) / 2)
) over ( order by level ) ) / sqrt( 5 ) ) fibo
from dual
connect by level <= 10;
</syntaxhighlight>
<pre>
FIB
Line 12,055:
</pre>
As a power:
<
select round ( power( ( 1 + sqrt( 5 ) ) / 2, level ) / sqrt( 5 ) ) fib
from dual
connect by level <= 10;
</syntaxhighlight>
<pre>
FIB
Line 12,081:
Oracle 12c required
<
SQL> with fib(e,f) as (select 1, 1 from dual union all select e+f,e from fib where e <= 55) select f from fib;
Line 12,098:
10 rows selected.
</syntaxhighlight>
{{works with|PostgreSQL}}
<
-- This recursive with generates endless list of Fibonacci numbers.
WITH RECURSIVE fibonacci(current, previous) AS (
Line 12,128:
-- position in the list.
OFFSET n
$$ LANGUAGE SQL RETURNS NULL ON NULL INPUT IMMUTABLE;</
=={{header|SSEM}}==
Calculates the tenth Fibonacci number. To calculate the <i>n</i>th, change the initial value of the counter to <i>n</i>-1 (subject to the restriction that the answer must be small enough to fit in a signed 32-bit integer, the SSEM's only data type). The algorithm is basically straightforward, but the absence of an Add instruction makes the implementation a little more complicated than it would otherwise be.
<
01101000000001100000000000000000 1. c to 22 temp = acc
00101000000001010000000000000000 2. Sub. 20 acc -= m
Line 12,157:
10010000000000000000000000000000 23. 9 var count = 9
11111111111111111111111111111111 24. -1 const -1
11110000000000000000000000000000 25. 15 const 15</
=={{header|Stata}}==
<
args n
clear
Line 12,167:
qui gen a=1
qui replace a=a[_n-1]+a[_n-2] in 3/l
end</
An implementation using '''[https://www.stata.com/help.cgi?dyngen dyngen]'''.
<
args n
clear
Line 12,182:
fib 10
list</
'''Output'''
Line 12,203:
=== Mata ===
<
: function fib(n) {
return((((1+sqrt(5))/2):^n-((1-sqrt(5))/2):^n)/sqrt(5))
Line 12,214:
+--------------------------------------------------------+
: end</
=={{header|StreamIt}}==
<
join roundrobin(0,1);
body in->int filter {
Line 12,226:
enqueue(0);
enqueue(1);
}</
=={{header|SuperCollider}}==
===Recursive===
nth fibonacci term for positive n
<
f = { |n| if(n < 2) { n } { f.(n-1) + f.(n-2) } };
(0..20).collect(f)
</syntaxhighlight>
nth fibonacci term for positive and negative n.
<
f = { |n| var u = neg(sign(n)); if(abs(n) < 2) { n } { f.(2 * u + n) + f.(u + n) } };
(-20..20).collect(f)
</syntaxhighlight>
===Analytic===
<
f = { |n|
var sqrt5 = sqrt(5);
Line 12,251:
};
(0..20).collect(f)
)</
===Iterative===
<
f = { |n| var a = [1, 1]; n.do { a = a.addFirst(a[0] + a[1]) }; a.reverse };
f.(18)
</syntaxhighlight>
=={{header|Swift}}==
===Analytic===
<
func fibonacci(n: Int) -> Int {
Line 12,272:
for i in 1...30 {
println(fibonacci(i))
}</
===Iterative===
<
if n < 2 {
return n
Line 12,285:
}
return fib
}</
Sequence:
<
return SequenceOf {() -> GeneratorOf<UInt> in
var window: (UInt, UInt, UInt) = (0, 0, 1)
Line 12,295:
}
}
}</
===Recursive===
<
if n < 2 {
return n
Line 12,306:
}
println(fibonacci(30))</
=={{header|Tailspin}}==
===Recursive simple===
The simplest exponential-time recursive algorithm only handling positive N. Note that the "#" is the tailspin internal recursion which sends the value to the matchers. In this case where there is no initial block and no templates state, we could equivalently write the templates name "nthFibonacci" in place of the "#" to do a normal recursion.
<
templates nthFibonacci
when <=0|=1> do $ !
otherwise ($ - 1 -> #) + ($ - 2 -> #) !
end nthFibonacci
</syntaxhighlight>
===Iterative, mutable state===
We could use the templates internal mutable state, still only positive N.
<
templates nthFibonacci
@: {n0: 0"1", n1: 1"1"};
Line 12,326:
$@.n0!
end nthFibonacci
</syntaxhighlight>
To handle negatives, we can keep track of the sign and send it to the matchers.
<
templates nthFibonacci
@: {n0: 0"1", n1: 1"1"};
Line 12,339:
@: {n0: $@.n1 - $@.n0, n1: $@.n0};
end nthFibonacci
</syntaxhighlight>
===State machine===
Instead of mutating state, we could just recurse internally on a state structure.
<
templates nthFibonacci
{ N: ($)"1", n0: 0"1", n1: 1"1" } -> #
Line 12,360:
-6 -> nthFibonacci -> '$;
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 12,373:
====Iterative====
{{trans|Perl}}
<
if {$n < 2} {return $n}
set prev 1
Line 12,381:
}
return $fib
}</
====Recursive====
<
if {$n < 2} then {expr {$n}} else {expr {[fib [expr {$n-1}]]+[fib [expr {$n-2}]]} }
}</
The following {{works with|Tcl|8.5}}: defining a procedure in the <code>::tcl::mathfunc</code> namespace allows that proc to be used as a function in <code>[http://www.tcl.tk/man/tcl8.5/TclCmd/expr.htm expr]</code> expressions.
<
if { $n < 2 } {
return $n
Line 12,398:
# or, more tersely
proc tcl::mathfunc::fib {n} {expr {$n<2 ? $n : fib($n-1) + fib($n-2)}}</
E.g.:
<
namespace path tcl::mathfunc #; or, interp alias {} fib {} tcl::mathfunc::fib
fib 7 ;# ==> 13</
====Tail-Recursive====
In Tcl 8.6 a ''tailcall'' function is available to permit writing tail-recursive functions in Tcl. This makes deeply recursive functions practical. The availability of large integers also means no truncation of larger numbers.
<
proc fib:inner {a b n} {
if {$n < 1} {
Line 12,420:
}
return [fib:inner 0 1 $n]
}</
% fib-tailrec 100
354224848179261915075
Line 12,426:
===Handling Negative Numbers===
====Iterative====
<
if {$n < 0} {
set n [expr {abs($n)}]
Line 12,442:
}
fibiter -5 ;# ==> 5
fibiter -6 ;# ==> -8</
====Recursive====
<
expr {fib(-5)} ;# ==> 5
expr {fib(-6)} ;# ==> -8</
===For the Mathematically Inclined===
This works up to <math>fib(70)</math>, after which the limited precision of IEEE double precision floating point arithmetic starts to show.<br>
{{works with|Tcl|8.5}}
<
=={{header|Tern}}==
===Recursive===
<
if (n < 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}</
===Coroutine===
<
let a = 1;
let b = 2;
Line 12,471:
(a, b) = (b, a + b);
}
}</
=={{header|TI-83 BASIC}}==
Sequence table:
<
nMin=0
u(n)=u(n-1)+u(n-2)
Line 12,494:
10 55
11 89
12 144 </
Iterative:
<
While 1
Disp Ans(1
{Ans(2),sum(Ans
End</
Binet's formula:
<
.5(1+√(5 //golden ratio
(Ans^N–(-Ans)^-N)/√(5</
=={{header|TI-89 BASIC}}==
Line 12,512:
Optimized implementation (too slow to be usable for ''n'' higher than about 12).
<
when(n<2, n, fib(n-1) + fib(n-2))</
===Iterative===
Unoptimized implementation (I think the for loop can be eliminated, but I'm not sure).
<
Func
Local a,b,c,i
Line 12,529:
EndFor
a
EndFunc</
=={{header|Tiny BASIC}}==
<
20 LET B = 1
30 PRINT "Which F_n do you want?"
Line 12,547:
140 PRINT 0
150 END
</syntaxhighlight>
=={{header|True BASIC}}==
<
LET n1 = 0
LET n2 = 1
Line 12,569:
PRINT fibonacci(-42) !-267914296
PRINT fibonacci(47) ! 2971215073
END</
=={{header|TSE SAL}}==
<
// library: math: get: series: fibonacci <description></description> <version control></version control> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=getmasfi.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 22:04:02]
Line 12,619:
END
</syntaxhighlight>
=={{header|Turing}}==
<
function fibb (n: int) : int
if n < 2 then
Line 12,644:
for i : 0 .. 10
put fibb (i) : 4, ifibb (i) : 4
end for</
Output:<pre> 0 0
Line 12,659:
=={{header|TUSCRIPT}}==
<
$$ MODE TUSCRIPT
ASK "What fibionacci number do you want?": searchfib=""
Line 12,674:
PRINT "fibionacci number ",n,"=",fib
ENDLOOP
</syntaxhighlight>
Output:
<pre>
Line 12,693:
=={{header|UNIX Shell}}==
{{works with|bash|3}}
<
a=0
Line 12,704:
echo "F($n): $a"
b=$(($a - $b))
done</
Recursive:
{{works with|bash|3}}
<
local n=$1
[ $n -lt 2 ] && echo -n $n || echo -n $(( $( fib $(( n - 1 )) ) + $( fib $(( n - 2 )) ) ))
}</
=={{header|UnixPipes}}==
{{incorrect|UnixPipes|There is a race between parallel commands. <code>tee last</code> might open and truncate the file before <code>cat last</code> opens it. Then <code>cat last</code> pipes the empty file to ''xargs'', and ''expr'' reports a syntax error, and the script hangs forever.}}
<
do
cat last | tee -a fib | xargs -n 1 expr $x + |tee last
done</
=={{header|Ursa}}==
{{trans|Python}}
===Iterative===
<
if (< n 2)
return n
Line 12,736:
end for
return fib
end</
=={{header|Ursala}}==
All three methods are shown here, and all have unlimited precision.
<
#import nat
Line 12,753:
(mp..div^|\~& mp..sub+ ~~ @rlX mp..pow_ui)^lrlPGrrPX/~& -+
^\~& ^(~&,mp..sub/1.E0)+ mp..div\2.E0+ mp..add/1.E0,
mp..sqrt+ ..grow/5.E0+-+-</
The analytical method uses arbitrary precision floating point
arithmetic from the mpfr library and then converts the result to
Line 12,759:
always chosen based on the argument. This test program computes the first
twenty Fibonacci numbers by all three methods.
<
examples = <.iterative_fib,recursive_fib,analytical_fib>* iota20</
output:
<pre>
Line 12,789:
Generate n'th fib by using binary recursion
<
[small?] []
[pred dup pred]
[+]
binrec].</
=={{header|Vala}}==
Line 12,799:
===Recursive===
Using int, but could easily replace with double, long, ulong, etc.
<
int fibRec(int n){
if (n < 2)
Line 12,806:
return fibRec(n - 1) + fibRec(n - 2);
}
</syntaxhighlight>
===Iterative===
Using int, but could easily replace with double, long, ulong, etc.
<
int fibIter(int n){
if (n < 2)
Line 12,827:
return cur;
}
</syntaxhighlight>
=={{header|VAX Assembly}}==
<
7E 7CFD 0002 2 clro -(sp) ;result buffer
5E DD 0005 3 pushl sp ;pointer to buffer
Line 12,864:
1836311903
$
</syntaxhighlight>
=={{header|VBA}}==
Like Visual Basic .NET, but with keyword "Public" and type Variant (subtype Currency) instead of Decimal:
<
Dim fib0 As Variant, fib1 As Variant, sum As Variant
Dim i As Integer
Line 12,879:
Next i
Fib = fib0
End Function </
With Currency type, maximum value is fibo(73).
The (slow) recursive version:
<
Public Function RFib(Term As Integer) As Long
If Term < 2 Then RFib = Term Else RFib = RFib(Term - 1) + RFib(Term - 2)
End Function
</syntaxhighlight>
With Long type, maximum value is fibo(46).
Line 12,897:
====Class Definition:====
<
dim t1
dim t2
Line 12,940:
end property
end class</
====Invocation:====
<
set fib = new generator
dim i
Line 12,952:
exit for
end if
next</
====Output:====
<
=={{header|Vedit macro language}}==
Line 12,961:
Calculate fibonacci(#1). Negative values return 0.
<
#11 = 0
#12 = 1
Line 12,969:
#12 = #10
}
Return(#11)</
===Unlimited precision===
<
// input: #1 = n
// return: fibonacci(n) in text register 10
Line 13,026:
}
Buf_Quit(OK)
return</
Test:
<
Ins_Text("fibonacci(") Num_Ins(#1, LEFT+NOCR) Ins_Text(") = ")
Call("fibo_unlimited")
Reg_Ins(10) IN
return</
{{out}}
Line 13,041:
{{works with|Visual Basic|VB6 Standard}}
Maximum integer value (7*10^28) can be obtained by using decimal type, but decimal type is only a sub type of the variant type.
<
Const n = 139
Dim i As Integer
Line 13,054:
f2 = f3
Next i
End Sub 'fibonacci</
{{Out}}
<pre>fibo( 0 )= 0
Line 13,069:
{{works with|Visual Basic .NET|9.0+}}
With Decimal type, maximum value is fibo(139).
<
Dim fib0, fib1, sum As Decimal
Dim i As Integer
Line 13,080:
Next
Fib = fib0
End Function</
===Recursive===
{{works with|Visual Basic .NET|9.0+}}
<
If Term < 2 Then Return Term
Return Seq(Term - 1) + Seq(Term - 2)
End Function</
===BigInteger===
There is no real maximum value of BigInterger class, except the memory to store the number.
Within a minute, fibo(2000000) is a number with 417975 digits.
<
' Fibonacci sequence with BigInteger
Dim fibn2, fibn1, fibn As BigInteger
Line 13,117:
s = FiboBig(i).ToString
Console.WriteLine("fibo(" & i & ")=" & s & " - length=" & Len(s))
End Sub 'fibotest</
===BigInteger, speedier method===
Line 13,123:
{{Libheader|System.Numerics}}
This method doesn't need to iterate the entire list, and is much faster. The 2000000 (two millionth) Fibonacci number can be found in a fraction of a second.<br/>Algorithm from [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html here, see section 3, ''Finding Fibonacci Numbers Fully''.]
<
Imports System.Collections.Generic
Imports BI = System.Numerics.BigInteger
Line 13,171:
End If
End Sub
End Module</
{{out}}
<pre>120.374 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975
Line 13,179:
Update Vlang to version 0.2.2
===Iterative===
<
if n < 2 {
return n
Line 13,195:
println('fibonacci(${val:2d}) = ${fib_iter(val):3d}')
}
}</
===Recursive===
<
if n < 2 {
return n
Line 13,210:
}
}
</syntaxhighlight>
{{out}}
<pre>fibonacci( 0) = 0
Line 13,228:
===Recursive, all at once===
<
if (n < 2)
n
(+ (fib n-1) (fib n-2))</
===Recursive, using cases===
<
(+ (fib n-1) (fib n-2))
def (fib n) :case (n < 2)
n</
===Recursive, using memoization===
<
# all args in Wart are optional, and we expect callers to not provide `saved`
default saved :to (table 0 0 1 1) # pre-populate base cases
default saved.n :to
(+ (fib n-1 saved) (fib n-2 saved))
saved.n</
=={{header|WDTE}}==
===Memoized Recursive===
<
===Iterative===
<
let a => import 'arrays';
Line 13,263:
-> a.at 1
;
);</
=={{header|WebAssembly}}==
Line 13,318:
===Iterative===
This program generates Fibonacci numbers until it is [http://ideone.com/VBDLzk forced to terminate].
<
Line 13,330:
</
It was generated from the following pseudo-Assembly.
<
push 1
Line 13,344:
copy 1
add
jump 0</
{{out}}
<pre>$ wspace fib.ws | head -n 6
Line 13,357:
This program takes a number ''n'' on standard input and outputs the ''n''th member of the Fibonacci sequence.
<
Line 13,385:
</
<
push 0
dup
Line 13,414:
add ; Leave the sum on the stack.
1:
ret</
{{out}}
Line 13,422:
=={{header|Wrapl}}==
===Generator===
<
VAR seq <- [0, 1]; EVERY SUSP seq:values;
REP SUSP seq:put(seq:pop + seq[1])[-1];
);</
To get the 17th number:
<syntaxhighlight lang
To get the list of all 17 numbers:
<syntaxhighlight lang
===Iterator===
Using type match signature to ensure integer argument:
<
VAR seq <- [0, 1];
EVERY 3:to(n) DO seq:put(seq:pop + seq[1]);
RET seq[-1];
);</
=={{header|Wren}}==
<
var fibItr = Fn.new { |n|
if (n < 2) return n
Line 13,460:
System.print("Iterative: %(fibItr.call(36))")
System.print("Recursive: %(fibRec.call(36))")</
{{out}}
Line 13,470:
=={{header|x86 Assembly}}==
{{Works with|MASM}}
<
; __ __/--------\
; >__ \ / | |\
Line 13,520:
main ENDP
END main</
=={{header|xEec}}==
This will display the first 93 numbers of the sequence.
<
h#1 h#1 h#1 o#
h#10 o$ p
Line 13,532:
t
jnf
</syntaxhighlight>
=={{header|XLISP}}==
===Analytic===
Uses Binet's method, based on the golden ratio, which almost feels like cheating—but the task specification doesn't require any particular algorithm, and this one is straightforward and fast.
<
(FLOOR (+ (/ (EXPT (/ (+ (SQRT 5) 1) 2) N) (SQRT 5)) 0.5)))</
To test it, we'll define a <tt>RANGE</tt> function and ask for the first 50 numbers in the sequence:
<
(IF (<= X Y)
(CONS X (RANGE (+ X 1) Y))))
(PRINT (MAPCAR FIBONACCI (RANGE 1 50)))</
{{out}}
<pre>(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025)</pre>
Line 13,550:
===Tail recursive===
Alternatively, this approach is reasonably efficient:
<
(defun fib (a b n)
(if (= n 2)
Line 13,557:
(if (< x 2)
x
(fib 1 1 x) ) )</
=={{header|Xojo}}==
Pass n to this function where n is the desired number of iterations. This example uses the UInt64 datatype which is as unsigned 64 bit integer. As such, it overflows after the 93rd iteration.
<
Dim noOne As UInt64 = 1
Line 13,574:
Return noOne
End Function</
=={{header|XPL0}}==
<
int N;
int Fn, F0, F1;
Line 13,599:
for N:= 0 to 20 do [IntOut(0, Fib2(N)); ChOut(0, ^ )];
CrLf(0);
]</
{{out}}
Line 13,608:
=={{header|XQuery}}==
<
if($n < 2)
then $n
else local:fib($n - 1) + local:fib($n - 2)
};</
=={{header|Yabasic}}==
<
n1 = 0
n2 = 1
Line 13,629:
return n1
end if
end sub</
=={{header|Z80 Assembly}}==
<
; IN : a = n (n <= 13, otherwise overflows)
; OUT: a = FIB(n)
Line 13,650:
ret
</syntaxhighlight>
8 bits only? That's so 80's!
Line 13,656:
Let's go 32 bits...
<
; IN : a = n (n <= 47, otherwise overflows)
; OUT: hlh'l' = FIB(n)
Line 13,689:
exx ; now in reg set
ret</
=={{header|zkl}}==
A slight tweak to the task; creates a function that continuously generates fib numbers
<
<pre>
zkl: do(15){ fibShift().print(",") }
Line 13,704:
=={{header|ZX Spectrum Basic}}==
====Iterative====
<
20 LET n=10
30 LET n1=0: LET n2=1
Line 13,712:
70 LET n2=sum
80 NEXT k
90 PRINT n1</
====Analytic====
<
[[Category:Arithmetic]]
|