Fibonacci sequence

From Rosetta Code
Task
Fibonacci sequence
You are encouraged to solve this task according to the task description, using any language you may know.
The Fibonacci sequence is a sequence   Fn   of natural numbers defined recursively:
 F0 = 0                                           
 F1 = 1                                           
 Fn = Fn-1 + Fn-2, if n>1   

Write a function to generate the   nth   Fibonacci number.

Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).

The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:

 Fn = Fn+2 - Fn+1, if n<0   

support for negative     n     in the solution is optional.


Cf.


References



Contents

0815[edit]

 
%<:0D:>~$<:01:~%>=<:a94fad42221f2702:>~>
}:_s:{x{={~$x+%{=>~>x~-x<:0D:~>~>~^:_s:?
 

360 Assembly[edit]

For maximum compatibility, this program uses only the basic instruction set.

 
FIBONACC CSECT
USING FIBONACC,R12
SAVEAREA B STM-SAVEAREA(R15)
DC 17F'0'
DC CL8'FIBONACC'
STM STM R14,R12,12(R13)
ST R13,4(R15)
ST R15,8(R13)
LR R12,R15
* ---- CODE
LA R1,0 f1=0
LA R2,1 f2=1
LA R4,1 i=1
LA R6,1
LH R7,N
LOOP BXH R4,R6,ENDLOOP for i=2 to n
LR R3,R2
AR R3,R1 f3=f1+f2
CVD R4,P i
UNPK Z,P
MVC C,Z
OI C+L'C-1,X'F0'
MVC WTOBUF+5(5),C+11
CVD R3,P f3
UNPK Z,P
MVC C,Z
OI C+L'C-1,X'F0'
MVC WTOBUF+12(10),C+6
WTO MF=(E,WTOMSG)
LR R1,R2 f1=f2
LR R2,R3 f2=f3
B LOOP next i
ENDLOOP EQU *
* ---- END CODE
RETURN EQU *
LM R14,R12,12(R13)
XR R15,R15
BR R14
* ---- DATA
N DC H'46' max i
P DS PL8
Z DS ZL16
C DS CL16
WTOMSG DS 0F
DC H'80'
DC H'0'
WTOBUF DC CL80'fibo(12345)=1234567890 '
YREGS
END FIBONACC
 
Output:
...
fibo(00043)=0433494437
fibo(00044)=0701408733
fibo(00045)=1134903170
fibo(00046)=1836311903

6502 Assembly[edit]

This subroutine stores the first n—by default the first ten—Fibonacci numbers in memory, beginning (because, why not?) at address 3867 decimal = F1B hex. Intermediate results are stored in three sequential addresses within the low 256 bytes of memory, which are the most economical to access.

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.

       LDA  #0
STA $F0  ; LOWER NUMBER
LDA #1
STA $F1  ; HIGHER NUMBER
LDX #0
LOOP: LDA $F1
STA $0F1B,X
STA $F2  ; OLD HIGHER NUMBER
ADC $F0
STA $F1  ; NEW HIGHER NUMBER
LDA $F2
STA $F0  ; NEW LOWER NUMBER
INX
CPX #$0A  ; STOP AT FIB(10)
BMI LOOP
RTS  ; RETURN FROM SUBROUTINE

ACL2[edit]

Fast, tail recursive solution:

(defun fast-fib-r (n a b)
(if (or (zp n) (zp (1- n)))
b
(fast-fib-r (1- n) b (+ a b))))
 
(defun fast-fib (n)
(fast-fib-r n 1 1))
 
(defun first-fibs-r (n i)
(declare (xargs :measure (nfix (- n i))))
(if (zp (- n i))
nil
(cons (fast-fib i)
(first-fibs-r n (1+ i)))))
 
(defun first-fibs (n)
(first-fibs-r n 0))
Output:
>(first-fibs 20)
(1 1 2 3 5 8 13 21 34 55 89
   144 233 377 610 987 1597 2584 4181 6765)

ActionScript[edit]

public function fib(n:uint):uint
{
if (n < 2)
return n;
 
return fib(n - 1) + fib(n - 2);
}

Ada[edit]

Recursive[edit]

with Ada.Text_IO, Ada.Command_Line;
 
procedure Fib is
 
X: Positive := Positive'Value(Ada.Command_Line.Argument(1));
 
function Fib(P: Positive) return Positive is
begin
if P <= 2 then
return 1;
else
return Fib(P-1) + Fib(P-2);
end if;
end Fib;
 
begin
Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
Ada.Text_IO.Put_Line(Integer'Image(Fib(X)));
end Fib;

Iterative, build-in integers[edit]

with Ada.Text_IO;  use Ada.Text_IO;
 
procedure Test_Fibonacci is
function Fibonacci (N : Natural) return Natural is
This : Natural := 0;
That : Natural := 1;
Sum  : Natural;
begin
for I in 1..N loop
Sum  := This + That;
That := This;
This := Sum;
end loop;
return This;
end Fibonacci;
begin
for N in 0..10 loop
Put_Line (Positive'Image (Fibonacci (N)));
end loop;
end Test_Fibonacci;
Output:
 0
 1
 1
 2
 3
 5
 8
 13
 21
 34
 55

Iterative, long integers[edit]

Using the big integer implementation from a cryptographic library [1].

with Ada.Text_IO, Ada.Command_Line, Crypto.Types.Big_Numbers;
 
procedure Fibonacci is
 
X: Positive := Positive'Value(Ada.Command_Line.Argument(1));
 
Bit_Length: Positive := 1 + (696 * X) / 1000;
-- that number of bits is sufficient to store the full result.
 
package LN is new Crypto.Types.Big_Numbers
(Bit_Length + (32 - Bit_Length mod 32));
-- the actual number of bits has to be a multiple of 32
use LN;
 
function Fib(P: Positive) return Big_Unsigned is
Previous: Big_Unsigned := Big_Unsigned_Zero;
Result: Big_Unsigned := Big_Unsigned_One;
Tmp: Big_Unsigned;
begin
-- Result = 1 = Fibonacci(1)
for I in 1 .. P-1 loop
Tmp := Result;
Result := Previous + Result;
Previous := Tmp;
-- Result = Fibonacci(I+1))
end loop;
return Result;
end Fib;
 
begin
Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
Ada.Text_IO.Put_Line(LN.Utils.To_String(Fib(X)));
end Fibonacci;
Output:
> ./fibonacci 777
Fibonacci( 777 ) = 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082


AdvPL[edit]

Recursive[edit]

 
#include "totvs.ch"
User Function fibb(a,b,n)
return(if(--n>0,fibb(b,a+b,n),a))
 

Iterative[edit]

 
#include "totvs.ch"
User Function fibb(n)
local fnow:=0, fnext:=1, tempf
while (--n>0)
tempf:=fnow+fnext
fnow:=fnext
fnext:=tempf
end while
return(fnext)
 

Aime[edit]

integer
fibs(integer n)
{
integer w;
 
if (n == 0) {
w = 0;
} elif (n == 1) {
w = 1;
} else {
integer a, b, i;
 
i = 1;
a = 0;
b = 1;
while (i < n) {
w = a + b;
a = b;
b = w;
i += 1;
}
}
 
return w;
}
 

ALGOL 68[edit]

Analytic[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC analytic fibonacci = (LONG INT n)LONG INT:(
LONG REAL sqrt 5 = long sqrt(5);
LONG REAL p = (1 + sqrt 5) / 2;
LONG REAL q = 1/p;
ROUND( (p**n + q**n) / sqrt 5 )
);
 
FOR i FROM 1 TO 30 WHILE
print(whole(analytic fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)
Output:
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

Iterative[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC iterative fibonacci = (INT n)INT: 
CASE n+1 IN
0, 1, 1, 2, 3, 5
OUT
INT even:=3, odd:=5;
FOR i FROM odd+1 TO n DO
(ODD i|odd|even) := odd + even
OD;
(ODD n|odd|even)
ESAC;
 
FOR i FROM 0 TO 30 WHILE
print(whole(iterative fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)
Output:
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

Recursive[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC recursive fibonacci = (INT n)INT:
( n < 2 | n | fib(n-1) + fib(n-2));

Generative[edit]

Translation of: Python
- note: This specimen retains the original Python coding style.
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
MODE YIELDINT = PROC(INT)VOID;
 
PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (
INT even:=0, odd:=1;
yield(even);
yield(odd);
FOR i FROM odd+1 TO n DO
yield( (ODD i|odd|even) := odd + even )
OD
);
 
main:(
# FOR INT n IN # gen fibonacci(30, # ) DO ( #
## (INT n)VOID:(
print((" ",whole(n,0)))
# OD # ));
print(new line)
)
Output:
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

Array (Table) Lookup[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

This uses a pre-generated list, requiring much less run-time processor usage, but assumes that INT is only 31 bits wide.

[]INT const fibonacci = []INT( -1836311903, 1134903170,
-701408733, 433494437, -267914296, 165580141, -102334155,
63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
3524578, -2178309, 1346269, -832040, 514229, -317811, 196418,
-121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181,
-2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13,
-8, 5, -3, 2, -1, 1, 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,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
701408733, 1134903170, 1836311903
)[@-46];
 
PROC VOID value error := stop;
 
PROC lookup fibonacci = (INT i)INT: (
IF LWB const fibonacci <= i AND i<= UPB const fibonacci THEN
const fibonacci[i]
ELSE
value error; SKIP
FI
);
 
FOR i FROM 0 TO 30 WHILE
print(whole(lookup fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)
Output:
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

Alore[edit]

def fib(n as Int) as Int
if n < 2
return 1
end
return fib(n-1) + fib(n-2)
end

Apex[edit]

 
/*
author: snugsfbay
date: March 3, 2016
description: Create a list of x numbers in the Fibonacci sequence.
- user may specify the length of the list
- enforces a minimum of 2 numbers in the sequence because any fewer is not a sequence
- enforces a maximum of 47 because further values are too large for integer data type
- Fibonacci sequence always starts with 0 and 1 by definition
*/
public class FibNumbers{
 
final static Integer MIN = 2; //minimum length of sequence
final static Integer MAX = 47; //maximum length of sequence
 
/*
description: method to create a list of numbers in the Fibonacci sequence
param: user specified integer representing length of sequence should be 2-47, inclusive.
- Sequence starts with 0 and 1 by definition so the minimum length could be as low as 2.
- For 48th number in sequence or greater, code would require a Long data type rather than an Integer.
return: list of integers in sequence.
*/
public static List<Integer> makeSeq(Integer len){
 
List<Integer> fib = new List<Integer>{0,1}; // initialize list with first two values
Integer i;
 
if(len<MIN || len==null || len>MAX) {
if (len>MAX){
len=MAX; //set length to maximum if user entered too high a value
}else{
len=MIN; //set length to minimum if user entered too low a value or none
}
} //This could be refactored using teneray operator, but we want code coverage to be reflected for each condition
 
//start with initial list size to find previous two values in the sequence, continue incrementing until list reaches user defined length
for(i=fib.size(); i<len; i++){
fib.add(fib[i-1]+fib[i-2]); //create new number based on previous numbers and add that to the list
}
 
return fib;
}
 
}
 

APL[edit]

Since APL is an array language we'll use the following identity:

In APL:

 
↑+.×/N/⊂2 2⍴1 1 1 0
 

Plugging in 4 for N gives the following result:

Here's what happens: We replicate the 2-by-2 matrix N times and then apply inner product-replication. The First removes the shell from the Enclose. At this point we're basically done, but we need to pick out only in order to complete the task. Here's one way:

 
↑0 1↓↑+.×/N/⊂2 2⍴1 1 1 0
 

Analytic[edit]

An alternative approach, using Binet's formula (which was apparently known long before Binet):

⌊.5+(((1+PHI)÷2)*⍳N)÷PHI←5*.5

AppleScript[edit]

set fibs to {}
set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3"))
set x to x as integer
repeat with y from 1 to x
if (y = 1 or y = 2) then
copy 1 to the end of fibs
else
copy ((item (y - 1) of fibs) + (item (y - 2) of fibs)) to the end of fibs
end if
end repeat
return item x of fibs


The simple recursive version is famously slow:

on fib(n)
if n < 1 then
0
else if n < 3 then
1
else
fib(n - 2) + fib(n - 1)
end if
end fib

but with range() and map(), for example, we can use a list to memoize the series:

on run {}
fib(32)
end run
 
on fib(n)
item -1 of map(range(0, n), my fibs)
end fib
 
on fibs(_, i, lst)
if i < 2 then
set item i of lst to 0
else if i < 4 then
set item i of lst to 1
else
set item i of lst to ((item (i - 2) of lst) + (item (i - 1) of lst))
end if
end fibs
 
 
-- GENERIC LIBRARY FUNCTIONS
 
-- m..n
on range(m, n)
set lng to (n - m) + 1
set base to m - 1
set lst to {}
repeat with i from 1 to lng
set end of lst to i + base
end repeat
return lst
end range
 
-- [a] -> (a -> b) -> [b]
on map(xs, f)
set mf to mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to mf's lambda(item i of xs, i, xs)
end repeat
return lst
end map
 
-- Script | Handler -> Script
on mReturn(f)
script
property lambda : f
end script
end mReturn
 
Output:
2178309

Arendelle[edit]

( fibonacci , 1; 1 )

[ 98 , // 100 numbers of fibonacci

	( fibonacci[ @fibonacci? ] ,

		@fibonacci[ @fibonacci - 1 ] + @fibonacci[ @fibonacci - 2 ]

	)

	"Index: | @fibonacci? | => | @fibonacci[ @fibonacci? - 1 ] |"
]


ATS[edit]

Recursive[edit]

 
fun fib_rec(n: int): int =
if n >= 2 then fib_rec(n-1) + fib_rec(n-2) else n
 

Iterative[edit]

 
(*
** This one is also referred to as being tail-recursive
*)
fun
fib_trec(n: int): int =
if
n > 0
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
 

Iterative and Verified[edit]

 
(*
** This implementation is verified!
*)
 
dataprop FIB (int, int) =
| FIB0 (0, 0) | FIB1 (1, 1)
| {n:nat} {r0,r1:int} FIB2 (n+2, r0+r1) of (FIB (n, r0), FIB (n+1, r1))
// end of [FIB] // end of [dataprop]
 
fun
fibats{n:nat}
(n: int (n))
: [r:int] (FIB (n, r) | int r) = let
fun loop
{i:nat | i <= n}{r0,r1:int}
(
pf0: FIB (i, r0), pf1: FIB (i+1, r1)
| ni: int (n-i), r0: int r0, r1: int r1
) : [r:int] (FIB (n, r) | int r) =
if (ni > 0)
then loop{i+1}(pf1, FIB2 (pf0, pf1) | ni - 1, r1, r0 + r1)
else (pf0 | r0)
// end of [if]
// end of [loop]
in
loop {0} (FIB0 (), FIB1 () | n, 0, 1)
end // end of [fibats]
 

Matrix-based[edit]

 
(* ****** ****** *)
//
// How to compile:
// patscc -o fib fib.dats
//
(* ****** ****** *)
//
#include
"share/atspre_staload.hats"
//
(* ****** ****** *)
//
[email protected]
int3_t0ype =
(int, int, int)
//
typedef int3 = int3_t0ype
//
(* ****** ****** *)
 
extern
fun int3 : (int, int, int) -<> int3
extern
fun int3_1 : int3 -<> int
extern
fun mul_int3_int3: (int3, int3) -<> int3
 
(* ****** ****** *)
 
local
 
assume
int3_t0ype = (int, int, int)
 
in (* in-of-local *)
//
implement
int3 (x, y, z) = @(x, y, z)
//
implement int3_1 (xyz) = xyz.1
//
implement
mul_int3_int3
(
@(a,b,c), @(d,e,f)
) =
(a*d + b*e, a*e + b*f, b*e + c*f)
//
end // end of [local]
 
(* ****** ****** *)
//
implement
gnumber_int<int3> (n) = int3(n, 0, n)
//
implement gmul_val<int3> = mul_int3_int3
//
(* ****** ****** *)
//
fun
fib (n: intGte(0)): int =
int3_1(gpow_int_val<int3> (n, int3(1, 1, 0)))
//
(* ****** ****** *)
 
implement
main0 () =
{
//
val N = 10
val () = println! ("fib(", N, ") = ", fib(N))
val N = 20
val () = println! ("fib(", N, ") = ", fib(N))
val N = 30
val () = println! ("fib(", N, ") = ", fib(N))
val N = 40
val () = println! ("fib(", N, ") = ", fib(N))
//
} (* end of [main0] *)
 

AutoHotkey[edit]

Search autohotkey.com: sequence

Iterative[edit]

Translation of: C
Loop, 5
MsgBox % fib(A_Index)
Return
 
fib(n)
{
If (n < 2)
Return n
i := last := this := 1
While (i <= n)
{
new := last + this
last := this
this := new
i++
}
Return this
}

Recursive and iterative[edit]

Source: AutoHotkey forum by Laszlo

/*
Important note: the recursive version would be very slow
without a global or static array. The iterative version
handles also negative arguments properly.
*/

 
FibR(n) { ; n-th Fibonacci number (n>=0, recursive with static array Fibo)
Static
Return n<2 ? n : Fibo%n% ? Fibo%n% : Fibo%n% := FibR(n-1)+FibR(n-2)
}
 
Fib(n) { ; n-th Fibonacci number (n < 0 OK, iterative)
a := 0, b := 1
Loop % abs(n)-1
c := b, b += a, a := c
Return n=0 ? 0 : n>0 || n&1 ? b : -b
}

AutoIt[edit]

Iterative[edit]

#AutoIt Version: 3.2.10.0
$n0 = 0
$n1 = 1
$n = 10
MsgBox (0,"Iterative Fibonacci ", it_febo($n0,$n1,$n))
 
Func it_febo($n_0,$n_1,$N)
$first = $n_0
$second = $n_1
$next = $first + $second
$febo = 0
For $i = 1 To $N-3
$first = $second
$second = $next
$next = $first + $second
Next
if $n==0 Then
$febo = 0
ElseIf $n==1 Then
$febo = $n_0
ElseIf $n==2 Then
$febo = $n_1
Else
$febo = $next
EndIf
Return $febo
EndFunc
 

Recursive[edit]

#AutoIt Version: 3.2.10.0
$n0 = 0
$n1 = 1
$n = 10
MsgBox (0,"Recursive Fibonacci ", rec_febo($n0,$n1,$n))
Func rec_febo($r_0,$r_1,$R)
if $R<3 Then
if $R==2 Then
Return $r_1
ElseIf $R==1 Then
Return $r_0
ElseIf $R==0 Then
Return 0
EndIf
Return $R
Else
Return rec_febo($r_0,$r_1,$R-1) + rec_febo($r_0,$r_1,$R-2)
EndIf
EndFunc
 

AWK[edit]

As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout.

$ awk 'func fib(n){return(n<2?n:fib(n-1)+fib(n-2))}{print "fib("$1")="fib($1)}'
10
fib(10)=55

Axe[edit]

A recursive solution is not practical in Axe because there is no concept of variable scope in Axe.

Iterative solution:

Lbl FIB
r₁→N
0→I
1→J
For(K,1,N)
I+J→T
J→I
T→J
End
J
Return


bash[edit]

Recursive[edit]

fib()
{
if [ $1 -le 0 ]
then
echo 0
return 0
fi
if [ $1 -le 2 ]
then
echo 1
else
a=$(fib $[$1-1])
b=$(fib $[$1-2])
echo $(($a+$b))
fi
}
 

Babel[edit]

In Babel, we can define fib using a stack-based approach that is not recursive:

fib { <- 0 1 { dup <- + -> swap } -> times zap } <

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:

1, 1, 1 (dup)  
1, 1, (<-)  
2 (+)  
2, 1 (->)  
1, 2 (swap)  

And so on. To test fib:

{19 iter - fib !} 20 times collect ! lsnum !
Output:
( 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 )

BASIC[edit]

Works with: QBasic
Works with: FreeBASIC

Iterative[edit]

FUNCTION itFib (n)
n1 = 0
n2 = 1
FOR k = 1 TO ABS(n)
sum = n1 + n2
n1 = n2
n2 = sum
NEXT k
IF n < 0 THEN
itFib = n1 * ((-1) ^ ((-n) + 1))
ELSE
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 REDIM PRESERVE, it requires QuickBASIC 4.5 or newer):

DECLARE FUNCTION fibonacci& (n AS INTEGER)
 
REDIM SHARED fibNum(1) AS LONG
 
fibNum(1) = 1
 
'*****sample inputs*****
PRINT fibonacci(0) 'no calculation needed
PRINT fibonacci(13) 'figure F(2)..F(13)
PRINT fibonacci(-42) 'figure F(14)..F(42)
PRINT fibonacci(47) 'error: too big
'*****sample inputs*****
 
FUNCTION fibonacci& (n AS INTEGER)
DIM a AS INTEGER
a = ABS(n)
SELECT CASE a
CASE 0 TO 46
SHARED fibNum() AS LONG
DIM u AS INTEGER, L0 AS INTEGER
u = UBOUND(fibNum)
IF a > u THEN
REDIM PRESERVE fibNum(a) AS LONG
FOR L0 = u + 1 TO a
fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
NEXT
END IF
IF n < 0 THEN
fibonacci = fibNum(a) * ((-1) ^ (a + 1))
ELSE
fibonacci = fibNum(n)
END IF
CASE ELSE
'limited to signed 32-bit int (LONG)
'F(47)=&hB11924E1
ERROR 6 'overflow
END SELECT
END FUNCTION
Output:
(unhandled error in final input prevents output):
 0
 233
-267914296

Recursive[edit]

This example can't handle n < 0.

FUNCTION recFib (n)
IF (n < 2) THEN
recFib = n
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF
END FUNCTION

Array (Table) Lookup[edit]

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 -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155
DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309
DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711
DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3
DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765
DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269
DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986
DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903
 
DIM fibNum(-46 TO 46) AS LONG
 
FOR n = -46 TO 46
READ fibNum(n)
NEXT
 
'*****sample inputs*****
FOR n = -46 TO 46
PRINT fibNum(n),
NEXT
PRINT
'*****sample inputs*****

Batch File[edit]

Recursive version

::fibo.cmd
@echo off
if "%1" equ "" goto :eof
call :fib %1
echo %errorlevel%
goto :eof
 
:fib
setlocal enabledelayedexpansion
if %1 geq 2 goto :ge2
exit /b %1
 
:ge2
set /a r1 = %1 - 1
set /a r2 = %1 - 2
call :fib !r1!
set r1=%errorlevel%
call :fib !r2!
set r2=%errorlevel%
set /a r0 = r1 + r2
exit /b !r0!
Output:
>for /L %i in (1,5,20) do fibo.cmd %i

>fibo.cmd 1
1

>fibo.cmd 6
8

>fibo.cmd 11
89

>fibo.cmd 16
987


Battlestar[edit]

 
// Fibonacci sequence, recursive version
fun fibb
loop
a = funparam[0]
break (a < 2)
 
a--
 
// Save "a" while calling fibb
a -> stack
 
// Set the parameter and call fibb
funparam[0] = a
call fibb
 
// Handle the return value and restore "a"
b = funparam[0]
stack -> a
 
// Save "b" while calling fibb again
b -> stack
 
a--
 
// Set the parameter and call fibb
funparam[0] = a
call fibb
 
// Handle the return value and restore "b"
c = funparam[0]
stack -> b
 
// Sum the results
b += c
a = b
 
funparam[0] = a
 
break
end
end
 
// vim: set syntax=c ts=4 sw=4 et:
 

BBC BASIC[edit]

      PRINT FNfibonacci_r(1),  FNfibonacci_i(1)
PRINT FNfibonacci_r(13), FNfibonacci_i(13)
PRINT FNfibonacci_r(26), FNfibonacci_i(26)
END
 
DEF FNfibonacci_r(N)
IF N < 2 THEN = N
= FNfibonacci_r(N-1) + FNfibonacci_r(N-2)
 
DEF FNfibonacci_i(N)
LOCAL F, I, P, T
IF N < 2 THEN = N
P = 1
FOR I = 1 TO N
T = F
F += P
P = T
NEXT
= F
 
Output:
         1         1
       233       233
    121393    121393

bc[edit]

iterative[edit]

#! /usr/bin/bc -q
 
define fib(x) {
if (x <= 0) return 0;
if (x == 1) return 1;
 
a = 0;
b = 1;
for (i = 1; i < x; i++) {
c = a+b; a = b; b = c;
}
return c;
}
fib(1000)
quit


beeswax[edit]

                        #>'#{;
_`Enter n: `TN`Fib(`{`)=`X~P~K#{;
#>~P~L#MM@>+@'q@{;
[email protected]<

Example output:

Notice the UInt64 wrap-around at Fib(94)!

julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i0
 
Fib(0)=0
Program finished!
 
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i10
 
Fib(10)=55
Program finished!
 
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i92
 
Fib(92)=7540113804746346429
Program finished!
 
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i93
 
Fib(93)=12200160415121876738
Program finished!
 
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i94
 
Fib(94)=1293530146158671551
Program finished!

Befunge[edit]

00:.1:.>:"@"8**++\1+:67+`#@_v
^ .:\/*8"@"\%*8"@":\ <

Brainf***[edit]

Works with: Brainf*** version 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.

+++++ +++++	#0 set to n
>> + Init #2 to 1
<<
[
- #Decrement counter in #0
>>. Notice: This doesn't print it in ascii
To look at results you can pipe into a file and look with a hex editor
 
Copying sequence to save #2 in #4 using #5 as restore space
>>[-] Move to #4 and clear
>[-] Clear #5
<<< #2
[ Move loop
- >> + > + <<< Subtract #2 and add #4 and #5
]
>>>
[ Restore loop
- <<< + >>> Subtract from #5 and add to #2
]
 
<<<< Back to #1
Non destructive add sequence using #3 as restore value
[ Loop to add
- > + > + << Subtract #1 and add to value #2 and restore space #3
]
>>
[ Loop to restore #1 from #3
- << + >> Subtract from restore space #3 and add in #1
]
 
<< [-] Clear #1
>>>
[ Loop to move #4 to #1
- <<< + >>> Subtract from #4 and add to #1
]
<<<< Back to #0
]

Bracmat[edit]

Recursive[edit]

fib=.!arg:<2|fib$(!arg+-2)+fib$(!arg+-1)
 fib$30
 832040

Iterative[edit]

(fib=
last i this new
.  !arg:<2
| 0:?last:?i
& 1:?this
& whl
' ( !i+1:<!arg:?i
& !last+!this:?new
& !this:?last
& !new:?this
)
& !this
)
 fib$777
 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082

Brat[edit]

Recursive[edit]

fibonacci = { x |
true? x < 2, x, { fibonacci(x - 1) + fibonacci(x - 2) }
}

Tail Recursive[edit]

fib_aux = { x, next, result |
true? x == 0,
result,
{ fib_aux x - 1, next + result, next }
}
 
fibonacci = { x |
fib_aux x, 1, 0
}

Memoization[edit]

cache = hash.new
 
fibonacci = { x |
true? cache.key?(x)
{ cache[x] }
{true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}
}

Burlesque[edit]

 
{0 1}{^^++[+[-^^-]\/}30.*\[e!vv
 
 
0 1{{.+}c!}{1000.<}w!
 

C[edit]

Recursive[edit]

long long fibb(long long a, long long b, int n) {
return (--n>0)?(fibb(b, a+b, n)):(a);
}

Iterative[edit]

long long int fibb(int n) {
int fnow = 0, fnext = 1, tempf;
while(--n>0){
tempf = fnow + fnext;
fnow = fnext;
fnext = tempf;
}
return fnext;
}

Analytic[edit]

#include <tgmath.h>
#define PHI ((1 + sqrt(5))/2)
 
long long unsigned fib(unsigned n) {
return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );
}

Generative[edit]

Translation of: Python
Works with: gcc version version 4.1.2 20080704 (Red Hat 4.1.2-44)
#include <stdio.h>
typedef enum{false=0, true=!0} bool;
typedef void iterator;
 
#include <setjmp.h>
/* declare label otherwise it is not visible in sub-scope */
#define LABEL(label) jmp_buf label; if(setjmp(label))goto label;
#define GOTO(label) longjmp(label, true)
 
/* the following line is the only time I have ever required "auto" */
#define FOR(i, iterator) { auto bool lambda(i); yield_init = (void *)&lambda; iterator; bool lambda(i)
#define DO {
#define YIELD(x) if(!yield(x))return
#define BREAK return false
#define CONTINUE return true
#define OD CONTINUE; } }
 
static volatile void *yield_init; /* not thread safe */
#define YIELDS(type) bool (*yield)(type) = yield_init
 
iterator fibonacci(int stop){
YIELDS(int);
int f[] = {0, 1};
int i;
for(i=0; i<stop; i++){
YIELD(f[i%2]);
f[i%2]=f[0]+f[1];
}
}
 
main(){
printf("fibonacci: ");
FOR(int i, fibonacci(16)) DO
printf("%d, ",i);
OD;
printf("...\n");
}
Output:
fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Fast method for a single large value[edit]

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
 
typedef struct node node;
struct node {
int n;
mpz_t v;
node *next;
};
 
#define CSIZE 37
node *cache[CSIZE];
 
// very primitive linked hash table
node * find_cache(int n)
{
int idx = n % CSIZE;
node *p;
 
for (p = cache[idx]; p && p->n != n; p = p->next);
if (p) return p;
 
p = malloc(sizeof(node));
p->next = cache[idx];
cache[idx] = p;
 
if (n < 2) {
p->n = n;
mpz_init_set_ui(p->v, 1);
} else {
p->n = -1; // -1: value not computed yet
mpz_init(p->v);
}
return p;
}
 
mpz_t tmp1, tmp2;
mpz_t *fib(int n)
{
int x;
node *p = find_cache(n);
 
if (p->n < 0) {
p->n = n;
x = n / 2;
 
mpz_mul(tmp1, *fib(x-1), *fib(n - x - 1));
mpz_mul(tmp2, *fib(x), *fib(n - x));
mpz_add(p->v, tmp1, tmp2);
}
return &p->v;
}
 
int main(int argc, char **argv)
{
int i, n;
if (argc < 2) return 1;
 
mpz_init(tmp1);
mpz_init(tmp2);
 
for (i = 1; i < argc; i++) {
n = atoi(argv[i]);
if (n < 0) {
printf("bad input: %s\n", argv[i]);
continue;
}
 
// about 75% of time is spent in printing
gmp_printf("%Zd\n", *fib(n));
}
return 0;
}
Output:
% ./a.out 0 1 2 3 4 5
1
1
2
3
5
8
% ./a.out 10000000 | wc -c    # count length of output, including the newline
1919488

C++[edit]

Using unsigned int, this version only works up to 48 before fib overflows.

#include <iostream>
 
int main()
{
unsigned int a = 1, b = 1;
unsigned int target = 48;
for(unsigned int n = 3; n <= target; ++n)
{
unsigned int fib = a + b;
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
 
return 0;
}


Library: GMP

This version does not have an upper bound.

#include <iostream>
#include <gmpxx.h>
 
int main()
{
mpz_class a = mpz_class(1), b = mpz_class(1);
mpz_class target = mpz_class(100);
for(mpz_class n = mpz_class(3); n <= target; ++n)
{
mpz_class fib = b + a;
if ( fib < b )
{
std::cout << "Overflow at " << n << std::endl;
break;
}
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
return 0;
}

Version using transform:

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
 
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0;
std::vector<int> v(n+1);
v[1] = 1;
transform(v.begin(), v.end()-2, v.begin()+1, v.begin()+2, std::plus<int>());
// "v" now contains the Fibonacci sequence from 0 up
return v[n];
}

Far-fetched version using adjacent_difference:

#include <numeric>
#include <vector>
#include <functional>
#include <iostream>
 
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0;
std::vector<int> v(n, 1);
adjacent_difference(v.begin(), v.end()-1, v.begin()+1, std::plus<int>());
// "array" now contains the Fibonacci sequence from 1 up
return v[n-1];
}
 

Version which computes at compile time with metaprogramming:

#include <iostream>
 
template <int n> struct fibo
{
enum {value=fibo<n-1>::value+fibo<n-2>::value};
};
 
template <> struct fibo<0>
{
enum {value=0};
};
 
template <> struct fibo<1>
{
enum {value=1};
};
 
 
int main(int argc, char const *argv[])
{
std::cout<<fibo<12>::value<<std::endl;
std::cout<<fibo<46>::value<<std::endl;
return 0;
}

The following version is based on fast exponentiation:

#include <iostream>
 
inline void fibmul(int* f, int* g)
{
int tmp = f[0]*g[0] + f[1]*g[1];
f[1] = f[0]*g[1] + f[1]*(g[0] + g[1]);
f[0] = tmp;
}
 
int fibonacci(int n)
{
int f[] = { 1, 0 };
int g[] = { 0, 1 };
while (n > 0)
{
if (n & 1) // n odd
{
fibmul(f, g);
--n;
}
else
{
fibmul(g, g);
n >>= 1;
}
}
return f[1];
}
 
int main()
{
for (int i = 0; i < 20; ++i)
std::cout << fibonacci(i) << " ";
std::cout << std::endl;
}
Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Using Zeckendorf Numbers[edit]

The nth fibonacci is represented as Zeckendorf 1 followed by n-1 zeroes. 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
int main(void) {
char NG[22] = {'1',0};
int x = -1;
N G;
for (int fibs = 1; fibs <= 20; fibs++) {
for (;G <= N(NG); ++G) x++;
NG[fibs] = '0';
NG[fibs+1] = 0;
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
 
Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946

Using Standard Template Library[edit]

Possibly less "Far-fetched version".

 
// Use Standard Template Library to display Fibonacci sequence.
// Nigel Galloway March 30th., 2013
#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
int x = 1, y = 1;
generate_n(std::ostream_iterator<int>(std::cout, " "), 21, [&]{int n=x; x=y; y+=n; return n;});
return 0;
}
 
Output:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946

C#[edit]

Recursive[edit]

 
public static ulong Fib(uint n) {
return (n < 2)? n : Fib(n - 1) + Fib(n - 2);
}
 

Tail-Recursive[edit]

 
public static ulong Fib(uint n) {
return Fib(0, 1, n);
}
 
private static ulong Fib(ulong a, ulong b, uint n) {
return (n < 1)? a :(n == 1)? b : Fib(b, a + b, n - 1);
}
 

Iterative[edit]

 
public static ulong Fib(uint x) {
if (x == 0) return 0;
 
ulong prev = 0;
ulong next = 1;
for (int i = 1; i < x; i++)
{
ulong sum = prev + next;
prev = next;
next = sum;
}
return next;
}
 

Eager-Generative[edit]

 
public static IEnumerable<long> Fibs(uint x) {
IList<ulong> fibs = new List<ulong>();
 
ulong prev = -1;
ulong next = 1;
for (int i = 0; i < x; i++)
{
long sum = prev + next;
prev = next;
next = sum;
fibs.Add(sum);
}
return fibs;
}
 

Lazy-Generative[edit]

 
public static IEnumerable<ulong> Fibs(uint x) {
ulong prev = -1;
ulong next = 1;
for (uint i = 0; i < x; i++) {
ulong sum = prev + next;
prev = next;
next = sum;
yield return sum;
}
}
 

Analytic[edit]

Only works to the 92th fibonacci number.

 
private static double Phi = ((1d + Math.Sqrt(5d))/2d);
private static double D = 1d/Math.Sqrt(5d);
 
ulong Fib(uint n) {
if(n > 92) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 93.");
return (ulong)((Phi^n) - (1d - Phi)^n))*D);
}
 

Matrix[edit]

Algorithm is based on

.

Needs System.Windows.Media.Matrix or similar Matrix class. Calculates in .

 
public static ulong Fib(uint n) {
var M = new Matrix(1,0,0,1);
var N = new Matrix(1,1,1,0);
for (uint i = 1; i < n; i++) M *= N;
return (ulong)M[0][0];
}
 

Needs System.Windows.Media.Matrix or similar Matrix class. Calculates in .

 
private static Matrix M;
private static readonly Matrix N = new Matrix(1,1,1,0);
 
public static ulong Fib(uint n) {
M = new Matrix(1,0,0,1);
MatrixPow(n-1);
return (ulong)M[0][0];
}
 
private static void MatrixPow(double n){
if (n > 1) {
MatrixPow(n/2);
M *= M;
}
if (n % 2 == 0) M *= N;
}
 

Array (Table) Lookup[edit]

 
private static int[] fibs = new int[]{ -1836311903, 1134903170,
-701408733, 433494437, -267914296, 165580141, -102334155,
63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
3524578, -2178309, 1346269, -832040, 514229, -317811, 196418,
-121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181,
-2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13,
-8, 5, -3, 2, -1, 1, 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,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
701408733, 1134903170, 1836311903};
 
public static int Fib(int n) {
if(n < -46 || n > 46) throw new ArgumentOutOfRangeException("n", n, "Has to be between -46 and 47.")
return fibs[n+46];
}
 

Cat[edit]

define fib {
dup 1 <=
[]
[dup 1 - fib swap 2 - fib +]
if
}

Chapel[edit]

iter fib() {
var a = 0, b = 1;
 
while true {
yield a;
(a, b) = (b, b + a);
}
}

Chef[edit]

Stir-Fried Fibonacci Sequence.
 
An unobfuscated iterative implementation.
It prints the first N + 1 Fibonacci numbers,
where N is taken from standard input.
 
Ingredients.
0 g last
1 g this
0 g new
0 g input
 
Method.
Take input from refrigerator.
Put this into 4th mixing bowl.
Loop the input.
Clean the 3rd mixing bowl.
Put last into 3rd mixing bowl.
Add this into 3rd mixing bowl.
Fold new into 3rd mixing bowl.
Clean the 1st mixing bowl.
Put this into 1st mixing bowl.
Fold last into 1st mixing bowl.
Clean the 2nd mixing bowl.
Put new into 2nd mixing bowl.
Fold this into 2nd mixing bowl.
Put new into 4th mixing bowl.
Endloop input until looped.
Pour contents of the 4th mixing bowl into baking dish.
 
Serves 1.

CMake[edit]

Iteration uses a while() loop. Memoization uses global properties.

set_property(GLOBAL PROPERTY fibonacci_0 0)
set_property(GLOBAL PROPERTY fibonacci_1 1)
set_property(GLOBAL PROPERTY fibonacci_next 2)
 
# var = nth number in Fibonacci sequence.
function(fibonacci var n)
# If the sequence is too short, compute more Fibonacci numbers.
get_property(next GLOBAL PROPERTY fibonacci_next)
if(NOT next GREATER ${n})
# a, b = last 2 Fibonacci numbers
math(EXPR i "${next} - 2")
get_property(a GLOBAL PROPERTY fibonacci_${i})
math(EXPR i "${next} - 1")
get_property(b GLOBAL PROPERTY fibonacci_${i})
 
while(NOT next GREATER ${n})
math(EXPR i "${a} + ${b}") # i = next Fibonacci number
set_property(GLOBAL PROPERTY fibonacci_${next} ${i})
set(a ${b})
set(b ${i})
math(EXPR next "${next} + 1")
endwhile()
set_property(GLOBAL PROPERTY fibonacci_next ${next})
endif()
 
get_property(answer GLOBAL PROPERTY fibonacci_${n})
set(${var} ${answer} PARENT_SCOPE)
endfunction(fibonacci)
# Test program: print 0th to 9th and 25th to 30th Fibonacci numbers.
set(s "")
foreach(i RANGE 0 9)
fibonacci(f ${i})
set(s "${s} ${f}")
endforeach(i)
set(s "${s} ... ")
foreach(i RANGE 25 30)
fibonacci(f ${i})
set(s "${s} ${f}")
endforeach(i)
message(${s})
 0 1 1 2 3 5 8 13 21 34 ... 75025 121393 196418 317811 514229 832040

Clojure[edit]

Lazy Sequence[edit]

This is implemented idiomatically as an infinitely long, lazy sequence of all Fibonacci numbers:

(defn fibs []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

Thus to get the nth one:

(nth (fibs) 5)

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.

(defn fibs []
(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:

(def fib (lazy-cat [0 1] (map + fib (rest fib))))

Then, to see the first ten,

user> (take 10 fib)
(0 1 1 2 3 5 8 13 21 34)

Iterative[edit]

Here's a simple interative process (using a recursive function) that carries state along with it (as args) until it reaches a solution:

;; max is which fib number you'd like computed (0th, 1st, 2nd, etc.)
;; 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)
;; i is the nth - 1 fib number
(defn- fib-iter
[max n i j]
(if (= n max)
j
(recur max
(inc n)
j
(+ i j))))
 
(defn fib
[max]
(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.

Recursive[edit]

A naive slow recursive solution:

(defn fib [n]
(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.

(def fib
(memoize
(fn [n]
(case n
0 0
1 1
(+ (fib (- n 1))
(fib (- n 2)))))))

Using core.async[edit]

(ns fib.core)
(require '[clojure.core.async
 :refer [<! >! >!! <!! timeout chan alt! go]])
 
(defn fib [c]
(loop [a 0 b 1]
(>!! c a)
(recur b (+ a b))))
 
 
(defn -main []
(let [c (chan)]
(go (fib c))
(dorun
(for [i (range 10)]
(println (<!! c))))))
 

COBOL[edit]

Iterative[edit]

Program-ID. Fibonacci-Sequence.
Data Division.
Working-Storage Section.
01 FIBONACCI-PROCESSING.
05 FIBONACCI-NUMBER PIC 9(36) VALUE 0.
05 FIB-ONE PIC 9(36) VALUE 0.
05 FIB-TWO PIC 9(36) VALUE 1.
01 DESIRED-COUNT PIC 9(4).
01 FORMATTING.
05 INTERM-RESULT PIC Z(35)9.
05 FORMATTED-RESULT PIC X(36).
05 FORMATTED-SPACE PIC x(35).
Procedure Division.
000-START-PROGRAM.
Display "What place of the Fibonacci Sequence would you like (<173)? " with no advancing.
Accept DESIRED-COUNT.
If DESIRED-COUNT is less than 1
Stop run.
If DESIRED-COUNT is less than 2
Move FIBONACCI-NUMBER to INTERM-RESULT
Move INTERM-RESULT to FORMATTED-RESULT
Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT
Display FORMATTED-RESULT
Stop run.
Subtract 1 from DESIRED-COUNT.
Move FIBONACCI-NUMBER to INTERM-RESULT.
Move INTERM-RESULT to FORMATTED-RESULT.
Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT.
Display FORMATTED-RESULT.
Perform 100-COMPUTE-FIBONACCI until DESIRED-COUNT = zero.
Stop run.
100-COMPUTE-FIBONACCI.
Compute FIBONACCI-NUMBER = FIB-ONE + FIB-TWO.
Move FIB-TWO to FIB-ONE.
Move FIBONACCI-NUMBER to FIB-TWO.
Subtract 1 from DESIRED-COUNT.
Move FIBONACCI-NUMBER to INTERM-RESULT.
Move INTERM-RESULT to FORMATTED-RESULT.
Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT.
Display FORMATTED-RESULT.

Recursive[edit]

Works with: GNU Cobol version 2.0
       >>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci-main.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 num PIC 9(6) COMP.
01 fib-num PIC 9(6) COMP.
 
PROCEDURE DIVISION.
ACCEPT num
CALL "fibonacci" USING CONTENT num RETURNING fib-num
DISPLAY fib-num
.
END PROGRAM fibonacci-main.
 
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci RECURSIVE.
 
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 1-before PIC 9(6) COMP.
01 2-before PIC 9(6) COMP.
 
LINKAGE SECTION.
01 num PIC 9(6) COMP.
 
01 fib-num PIC 9(6) COMP BASED.
 
PROCEDURE DIVISION USING num RETURNING fib-num.
ALLOCATE fib-num
EVALUATE num
WHEN 0
MOVE 0 TO fib-num
WHEN 1
MOVE 1 TO fib-num
WHEN OTHER
SUBTRACT 1 FROM num
CALL "fibonacci" USING CONTENT num RETURNING 1-before
SUBTRACT 1 FROM num
CALL "fibonacci" USING CONTENT num RETURNING 2-before
ADD 1-before TO 2-before GIVING fib-num
END-EVALUATE
.
END PROGRAM fibonacci.

CoffeeScript[edit]

Analytic[edit]

fib_ana = (n) ->
sqrt = Math.sqrt
phi = ((1 + sqrt(5))/2)
return Math.round((Math.pow(phi, n)/sqrt(5)))

Iterative[edit]

fib_iter = (n) ->
return n if n < 2
[prev, curr] = [0, 1]
[prev, curr] = [curr, curr + prev] for i in [1..n]
curr

Recursive[edit]

fib_rec = (n) ->
if n < 2 then n else fib_rec(n-1) + fib_rec(n-2)

Common Lisp[edit]

Note that Common Lisp uses bignums, so this will never overflow.

Iterative[edit]

(defun fibonacci-iterative (n &aux (f0 0) (f1 1))
(case n
(0 f0)
(1 f1)
(t (loop for n from 2 to n
for a = f0 then b and b = f1 then result
for result = (+ a b)
finally (return result)))))

Simpler one:

(defun fibonacci (n)
(let ((a 0) (b 1) (c n))
(loop for i from 2 to n do
(setq c (+ a b)
a b
b c))
c))
Not a function, just printing out the entire (for some definition of "entire") sequence with a for var = loop:
(loop for x = 0 then y and y = 1 then (+ x y) do (print x))

Recursive[edit]

(defun fibonacci-recursive (n)
(if (< n 2)
n
(+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))


(defun fibonacci-tail-recursive ( n &optional (a 0) (b 1))
(if (= n 0)
a
(fibonacci-tail-recursive (- n 1) b (+ a b))))

Tail recursive and squaring:

(defun fib (n &optional (a 1) (b 0) (p 0) (q 1))
(if (= n 1) (+ (* b p) (* a q))
(fib (ash n -1)
(if (evenp n) a (+ (* b q) (* a (+ p q))))
(if (evenp n) b (+ (* b p) (* a q)))
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))))) ;p is Fib(2^n-1), q is Fib(2^n).
 
(print (fib 100000))

D[edit]

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.

import std.stdio, std.conv, std.algorithm, std.math;
 
long sgn(alias unsignedFib)(int n) { // break sign manipulation apart
immutable uint m = (n >= 0) ? n : -n;
if (n < 0 && (n % 2 == 0))
return -unsignedFib(m);
else
return unsignedFib(m);
}
 
long fibD(uint m) { // Direct Calculation, correct for abs(m) <= 84
enum sqrt5r = 1.0L / sqrt(5.0L); // 1 / sqrt(5)
enum golden = (1.0L + sqrt(5.0L)) / 2.0L; // (1 + sqrt(5)) / 2
return roundTo!long(pow(golden, m) * sqrt5r);
}
 
long fibI(in uint m) pure nothrow { // Iterative
long thisFib = 0;
long nextFib = 1;
foreach (i; 0 .. m) {
long tmp = nextFib;
nextFib += thisFib;
thisFib = tmp;
}
return thisFib;
}
 
long fibR(uint m) { // Recursive
return (m < 2) ? m : fibR(m - 1) + fibR(m - 2);
}
 
long fibM(uint m) { // memoized Recursive
static long[] fib = [0, 1];
while (m >= fib.length )
fib ~= fibM(m - 2) + fibM(m - 1);
return fib[m];
}
 
alias sgn!fibD sfibD;
alias sgn!fibI sfibI;
alias sgn!fibR sfibR;
alias sgn!fibM sfibM;
 
auto fibG(in int m) { // generator(?)
immutable int sign = (m < 0) ? -1 : 1;
long yield;
 
return new class {
final int opApply(int delegate(ref int, ref long) dg) {
int idx = -sign; // prepare for pre-increment
foreach (f; this)
if (dg(idx += sign, f))
break;
return 0;
}
 
final int opApply(int delegate(ref long) dg) {
long f0, f1 = 1;
foreach (p; 0 .. m * sign + 1) {
if (sign == -1 && (p % 2 == 0))
yield = -f0;
else
yield = f0;
if (dg(yield)) break;
auto temp = f1;
f1 = f0 + f1;
f0 = temp;
}
return 0;
}
};
}
 
void main(in string[] args) {
int k = args.length > 1 ? to!int(args[1]) : 10;
writefln("Fib(%3d) = ", k);
writefln("D : %20d <- %20d + %20d",
sfibD(k), sfibD(k - 1), sfibD(k - 2));
writefln("I : %20d <- %20d + %20d",
sfibI(k), sfibI(k - 1), sfibI(k - 2));
if (abs(k) < 36 || args.length > 2)
// set a limit for recursive version
writefln("R : %20d <- %20d + %20d",
sfibR(k), sfibM(k - 1), sfibM(k - 2));
writefln("O : %20d <- %20d + %20d",
sfibM(k), sfibM(k - 1), sfibM(k - 2));
foreach (i, f; fibG(-9))
writef("%d:%d | ", i, f);
}
Output:
for n = 85:
Fib( 85) = 
D :   259695496911122586 <-   160500643816367088 +    99194853094755497
I :   259695496911122585 <-   160500643816367088 +    99194853094755497
O :   259695496911122585 <-   160500643816367088 +    99194853094755497
0:0 | -1:1 | -2:-1 | -3:2 | -4:-3 | -5:5 | -6:-8 | -7:13 | -8:-21 | -9:34 | 

Matrix Exponentiation Version[edit]

import std.bigint;
 
T fibonacciMatrix(T=BigInt)(size_t n) {
int[size_t.sizeof * 8] binDigits;
size_t nBinDigits;
while (n > 0) {
binDigits[nBinDigits] = n % 2;
n /= 2;
nBinDigits++;
}
 
T x=1, y, z=1;
foreach_reverse (b; binDigits[0 .. nBinDigits]) {
if (b) {
x = (x + z) * y;
y = y ^^ 2 + z ^^ 2;
} else {
auto x_old = x;
x = x ^^ 2 + y ^^ 2;
y = (x_old + z) * y;
}
z = x + y;
}
 
return y;
}
 
void main() {
10_000_000.fibonacciMatrix;
}

Faster Version[edit]

For N = 10_000_000 this is about twice faster (run-time about 2.20 seconds) than the matrix exponentiation version.

import std.bigint, std.math;
 
// Algorithm from: Takahashi, Daisuke,
// "A fast algorithm for computing large Fibonacci numbers".
// Information Processing Letters 75.6 (30 November 2000): 243-246.
// Implementation from:
// pythonista.wordpress.com/2008/07/03/pure-python-fibonacci-numbers
BigInt fibonacci(in ulong n)
in {
assert(n > 0, "fibonacci(n): n must be > 0.");
} body {
if (n <= 2)
return 1.BigInt;
BigInt F = 1;
BigInt L = 1;
int sign = -1;
immutable uint n2 = cast(uint)n.log2.floor;
auto mask = 2.BigInt ^^ (n2 - 1);
foreach (immutable i; 1 .. n2) {
auto temp = F ^^ 2;
F = (F + L) / 2;
F = 2 * F ^^ 2 - 3 * temp - 2 * sign;
L = 5 * temp + 2 * sign;
sign = 1;
if (n & mask) {
temp = F;
F = (F + L) / 2;
L = F + 2 * temp;
sign = -1;
}
mask /= 2;
}
if ((n & mask) == 0) {
F *= L;
} else {
F = (F + L) / 2;
F = F * L - sign;
}
return F;
}
 
void main() {
10_000_000.fibonacci;
}

Dart[edit]

int fib(int n) {
if (n==0 || n==1) {
return n;
}
var prev=1;
var current=1;
for (var i=2; i<n; i++) {
var next = prev + current;
prev = current;
current = next;
}
return current;
}
 
int fibRec(int n) => n==0 || n==1 ? n : fibRec(n-1) + fibRec(n-2);
 
main() {
print(fib(11));
print(fibRec(11));
}

Delphi[edit]

Iterative[edit]

 
function FibonacciI(N: Word): UInt64;
var
Last, New: UInt64;
I: Word;
begin
if N < 2 then
Result := N
else begin
Last := 0;
Result := 1;
for I := 2 to N do
begin
New := Last + Result;
Last := Result;
Result := New;
end;
end;
end;
 

Recursive[edit]

 
function Fibonacci(N: Word): UInt64;
begin
if N < 2 then
Result := N
else
Result := Fibonacci(N - 1) + Fibonacci(N - 2);
end;
 

Matrix[edit]

Algorithm is based on

.
 
function fib(n: Int64): Int64;
 
type TFibMat = array[0..1] of array[0..1] of Int64;
 
function FibMatMul(a,b: TFibMat): TFibMat;
var i,j,k: integer;
tmp: TFibMat;
begin
for i := 0 to 1 do
for j := 0 to 1 do
begin
tmp[i,j] := 0;
for k := 0 to 1 do tmp[i,j] := tmp[i,j] + a[i,k] * b[k,j];
end;
FibMatMul := tmp;
end;
 
function FibMatExp(a: TFibMat; n: Int64): TFibmat;
begin
if n <= 1 then fibmatexp := a
else if (n mod 2 = 0) then FibMatExp := FibMatExp(FibMatMul(a,a), n div 2)
else if (n mod 2 = 1) then FibMatExp := FibMatMul(a, FibMatExp(FibMatMul(a,a), n div 2));
end;
 
var
matrix: TFibMat;
 
begin
matrix[0,0] := 1;
matrix[0,1] := 1;
matrix[1,0] := 1;
matrix[1,1] := 0;
if n > 1 then
matrix := fibmatexp(matrix,n-1);
fib := matrix[0,0];
end;
 

DWScript[edit]

function fib(N : Integer) : Integer;
begin
if N < 2 then Result := 1
else Result := fib(N-2) + fib(N-1);
End;

E[edit]

def fib(n) {
var s := [0, 1]
for _ in 0..!n {
def [a, b] := s
s := [b, a+b]
}
return s[0]
}

(This version defines fib(0) = 0 because OEIS A000045 does.)

EchoLisp[edit]

Use memoization with the recursive version.

 
(define (fib n)
(if (< n 2) n
(+ (fib (- n 2)) (fib (1- n)))))
 
(remember 'fib #(0 1))
 
(for ((i 12)) (write (fib i)))
0 1 1 2 3 5 8 13 21 34 55 89
 

ECL[edit]

Analytic[edit]

//Calculates Fibonacci sequence up to n steps using Binet's closed form solution
 
 
FibFunction(UNSIGNED2 n) := FUNCTION
REAL Sqrt5 := Sqrt(5);
REAL Phi := (1+Sqrt(5))/2;
REAL Phi_Inv := 1/Phi;
UNSIGNED FibValue := ROUND( ( POWER(Phi,n)-POWER(Phi_Inv,n) ) /Sqrt5);
RETURN FibValue;
END;
 
FibSeries(UNSIGNED2 n) := FUNCTION
 
Fib_Layout := RECORD
UNSIGNED5 FibNum;
UNSIGNED5 FibValue;
END;
 
FibSeq := DATASET(n+1,
TRANSFORM
( Fib_Layout
, SELF.FibNum := COUNTER-1
, SELF.FibValue := IF(SELF.FibNum<2,SELF.FibNum, FibFunction(SELF.FibNum) )
)
);
 
RETURN FibSeq;
 
END; }

Eiffel[edit]

 
class
APPLICATION
 
create
make
 
feature
 
fibonacci (n: INTEGER): INTEGER
require
non_negative: n >= 0
local
i, n2, n1, tmp: INTEGER
do
n2 := 0
n1 := 1
from
i := 1
until
i >= n
loop
tmp := n1
n1 := n2 + n1
n2 := tmp
i := i + 1
end
Result := n1
if n = 0 then
Result := 0
end
end
 
feature {NONE} -- Initialization
 
make
-- Run application.
do
print (fibonacci (0))
print (" ")
print (fibonacci (1))
print (" ")
print (fibonacci (2))
print (" ")
print (fibonacci (3))
print (" ")
print (fibonacci (4))
print ("%N")
end
 
end
 

Ela[edit]

Tail-recursive function:

fib = fib' 0 1           
where fib' a b 0 = a
fib' a b n = fib' b (a + b) (n - 1)

Infinite (lazy) list:

fib = fib' 1 1
where fib' x y = & x :: fib' y (x + y)

Elixir[edit]

defmodule Fibonacci do
def fib(0), do: 0
def fib(1), do: 1
def fib(n), do: fib(0, 1, n-2)
 
def fib(_, prv, -1), do: prv
def fib(prvprv, prv, n) do
next = prv + prvprv
fib(prv, next, n-1)
end
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)
 
Output:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Emacs Lisp[edit]

version 1[edit]

 
(defun fib (n a b c)
(if (< c n) (fib n b (+ a b) (+ 1 c) )
(if (= c n) b a) ))
 
(defun fibonacci (n) (if (< n 2) n (fib n 0 1 1) ))
 

version 2[edit]

 
(defun fibonacci (n)
(let ( (vec) (i) (j) (k) )
(if (< n 2) n
(progn
(setq vec (make-vector (+ n 1) 0) i 0 j 1 k 2)
(setf (aref vec 1) 1)
(while (<= k n)
(setf (aref vec k) (+ (elt vec i) (elt vec j) ))
(setq i (+ 1 i) j (+ 1 j) k (+ 1 k) ))
(elt vec n) ))))
 

Eval:

 
(insert
(mapconcat '(lambda (n) (format "%d" (fibonacci n) ))
(number-sequence 0 15) " ") )
 

Output:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Erlang[edit]

Recursive[edit]

 
-module(fib).
-export([fib/1).
 
fib(0) -> 1;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
 

Iterative[edit]

 
-module(fiblin).
-export([fib/1])
 
fib(0) -> 0;
fib(1) -> 1;
fib(2) -> 1;
fib(3) -> 2;
fib(4) -> 3;
fib(5) -> 5;
 
fib(N) when is_integer(N) -> fib(N - 6, 5, 8).
fib(N, A, B) -> if N < 1 -> B; true -> fib(N-1, B, A+B) end.
 
 

Evaluate:

 
io:write([fiblin:fib(X) || X <- lists:seq(1,10) ]).
 

Output:

   
[1,1,2,3,5,8,13,21,34,55]ok

ERRE[edit]

!-------------------------------------------
! derived from my book "PROGRAMMARE IN ERRE"
! iterative solution
!-------------------------------------------
 
PROGRAM FIBONACCI
 
!$DOUBLE
 
!VAR F1#,F2#,TEMP#,COUNT%,N%
 
BEGIN  !main
INPUT("Number",N%)
F1=0
F2=1
REPEAT
TEMP=F2
F2=F1+F2
F1=TEMP
COUNT%=COUNT%+1
UNTIL COUNT%=N%
PRINT("FIB(";N%;")=";F2)
 
 ! Obviously a FOR loop or a WHILE loop can
 ! be used to solve this problem
 
END PROGRAM
 
Output:
Number? 20
FIB( 20 )= 6765

Euphoria[edit]

'Recursive' version[edit]

Works with: Euphoria version any version
 
function fibor(integer n)
if n<2 then return n end if
return fibor(n-1)+fibor(n-2)
end function
 

'Iterative' version[edit]

Works with: Euphoria version any version
 
function fiboi(integer n)
integer f0=0, f1=1, f
if n<2 then return n end if
for i=2 to n do
f=f0+f1
f0=f1
f1=f
end for
return f
end function
 

'Tail recursive' version[edit]

Works with: Euphoria version 4.0.0
 
function fibot(integer n, integer u = 1, integer s = 0)
if n < 1 then
return s
else
return fibot(n-1,u+s,u)
end if
end function
 
-- example:
? fibot(10) -- says 55
 

'Paper tape' version[edit]

Works with: Euphoria version 4.0.0
 
include std/mathcons.e -- for PINF constant
 
enum ADD, MOVE, GOTO, OUT, TEST, TRUETO
 
global sequence tape = { 0,
1,
{ ADD, 2, 1 },
{ TEST, 1, PINF },
{ TRUETO, 0 },
{ OUT, 1, "%.0f\n" },
{ MOVE, 2, 1 },
{ MOVE, 0, 2 },
{ GOTO, 3 } }
 
global integer ip
global integer test
global atom accum
 
procedure eval( sequence cmd )
atom i = 1
while i <= length( cmd ) do
switch cmd[ i ] do
case ADD then
accum = tape[ cmd[ i + 1 ] ] + tape[ cmd[ i + 2 ] ]
i += 2
 
case OUT then
printf( 1, cmd[ i + 2], tape[ cmd[ i + 1 ] ] )
i += 2
 
case MOVE then
if cmd[ i + 1 ] = 0 then
tape[ cmd[ i + 2 ] ] = accum
else
tape[ cmd[ i + 2 ] ] = tape[ cmd[ i + 1 ] ]
end if
i += 2
 
case GOTO then
ip = cmd[ i + 1 ] - 1 -- due to ip += 1 in main loop
i += 1
 
case TEST then
if tape[ cmd[ i + 1 ] ] = cmd[ i + 2 ] then
test = 1
else
test = 0
end if
i += 2
 
case TRUETO then
if test then
if cmd[ i + 1 ] = 0 then
abort(0)
else
ip = cmd[ i + 1 ] - 1
end if
end if
 
end switch
i += 1
end while
end procedure
 
test = 0
accum = 0
ip = 1
 
while 1 do
 
-- embedded sequences (assumed to be code) are evaluated
-- atoms (assumed to be data) are ignored
 
if sequence( tape[ ip ] ) then
eval( tape[ ip ] )
end if
ip += 1
end while
 
 

FALSE[edit]

[[$0=~][1-@@\$@@+\$44,.@]#]f:
20n: {First 20 numbers}
0 1 n;f;!%%44,. {Output: "0,1,1,2,3,5..."}

Factor[edit]

Iterative[edit]

: fib ( n -- m )
dup 2 < [
[ 0 1 ] dip [ swap [ + ] keep ] times
drop
] unless ;

Recursive[edit]

: fib ( n -- m )
dup 2 < [
[ 1 - fib ] [ 2 - fib ] bi +
] unless ;

Tail-Recursive[edit]

: fib2 ( x y n -- a )
dup 1 <
[ 2drop ]
[ [ swap [ + ] keep ] dip 1 - fib2 ]
if ;
: fib ( n -- m ) [ 0 1 ] dip fib2 ;

Matrix[edit]

Translation of: Ruby
USE: math.matrices
 
: fib ( n -- m )
dup 2 < [
[ { { 0 1 } { 1 1 } } ] dip 1 - m^n
second second
] unless ;

Fancy[edit]

class Fixnum {
def fib {
match self -> {
case 0 -> 0
case 1 -> 1
case _ -> self - 1 fib + (self - 2 fib)
}
}
}
 
15 times: |x| {
x fib println
}
 

Falcon[edit]

Iterative[edit]

function fib_i(n)
 
if n < 2: return n
 
fibPrev = 1
fib = 1
for i in [2:n]
tmp = fib
fib += fibPrev
fibPrev = tmp
end
return fib
end

Recursive[edit]

function fib_r(n)
if n < 2 : return n
return fib_r(n-1) + fib_r(n-2)
end

Tail Recursive[edit]

function fib_tr(n)
return fib_aux(n,0,1)
end
function fib_aux(n,a,b)
switch n
case 0 : return a
default: return fib_aux(n-1,a+b,a)
end
end

Fantom[edit]

Ints have a limit of 64-bits, so overflow errors occur after computing Fib(92) = 7540113804746346429.

 
class Main
{
static Int fib (Int n)
{
if (n < 2) return n
fibNums := [1, 0]
while (fibNums.size <= n)
{
fibNums.insert (0, fibNums[0] + fibNums[1])
}
return fibNums.first
}
 
public static Void main ()
{
20.times |n|
{
echo ("Fib($n) is ${fib(n)}")
}
}
}
 


Fexl[edit]

 
# (fib n) = the nth Fibonacci number
\fib=
(
\loop==
(\x\y\n
le n 0 x;
\z=(+ x y)
\n=(- n 1)
loop y z n
)
loop 0 1
)
 
 
# Now test it:
for 0 20 (\n say (fib n))
 
Output:
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765

Forth[edit]

: fib ( n -- fib )
0 1 rot 0 ?do over + swap loop drop ;

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-start,  here 1 0 dup , ;
: F-next, over + swap
dup 0> IF dup , true ELSE false THEN ;
 
: computed-table ( compile: 'start 'next / run: i -- x )
create
>r execute
BEGIN r@ execute not UNTIL rdrop
does>
swap cells + @ ;
 
' F-start, ' F-next, computed-table fibonacci 2drop
here swap - cell/ Constant #F/64 \ # of fibonacci numbers generated
 
16 fibonacci . 987 ok
#F/64 . 93 ok
92 fibonacci . 7540113804746346429 ok \ largest number generated.

Fortran[edit]

FORTRAN 77[edit]

 
FUNCTION IFIB(N)
IF (N.EQ.0) THEN
ITEMP0=0
ELSE IF (N.EQ.1) THEN
ITEMP0=1
ELSE IF (N.GT.1) THEN
ITEMP1=0
ITEMP0=1
DO 1 I=2,N
ITEMP2=ITEMP1
ITEMP1=ITEMP0
ITEMP0=ITEMP1+ITEMP2
1 CONTINUE
ELSE
ITEMP1=1
ITEMP0=0
DO 2 I=-1,N,-1
ITEMP2=ITEMP1
ITEMP1=ITEMP0
ITEMP0=ITEMP2-ITEMP1
2 CONTINUE
END IF
IFIB=ITEMP0
END
 

Test program

 
EXTERNAL IFIB
CHARACTER*10 LINE
PARAMETER ( LINE = '----------' )
WRITE(*,900) 'N', 'F[N]', 'F[-N]'
WRITE(*,900) LINE, LINE, LINE
DO 1 N = 0, 10
WRITE(*,901) N, IFIB(N), IFIB(-N)
1 CONTINUE
900 FORMAT(3(X,A10))
901 FORMAT(3(X,I10))
END
 
Output:
          N       F[N]      F[-N]
 ---------- ---------- ----------
          0          0          0
          1          1          1
          2          1         -1
          3          2          2
          4          3         -3
          5          5          5
          6          8         -8
          7         13         13
          8         21        -21
          9         34         34
         10         55        -55

Recursive[edit]

In ISO Fortran 90 or later, use a RECURSIVE function:

module fibonacci
contains
recursive function fibR(n) result(fib)
integer, intent(in) :: n
integer :: fib
 
select case (n)
case (:0); fib = 0
case (1); fib = 1
case default; fib = fibR(n-1) + fibR(n-2)
end select
end function fibR

Iterative[edit]

In ISO Fortran 90 or later:

    function fibI(n)
integer, intent(in) :: n
integer, parameter :: fib0 = 0, fib1 = 1
integer :: fibI, back1, back2, i
 
select case (n)
case (:0); fibI = fib0
case (1); fibI = fib1
 
case default
fibI = fib1
back1 = fib0
do i = 2, n
back2 = back1
back1 = fibI
fibI = back1 + back2
end do
end select
end function fibI
end module fibonacci

Test program

program fibTest
use fibonacci
 
do i = 0, 10
print *, fibr(i), fibi(i)
end do
end program fibTest
Output:
0 0
1 1
1 1
2 2
3 3
5 5
8 8
13 13
21 21
34 34
55 55

FreeBASIC[edit]

Extended sequence coded big integer.

'Fibonacci extended
'Freebasic version 24 Windows
Dim Shared ADDQmod(0 To 19) As Ubyte
Dim Shared ADDbool(0 To 19) As Ubyte
For z As Integer=0 To 19
ADDQmod(z)=(z Mod 10+48)
ADDbool(z)=(-(10<=z))
Next z
Function plusINT(NUM1 As String,NUM2 As String) As String
Dim As Byte flag
#macro finish()
three=Ltrim(three,"0")
If three="" Then Return "0"
If flag=1 Then Swap NUM2,NUM1
Return three
Exit Function
#endmacro
var lenf=Len(NUM1)
var lens=Len(NUM2)
If lens>lenf Then
Swap NUM2,NUM1
Swap lens,lenf
flag=1
End If
 
var diff=lenf-lens-Sgn(lenf-lens)
var three="0"+NUM1
var two=String(lenf-lens,"0")+NUM2
Dim As Integer n2
Dim As Ubyte addup,addcarry
 
addcarry=0
 
For n2=lenf-1 To diff Step -1
addup=two[n2]+NUM1[n2]-96
three[n2+1]=addQmod(addup+addcarry)
addcarry=addbool(addup+addcarry)
Next n2
If addcarry=0 Then
finish()
End If
If n2=-1 Then
three[0]=addcarry+48
finish()
End If
 
For n2=n2 To 0 Step -1
addup=two[n2]+NUM1[n2]-96
three[n2+1]=addQmod(addup+addcarry)
addcarry=addbool(addup+addcarry)
Next n2
three[0]=addcarry+48
finish()
End Function
 
 
 
Function fibonacci(n As Integer) As String
Dim As String sl,l,term
sl="0": l="1"
If n=1 Then Return "0"
If n=2 Then Return "1"
n=n-2
For x As Integer= 1 To n
term=plusINT(l,sl)
sl=l
l=term
Next x
Function =term
End Function
 
'============== EXAMPLE ===============
print "THE SEQUENCE TO 10:"
print
For n As Integer=1 To 10
Print "term";n;": "; fibonacci(n)
Next n
print
print "Selected Fibonacci number"
print "Fibonacci 500"
print
print fibonacci(500)
Sleep
 
Output:
THE SEQUENCE TO 10:

term 1: 0
term 2: 1
term 3: 1
term 4: 2
term 5: 3
term 6: 5
term 7: 8
term 8: 13
term 9: 21
term 10: 34

Selected Fibonacci number
Fibonacci 500

86168291600238450732788312165664788095941068326060883324529903470149056115823592
713458328176574447204501


Frink[edit]

All of Frink's integers can be arbitrarily large.

 
fibonacciN[n] :=
{
a = 0
b = 1
count = 0
while count < n
{
[a,b] = [b, a + b]
count = count + 1
}
return a
}
 

F#[edit]

This is a fast [tail-recursive] approach using the F# big integer support:

 
let fibonacci n : bigint =
let rec f a b n =
match n with
| 0 -> a
| 1 -> b
| n -> (f b (a + b) (n - 1))
f (bigint 0) (bigint 1) n
> fibonacci 100;;
val it : bigint = 354224848179261915075I

Lazy evaluated using sequence workflow:

let rec fib = seq { yield! [0;1];
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:

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 10000
 

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
open System.Numerics
 
/// Finds the highest power of two which is less than or equal to a given input.
let inline prevPowTwo (x : int) =
let mutable n = x
n <- n - 1
n <- n ||| (n >>> 1)
n <- n ||| (n >>> 2)
n <- n ||| (n >>> 4)
n <- n ||| (n >>> 8)
n <- n ||| (n >>> 16)
n <- n + 1
match x with
| x when x = n -> x
| _ -> n/2
 
/// Evaluates the nth Fibonacci number using matrix arithmetic and
/// exponentiation by squaring.
let crazyFib (n : int) =
let powTwo = prevPowTwo n
 
/// Applies 2n rule repeatedly until another application of the rule would
/// go over the target value (or the target value has been reached).
let rec iter1 i q r s =
match i with
| i when i < powTwo ->
iter1 (i*2) (q*q + r*r) (r * (q+s)) (r*r + s*s)
| _ -> i, q, r, s
 
/// Applies n+1 rule until the target value is reached.
let rec iter2 (i, q, r, s) =
match i with
| i when i < n ->
iter2 ((i+1), (q+r), q, r)
| _ -> q
 
match n with
| 0 -> 1I
| _ ->
iter1 1 1I 1I 0I
|> iter2
 

FunL[edit]

Recursive[edit]

def
fib( 0 ) = 0
fib( 1 ) = 1
fib( n ) = fib( n - 1 ) + fib( n - 2 )

Tail Recursive[edit]

def fib( n ) =
def
_fib( 0, prev, _ ) = prev
_fib( 1, _, next ) = next
_fib( n, prev, next ) = _fib( n - 1, next, next + prev )
 
_fib( n, 0, 1 )

Lazy List[edit]

val fib =
def _fib( a, b ) = a # _fib( b, a + b )
 
_fib( 0, 1 )
 
println( fib(10000) )
Output:
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

Iterative[edit]

def fib( n ) =
a, b = 0, 1
 
for i <- 1..n
a, b = b, a+b
 
a

Binet's Formula[edit]

import math.sqrt
 
def fib( n ) =
phi = (1 + sqrt( 5 ))/2
int( (phi^n - (-phi)^-n)/sqrt(5) + .5 )

Matrix Exponentiation[edit]

def mul( a, b ) =
res = array( a.length(), b(0).length() )
 
for i <- 0:a.length(), j <- 0:b(0).length()
res( i, j ) = sum( a(i, k)*b(k, j) | k <- 0:b.length() )
 
vector( res )
 
def
pow( _, 0 ) = ((1, 0), (0, 1))
pow( x, 1 ) = x
pow( x, n )
| 2|n = pow( mul(x, x), n\2 )
| otherwise = mul(x, pow( mul(x, x), (n - 1)\2 ) )
 
def fib( n ) = pow( ((0, 1), (1, 1)), n )(0, 1)
 
for i <- 0..10
println( fib(i) )
Output:
0
1
1
2
3
5
8
13
21
34
55

GAP[edit]

fib := function(n)
local a;
a := [[0, 1], [1, 1]]^n;
return a[1][2];
end;

GAP has also a buit-in function for that.

Fibonacci(n);

Gecho[edit]

0 1 dup wover + dup wover + dup wover + dup wover +

Prints the first several fibonacci numbers...

GFA Basic[edit]

 
'
' Compute nth Fibonacci number
'
' open a window for display
OPENW 1
CLEARW 1
' Display some fibonacci numbers
' Fib(46) is the largest number GFA Basic can reach
' (long integers are 4 bytes)
FOR i%=0 TO 46
PRINT "fib(";i%;")=";@fib(i%)
NEXT i%
' wait for a key press and tidy up
~INP(2)
CLOSEW 1
'
' Function to compute nth fibonacci number
' n must be in range 0 to 46, inclusive
'
FUNCTION fib(n%)
LOCAL n0%,n1%,nn%,i%
n0%=0
n1%=1
SELECT n%
CASE 0
RETURN n0%
CASE 1
RETURN n1%
DEFAULT
FOR i%=2 TO n%
nn%=n0%+n1%
n0%=n1%
n1%=nn%
NEXT i%
RETURN nn%
ENDSELECT
ENDFUNC
 

GML[edit]

///fibonacci(n)
//Returns the nth fibonacci number
 
var n, numb;
n = argument0;
 
if (n == 0)
{
numb = 0;
}
else
{
var fm2, fm1;
fm2 = 0;
fm1 = 1;
numb = 1;
repeat(n-1)
{
numb = fm2+fm1;
fm2 = fm1;
fm1 = numb;
}
}
 
return numb;

Go[edit]

Recursive[edit]

func fib(a int) int {
if a < 2 {
return a
}
return fib(a - 1) + fib(a - 2)
}

Iterative[edit]

import (
"math/big"
)
 
func fib(n uint64) *big.Int {
if n < 2 {
return big.NewInt(int64(n))
}
a, b := big.NewInt(0), big.NewInt(1)
for n--; n > 0; n-- {
a.Add(a, b)
a, b = b, a
}
return b
}

Iterative using a closure[edit]

func fibNumber() func() int {
fib1, fib2 := 0, 1
return func() int {
fib1, fib2 = fib2, fib1 + fib2
return fib1
}
}
 
func fibSequence(n int) int {
f := fibNumber()
fib := 0
for i := 0; i < n; i++ {
fib = f()
}
return fib
}

Using a goroutine and channel[edit]

func fib(c chan int) {
a, b := 0, 1
for {
c <- a
a, b = b, a+b
}
}
 
func main() {
c := make(chan int)
go fib(c)
for i := 0; i < 10; i++ {
fmt.println(<-c)
}
}
 

Groovy[edit]

Recursive[edit]

A recursive closure must be pre-declared.

def rFib
rFib = { it < 1 ? 0 : it == 1 ? 1 : rFib(it-1) + rFib(it-2) }

Iterative[edit]

def iFib = { it < 1 ? 0 : it == 1 ? 1 : (2..it).inject([0,1]){i, j -> [i[1], i[0]+i[1]]}[1] }

Test program:

(0..20).each { println "${it}:    ${rFib(it)}    ${iFib(it)}" }
Output:
0:    0    0
1:    1    1
2:    1    1
3:    2    2
4:    3    3
5:    5    5
6:    8    8
7:    13    13
8:    21    21
9:    34    34
10:    55    55
11:    89    89
12:    144    144
13:    233    233
14:    377    377
15:    610    610
16:    987    987
17:    1597    1597
18:    2584    2584
19:    4181    4181
20:    6765    6765

Harbour[edit]

Recursive[edit]

 
#include "harbour.ch"
Function fibb(a,b,n)
return(if(--n>0,fibb(b,a+b,n),a))
 

Iterative[edit]

 
#include "harbour.ch"
Function fibb(n)
local fnow:=0, fnext:=1, tempf
while (--n>0)
tempf:=fnow+fnext
fnow:=fnext
fnext:=tempf
end while
return(fnext)
 

Haskell[edit]

Analytic[edit]

[floor(0.01+(1/p**n+p**n)/sqrt 5)|let p=(1+sqrt 5)/2, n<-[0..42]]

Recursive[edit]

Simple definition, very inefficient.

fib x = if x < 1 then 0 else if x < 2 then 1 else fib(x - 1) + fib(x - 2)

Recursive with Memoization[edit]

Very fast.

fib x = if x < 1 then 0 
else if x==1 then 1
else fibs!!(x - 1) + fibs!!(x - 2)
where
fibs = map fib [0..]

Iterative[edit]

fib n = go n 0 1
where
go n a b | n==0 = a
| otherwise = go (n-1) b (a+b)

With lazy lists[edit]

This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:

fib = 0 : 1 : zipWith (+) fib (tail fib)

Or alternatively:

 fib = 0 : 1 : (zipWith (+) <*> tail) fib 

The nth Fibonacci number is then just fib !! n. The above is equivalent to

fib = 0 : 1 : next fib where next (a: t@(b:_)) = (a+b) : next t

Also

fib = 0 : scanl (+) 1 fib

With matrix exponentiation[edit]

With the (rather slow) code from Matrix exponentiation operator

import Data.List
 
xs <+> ys = zipWith (+) xs ys
xs <*> ys = sum $ zipWith (*) xs ys
 
newtype Mat a = Mat {unMat :: [[a]]} deriving Eq
 
instance Show a => Show (Mat a) where
show xm = "Mat " ++ show (unMat xm)
 
instance Num a => Num (Mat a) where
negate xm = Mat $ map (map negate) $ unMat xm
xm + ym = Mat $ zipWith (<+>) (unMat xm) (unMat ym)
xm * ym = Mat [[xs <*> ys | ys <- transpose $ unMat ym] | xs <- unMat xm]
fromInteger n = Mat [[fromInteger n]]

we can simply write

fib 0 = 0 -- this line is necessary because "something ^ 0" returns "fromInteger 1", which unfortunately
-- in our case is not our multiplicative identity (the identity matrix) but just a 1x1 matrix of 1
fib n = last $ head $ unMat $ (Mat [[1,1],[1,0]]) ^ n

So, for example, the hundred-thousandth Fibonacci number starts with the digits

*Main> take 10 $ show $ fib (10^5)
"2597406934"

With recurrence relations[edit]

Using Fib[m=3n+r] recurrence identities:

fibsteps (a,b) n 
| n <= 0 = (a,b)
| otherwise = fibsteps (b, a+b) (n-1)
 
fibnums :: [Integer]
fibnums = map fst $ iterate (`fibsteps` 1) (0,1)
 
fibN2 :: Integer -> (Integer, Integer)
fibN2 m | m < 10 = fibsteps (0,1) m
fibN2 m = fibN2_next (n,r) (fibN2 n)
where (n,r) = quotRem m 3
 
fibN2_next (n,r) (f,g) | r==0 = (a,b) -- 3n ,3n+1
| r==1 = (b,c) -- 3n+1,3n+2
| r==2 = (c,d) -- 3n+2,3n+3 (*)
where
a = ( 5*f^3 + if even n then 3*f else (- 3*f) ) -- 3n
b = ( g^3 + 3 * g * f^2 - f^3 ) -- 3n+1
c = ( g^3 + 3 * g^2 * f + f^3 ) -- 3n+2
d = ( 5*g^3 + if even n then (- 3*g) else 3*g ) -- 3(n+1) (*)

(fibN2 n) directly calculates a pair (f,g) of two consecutive Fibonacci numbers, (Fib[n], Fib[n+1]), from recursively calculated such pair at about n/3:

 *Main> take 10 $ show $ fst $ fibN2 (10^6)
"1953282128"

The above should take less than 0.1s on modern PC to calculate; 10,000,000 takes 0.5s. Other identities that could also be used are here.

Haxe[edit]

Iterative[edit]

static function fib(steps:Int, handler:Int->Void)
{
var current = 0;
var next = 1;
 
for (i in 1...steps)
{
handler(current);
 
var temp = current + next;
current = next;
next = temp;
}
handler(current);
}

As Iterator[edit]

class FibIter
{
public var current:Int;
private var nextItem:Int;
private var limit:Int;
 
public function new(limit) {
current = 0;
nextItem = 1;
this.limit = limit;
}
 
public function hasNext() return limit > 0
 
public function next() {
limit--;
var ret = current;
var temp = current + nextItem;
current = nextItem;
nextItem = temp;
return ret;
}
}

Used like:

for (i in new FibIter(10))
Sys.println(i);

Hope[edit]

Recursive[edit]

dec f : num -> num;
--- f 0 <= 0;
--- f 1 <= 1;
--- f(n+2) <= f n + f(n+1);

Tail-recursive[edit]

dec fib : num -> num;
--- 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[edit]

This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers:

dec fibs : list num;
--- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs);

The nth Fibonacci number is then just fibs @ n.

HicEst[edit]

REAL :: Fibonacci(10)
 
Fibonacci = ($==2) + Fibonacci($-1) + Fibonacci($-2)
WRITE(ClipBoard) Fibonacci ! 0 1 1 2 3 5 8 13 21 34

Icon and Unicon[edit]

Icon has built-in support for big numbers. First, a simple recursive solution augmented by caching for non-negative input. This examples computes fib(1000) if there is no integer argument.

procedure main(args)
write(fib(integer(!args) | 1000)
end
 
procedure fib(n)
static fCache
initial {
fCache := table()
fCache[0] := 0
fCache[1] := 1
}
/fCache[n] := fib(n-1) + fib(n-2)
return fCache[n]
end

The above solution is similar to the one provided fib in memrfncs

Now, an O(logN) solution. For large N, it takes far longer to convert the result to a string for output than to do the actual computation. This example computes fib(1000000) if there is no integer argument.

procedure main(args)
write(fib(integer(!args) | 1000000))
end
 
procedure fib(n)
return fibMat(n)[1]
end
 
procedure fibMat(n)
if n <= 0 then return [0,0]
if n = 1 then return [1,0]
fp := fibMat(n/2)
c := fp[1]*fp[1] + fp[2]*fp[2]
d := fp[1]*(fp[1]+2*fp[2])
if n%2 = 1 then return [c+d, d]
else return [d, c]
end

IDL[edit]

Recursive[edit]

function fib,n
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[edit]

function fib,n
psum = (csum = 1uL)
if n lt 3 then return,csum
for i = 3,n do begin
nsum = psum + csum
psum = csum
csum = nsum
endfor
return,nsum
end

Execution time O(n). Limited by size of uLong to fib(49)

Analytic[edit]

function fib,n
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).

Idris[edit]

Analytic[edit]

fibAnalytic : Nat -> Double
fibAnalytic n =
floor $ ((pow goldenRatio n) - (pow (-1.0/goldenRatio) n)) / sqrt(5)
where goldenRatio : Double
goldenRatio = (1.0 + sqrt(5)) / 2.0

Recursive[edit]

fibRecursive : Nat -> Nat
fibRecursive Z = Z
fibRecursive (S Z) = (S Z)
fibRecursive (S (S n)) = fibRecursive (S n) + fibRecursive n

Iterative[edit]

fibIterative : Nat -> Nat
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[edit]

fibLazy : Lazy (List Nat)
fibLazy = 0 :: 1 :: zipWith (+) fibLazy (
case fibLazy of
(x::xs) => xs
[] => [])

J[edit]

The Fibonacci Sequence essay on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number. Here is one:

   fibN=: (-&2 +&$: -&1)^:(1&<) M."0

Examples:

   fibN 12
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.)

Java[edit]

Iterative[edit]

public static long itFibN(int n)
{
if (n < 2)
return n;
long ans = 0;
long n1 = 0;
long n2 = 1;
for(n--; n > 0; n--)
{
ans = n1 + n2;
n1 = n2;
n2 = ans;
}
return ans;
}
 
/**
* O(log(n))
*/

public static long fib(long n) {
if (n <= 0)
return 0;
 
long i = (int) (n - 1);
long a = 1, b = 0, c = 0, d = 1, tmp1,tmp2;
 
while (i > 0) {
if (i % 2 != 0) {
tmp1 = d * b + c * a;
tmp2 = d * (b + a) + c * b;
a = tmp1;
b = tmp2;
}
 
tmp1 = (long) (Math.pow(c, 2) + Math.pow(d, 2));
tmp2 = d * (2 * c + d);
 
c = tmp1;
d = tmp2;
 
i = i / 2;
}
return a + b;
}
 

Recursive[edit]

public static long recFibN(final int n)
{
return (n < 2) ? n : recFibN(n - 1) + recFibN(n - 2);
}

Analytic[edit]

This method works up to the 92nd Fibonacci number. After that, it goes out of range.

public static long anFibN(final long n)
{
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[edit]

public static long fibTailRec(final int n)
{
return fibInner(0, 1, n);
}
 
private static long fibInner(final long a, final long b, final int n)
{
return n < 1 ? a : n == 1 ? b : fibInner(b, a + b, n - 1);
}

Streams[edit]

 
import java.util.function.LongUnaryOperator;
import java.util.stream.LongStream;
 
public class FibUtil {
public static LongStream fibStream() {
return LongStream.iterate( 1l, new LongUnaryOperator() {
private long lastFib = 0;
@Override public long applyAsLong( long operand ) {
long ret = operand + lastFib;
lastFib = operand;
return ret;
}
});
}
public static long fib(long n) {
return fibStream().limit( n ).reduce((prev, last) -> last).getAsLong();
}
}
 

JavaScript[edit]

Recursive[edit]

One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion:

function fib(n) {
return function(n,a,b) {
return n>0 ? arguments.callee(n-1,b,a+b) : a;
}(n,0,1);
}

Iterative[edit]

 
function fib(n) {
var a = 0, b = 1, t;
while (n-- > 0) {
t = a;
a = b;
b += t;
console.log(a);
}
return a;
}
 

Memoization[edit]

With the keys of a dictionary,

var fib = (function(cache){
return cache = cache || {}, function(n){
if (cache[n]) return cache[n];
else return cache[n] = n == 0 ? 0 : n < 0 ? -fib(-n)
: n <= 2 ? 1 : fib(n-2) + fib(n-1);
};
})();
 

or with the indices of an array:

(function () {
'use strict';
 
function fib(n) {
return Array.apply(null, Array(n + 1))
.map(function (_, i, lst) {
return lst[i] = (
i ? i < 2 ? 1 :
lst[i - 2] + lst[i - 1] :
0
);
})[n];
}
 
return fib(32);
 
})();
Output:
2178309

Y-Combinator[edit]

function Y(dn) {
return (function(fn) {
return fn(fn);
}(function(fn) {
return dn(function() {
return fn(fn).apply(null, arguments);
});
}));
}
var fib = Y(function(fn) {
return function(n) {
if (n === 0 || n === 1) {
return n;
}
return fn(n - 1) + fn(n - 2);
};
});

Generators[edit]

function* fibonacciGenerator() {
var prev = 0;
var curr = 1;
while (true) {
yield curr;
curr = curr + prev;
prev = curr - prev;
}
}
var fib = fibonacciGenerator();

Joy[edit]

Recursive[edit]

DEFINE fib == [small] [] [pred dup pred] [+] binrec.

Iterative[edit]

DEFINE fib == [1 0] dip [swap [+] unary] times popd.

jq[edit]

jq does not (yet) have infinite-precision integer arithmetic, and currently the following algorithms only give exact answers up to fib(78). At a certain point, integers are converted to floats, but floating point precision for fib(n) fails after n = 1476: in jq, fib(1476) evaluates to 1.3069892237633987e+308

Recursive[edit]

def nth_fib_naive(n):
if (n < 2) then n
else nth_fib_naive(n - 1) + nth_fib_naive(n - 2)
end;

Tail Recursive[edit]

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.

def nth_fib(n):
# input: [f(i-2), f(i-1), countdown]
def fib: (.[0] + .[1]) as $sum
| .[2] as $n
| if ($n <= 0) then $sum
else [ .[1], $sum, $n - 1 ]
| fib end;
[-1, 1, n] | fib;
 
Example:
 
(range(0;5), 50) | [., nth_fib(.)]
 
yields:
[0,0]
[1,1]
[2,1]
[3,2]
[4,3]
[50,12586269025]

Binet's Formula[edit]

def fib_binet(n):
(5|sqrt) as $rt
| ((1 + $rt)/2) as $phi
| (($phi | log) * n | exp) as $phin
| (if 0 == (n % 2) then 1 else -1 end) as $sign
| ( ($phin - ($sign / $phin) ) / $rt ) + .5
| floor;

Generator[edit]

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)".
# Generator
def fibonacci(n):
# input: [f(i-2), f(i-1), countdown]
def fib: (.[0] + .[1]) as $sum
| if .[2] == 0 then $sum
else $sum, ([ .[1], $sum, .[2] - 1 ] | fib)
end;
[-1, 1, n] | fib;

Julia[edit]

Recursive[edit]

fib(n) = n < 2 ? n : fib(n-1) + fib(n-2)

Iterative[edit]

function fib(n)
x,y = (0,1)
for i = 1:n x,y = (y, x+y) end
x
end

Matrix form[edit]

fib(n) = ([1 1 ; 1 0]^n)[1,2]

K[edit]

Recursive[edit]

{:[x<3;1;_f[x-1]+_f[x-2]]}

Recursive with memoization[edit]

Using a (global) dictionary c.

{c::.();{v:c[a:`$$x];:[x<3;1;:[_n~v;c[a]:_f[x-1]+_f[x-2];v]]}x}

Analytic[edit]

phi:(1+_sqrt(5))%2
{_((phi^x)-((1-phi)^x))%_sqrt[5]}

Sequence to n[edit]

{(x(|+\)\1 1)[;1]}
{x{x,+/-2#x}/!2}

Kotlin[edit]

package fibonacci
 
enum class Fibonacci {
ITERATIVE {
override fun invoke(n: Long) = if (n < 2 )
n
else {
var n1: Long = 0
var n2: Long = 1
var i = n
do {
val sum = n1 + n2
n1 = n2
n2 = sum
} while (i-- > 1)
n1
}
},
RECURSIVE {
override fun invoke(n: Long): Long = if (n < 2) n else this(n - 1) + this(n - 2)
};
 
abstract operator fun invoke(n: Long): Long
}
 
fun main(a: Array<String>) {
val r = 0..30L
Fibonacci.values().forEach {
print("${it.name}: ")
r.forEach { i -> print(" " + it(i)) }
println()
}
}
Output:
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
RECURSIVE:  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

L++[edit]

(defn int fib (int n) (return (? (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
(main (prn (fib 30)))

LabVIEW[edit]

This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.
LabVIEW Fibonacci sequence.png

Lang5[edit]

[] '__A set : dip swap __A swap 2 compress collapse '__A set execute
__A -1 extract nip ;  : nip swap drop ;  : tuck swap over ;
: -rot rot rot ; : 0= 0 == ; : 1+ 1 + ; : 1- 1 - ; : sum '+ reduce ;
: bi 'keep dip execute ;  : keep over 'execute dip ;
 
: fib dup 1 > if dup 1- fib swap 2 - fib + then ;
: fib dup 1 > if "1- fib" "2 - fib" bi + then ;


Lasso[edit]

 
define fibonacci(n::integer) => {
 
#n < 1 ? return false
 
local(
swap = 0,
n1 = 0,
n2 = 1
)
 
loop(#n) => {
#swap = #n1 + #n2;
#n2 = #n1;
#n1 = #swap;
}
return #n1
 
}
 
fibonacci(0) //->output false
fibonacci(1) //->output 1
fibonacci(2) //->output 1
fibonacci(3) //->output 2
 

LFE[edit]

Recursive[edit]

 
(defun fib
((0) 0)
((1) 1)
((n)
(+ (fib (- n 1))
(fib (- n 2)))))
 

Iterative[edit]

 
(defun fib
((n) (when (>= n 0))
(fib n 0 1)))
 
(defun fib
((0 result _)
result)
((n result next)
(fib (- n 1) next (+ result next))))
 
 

Liberty BASIC[edit]

for i = 0 to 15
print fiboR(i),fiboI(i)
next i
 
function fiboR(n)
if n <= 1 then
fiboR = n
else
fiboR = fiboR(n-1) + fiboR(n-2)
end if
end function
 
function fiboI(n)
a = 0
b = 1
for i = 1 to n
temp = a + b
a = b
b = temp
next i
fiboI = a
end function
 

Lisaac[edit]

- fib(n : UINTEGER_32) : UINTEGER_64 <- (
+ result : UINTEGER_64;
(n < 2).if {
result := n;
} else {
result := fib(n - 1) + fib(n - 2);
};
result
);

LiveCode[edit]

-- Iterative, translation of the basic version.
function fibi n
put 0 into aa
put 1 into b
repeat with i = 1 to n
put aa + b into temp
put b into aa
put temp into b
end repeat
return aa
end fibi
 
-- Recursive
function fibr n
if n <= 1 then
return n
else
return fibr(n-1) + fibr(n-2)
end if
end fibr

[edit]

to fib :n [:a 0] [:b 1]
if :n < 1 [output :a]
output (fib :n-1 :b :a+:b)
end

Lua[edit]

--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
 
--more pedantic version, returns 0 for non-integer n
function pfibs(n)
if n ~= math.floor(n) then return 0
elseif n < 0 then return pfibs(n + 2) - pfibs(n + 1)
elseif n < 2 then return n
else return pfibs(n - 1) + pfibs(n - 2)
end
end
 
--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
 
--table-recursive
fib_n = setmetatable({1, 1}, {__index = function(z,n) return n<=0 and 0 or z[n-1] + z[n-2] end})
 
--loop version
function lfibs(n)
local p0,p1=0,1
for _=1,n do p0,p1 = p1,p0+p1 end
return p0
end

Luck[edit]

function fib(x: int): int = (
let cache = {} in
let fibc x = if x<=1 then x else (
if x not in cache then
cache[x] = fibc(x-1) + fibc(x-2);
cache[x]
) in fibc(x)
);;
for x in range(10) do print(fib(x))

Lush[edit]

(de fib-rec (n)
(if (< n 2)
n
(+ (fib-rec (- n 2)) (fib-rec (- n 1)))))

LSL[edit]

Rez a box on the ground, and add the following as a New Script.

integer Fibonacci(integer n) {
if(n<2) {
return n;
} else {
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
default {
state_entry() {
integer x = 0;
for(x=0 ; x<35 ; x++) {
llOwnerSay("Fibonacci("+(string)x+")="+(string)Fibonacci(x));
}
}
}

Output:

Fibonacci(0)=0
Fibonacci(1)=1
Fibonacci(2)=1
Fibonacci(3)=2
Fibonacci(4)=3
Fibonacci(5)=5
Fibonacci(6)=8
Fibonacci(7)=13
Fibonacci(8)=21
Fibonacci(9)=34
Fibonacci(10)=55
Fibonacci(11)=89
Fibonacci(12)=144
Fibonacci(13)=233
Fibonacci(14)=377
Fibonacci(15)=610
Fibonacci(16)=987
Fibonacci(17)=1597
Fibonacci(18)=2584
Fibonacci(19)=4181
Fibonacci(20)=6765
Fibonacci(21)=10946
Fibonacci(22)=17711
Fibonacci(23)=28657
Fibonacci(24)=46368
Fibonacci(25)=75025
Fibonacci(26)=121393
Fibonacci(27)=196418
Fibonacci(28)=317811
Fibonacci(29)=514229
Fibonacci(30)=832040
Fibonacci(31)=1346269
Fibonacci(32)=2178309
Fibonacci(33)=3524578
Fibonacci(34)=5702887

M4[edit]

define(`fibo',`ifelse(0,$1,0,`ifelse(1,$1,1,
`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')

Mathematica / Wolfram Language[edit]

The Wolfram Language already has a built-in function Fibonacci, but a simple recursive implementation would be

fib[0] = 0
fib[1] = 1
fib[n_Integer] := fib[n - 1] + fib[n - 2]

An optimization is to cache the values already calculated:

fib[0] = 0
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:

fibi[prvprv_Integer, prv_Integer, rm_Integer] :=
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):

fib[n_Integer] := Block[{tmp, prvprv = 0, prv = 1},
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:

fibi[{prvprv_Integer, prv_Integer}] := {prv, prvprv + prv}
fibList[n_Integer] := Map[Take[#, 1] &, NestList[fibi, {0, 1}, n]] // Flatten

Output from the last with "fibList[100]":

{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, 1346269, 2178309, 3524578, 5702887, \
9227465, 14930352, 24157817, 39088169, 63245986, 102334155, \
165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, \
2971215073, 4807526976, 7778742049, 12586269025, 20365011074, \
32951280099, 53316291173, 86267571272, 139583862445, 225851433717, \
365435296162, 591286729879, 956722026041, 1548008755920, \
2504730781961, 4052739537881, 6557470319842, 10610209857723, \
17167680177565, 27777890035288, 44945570212853, 72723460248141, \
117669030460994, 190392490709135, 308061521170129, 498454011879264, \
806515533049393, 1304969544928657, 2111485077978050, \
3416454622906707, 5527939700884757, 8944394323791464, \
14472334024676221, 23416728348467685, 37889062373143906, \
61305790721611591, 99194853094755497, 160500643816367088, \
259695496911122585, 420196140727489673, 679891637638612258, \
1100087778366101931, 1779979416004714189, 2880067194370816120, \
4660046610375530309, 7540113804746346429, 12200160415121876738, \
19740274219868223167, 31940434634990099905, 51680708854858323072, \
83621143489848422977, 135301852344706746049, 218922995834555169026, \
354224848179261915075}

MATLAB[edit]

Matrix[edit]

Translation of: Julia
function f = fib(n)
 
f = [1 1 ; 1 0]^(n-1);
f = f(1,1);
 
end

Iterative[edit]

function F = fibonacci(n)
 
Fn = [1 0]; %Fn(1) is F_{n-2}, Fn(2) is F_{n-1}
F = 0; %F is F_{n}
 
for i = (1:abs(n))
Fn(2) = F;
F = sum(Fn);
Fn(1) = Fn(2);
end
 
if n < 0
F = F*((-1)^(n+1));
end
 
end

Dramadah Matrix Method[edit]

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.

function number = fibonacci2(n)
 
if n == 1
number = 1;
elseif n == 0
number = 0;
elseif n < 0
number = ((-1)^(n+1))*fibonacci2(-n);;
else
number = det(gallery('dramadah',n,3));
end
 
end

Maxima[edit]

/* fib(n) is built-in; here is an implementation */
fib2(n) := (matrix([0, 1], [1, 1])^^n)[1, 2]$
 
fib2(100)-fib(100);
0
 
fib2(-10);
-55

MAXScript[edit]

Iterative[edit]

fn fibIter n =
(
if n < 2 then
(
n
)
else
(
fib = 1
fibPrev = 1
for num in 3 to n do
(
temp = fib
fib += fibPrev
fibPrev = temp
)
fib
)
)

Recursive[edit]

fn fibRec n =
(
if n < 2 then
(
n
)
else
(
fibRec (n - 1) + fibRec (n - 2)
)
)

Mercury[edit]

Mercury is both a logic language and a functional language. As such there are two possible interfaces for calculating a Fibonacci number. This code shows both styles. Note that much of the code here is ceremony put in place to have this be something which can actually compile. The actual Fibonacci number generation is contained in the predicate fib/2 and in the function fib/1. The predicate main/2 illustrates first the unification semantics of the predicate form and the function call semantics of the function form.

The provided code uses a very naive form of generating a Fibonacci number. A more realistic implementation would use memoization to cache previous results, exchanging time for space. Also, in the case of supplying both a function implementation and a predicate implementation, one of the two would be implemented in terms of the other. Examples of this are given as comments below.

fib.m[edit]

 
% The following code is derived from the Mercury Tutorial by Ralph Becket.
% http://www.mercury.csse.unimelb.edu.au/information/papers/book.pdf
:- module fib.
 
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
 
:- implementation.
:- import_module int.
 
:- pred fib(int::in, int::out) is det.
fib(N, X) :-
( if N =< 2
then X = 1
else fib(N - 1, A), fib(N - 2, B), X = A + B ).
 
:- func fib(int) = int is det.
fib(N) = X :- fib(N, X).
 
main(!IO) :-
fib(40, X),
write_string("fib(40, ", !IO),
write_int(X, !IO),
write_string(")\n", !IO),
 
write_string("fib(40) = ", !IO),
write_int(fib(40), !IO),
write_string("\n", !IO).
 

Iterative algorithm[edit]

The much faster iterative algorithm can be written as:

 
:- pred fib_acc(int::in, int::in, int::in, int::in, int::out) is det.
 
fib_acc(N, Limit, Prev2, Prev1, Res) :-
( N < Limit ->
 % limit not reached, continue computation.
( N =< 2 ->
Res0 = 1
 ;
Res0 = Prev2 + Prev1
),
fib_acc(N+1, Limit, Prev1, Res0, Res)
 ;
 % Limit reached, return the sum of the two previous results.
Res = Prev2 + Prev1
).
 
This predicate can be called as
fib_acc(1, 40, 1, 1, Result)

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.

Memoization[edit]

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.
fib(N, X) :-
( if N =< 2
then X = 1
else fib(N - 1, A), fib(N - 2, B), X = A + B ).
 

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.

Memoization trades speed for space, a table of results is constructed and kept in memory. So this version of fib consumes more memory than than fib_acc. It is also slightly slower than fib_acc since it must manage its table of results but it is much much faster than without memoization. Memoization works very well for the Fibonacci sequence because in the naive version the same results are calculated over and over again.

Metafont[edit]

vardef fibo(expr n) =
if n=0: 0
elseif n=1: 1
else:
fibo(n-1) + fibo(n-2)
fi
enddef;
 
for i=0 upto 10: show fibo(i); endfor
end

Mirah[edit]

def fibonacci(n:int)
return n if n < 2
fibPrev = 1
fib = 1
3.upto(Math.abs(n)) do
oldFib = fib
fib = fib + fibPrev
fibPrev = oldFib
end
fib * (n<0 ? int(Math.pow(n+1, -1)) : 1)
end
 
puts fibonacci 1
puts fibonacci 2
puts fibonacci 3
puts fibonacci 4
puts fibonacci 5
puts fibonacci 6
puts fibonacci 7
 

МК-61/52[edit]

П0	1	lg	Вx	<->	+	L0	03	С/П	БП
03

Instruction: n В/О С/П, where n is serial number of the number of Fibonacci sequence; С/П for the following numbers.

ML[edit]

Standard ML[edit]

Recursion[edit]

This version is tail recursive.

fun fib n = 
let
fun fib' (0,a,b) = a
| fib' (n,a,b) = fib' (n-1,a+b,a)
in
fib' (n,0,1)
end

MLite[edit]

Recursion[edit]

Tail recursive.

fun fib 
(0, x1, x2) = x2
| (n, x1, x2) = fib (n-1, x2, x1+x2)
| n = fib (n, 0, 1)

ML/I[edit]

MCSKIP "WITH" NL
"" Fibonacci - recursive
MCSKIP MT,<>
MCINS %.
MCDEF FIB WITHS ()
AS <MCSET T1=%A1.
MCGO L1 UNLESS 2 GR T1
%T1.<>MCGO L0
%L1.%FIB(%T1.-1)+FIB(%T1.-2).>
fib(0) is FIB(0)
fib(1) is FIB(1)
fib(2) is FIB(2)
fib(3) is FIB(3)
fib(4) is FIB(4)
fib(5) is FIB(5)

Modula-3[edit]

Recursive[edit]

PROCEDURE Fib(n: INTEGER): INTEGER =
BEGIN
IF n < 2 THEN
RETURN n;
ELSE
RETURN Fib(n-1) + Fib(n-2);
END;
END Fib;

Monicelli[edit]

Recursive version. It includes a main that reads a number N from standard input and prints the Nth Fibonacci number.

 
# Main
Lei ha clacsonato
voglio un nonnulla, Necchi mi porga un nonnulla
il nonnulla come se fosse brematurata la supercazzola bonaccia con il nonnulla o scherziamo?
un nonnulla a posterdati
 
# Fibonacci function 'bonaccia'
blinda la supercazzola Necchi bonaccia con antani Necchi o scherziamo? che cos'è l'antani?
minore di 3: vaffanzum 1! o tarapia tapioco: voglio unchiamo, Necchi come se fosse brematurata
la supercazzola bonaccia con antani meno 1 o scherziamo? voglio duechiamo,
Necchi come se fosse brematurata la supercazzola bonaccia con antani meno 2 o scherziamo? vaffanzum
unchiamo più duechiamo! e velocità di esecuzione
 

MUMPS[edit]

Iterative[edit]

FIBOITER(N)
 ;Iterative version to get the Nth Fibonacci number
 ;N must be a positive integer
 ;F is the tree containing the values
 ;I is a loop variable.
QUIT:(N\1'=N)!(N<0) "Error: "_N_" is not a positive integer."
NEW F,I
SET F(0)=0,F(1)=1
QUIT:N<2 F(N)
FOR I=2:1:N SET F(I)=F(I-1)+F(I-2)
QUIT F(N)
USER>W $$FIBOITER^ROSETTA(30)
832040

Nemerle[edit]

Recursive[edit]

using System;
using System.Console;
 
module Fibonacci
{
Fibonacci(x : long) : long
{
|x when x < 2 => x
|_ => Fibonacci(x - 1) + Fibonacci(x - 2)
}
 
Main() : void
{
def num = Int64.Parse(ReadLine());
foreach (n in $[0 .. num])
WriteLine("{0}: {1}", n, Fibonacci(n));
}
}

Tail Recursive[edit]

Fibonacci(x : long, current : long, next : long) : long
{
match(x)
{
|0 => current
|_ => Fibonacci(x - 1, next, current + next)
}
}
 
Fibonacci(x : long) : long
{
Fibonacci(x, 0, 1)
}

NetRexx[edit]

Translation of: REXX
/* NetRexx */
 
options replace format comments java crossref savelog symbols
 
numeric digits 210000 /*prepare for some big 'uns. */
parse arg x y . /*allow a single number or range.*/
if x == '' then do /*no input? Then assume -30-->+30*/
x = -30
y = -x
end
 
if y == '' then y = x /*if only one number, show fib(n)*/
loop k = x to y /*process each Fibonacci request.*/
q = fib(k)
w = q.length /*if wider than 25 bytes, tell it*/
say 'Fibonacci' k"="q
if w > 25 then say 'Fibonacci' k "has a length of" w
end k
exit
 
/*-------------------------------------FIB subroutine (non-recursive)---*/
method fib(arg) private static
parse arg n
na = n.abs
 
if na < 2 then return na /*handle special cases. */
a = 0
b = 1
 
loop j = 2 to na
s = a + b
a = b
b = s
end j
 
if n > 0 | na // 2 == 1 then return s /*if positive or odd negative... */
else return -s /*return a negative Fib number. */
 

NewLISP[edit]

Iterative[edit]

(define (fibonacci n)
(let (L '(0 1))
(dotimes (i n)
(setq L (list (L 1) (apply + L))))
(L 1)) )
 

Recursive[edit]

(define (fibonacci n)
(if (< n 2) 1
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))
 

Matrix multiplication[edit]

(define (fibonacci n)
(letn (f '((0 1) (1 1)) fib f)
(dotimes (i n)
(set 'fib (multiply fib f)))
(fib 0 1)) )
 
(print(fibonacci 10)) ;;89

NGS[edit]

Iterative[edit]

Translation of: Python
F fib(n:Int) {
n < 2 returns n
local a = 1, b = 1
# i is automatically local because of for()
for(i=2; i<n; i=i+1) {
local next = a + b
a = b
b = next
}
b
}

Nim[edit]

Analytic[edit]

proc Fibonacci(n: int): int64 =
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[edit]

proc Fibonacci(n: int): int =
var
first = 0
second = 1
 
for i in 0 .. <n:
swap first, second
second += first
 
result = first

Recursive[edit]

proc Fibonacci(n: int): int64 =
if n <= 2:
result = 1
else:
result = Fibonacci(n - 1) + Fibonacci(n - 2)

Tail-recursive[edit]

proc Fibonacci(n: int, current: int64, next: int64): int64 =
if n == 0:
result = current
else:
result = Fibonacci(n - 1, next, current + next)
proc Fibonacci(n: int): int64 =
result = Fibonacci(n, 0, 1)

Continuations[edit]

iterator fib: int {.closure.} =
var a = 0
var b = 1
while true:
yield a
swap a, b
b = a + b
 
var f = fib
for i in 0.. <10:
echo f()

Oberon-2[edit]

Works with: oo2c Version 2
 
MODULE Fibonacci;
IMPORT
Out := NPCT:Console;
 
PROCEDURE Fibs(VAR r: ARRAY OF LONGREAL);
VAR
i: LONGINT;
BEGIN
r[0] := 1.0; r[1] := 1.0;
FOR i := 2 TO LEN(r) - 1 DO
r[i] := r[i - 2] + r[i - 1];
END
END Fibs;
 
PROCEDURE FibsR(n: LONGREAL): LONGREAL;
BEGIN
IF n < 2. THEN
RETURN n
ELSE
RETURN FibsR(n - 1) + FibsR(n - 2)
END
END FibsR;
 
PROCEDURE Show(r: ARRAY OF LONGREAL);
VAR
i: LONGINT;
BEGIN
Out.String("First ");Out.Int(LEN(r),0);Out.String(" Fibonacci numbers");Out.Ln;
FOR i := 0 TO LEN(r) - 1 DO
Out.LongRealFix(r[i],8,0)
END;
Out.Ln
END Show;
 
PROCEDURE Gen(s: LONGINT);
VAR
x: POINTER TO ARRAY OF LONGREAL;
BEGIN
NEW(x,s);
Fibs(x^);
Show(x^)
END Gen;
 
PROCEDURE GenR(s: LONGINT);
VAR
i: LONGINT;
BEGIN
Out.String("First ");Out.Int(s,0);Out.String(" Fibonacci numbers (Recursive)");Out.Ln;
FOR i := 1 TO s DO
Out.LongRealFix(FibsR(i),8,0)
END;
Out.Ln
END GenR;
 
BEGIN
Gen(10);
Gen(20);
GenR(10);
GenR(20);
END Fibonacci.
 
Output:
First 10 Fibonacci numbers
      1.      1.      2.      3.      5.      8.     13.     21.     34.     55.
First 20 Fibonacci numbers
      1.      1.      2.      3.      5.      8.     13.     21.     34.     55.     89.    144.    233.    377.    610.    987.   1597.   2584.   4181.   6765.
First 10 Fibonacci numbers (Recursive)
      1.      1.      2.      3.      5.      8.     13.     21.     34.     55.
First 20 Fibonacci numbers (Recursive)
      1.      1.      2.      3.      5.      8.     13.     21.     34.     55.     89.    144.    233.    377.    610.    987.   1597.   2584.   4181.   6765.

Objeck[edit]

Recursive[edit]

bundle Default {
class Fib {
function : Main(args : String[]), Nil {
for(i := 0; i <= 10; i += 1;) {
Fib(i)->PrintLine();
};
}
 
function : native : Fib(n : Int), Int {
if(n < 2) {
return n;
};
 
return Fib(n-1) + Fib(n-2);
}
}
}

Objective-C[edit]

Recursive[edit]

-(long)fibonacci:(int)position
{
long result = 0;
if (position < 2) {
result = position;
} else {
result = [self fibonacci:(position -1)] + [self fibonacci:(position -2)];
}
return result;
}

Iterative[edit]

+(long)fibonacci:(int)index {
long beforeLast = 0, last = 1;
while (index > 0) {
last += beforeLast;
beforeLast = last - beforeLast;
--index;
}
return last;
}

OCaml[edit]

Iterative[edit]

let fib_iter n =
if n < 2 then
n
else let fib_prev = ref 1
and fib = ref 1 in
for num = 2 to n - 1 do
let temp = !fib in
fib := !fib + !fib_prev;
fib_prev := temp
done;
!fib

Recursive[edit]

let rec fib_rec n =
if n < 2 then
n
else
fib_rec (n - 1) + fib_rec (n - 2)
 
(* with support for negatives *)
let rec fib = function
0 -> 0
| 1 -> 1
| n -> if n > 0 then fib (n-1) + fib (n-2)
else fib (n+2) - fib (n+1)
 

The previous way is the naive form, because for most n the fib_rec is called twice, and it is not tail recursive because it adds the result of two function calls. The next version resolves these problems through accumulator argument technique. It is computationally equivalent to the iterative version above (tail recursion is effectively iteration):

let fib n =
let rec fib_aux n a b =
match n with
| 0 -> a
| _ -> fib_aux (n-1) b (a+b)
in
fib_aux n 0 1
 
(* support for negatives *)
let fib n =
if n < 0 && n mod 2 = 0 then -fib (abs n)
else fib (abs n)
 

Arbitrary Precision[edit]

Using OCaml's Num module.

open Num
 
let fib =
let rec fib_aux f0 f1 = function
| 0 -> f0
| 1 -> f1
| n -> fib_aux f1 (f1 +/ f0) (n - 1)
in
fib_aux (num_of_int 0) (num_of_int 1)
 
(* support for negatives *)
let fib n =
if n < 0 && n mod 2 = 0 then minus_num (fib (abs n))
else fib (abs n)
;;
(* It can be called from the command line with an argument *)
(* Result is send to standart output *)
let n = int_of_string Sys.argv.(1) in
print_endline (string_of_num (fib n))
 

compile with:

ocamlopt nums.cmxa -o fib fib.ml
Output:
$ ./fib 0
0
$ ./fib 10
55
$ ./fib 399
108788617463475645289761992289049744844995705477812699099751202749393926359816304226
$ ./fib -6
-8

O(log(n)) with arbitrary precision[edit]

This performs log2(N) matrix multiplys. Each multiplication is not constant-time but increases sub-linearly, about O(log(N)).

open Num
 
let mul (a,b,c) (d,e,f) = let bxe = b*/e in
(a*/d +/ bxe, a*/e +/ b*/f, bxe +/ c*/f)
 
let id = (Int 1, Int 0, Int 1)
let rec pow a n =
if n=0 then id else
let b = pow a (n/2) in
if (n mod 2) = 0 then mul b b else mul a (mul b b)
 
let fib n =
let (_,y,_) = (pow (Int 1, Int 1, Int 0) n) in
string_of_num y
;;
Printf.printf "fib %d = %s\n" 300 (fib 300)
Output:
fib 300 = 222232244629420445529739893461909967206666939096499764990979600

Octave[edit]

Recursive

% recursive
function fibo = recfibo(n)
if ( n < 2 )
fibo = n;
else
fibo = recfibo(n-1) + recfibo(n-2);
endif
endfunction

Iterative

% iterative
function fibo = iterfibo(n)
if ( n < 2 )
fibo = n;
else
f = zeros(2,1);
f(1) = 0;
f(2) = 1;
for i = 2 : n
t = f(2);
f(2) = f(1) + f(2);
f(1) = t;
endfor
fibo = f(2);
endif
endfunction

Testing

% testing
for i = 0 : 20
printf("%d %d\n", iterfibo(i), recfibo(i));
endfor

Oforth[edit]

: fib   0 1 rot #[ tuck + ] times drop ;

OPL[edit]

FIBON:
REM Fibonacci sequence is generated to the Organiser II floating point variable limit.
REM CLEAR/ON key quits.
REM Mikesan - http://forum.psion2.org/
LOCAL A,B,C
A=1 :B=1 :C=1
PRINT A,
DO
C=A+B
A=B
B=C
PRINT A,
UNTIL GET=1

Order[edit]

Recursive[edit]

#include <order/interpreter.h>
 
#define ORDER_PP_DEF_8fib_rec \
ORDER_PP_FN(8fn(8N, \
8if(8less(8N, 2), \
8N, \
8add(8fib_rec(8sub(8N, 1)), \
8fib_rec(8sub(8N, 2))))))

 
ORDER_PP(8fib_rec(10))

Tail recursive version (example supplied with language):

#include <order/interpreter.h>
 
#define ORDER_PP_DEF_8fib \
ORDER_PP_FN(8fn(8N, \
8fib_iter(8N, 0, 1)))

 
#define ORDER_PP_DEF_8fib_iter \
ORDER_PP_FN(8fn(8N, 8I, 8J, \
8if(8is_0(8N), \
8I, \
8fib_iter(8dec(8N), 8J, 8add(8I, 8J)))))

 
ORDER_PP(8to_lit(8fib(8nat(5,0,0))))

Memoization[edit]

#include <order/interpreter.h>
 
#define ORDER_PP_DEF_8fib_memo \
ORDER_PP_FN(8fn(8N, \
8tuple_at(0, 8fib_memo_inner(8N, 8seq))))

 
 
#define ORDER_PP_DEF_8fib_memo_inner \
ORDER_PP_FN(8fn(8N, 8M, \
8cond((8less(8N, 8seq_size(8M)), 8pair(8seq_at(8N, 8M), 8M)) \
(8equal(8N, 0), 8pair(0, 8seq(0))) \
(8equal(8N, 1), 8pair(1, 8seq(0, 1))) \
(8else, \
8lets((8S, 8fib_memo_inner(8sub(8N, 2), 8M)) \
(8T, 8fib_memo_inner(8dec(8N), 8tuple_at(1, 8S))) \
(8U, 8add(8tuple_at(0, 8S), 8tuple_at(0, 8T))), \
8pair(8U, \
8seq_append(8tuple_at(1, 8T), 8seq(8U))))))))

 
 
ORDER_PP(
8for_each_in_range(8fn(8N,
8print(8to_lit(8fib_memo(8N)) (,) 8space)),
1, 21)
)

Oz[edit]

Iterative[edit]

Using mutable references (cells).

fun{FibI N}
Temp = {NewCell 0}
A = {NewCell 0}
B = {NewCell 1}
in
for I in 1..N do
Temp := @A + @B
A := @B
B := @Temp
end
@A
end

Recursive[edit]

Inefficient (blows up the stack).

fun{FibR N}
if N < 2 then N
else {FibR N-1} + {FibR N-2}
end
end

Tail-recursive[edit]

Using accumulators.

fun{Fib N}
fun{Loop N A B}
if N == 0 then
B
else
{Loop N-1 A+B A}
end
end
in
{Loop N 1 0}
end

Lazy-recursive[edit]

declare
fun lazy {FiboSeq}
{LazyMap
{Iterate fun {$ [A B]} [B A+B] end [0 1]}
Head}
end
 
fun {Head A|_} A end
 
fun lazy {Iterate F I}
I|{Iterate F {F I}}
end
 
fun lazy {LazyMap Xs F}
case Xs of X|Xr then {F X}|{LazyMap Xr F}
[] nil then nil
end
end
in
{Show {List.take {FiboSeq} 8}}

PARI/GP[edit]

Built-in[edit]

fibonocci(n)

Matrix[edit]

fibo(n)=([1,1;1,0]^n)[1,2]

Analytic[edit]

This uses the Binet form.

fib(n)=my(phi=(1+sqrt(5))/2);round((phi^n-phi^-n)/sqrt(5))

The second term can be dropped since the error is always small enough to be subsumed by the rounding.

fib(n)=round(((1+sqrt(5))/2)^n/sqrt(5))

Algebraic[edit]

This is an exact version of the above formula. quadgen(5) represents and the number is stored in the form . imag takes the coefficient of . This uses the relation

and hence real(quadgen(5)^n) would give the (n-1)-th Fibonacci number.

fib(n)=imag(quadgen(5)^n)

A more direct translation (note that ) would be

fib(n)=my(phi=quadgen(5));(phi^n-(-1/phi)^n)/(2*phi-1)

Combinatorial[edit]

This uses the generating function. It can be trivially adapted to give the first n Fibonacci numbers.

fib(n)=polcoeff(x/(1-x-x^2)+O(x^(n+1)),n)

Binary powering[edit]

fib(n)={
if(n<=0,
if(n,(-1)^(n+1)*fib(n),0)
,
my(v=lucas(n-1));
(2*v[1]+v[2])/5
)
};
lucas(n)={
if (!n, return([2,1]));
my(v=lucas(n >> 1), z=v[1], t=v[2], pr=v[1]*v[2]);
n=n%4;
if(n%2,
if(n==3,[v[1]*v[2]+1,v[2]^2-2],[v[1]*v[2]-1,v[2]^2+2])
,
if(n,[v[1]^2+2,v[1]*v[2]+1],[v[1]^2-2,v[1]*v[2]-1])
)
};

Recursive[edit]

fib(n)={
if(n<2,
n
,
fib(n-1)+fib(n)
)
};

Anonymous recursion[edit]

Works with: PARI/GP version 2.8.0+

This uses self() which gives a self-reference.

fib(n)={
if(n<2,
n
,
my(s=self());
s(n-2)+s(n-1)
)
};

It can be used without being named:

( n->if(n<2,n,my(s=self());s(n-2)+s(n-1)) )(10)

gives

Output:
55

Memoization[edit]

F=[];
fib(n)={
if(n>#F,
F=concat(F, vector(n-#F));
F[n]=fib(n-1)+fib(n-2)
,
if(n<2,
n
,
if(F[n],F[n],F[n]=fib(n-1)+fib(n-2))
)
);
}

Iterative[edit]

fib(n)={
if(n<0,return((-1)^(n+1)*fib(n)));
my(a=0,b=1,t);
while(n,
t=a+b;
a=b;
b=t;
n--
);
a
};

Anti-Hadamard matrix[edit]

All n×n (0,1) lower Hessenberg matrices have determinant at most F(n). The n×n anti-Hadamard matrix[1] 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.

matantihadamard(n)={
matrix(n,n,i,j,
my(t=j-i+1);
if(t<1,t%2,t<3)
);
}
fib(n)=matdet(matantihadamard(n))


One-by-one[edit]

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.

fib(n)=my(k=0);while(n--,k++;while(!issquare(5*k^2+4)&&!issquare(5*k^2-4),k++));k

Pascal[edit]

Analytic[edit]

function fib(n: integer):longInt;
const
Sqrt5 = sqrt(5.0);
C1 = ln((Sqrt5+1.0)*0.5);//ln( 1.618..)
//C2 = ln((1.0-Sqrt5)*0.5);//ln(-0.618 )) tsetsetse
C2 = ln((Sqrt5-1.0)*0.5);//ln(+0.618 ))
begin
IF n>0 then
begin
IF odd(n) then
fib := round((exp(C1*n) + exp(C2*n) )/Sqrt5)
else
fib := round((exp(C1*n) - exp(C2*n) )/Sqrt5)
end
else
Fibdirekt := 0
end;

Recursive[edit]

function fib(n: integer): integer;
begin
if (n = 0) or (n = 1)
then
fib := n
else
fib := fib(n-1) + fib(n-2)
end;

Iterative[edit]

function fib(n: integer): integer;
var
f0, f1, tmpf0, k: integer;
begin
f1 := n;
IF f1 >1 then
begin
k := f1-1;
f0 := 0;
f1 := 1;
repeat
tmpf0 := f0;
f0 := f1;
f1 := f1+tmpf0;
dec(k);
until k = 0;
end
else
IF f1 < 0 then
f1 := 0;
fib := f1;
end;

Analytic2[edit]

function FiboMax(n: integer):Extended;  //maXbox
begin
result:= (pow((1+SQRT5)/2,n)-pow((1-SQRT5)/2,n))/SQRT5
end;


function Fibo_BigInt(n: integer): string;  //maXbox
var tbig1, tbig2, tbig3: TInteger;
begin
result:= '0'
tbig1:= TInteger.create(1); //temp
tbig2:= TInteger.create(0); //result (a)
tbig3:= Tinteger.create(1); //b
for it:= 1 to n do begin
tbig1.assign(tbig2)
tbig2.assign(tbig3);
tbig1.add(tbig3);
tbig3.assign(tbig1);
end;
result:= tbig2.toString(false)
tbig3.free;
tbig2.free;
tbig1.free;
end;

writeln(floattoStr(FiboMax(555))) >>>4.3516638122555E115

writeln(Fibo_BigInt(555)) >>>43516638122555047989641805373140394725407202037260729735885664398655775748034950972577909265605502785297675867877570

Perl[edit]

Iterative[edit]

sub fib_iter {
my $n = shift;
use bigint try => "GMP,Pari";
my ($v2,$v1) = (-1,1);
($v2,$v1) = ($v1,$v2+$v1) for 0..$n;
$v1;
}

Recursive[edit]

sub fibRec {
my $n = shift;
$n < 2 ? $n : fibRec($n - 1) + fibRec($n - 2);
}

Modules[edit]

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 two are much faster at large values.

# Binary ladder, GMP if available, Pure Perl otherwise
use ntheory qw/lucasu/;
say lucasu(1, -1, 10000);
 
# Uses GMP internal method, so similar performance as above
use Math::GMP;
say Math::GMP::fibonacci(10000);
 
# All Perl
use Math::NumSeq::Fibonacci;
my $seq = Math::NumSeq::Fibonacci->new;
say $seq->ith(10000);
 
# All Perl
use Math::Big qw/fibonacci/;
say 0+fibonacci(10000); # Force scalar context
 
# Perl, gives floating point *approximation*
use Math::Fibonacci qw/term/;
say term(10000);

Perl 6[edit]

List Generator[edit]

This constructs the fibonacci sequence as a lazy infinite list.

my constant @fib = 0, 1, *+* ... *;

If you really need a function for it:

sub fib ($n) { @fib[$n] }

To support negative indices:

my constant @neg_fib = 0, 1, *-* ... *;
sub fib ($n) { $n >= 0 and @fib[$n] or @neg_fib[-$n]; }

Iterative[edit]

sub fib (Int $n --> Int) {
$n > 1 or return $n;
my ($prev, $this) = 0, 1;
($prev, $this) = $this, $this + $prev for 1 ..^ $n;
return $this;
}

Recursive[edit]

use experimental :cached;
proto fib (Int $n --> Int) is cached {*}
multi fib (0) { 0 }
multi fib (1) { 1 }
multi fib ($n) { fib($n - 1) + fib($n - 2) }

Analytic[edit]

sub fib (Int $n --> Int) {
constant φ1 = 1 / constant φ = (1 + sqrt 5)/2;
constant invsqrt5 = 1 / sqrt 5;
 
floor invsqrt5 * (φ**$n + φ1**$n);
}

Phix[edit]

Iterative and tail recursive solutions were only accurate to 43, and a standard recursive version was way too slow above 35, so I memoised it. Using native integers/atoms, errors creep in above 78

sequence fcache = {1,1}
 
function fibonamem(integer n) -- memoized, works for -ve numbers, inaccurate above 78
integer absn = abs(n)
if n=0 then return 0 end if
if absn>length(fcache) then
fcache = append(fcache,fibonamem(absn-1)+fibonamem(absn-2))
if absn!=length(fcache) then ?9/0 end if
end if
if n<0 and remainder(n,2)=0 then return -fcache[absn] end if
return fcache[absn]
end function
 
for i=0 to 30 do
printf(1,"%d", fibonamem(i))
if i!=30 then puts(1,", ") end if
end for
puts(1,"\n")
Output:
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

The same program converted to use bigatoms:

include builtins\bigatom.e
 
sequence fcacheba = {BA_ONE,BA_ONE}
 
function fibonamemba(integer n) -- memoized, works for -ve numbers, yields bigatom
integer absn = abs(n)
if n=0 then return BA_ZERO end if
if absn>length(fcacheba) then
fcacheba = append(fcacheba,ba_add(fibonamemba(absn-1),fibonamemba(absn-2)))
if absn!=length(fcacheba) then ?9/0 end if
end if
if n<0 and remainder(n,2)=0 then return ba_sub(0,fcacheba[absn]) end if
return fcacheba[absn]
end function
 
for i=0 to 30 do
ba_printf(1,"%B", fibonamemba(i))
if i!=30 then puts(1,", ") end if
end for
puts(1,"\n")
ba_printf(1,"%B", fibonamemba(777))
puts(1,"\n")
Output:
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
1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082

PHP[edit]

Iterative[edit]

function fibIter($n) {
if ($n < 2) {
return $n;
}
$fibPrev = 0;
$fib = 1;
foreach (range(1, $n-1) as $i) {
list($fibPrev, $fib) = array($fib, $fib + $fibPrev);
}
return $fib;
}

Recursive[edit]

function fibRec($n) {
return $n < 2 ? $n : fibRec($n-1) + fibRec($n-2);
}

PicoLisp[edit]

Recursive[edit]

(de fibo (N)
(if (>= 2 N)
1
(+ (fibo (dec N)) (fibo (- N 2))) ) )

Recursive with Cache[edit]

Using a recursive version doesn't need to be slow, as the following shows:

(de fibo (N)
(cache '(NIL) N # Use a cache to accelerate
(if (>= 2 N)
N
(+ (fibo (dec N)) (fibo (- N 2))) ) ) )
 
(bench (fibo 1000))

Output:

0.012 sec
-> 43466557686937456435688527675040625802564660517371780402481729089536555417949
05189040387984007925516929592259308032263477520968962323987332247116164299644090
6533187938298969649928516003704476137795166849228875

Iterative[edit]

Recursive can only go so far until a stack overflow brings the whole thing crashing down.

(de fibo (N)
(let (I 1 J 0)
(do N
(let (Tmp J)
(inc 'J I)
(setq I Tmp) ) )
J) )

PIR[edit]

Recursive:

Works with: Parrot version tested with 2.4.0
.sub fib
.param int n
.local int nt
.local int ft
if n < 2 goto RETURNN
nt = n - 1
ft = fib( nt )
dec nt
nt = fib(nt)
ft = ft + nt
.return( ft )
RETURNN:
.return( n )
end
.end
 
.sub main :main
.local int counter
.local int f
counter=0
LOOP:
if counter > 20 goto DONE
f = fib(counter)
print f
print "\n"
inc counter
goto LOOP
DONE:
end
.end

Iterative (stack-based):

Works with: Parrot version tested with 2.4.0
.sub fib
.param int n
.local int counter
.local int f
.local pmc fibs
.local int nmo
.local int nmt
 
fibs = new 'ResizableIntegerArray'
if n == 0 goto RETURN0
if n == 1 goto RETURN1
push fibs, 0
push fibs, 1
counter = 2
FIBLOOP:
if counter > n goto DONE
nmo = pop fibs
nmt = pop fibs
f = nmo + nmt
push fibs, nmt
push fibs, nmo
push fibs, f
inc counter
goto FIBLOOP
RETURN0:
.return( 0 )
end
RETURN1:
.return( 1 )
end
DONE:
f = pop fibs
.return( f )
end
.end
 
.sub main :main
.local int counter
.local int f
counter=0
LOOP:
if counter > 20 goto DONE
f = fib(counter)
print f
print "\n"
inc counter
goto LOOP
DONE:
end
.end

Pike[edit]

Iterative[edit]

int     
fibIter(int n) {
int fibPrev, fib, i;
if (n < 2) {
return 1;
}
fibPrev = 0;
fib = 1;
for (i = 1; i < n; i++) {
int oldFib = fib;
fib += fibPrev;
fibPrev = oldFib;
}
return fib;
}

Recursive[edit]

int 
fibRec(int n) {
if (n < 2) {
return(1);
}
return( fib(n-2) + fib(n-1) );
}

PL/I[edit]

/* Form the n-th Fibonacci number, n > 1. */
get list(n);
f1 = 0; f2 = 1;
do i = 2 to n;
f3 = f1 + f2;
put skip edit('fibo(',i,')=',f3)(a,f(5),a,f(5));
f1 = f2;
f2 = f3;
end;

PL/SQL[edit]

Create or replace Function fnu_fibonnaci(p_iNumber integer)
return integer
is
nuFib integer;
nuP integer;
nuQ integer;
Begin
if p_iNumber is not null then
if p_iNumber=0 then
nuFib:=0;
Elsif p_iNumber=1 then
nuFib:=1;
Else
nuP:=0;
nuQ:=1;
For nuI in 2..p_iNumber loop
nuFib:=nuP+nuQ;
nuP:=nuQ;
nuQ:=nuFib;
End loop;
End if;
End if;
return(nuFib);
End fnu_fibonnaci;

Pop11[edit]

define fib(x);
lvars a , b;
1 -> a;
1 -> b;
repeat x - 1 times
(a + b, b) -> (b, a);
endrepeat;
a;
enddefine;

PostScript[edit]

Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:

%!PS
 
% We want the 'n'th fibonacci number
/n 13 def
 
% Prepare output canvas:
/Helvetica findfont 20 scalefont setfont
100 100 moveto
 
%define the function recursively:
/fib { dup
3 lt
{ pop 1 }
{ dup 1 sub fib exch 2 sub fib add }
ifelse
} def
 
(Fib\() show n (....) cvs show (\)=) show n fib (.....) cvs show
 
showpage

Potion[edit]

Recursive[edit]

Starts with int and upgrades on-the-fly to doubles.

recursive = (n):
if (n <= 1): 1. else: recursive (n - 1) + recursive (n - 2)..
 
n = 40
("fib(", n, ")= ", recursive (n), "\n") join print
recursive(40)= 165580141
real	0m2.851s

Iterative[edit]

iterative = (n) :
curr = 0
prev = 1
tmp = 0
n times:
tmp = curr
curr = curr + prev
prev = tmp
.
curr
.

Matrix based[edit]

sqr = (x): x * x.
 
# Based on the fact that
# F2n = Fn(2Fn+1 - Fn)
# F2n+1 = Fn ^2 + Fn+1 ^2
matrix = (n) :
algorithm = (n) :
"computes (Fn, Fn+1)"
if (n < 2): return ((0, 1), (1, 1)) at(n).
 
# n = e + {0, 1}
q = algorithm(n / 2) # q = (Fe/2, Fe/2+1)
q = (q(0) * (2 * q(1) - q(0)), sqr(q(0)) + sqr(q(1))) # q => (Fe, Fe+1)
if (n % 2 == 1) : # q => (Fe+{0, 1}, Fe+1+{0,1}) = (Fn, Fn+1)
q = (q(1), q(1) + q(0))
.
q
.
algorithm(n)(0)
.

Handling negative values[edit]

fibonacci = (n) :
myFavorite = matrix
if (n >= 0) :
myFavorite(n)
. else :
n = n * -1
if (n % 2 == 1) :
myFavorite(n)
. else :
myFavorite(n) * -1
.
.
.

PowerBASIC[edit]

Translation of: BASIC

There seems to be a limitation (dare I say, bug?) in PowerBASIC regarding how large numbers are stored. 10E17 and larger get rounded to the nearest 10. For F(n), where ABS(n) > 87, is affected like this:

      actual:             displayed:
F(88) 1100087778366101931 1100087778366101930
F(89) 1779979416004714189 1779979416004714190
F(90) 2880067194370816120 2880067194370816120
F(91) 4660046610375530309 4660046610375530310
F(92) 7540113804746346429 7540113804746346430
FUNCTION fibonacci (n AS LONG) AS QUAD
DIM u AS LONG, a AS LONG, L0 AS LONG, outP AS QUAD
STATIC fibNum() AS QUAD
 
u = UBOUND(fibNum)
a = ABS(n)
 
IF u < 1 THEN
REDIM fibNum(1)
fibNum(1) = 1
u = 1
END IF
 
SELECT CASE a
CASE 0 TO 92
IF a > u THEN
REDIM PRESERVE fibNum(a)
FOR L0 = u + 1 TO a
fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
IF 88 = L0 THEN fibNum(88) = fibNum(88) + 1
NEXT
END IF
IF n < 0 THEN
fibonacci = fibNum(a) * ((-1)^(a+1))
ELSE
fibonacci = fibNum(a)
END IF
CASE ELSE
'Even without the above-mentioned bug, we're still limited to
'F(+/-92), due to data type limits. (F(93) = &hA94F AD42 221F 2702)
ERROR 6
END SELECT
END FUNCTION
 
FUNCTION PBMAIN () AS LONG
DIM n AS LONG
#IF NOT %DEF(%PB_CC32)
OPEN "out.txt" FOR OUTPUT AS 1
#ENDIF
FOR n = -92 TO 92
#IF %DEF(%PB_CC32)
PRINT STR$(n); ": "; FORMAT$(fibonacci(n), "#")
#ELSE
PRINT #1, STR$(n) & ": " & FORMAT$(fibonacci(n), "#")
#ENDIF
NEXT
CLOSE
END FUNCTION

PowerShell[edit]

Iterative[edit]

 
function FibonacciNumber ( [int]$N )
{
If ( $N -gt 1 )
{
$FNM1, $FN = 0, 1
2..$N | ForEach { $FNM1, $FN = $FN, ( $FNM1 + $FN ) }
return $FN
}
Else
{
$FNM1, $FN = 0, 1
0..$N | ForEach { $FNM1, $FN = ( $FN - $FNM1 ), $FNM1 }
return $FN
}
}
# The "return" keyword is superfluous in this sample, but is added as best practice for readability.
 
# The practice of setting multiple variables simultaneously is rarely used in PowerShell,
# as it tends to obscure the intended functionality, but is perfect for this scenario,
# a codependent simultaneous change of the variables.
 
# When N=1, the logic actually calculates F(-1), but this works because F(1) = F(-1).
 
 
FibonacciNumber 1
FibonacciNumber 2
FibonacciNumber 3
FibonacciNumber 4
FibonacciNumber 10
 
FibonacciNumber 1
FibonacciNumber 0
FibonacciNumber -1
FibonacciNumber -2
FibonacciNumber -3
FibonacciNumber -4
FibonacciNumber -5
FibonacciNumber -6
 
Output:
1
1
2
3
55
1
0
1
-1
2
-3
5
-8

Recursive[edit]

function fib($n) {
switch ($n) {
0 { return 0 }
1 { return 1 }
{ $_ -lt 0 } { return [Math]::Pow(-1, -$n + 1) * (fib (-$n)) }
default { return (fib ($n - 1)) + (fib ($n - 2)) }
}
}

Prolog[edit]

Works with: SWI Prolog
Works with: GNU Prolog
Works with: YAP
 
fib(1, 1) :- !.
fib(0, 0) :- !.
fib(N, Value) :-
A is N - 1, fib(A, A1),
B is N - 2, fib(B, B1),
Value is A1 + B1.
 

This naive implementation works, but is very slow for larger values of N. Here are some simple measurements (in SWI-Prolog):

?- time(fib(0,F)).
% 2 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 161943 Lips)
F = 0.
 
?- time(fib(10,F)).
% 265 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1458135 Lips)
F = 55.
 
?- time(fib(20,F)).
% 32,836 inferences, 0.016 CPU in 0.016 seconds (99% CPU, 2086352 Lips)
F = 6765.
 
?- time(fib(30,F)).
% 4,038,805 inferences, 1.122 CPU in 1.139 seconds (98% CPU, 3599899 Lips)
F = 832040.
 
?- 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.

Poor man's memoization[edit]

Works with: SWI Prolog
Works with: YAP
Works with: GNU Prolog

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.  % This is ISO, but GNU doesn't like it.
:- dynamic(fib/2). % Not ISO, but works in SWI, YAP and GNU unlike the ISO declaration.
fib(1, 1) :- !.
fib(0, 0) :- !.
fib(N, Value) :-
A is N - 1, fib(A, A1),
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:

?- time(fib(0,F)).
% 2 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 160591 Lips)
F = 0.
 
?- time(fib(10,F)).
% 37 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 552610 Lips)
F = 55.
 
?- time(fib(20,F)).
% 41 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 541233 Lips)
F = 6765.
 
?- time(fib(30,F)).
% 41 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 722722 Lips)
F = 832040.
 
?- 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:

?- listing(fib).
:- dynamic fib/2.
 
fib(40, 102334155) :- !.
fib(39, 63245986) :- !.
fib(38, 39088169) :- !.
fib(37, 24157817) :- !.
fib(36, 14930352) :- !.
fib(35, 9227465) :- !.
fib(34, 5702887) :- !.
fib(33, 3524578) :- !.
fib(32, 2178309) :- !.
fib(31, 1346269) :- !.
fib(30, 832040) :- !.
fib(29, 514229) :- !.
fib(28, 317811) :- !.
fib(27, 196418) :- !.
fib(26, 121393) :- !.
fib(25, 75025) :- !.
fib(24, 46368) :- !.
fib(23, 28657) :- !.
fib(22, 17711) :- !.
fib(21, 10946) :- !.
fib(20, 6765) :- !.
fib(19, 4181) :- !.
fib(18, 2584) :- !.
fib(17, 1597) :- !.
fib(16, 987) :- !.
fib(15, 610) :- !.
fib(14, 377) :- !.
fib(13, 233) :- !.
fib(12, 144) :- !.
fib(11, 89) :- !.
fib(10, 55) :- !.
fib(9, 34) :- !.
fib(8, 21) :- !.
fib(7, 13) :- !.
fib(6, 8) :- !.
fib(5, 5) :- !.
fib(4, 3) :- !.
fib(3, 2) :- !.
fib(2, 1) :- !.
fib(1, 1) :- !.
fib(0, 0) :- !.
fib(A, D) :-
B is A+ -1,
fib(B, E),
C is A+ -2,
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.

Continuation passing style[edit]

Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl

:- use_module(lambda).
fib(N, FN) :-
cont_fib(N, _, FN, \_^Y^_^U^(U = Y)).
 
cont_fib(N, FN1, FN, Pred) :-
( N < 2 ->
call(Pred, 0, 1, FN1, FN)
;
N1 is N - 1,
P = \X^Y^Y^U^(U is X + Y),
cont_fib(N1, FNA, FNB, P),
call(Pred, FNA, FNB, FN1, FN)
).
 

With lazy lists[edit]

Works with SWI-Prolog and others that support freeze/2.

fib([0,1|X]) :-
ffib(0,1,X).
ffib(A,B,X) :-
freeze(X, (C is A+B, X=[C|Y], ffib(B,C,Y)) ).

The predicate fib(Xs) unifies Xs with an infinite list whose values are the Fibonacci sequence. The list can be used like this:

?- fib(X), length(A,15), append(A,_,X), writeln(A).
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Generators idiom[edit]

take( 0, Next, Z-Z, Next).
take( N, Next, [A|B]-Z, NZ):- N>0, !, next( Next, A, Next1),
N1 is N-1,
take( N1, Next1, B-Z, NZ).
 
next( fib(A,B), A, fib(B,C)):- C is A+B.
 
%% 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[edit]

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.

% Fibonacci sequence generator
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).
 
fib(0, 0).
fib(1, 1).
fib(C, N) :- fib(2, [0,1], C, N). % Generate from 3rd sequence on

Looking at performance:

 ?- time(fib(30,X)).
% 86 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 832040 
 ?- time(fib(40,X)).
% 116 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 102334155
 ?- time(fib(100,X)).
% 296 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
X = 354224848179261915075 

What I really like about this one, is it is also a generator- i.e. capable of generating all the numbers in sequence needing no bound input variables or special Prolog predicate support (such as freeze/3 in the previous example):

?- time(fib(X,Fib)).
% 0 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = Fib, Fib = 0 ;
% 1 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = Fib, Fib = 1 ;
% 3 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 2,
Fib = 1 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 3,
Fib = 2 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 4,
Fib = 3 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = Fib, Fib = 5 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 6,
Fib = 8
...etc.

It stays at 5 inferences per iteration after X=3. Also, quite useful:

 ?- time(fib(100,354224848179261915075)).
% 296 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
true .

?- time(fib(X,354224848179261915075)).
% 394 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 100 .

Pure[edit]

Tail Recursive[edit]

fib n = loop 0 1 n with
loop a b n = if n==0 then a else loop b (a+b) (n-1);
end;

PureBasic[edit]

Macro based calculation[edit]

Macro Fibonacci (n)
Int((Pow(((1+Sqr(5))/2),n)-Pow(((1-Sqr(5))/2),n))/Sqr(5))
EndMacro

Recursive[edit]

Procedure FibonacciReq(n)
If n<2
ProcedureReturn n
Else
ProcedureReturn FibonacciReq(n-1)+FibonacciReq(n-2)
EndIf
EndProcedure

Recursive & optimized with a static hash table[edit]

This will be much faster on larger n's, this as it uses a table to store known parts instead of recalculating them. On my machine the speedup compares to above code is

Fib(n) Speedup
20           2
25          23
30         217
40       25847
46     1156741
Procedure Fibonacci(n)
Static NewMap Fib.i()
Protected FirstRecursion
 
If MapSize(Fib())= 0 ; Init the hash table the first run
Fib("0")=0: Fib("1")=1
FirstRecursion = #True
EndIf
 
If n >= 2
Protected.s s=Str(n)
If Not FindMapElement(Fib(),s) ; Calculate only needed parts
Fib(s)= Fibonacci(n-1)+Fibonacci(n-2)
EndIf
n = Fib(s)
EndIf
If FirstRecursion ; Free the memory when finalizing the first call
ClearMap(Fib())
EndIf
ProcedureReturn n
EndProcedure

Example

Fibonacci(0)= 0
Fibonacci(1)= 1
Fibonacci(2)= 1
Fibonacci(3)= 2
Fibonacci(4)= 3
Fibonacci(5)= 5

FibonacciReq(0)= 0
FibonacciReq(1)= 1
FibonacciReq(2)= 1
FibonacciReq(3)= 2
FibonacciReq(4)= 3
FibonacciReq(5)= 5

Purity[edit]

The following takes a natural number and generates an initial segment of the Fibonacci sequence of that length:

 
data Fib1 = FoldNat
<
const (Cons One (Cons One Empty)),
(uncurry Cons) . ((uncurry Add) . (Head, Head . Tail), id)
>
 

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)
 

As a histomorphism:

 
import Histo
 
data Fib3 = Histo . Memoize
<
const One,
(p1 =>
<
const One,
(p2 => Add (outl $p1) (outl $p2)). UnmakeCofree
> (outr $p1)) . UnmakeCofree
>
 

Python[edit]

Analytic[edit]

from math import *
 
def analytic_fibonacci(n):
sqrt_5 = sqrt(5);
p = (1 + sqrt_5) / 2;
q = 1/p;
return int( (p**n + q**n) / sqrt_5 + 0.5 )
 
for i in range(1,31):
print analytic_fibonacci(i),

Output:

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

Iterative[edit]

def fibIter(n):
if n < 2:
return n
fibPrev = 1
fib = 1
for num in xrange(2, n):
fibPrev, fib = fib, fib + fibPrev
return fib

Recursive[edit]

def fibRec(n):
if n < 2:
return n
else:
return fibRec(n-1) + fibRec(n-2)

Recursive with Memoization[edit]

def fibMemo():
pad = {0:0, 1:1}
def func(n):
if n not in pad:
pad[n] = func(n-1) + func(n-2)
return pad[n]
return func
 
fm = fibMemo()
for i in range(1,31):
print fm(i),

Output:

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

Better Recursive doesn't need Memoization[edit]

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 fibFastRec(n):
def fib(prvprv, prv, c):
if c < 1:
return prvprv
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[edit]

def fibGen(n):
a, b = 0, 1
while n>0:
yield a
a, b, n = b, a+b, n-1

Example use[edit]

 
>>> [i for i in fibGen(11)]
 
[0,1,1,2,3,5,8,13,21,34,55]
 

Matrix-Based[edit]

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'
if ((n & -n) == n):
return n
else:
n -= 1
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
n += 1
return (n/2)
 
def crazyFib(n):
'Crazy fast fibonacci number calculation'
powTwo = prevPowTwo(n)
 
q = r = i = 1
s = 0
 
while(i < powTwo):
i *= 2
q, r, s = q*q + r*r, r * (q + s), (r*r + s*s)
 
while(i < n):
i += 1
q, r, s = q+r, q, r
 
return q
 

Large step recurrence[edit]

This is much faster for a single, large value of n:

def fib(n, c={0:1, 1:1}):
if n not in c:
x = n // 2
c[n] = fib(x-1) * fib(n-x-1) + fib(x) * fib(n - x)
return c[n]
 
fib(10000000) # calculating it takes a few seconds, printing it takes eons

Generative with Recursion[edit]

This can get very slow and uses a lot of memory. Can be sped up by caching the generator results.

def fib():
"""Yield fib[n+1] + fib[n]"""
yield 1 # have to start somewhere
lhs, rhs = fib(), fib()
yield next(lhs) # move lhs one iteration ahead
while True:
yield next(lhs)+next(rhs)
 
f=fib()
print [next(f) for _ in range(9)]

Output:

[1, 1, 2, 3, 5, 8, 13, 21, 34]

Qi[edit]

Recursive[edit]

 
(define fib
0 -> 0
1 -> 1
N -> (+ (fib-r (- N 1))
(fib-r (- N 2))))
 

Iterative[edit]

 
(define fib-0
V2 V1 0 -> V2
V2 V1 N -> (fib-0 V1 (+ V2 V1) (1- N)))
 
(define fib
N -> (fib-0 0 1 N))
 

R[edit]

# recursive
recfibo <- function(n) {
if ( n < 2 ) n
else Recall(n-1) + Recall(n-2)
}
 
# print the first 21 elements
print.table(lapply(0:20, recfibo))
 
# iterative
iterfibo <- function(n) {
if ( n < 2 )
n
else {
f <- c(0, 1)
for (i in 2:n) {
t <- f[2]
f[2] <- sum(f)
f[1] <- t
}
f[2]
}
}
 
print.table(lapply(0:20, iterfibo))
 
# iterative but looping replaced by map-reduce'ing
funcfibo <- function(n) {
if (n < 2)
n
else {
generator <- function(f, ...) {
c(f[2], sum(f))
}
Reduce(generator, 2:n, c(0,1))[2]
}
}
 
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.

Output:

All three solutions print

 [1] 0    1    1    2    3    5    8    13   21   34   55   89   144  233  377 
[16] 610  987  1597 2584 4181 6765

Ra[edit]

 
class FibonacciSequence
**Prints the nth fibonacci number**
 
on start
 
args := program arguments
 
if args empty
print .fibonacci(8)
 
else
 
try
print .fibonacci(integer.parse(args[0]))
 
catch FormatException
print to Console.error made !, "Input must be an integer"
exit program with error code
 
catch OverflowException
print to Console.error made !, "Number too large"
exit program with error code
 
define fibonacci(n as integer) as integer is shared
**Returns the nth fibonacci number**
 
test
assert fibonacci(0) = 0
assert fibonacci(1) = 1
assert fibonacci(2) = 1
assert fibonacci(3) = 2
assert fibonacci(4) = 3
assert fibonacci(5) = 5
assert fibonacci(6) = 8
assert fibonacci(7) = 13
assert fibonacci(8) = 21
 
 
body
a, b := 0, 1
 
for n
a, b := b, a + b
 
return a
 

Racket[edit]

Tail Recursive[edit]

 
(define (fib n)
(let loop ((cnt 0) (a 0) (b 1))
(if (= n cnt)
a
(loop (+ cnt 1) b (+ a b)))))
 

Matrix Form[edit]

 
#lang racket
 
(require math/matrix)
 
(define (fibmat n) (matrix-ref
(matrix-expt (matrix ([1 1]
[1 0]))
n)
1 0))
 
(fibmat 1000)
 

REALbasic[edit]

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 92nd iteration.

Function fibo(n as integer) As UInt64
 
dim noOne as UInt64 = 1
dim noTwo as UInt64 = 1
dim sum As UInt64
 
for i as integer = 1 to n
sum = noOne + noTwo
noTwo = noOne
noOne = sum
Next
 
Return noOne
End Function

Retro[edit]

Recursive[edit]

: fib ( n-m ) dup [ 0 = ] [ 1 = ] bi or if; [ 1- fib ] sip [ 2 - fib ] do + ;

Iterative[edit]

: fib ( n-N )
[ 0 1 ] dip [ over + swap ] times drop ;

REXX[edit]

With   210,000   numeric decimal digits, this REXX program can handle Fibonacci numbers past one million.
[Generally speaking, some REXX interpreters can handle up to around eight million decimal digits.]

This version of the REXX program can also handle   negative   Fibonacci numbers.

/*REXX program calculates the  Nth  Fibonacci number,   N   can be  zero  or  negative. */
numeric digits 210000 /*be able to handle ginormous numbers. */
parse arg x y . /*allow a single number or a range. */
if x=='' then do; x=-40; y=+40; end /*No input? Then use range -40 ──► +40*/
if y=='' then y=x /*if only one number, display fib(X).*/
w=max(length(x), length(y)) /*W: used for making formatted output.*/
fw=10 /*Minimum maximum width. Sounds ka─razy*/
do j=x to y; q=fib(j) /*process all of the Fibonacci requests*/
L=length(q) /*obtain the length (decimal digs) of Q*/
fw=max(fw, L) /*fib number length, or the max so far.*/
say 'Fibonacci('right(j,w)") = " right(q,fw) /*right justify Q.*/
if L>10 then say 'Fibonacci('right(j, w)") has a length of" L
end /*j*/ /* [↑] list a Fib. sequence of x──►y */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
fib: procedure; parse arg n; $n=abs(n) /*use │n│ (absolute value of N). */
a=0; b=1; if $n<2 then return $n /*handle two special cases: zero & one.*/
/* [↓] this method is non─recursive. */
do k=2 to $n; s=a+b; a=b; b=s /*sum the numbers up to │n│ */
end /*k*/ /* [↑] (only positive Fibs nums used).*/
/* [↓] $n//2 [same as] ($n//2==1).*/
if n>0 | $n//2 then return s /*if positive or odd negative ··· */
return -s /* return a negative Fibonacci number.*/

output   using the default input:

Fibonacci(-40) =  -102334155
Fibonacci(-39) =    63245986
Fibonacci(-38) =   -39088169
Fibonacci(-37) =    24157817
Fibonacci(-36) =   -14930352
Fibonacci(-35) =     9227465
Fibonacci(-34) =    -5702887
Fibonacci(-33) =     3524578
Fibonacci(-32) =    -2178309
Fibonacci(-31) =     1346269
Fibonacci(-30) =     -832040
Fibonacci(-29) =      514229
Fibonacci(-28) =     -317811
Fibonacci(-27) =      196418
Fibonacci(-26) =     -121393
Fibonacci(-25) =       75025
Fibonacci(-24) =      -46368
Fibonacci(-23) =       28657
Fibonacci(-22) =      -17711
Fibonacci(-21) =       10946
Fibonacci(-20) =       -6765
Fibonacci(-19) =        4181
Fibonacci(-18) =       -2584
Fibonacci(-17) =        1597
Fibonacci(-16) =        -987
Fibonacci(-15) =         610
Fibonacci(-14) =        -377
Fibonacci(-13) =         233
Fibonacci(-12) =        -144
Fibonacci(-11) =          89
Fibonacci(-10) =         -55
Fibonacci( -9) =          34
Fibonacci( -8) =         -21
Fibonacci( -7) =          13
Fibonacci( -6) =          -8
Fibonacci( -5) =           5
Fibonacci( -4) =          -3
Fibonacci( -3) =           2
Fibonacci( -2) =          -1
Fibonacci( -1) =           1
Fibonacci(  0) =           0
Fibonacci(  1) =           1
Fibonacci(  2) =           1
Fibonacci(  3) =           2
Fibonacci(  4) =           3
Fibonacci(  5) =           5
Fibonacci(  6) =           8
Fibonacci(  7) =          13
Fibonacci(  8) =          21
Fibonacci(  9) =          34
Fibonacci( 10) =          55
Fibonacci( 11) =          89
Fibonacci( 12) =         144
Fibonacci( 13) =         233
Fibonacci( 14) =         377
Fibonacci( 15) =         610
Fibonacci( 16) =         987
Fibonacci( 17) =        1597
Fibonacci( 18) =        2584
Fibonacci( 19) =        4181
Fibonacci( 20) =        6765
Fibonacci( 21) =       10946
Fibonacci( 22) =       17711
Fibonacci( 23) =       28657
Fibonacci( 24) =       46368
Fibonacci( 25) =       75025
Fibonacci( 26) =      121393
Fibonacci( 27) =      196418
Fibonacci( 28) =      317811
Fibonacci( 29) =      514229
Fibonacci( 30) =      832040
Fibonacci( 31) =     1346269
Fibonacci( 32) =     2178309
Fibonacci( 33) =     3524578
Fibonacci( 34) =     5702887
Fibonacci( 35) =     9227465
Fibonacci( 36) =    14930352
Fibonacci( 37) =    24157817
Fibonacci( 38) =    39088169
Fibonacci( 39) =    63245986
Fibonacci( 40) =   102334155

output   when the following was used as input:   10000

Fibonacci(10000) =  3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958298727968298751063120057542878345321551510387081829896979161312785626503319548714021428753269818796204693609787990035096230229102636813149319527563022783762844154036058440257211433496118002309120828704608892396232883546150577658327125254609359112820392528539343462090424524892940390
170623388899108584106518317336043747073790855263176432573399371287193758774689747992630583706574283016163740896917842637862421283525811282051637029808933209990570792006436742620238978311147005407499845925036063356093388383192338678305613643535189213327973290813373264265263398976392272340788292817795358057099369104917547080893184105614632233821746563732124822638309210329770164805472624384237486241145309381220656491403275108664339451751216152654536133311131404243685480510676584349352383695965342807176877532834823434555736671973139274627362910821067928078471803532913117677892465908993863545932789
452377767440619224033763867400402133034329749690202832814593341882681768389307200363479562311710310129195316979460763273758925353077255237594378843450406771555577905645044301664011946258097221672975861502696844314695203461493229110597067624326851599283470989128470674086200858713501626031207190317208609408129832158107728207635318662461127824553720853236530577595643007251774431505153960090516860322034916322264088524885243315805153484962243484829938090507048348244932745373262456775587908918719080366205800959474315005240253270974699531877072437682590741993963226598414749819360928522394503970716544
3156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
Fibonacci(10000) has a length of  2090  decimal digits

Ring[edit]

 
give n
x = fib(n)
see n + " Fibonacci is : " + x
 
func fib nr if nr = 0 return 0 ok
if nr = 1 return 1 ok
if nr > 1 return fib(nr-1) + fib(nr-2) ok
 

Ruby[edit]

Iterative[edit]

def fib(n, sequence=[1])
n.times do
current_number, last_number = sequence.last(2)
sequence << current_number + (last_number or 0)
end
 
sequence.last
end

Recursive[edit]

def fib(n, sequence=[1])
return sequence.last if n == 0
 
current_number, last_number = sequence.last(2)
sequence << current_number + (last_number or 0)
 
fib(n-1, sequence)
end
 

Recursive with Memoization[edit]

# Use the Hash#default_proc feature to
# lazily calculate the Fibonacci numbers.
 
fib = Hash.new do |f, n|
f[n] = if n <= -2
(-1)**(n + 1) * f[n.abs]
elsif n <= 1
n.abs
else
f[n - 1] + f[n - 2]
end
end
# examples: fib[10] => 55, fib[-10] => (-55/1)

Matrix[edit]

require 'matrix'
 
# To understand why this matrix is useful for Fibonacci numbers, remember
# that the definition of Matrix.**2 for any Matrix[[a, b], [c, d]] is
# is [[a*a + b*c, a*b + b*d], [c*a + d*b, c*b + d*d]]. In other words, the
# lower right element is computing F(k - 2) + F(k - 1) every time M is multiplied
# by itself (it is perhaps easier to understand this by computing M**2, 3, etc, and
# watching the result march up the sequence of Fibonacci numbers).
 
M = Matrix[[0, 1], [1,1]]
 
# Matrix exponentiation algorithm to compute Fibonacci numbers.
# Let M be Matrix [[0, 1], [1, 1]]. Then, the lower right element of M**k is
# F(k + 1). In other words, the lower right element of M is F(2) which is 1, and the
# lower right element of M**2 is F(3) which is 2, and the lower right element
# of M**3 is F(4) which is 3, etc.
#
# This is a good way to compute F(n) because the Ruby implementation of Matrix.**(n)
# uses O(log n) rather than O(n) matrix multiplications. It works by squaring squares
# ((m**2)**2)... as far as possible
# and then multiplying that by by M**(the remaining number of times). E.g., to compute
# M**19, compute partial = ((M**2)**2) = M**16, and then compute partial*(M**3) = M**19.
# That's only 5 matrix multiplications of M to compute M*19.
def self.fib_matrix(n)
return 0 if n <= 0 # F(0)
return 1 if n == 1 # F(1)
# To get F(n >= 2), compute M**(n - 1) and extract the lower right element.
return CS::lower_right(M**(n - 1))
end
 
# Matrix utility to return
# the lower, right-hand element of a given matrix.
def self.lower_right matrix
return nil if matrix.row_size == 0
return matrix[matrix.row_size - 1, matrix.column_size - 1]
end

Generative[edit]

require 'generator'
 
def fib_gen
Generator.new do |g|
f0, f1 = 0, 1
loop do
g.yield f0
f0, f1 = f1, f0 + f1
end
end
end

Usage:

irb(main):012:0> fg = fib_gen
=> #<Generator:0xb7d3ead4 @cont_next=nil, @queue=[0], @cont_endp=nil, @index=0, @block=#<Proc:0xb7d41680@(irb):4>, @cont_yield=#<Continuation:0xb7d3e8a4>>
irb(main):013:0> 9.times { puts fg.next }
0
1
1
2
3
5
8
13
21
=> 9
Works with: Ruby version 1.9

"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." [2]

fib = Fiber.new do
a,b = 0,1
loop do
Fiber.yield a
a,b = b,a+b
end
end
9.times {puts fib.resume}

using a lambda

def fib_gen
a, b = 1, 1
lambda {ret, a, b = a, b, a+b; ret}
end
irb(main):034:0> fg = fib_gen
=> #<Proc:0xb7cdf750@(irb):22>
irb(main):035:0> 9.times { puts fg.call}
1
1
2
3
5
8
13
21
34
=> 9

Binet's Formula[edit]

def fib
phi = (1 + Math.sqrt(5)) / 2
((phi**self - (-1 / phi)**self) / Math.sqrt(5)).to_i
end
1.9.3p125 :001 > def fib
1.9.3p125 :002?>   phi = (1 + Math.sqrt(5)) / 2
1.9.3p125 :003?>   ((phi**self - (-1 / phi)**self) / Math.sqrt(5)).to_i
1.9.3p125 :004?>   end
 => nil 
1.9.3p125 :005 > (0..10).map(&:fib)
 => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Run BASIC[edit]

for i = 0 to 10
print i;" ";fibR(i);" ";fibI(i)
next i
end
 
function fibR(n)
if n < 2 then fibR = n else fibR = fibR(n-1) + fibR(n-2)
end function
 
function fibI(n)
b = 1
for i = 1 to n
t = a + b
a = b
b = t
next i
fibI = a
end function

Rust[edit]

Using an Iterator[edit]

Iterators are very idiomatic in rust, though they may be overkill for such a simple problem.

#![feature(zero_one)]
 
use std::mem;
use std::num::One;
use std::ops::Add;
 
struct Fib<T> {
curr: T,
next: T,
}
 
impl<T> Fib<T> where T: One {
fn new() -> Self {
Fib {curr: T::one(), next: T::one()}
}
}
 
impl<T> Iterator for Fib<T>
where T: Clone, for <'a> &'a T: Add<Output=T> {
type Item = T;
 
fn next(&mut self) -> Option<Self::Item>{
mem::swap(&mut self.next, &mut self.curr);
self.next = &self.next + &self.curr;
Some(self.curr.clone())
}
}
 
fn main() {
for i in Fib::<u64>::new() {
println!("{}", i);
}
}

SAS[edit]

Iterative[edit]

This code builds a table fib holding the first few values of the Fibonacci sequence.

data fib;
a=0;
b=1;
do n=0 to 20;
f=a;
output;
a=b;
b=f+a;
end;
keep n f;
run;

Naive recursive[edit]

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.

options cmplib=work.f;
 
proc fcmp outlib=work.f.p;
function fib(n);
if n = 0 or n = 1
then return(1);
else return(fib(n - 2) + fib(n - 1));
endsub;
run;
 
data _null_;
x = fib(5);
put 'fib(5) = ' x;
run;

Sather[edit]

The implementations use the arbitrary precision class INTI.

class MAIN is
 
-- RECURSIVE --
fibo(n :INTI):INTI
pre n >= 0
is
if n < 2.inti then return n; end;
return fibo(n - 2.inti) + fibo(n - 1.inti);
end;
 
-- ITERATIVE --
fibo_iter(n :INTI):INTI
pre n >= 0
is
n3w :INTI;
 
if n < 2.inti then return n; end;
last ::= 0.inti; this ::= 1.inti;
loop (n - 1.inti).times!;
n3w := last + this;
last := this;
this := n3w;
end;
return this;
end;
 
main is
loop i ::= 0.upto!(16);
#OUT + fibo(i.inti) + " ";
#OUT + fibo_iter(i.inti) + "\n";
end;
end;
 
end;

Scala[edit]

Recursive[edit]

def fib(i:Int):Int = i match{
case 0 => 0
case 1 => 1
case _ => fib(i-1) + fib(i-2)
}

Lazy sequence[edit]

lazy val fib: Stream[Int] = 0 #:: 1 #:: fib.zip(fib.tail).map{case (a,b) => a + b}

Tail recursive[edit]

def fib(x:Int, prev: BigInt = 0, next: BigInt = 1):BigInt = x match {
case 0 => prev
case 1 => next
case _ => fib(x-1, next, (next + prev))
}

foldLeft[edit]

// Fibonacci using BigInt with Stream.foldLeft optimized for GC (Scala v2.9 and above)
// Does not run out of memory for very large Fibonacci numbers
def fib(n:Int) = {
 
def series(i:BigInt,j:BigInt):Stream[BigInt] = i #:: series(j, i+j)
 
series(1,0).take(n).foldLeft(BigInt("0"))(_+_)
}
 
// Small test
(0 to 13) foreach {n => print(fib(n).toString + " ")}
 
// result: 0 1 1 2 3 5 8 13 21 34 55 89 144 233
 

Iterator[edit]

val it = Iterator.iterate((0,1)){case (a,b) => (b,a+b)}.map(_._1)
//example:
println(it.take(13).mkString(",")) //prints: 0,1,1,2,3,5,8,13,21,34,55,89,144

Scheme[edit]

Iterative[edit]

(define (fib-iter n)
(do ((num 2 (+ num 1))
(fib-prev 1 fib)
(fib 1 (+ fib fib-prev)))
((>= num n) fib)))

Recursive[edit]

(define (fib-rec n)
(if (< n 2)
n
(+ (fib-rec (- n 1))
(fib-rec (- n 2)))))

This version is tail recursive:

(define (fib n)
(let loop ((a 0) (b 1) (n n))
(if (= n 0) a
(loop b (+ a b) (- n 1)))))
 

Recursive Sequence Generator[edit]

Although the tail recursive version above is quite efficient, it only generates the final nth Fibonacci number and not the sequence up to that number without wasteful repeated calls to the procedure/function.

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)))))
(cons 0 (lambda () (nxt 0 1))))
 
;;; test...
(define (show-stream-take n strm)
(define (shw-nxt n strm) (begin (display (car strm))
(if (> n 1) (begin (display " ") (shw-nxt (- n 1) ((cdr strm)))) (display ")"))))
(begin (display "(") (shw-nxt n strm)))
(show-stream-take 30 (fib))
Output:
(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)

Dijkstra Algorithm[edit]

;;; Fibonacci numbers using Edsger Dijkstra's algorithm
;;; http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
 
(define (fib n)
(define (fib-aux a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-aux a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else
(fib-aux (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(fib-aux 1 0 0 1 n))

Scilab[edit]

    clear
n=46
f1=0; f2=1
printf("fibo(%d)=%d\n",0,f1)
printf("fibo(%d)=%d\n",1,f2)
for i=2:n
f3=f1+f2
printf("fibo(%d)=%d\n",i,f3)
f1=f2
f2=f3
end
Output:
...
fibo(43)=433494437
fibo(44)=701408733
fibo(45)=1134903170
fibo(46)=1836311903

sed[edit]

#!/bin/sed -f
 
# First we need to convert each number into the right number of ticks
# Start by marking digits
s/[0-9]/<&/g
 
# We have to do the digits manually.
s/0//g; s/1/|/g; s/2/||/g; s/3/|||/g; s/4/||||/g; s/5/|||||/g
s/6/||||||/g; s/7/|||||||/g; s/8/||||||||/g; s/9/|||||||||/g
 
# Multiply by ten for each digit from the front.
:tens
s/|</<||||||||||/g
t tens
 
# Done with digit markers
s/<//g
 
# Now the actual work.
:split
# Convert each stretch of n >= 2 ticks into two of n-1, with a mark between
s/|\(|\+\)/\1-\1/g
# Convert the previous mark and the first tick after it to a different mark
# giving us n-1+n-2 marks.
s/-|/+/g
# Jump back unless we're done.
t split
# Get rid of the pluses, we're done with them.
s/+//g
 
# Convert back to digits
:back
s/||||||||||/</g
s/<\([0-9]*\)$/<0\1/g
s/|||||||||/9/g;
s/|||||||||/9/g; s/||||||||/8/g; s/|||||||/7/g; s/||||||/6/g;
s/|||||/5/g; s/||||/4/g; s/|||/3/g; s/||/2/g; s/|/1/g;
s/</|/g
t back
s/^$/0/

Seed7[edit]

Recursive[edit]

const func integer: fib (in integer: number) is func
result
var integer: result is 1;
begin
if number > 2 then
result := fib(pred(number)) + fib(number - 2);
elsif number = 0 then
result := 0;
end if;
end func;

Original source: [3]

Iterative[edit]

This funtion uses a bigInteger result:

const func bigInteger: fib (in integer: number) is func
result
var bigInteger: result is 1_;
local
var integer: i is 0;
var bigInteger: a is 0_;
var bigInteger: c is 0_;
begin
for i range 1 to pred(number) do
c := a;
a := result;
result +:= c;
end for;
end func;

Original source: [4]

SequenceL[edit]

Recursive[edit]

fibonacci(n) := 
n when n < 2
else
fibonacci(n - 1) + fibonacci(n - 2);

Based on: [5]

Tail Recursive[edit]

fibonacci(n) := fibonacciHelper(0, 1, n);
 
fibonacciHelper(prev, next, n) :=
prev when n < 1
else
next when n = 1
else
fibonacciHelper(next, next + prev, n - 1);

Matrix[edit]

fibonacci(n) := fibonacciHelper([[1,0],[0,1]], n);
 
fibonacciHelper(M(2), n) :=
let
N := [[1,1],[1,0]];
in
M[1,1] when n <= 1
else
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: [6]

Using the SequenceL Matrix Multiply solution: [7]

SETL[edit]

$ Print out the first ten Fibonacci numbers
$ 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}'
print({fib(n) : n in {0..10}});
 
$ Iterative Fibonacci function
proc fib(n);
A := 0; B := 1; C := n;
for i in {0..n} loop
C := A + B;
A := B;
B := C;
end loop;
return C;
end proc;


Shen[edit]

(define fib
0 -> 0
1 -> 1
N -> (+ (fib (+ N 1)) (fib (+ N 2)))
where (< N 0)
N -> (+ (fib (- N 1)) (fib (- N 2))))

Sidef[edit]

Iterative[edit]

func fib_iter(n) {
var fib = [1, 1];
(n - fib.len).times {
fib = [fib[-1], fib[-2] + fib[-1]]
};
fib[-1];
}

Recursive[edit]

func fib_rec(n) {
n < 2 ? n : (__FUNC__(n-1) + __FUNC__(n-2));
}

Recursive with memoization[edit]

func fib_mem (n) is cached {
n < 2 ? n : (__FUNC__(n-1) + __FUNC__(n-2));
}

Closed-form solution[edit]

func fib_closed(n) {
define S = (1.25.sqrt + 0.5);
define T = (-S + 1);
(S**n - T**n) / (-T + S) -> roundf(0);
}

Slate[edit]

n@(Integer traits) fib
[
n <= 0 ifTrue: [^ 0].
n = 1 ifTrue: [^ 1].
(n - 1) fib + (n - 2) fib
].
 
slate[15]> 10 fib = 55.
True

Smalltalk[edit]

|fibo|
fibo := [ :i |
|ac t|
ac := Array new: 2.
ac at: 1 put: 0 ; at: 2 put: 1.
( i < 2 )
ifTrue: [ ac at: (i+1) ]
ifFalse: [
2 to: i do: [ :l |
t := (ac at: 2).
ac at: 2 put: ( (ac at: 1) + (ac at: 2) ).
ac at: 1 put: t
].
ac at: 2.
]
].
 
0 to: 10 do: [ :i |
(fibo value: i) displayNl
]

SNOBOL4[edit]

Recursive[edit]

	define("fib(a)")	:(fib_end)
fib fib = lt(a,2) a :s(return)
fib = fib(a - 1) + fib(a - 2) :(return)
fib_end
 
while a = trim(input) :f(end)
output = a " " fib(a) :(while)
end

Tail-recursive[edit]

        define('trfib(n,a,b)') :(trfib_end)
trfib trfib = eq(n,0) a :s(return)
trfib = trfib(n - 1, a + b, a) :(return)
trfib_end

Iterative[edit]

        define('ifib(n)f1,f2') :(ifib_end)
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[edit]

Works with: Macro Spitbol
Works with: CSnobol

Note: Snobol4+ lacks built-in sqrt( ) function.

        define('afib(n)s5') :(afib_end)
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

loop    i = lt(i,10) i + 1 :f(show)
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:

1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55

SNUSP[edit]

This is modular SNUSP (which introduces @ and # for threading).

Iterative[edit]

 @!\+++++++++#  /<<+>+>-\       
fib\==>>+<<?!/>!\  ?/\
#<</?\!>/@>\?-<<</@>/@>/>+<-\
\-/ \  !\ !\ !\  ?/#

Recursive[edit]

             /========\    />>+<<-\  />+<-\
fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
| #+==/ fib(n-2)|+fib(n-1)|
\=====recursion======/!========/

Softbridge BASIC[edit]

Iterative[edit]

 
Function Fibonacci(n)
x = 0
y = 1
i = 0
n = ABS(n)
If n < 2 Then
Fibonacci = n
Else
Do Until (i = n)
sum = x+y
x=y
y=sum
i=i+1
Loop
Fibonacci = x
End If
 
End Function
 

SQL[edit]

Works with: PostgreSQL
CREATE FUNCTION fib(n int) RETURNS numeric AS $$
-- This recursive with generates endless list of Fibonacci numbers.
WITH RECURSIVE fibonacci(current, previous) AS (
-- Initialize the current with 0, so the first value will be 0.
-- The previous value is set to 1, because its only goal is not
-- special casing the zero case, and providing 1 as the second
-- number in the sequence.
--
-- The numbers end with dots to make them numeric type in
-- Postgres. Numeric type has almost arbitrary precision
-- (technically just 131,072 digits, but that's good enough for
-- most purposes, including calculating huge Fibonacci numbers)
SELECT 0., 1.
UNION ALL
-- To generate Fibonacci number, we need to add together two
-- previous Fibonacci numbers. Current number is saved in order
-- to be accessed in the next iteration of recursive function.
SELECT previous + current, current FROM fibonacci
)
-- The user is only interested in current number, not previous.
SELECT current FROM fibonacci
-- We only need one number, so limit to 1
LIMIT 1
-- Offset the query by the requested argument to get the correct
-- position in the list.
OFFSET n
$$ LANGUAGE SQL RETURNS NULL ON NULL INPUT IMMUTABLE;

StreamIt[edit]

void->int feedbackloop Fib {
join roundrobin(0,1);
body in->int filter {
work pop 1 push 1 peek 2 { push(peek(0) + peek(1)); pop(); }
};
loop Identity<int>;
split duplicate;
enqueue(0);
enqueue(1);
}

Swift[edit]

Analytic[edit]

import Cocoa
 
func fibonacci(n: Int) -> Int {
let square_root_of_5 = sqrt(5.0)
let p = (1 + square_root_of_5) / 2
let q = 1 / p
return Int((pow(p,CDouble(n)) + pow(q,CDouble(n))) / square_root_of_5 + 0.5)
}
 
for i in 1...30 {
println(fibonacci(i))
}

Iterative[edit]

func fibonacci(n: Int) -> Int {
if n < 2 {
return n
}
var fibPrev = 1
var fib = 1
for num in 2...n {
(fibPrev, fib) = (fib, fib + fibPrev)
}
return fib
}

Sequence:

func fibonacci() -> SequenceOf<UInt> {
return SequenceOf {() -> GeneratorOf<UInt> in
var window: (UInt, UInt, UInt) = (0, 0, 1)
return GeneratorOf {
window = (window.1, window.2, window.1 + window.2)
return window.0
}
}
}

Recursive[edit]

func fibonacci(n: Int) -> Int {
if n < 2 {
return n
} else {
return fibonacci(n-1) + fibonacci(n-2)
}
}
 
println(fibonacci(30))

Tcl[edit]

Simple Version[edit]

These simple versions do not handle negative numbers -- they will return N for N < 2

Iterative[edit]

Translation of: Perl
proc fibiter n {
if {$n < 2} {return $n}
set prev 1
set fib 1
for {set i 2} {$i < $n} {incr i} {
lassign [list $fib [incr fib $prev]] prev fib
}
return $fib
}

Recursive[edit]

proc fib {n} {
if {$n < 2} then {expr {$n}} else {expr {[fib [expr {$n-1}]]+[fib [expr {$n-2}]]} }
}
The following
Works with: Tcl version 8.5
: defining a procedure in the ::tcl::mathfunc namespace allows that proc to be used as a function in expr expressions.
proc tcl::mathfunc::fib {n} {
if { $n < 2 } {
return $n
} else {
return [expr {fib($n-1) + fib($n-2)}]
}
}
 
# or, more tersely
 
proc tcl::mathfunc::fib {n} {expr {$n<2 ? $n : fib($n-1) + fib($n-2)}}

E.g.:

expr {fib(7)} ;# ==> 13
 
namespace path tcl::mathfunc #; or, interp alias {} fib {} tcl::mathfunc::fib
fib 7 ;# ==> 13

Tail-Recursive[edit]

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-tailrec {n} {
proc fib:inner {a b n} {
if {$n < 1} {
return $a
} elseif {$n == 1} {
return $b
} else {
tailcall fib:inner $b [expr {$a + $b}] [expr {$n - 1}]
}
}
return [fib:inner 0 1 $n]
}
% fib-tailrec 100
354224848179261915075

Handling Negative Numbers[edit]

Iterative[edit]

proc fibiter n {
if {$n < 0} {
set n [expr {abs($n)}]
set sign [expr {-1**($n+1)}]
} else {
set sign 1
}
if {$n < 2} {return $n}
set prev 1
set fib 1
for {set i 2} {$i < $n} {incr i} {
lassign [list $fib [incr fib $prev]] prev fib
}
return [expr {$sign * $fib}]
}
fibiter -5 ;# ==> 5
fibiter -6 ;# ==> -8

Recursive[edit]

proc tcl::mathfunc::fib {n} {expr {$n<-1 ? -1**($n+1) * fib(abs($n)) : $n<2 ? $n : fib($n-1) + fib($n-2)}}
expr {fib(-5)} ;# ==> 5
expr {fib(-6)} ;# ==> -8

For the Mathematically Inclined[edit]

This works up to , after which the limited precision of IEEE double precision floating point arithmetic starts to show.

Works with: Tcl version 8.5
proc fib n {expr {round((.5 + .5*sqrt(5)) ** $n / sqrt(5))}}

TI-83 BASIC[edit]

Iterative:

{0,1
While 1
Disp Ans(1
{Ans(2),sum(Ans
End

Binet's formula:

Prompt N
.5(1+√(5 //golden ratio
(Ans^N–(-Ans)^-N)/√(5

TI-89 BASIC[edit]

Recursive[edit]

Optimized implementation (too slow to be usable for n higher than about 12).

fib(n)
when(n<2, n, fib(n-1) + fib(n-2))

Iterative[edit]

Unoptimized implementation (I think the for loop can be eliminated, but I'm not sure).

fib(n)
Func
Local a,b,c,i
0→a
1→b
For i,1,n
a→c
b→a
c+b→b
EndFor
a
EndFunc

TSE SAL[edit]

 
 
// 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]
INTEGER PROC FNMathGetSeriesFibonacciI( INTEGER nI )
//
// Method:
//
// 1. Take the sum of the last 2 terms
//
// 2. Let the sum be the last term
// and goto step 1
//
INTEGER I = 0
INTEGER minI = 1
INTEGER maxI = nI
INTEGER term1I = 0
INTEGER term2I = 1
INTEGER term3I = 0
//
FOR I = minI TO maxI
//
// make value 3 equal to sum of two previous values 1 and 2
//
term3I = term1I + term2I
//
// make value 1 equal to next value 2
//
term1I = term2I
//
// make value 2 equal to next value 3
//
term2I = term3I
//
ENDFOR
//
RETURN( term3I )
//
END
 
PROC Main()
STRING s1[255] = "3"
REPEAT
IF ( NOT ( Ask( " = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF
Warn( FNMathGetSeriesFibonacciI( Val( s1 ) ) ) // gives e.g. 3
UNTIL FALSE
END
 
 


TUSCRIPT[edit]

 
$$ MODE TUSCRIPT
ASK "What fibionacci number do you want?": searchfib=""
IF (searchfib!='digits') STOP
Loop n=0,{searchfib}
IF (n==0) THEN
fib=fiba=n
ELSEIF (n==1) THEN
fib=fibb=n
ELSE
fib=fiba+fibb, fiba=fibb, fibb=fib
ENDIF
IF (n!=searchfib) CYCLE
PRINT "fibionacci number ",n,"=",fib
ENDLOOP
 

Output:

What fibionacci number do you want? >12
fibionacci number 12=144

Output:

What fibionacci number do you want? >31
fibionacci number 31=1346269 

Output:

What fibionacci number do you want? >46
fibionacci 46=1836311903

UnixPipes[edit]

This example is incorrect. There is a race between parallel commands. tee last might open and truncate the file before cat last opens it. Then cat last pipes the empty file to xargs, and expr reports a syntax error, and the script hangs forever. Please fix the code and remove this message.


echo 1 |tee last fib ; tail -f fib | while read x
do
cat last | tee -a fib | xargs -n 1 expr $x + |tee last
done

UNIX Shell[edit]

Works with: bash version 3
#!/bin/bash
 
a=0
b=1
max=$1
 
for (( n=1; "$n" <= "$max"; $((n++)) ))
do
a=$(($a + $b))
echo "F($n): $a"
b=$(($a - $b))
done

Recursive:

Works with: bash version 3
fib() {
local n=$1
[ $n -lt 2 ] && echo -n $n || echo -n $(( $( fib $(( n - 1 )) ) + $( fib $(( n - 2 )) ) ))
}

Ursala[edit]

All three methods are shown here, and all have unlimited precision.

#import std
#import nat
 
iterative_fib = ~&/(0,1); ~&r->ll ^|\predecessor ^/~&r sum
 
recursive_fib = {0,1}^?<a/~&a sum^|W/~& predecessor^~/~& predecessor
 
analytical_fib =
 
%np+ -+
mp..round; ..mp2str; sep`+; ^CNC/~&hh take^\~&htt [email protected],
(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 a natural number. Sufficient precision for an exact result is always chosen based on the argument. This test program computes the first twenty Fibonacci numbers by all three methods.

#cast %nLL
 
examples = <.iterative_fib,recursive_fib,analytical_fib>* iota20

output:

<
   <0,0,0>,
   <1,1,1>,
   <1,1,1>,
   <2,2,2>,
   <3,3,3>,
   <5,5,5>,
   <8,8,8>,
   <13,13,13>,
   <21,21,21>,
   <34,34,34>,
   <55,55,55>,
   <89,89,89>,
   <144,144,144>,
   <233,233,233>,
   <377,377,377>,
   <610,610,610>,
   <987,987,987>,
   <1597,1597,1597>,
   <2584,2584,2584>,
   <4181,4181,4181>>

V[edit]

Generate n'th fib by using binary recursion

[fib
[small?] []
[pred dup pred]
[+]
binrec].

Vala[edit]

Recursive[edit]

Using int, but could easily replace with double, long, ulong, etc.

 
int fibRec(int n){
if (n < 2)
return n;
else
return fibRec(n - 1) + fibRec(n - 2);
}
 

Iterative[edit]

Using int, but could easily replace with double, long, ulong, etc.

 
int fibIter(int n){
if (n < 2)
return n;
 
int last = 0;
int cur = 1;
int next;
 
for (int i = 1; i < n; ++i){
next = last + cur;
last = cur;
cur = next;
}
 
return cur;
}
 

VBA[edit]

Like Visual Basic .NET, but with keyword "Public" and type Long instead of Decimal:

 
Public Function Fib(n As Integer) As Long
Dim fib0, fib1, sum As Long
Dim i As Integer
fib0 = 0
fib1 = 1
For i = 1 To n
sum = fib0 + fib1
fib0 = fib1
fib1 = sum
Next
Fib = fib0
End Function
 

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
 

VBScript[edit]

Non-recursive, object oriented, generator[edit]

Defines a generator class, with a default Get property. Uses Currency for larger-than-Long values. Tests for overflow and switches to Double. Overflow information also available from class.

Class Definition:[edit]

class generator
dim t1
dim t2
dim tn
dim cur_overflow
 
Private Sub Class_Initialize
cur_overflow = false
t1 = ccur(0)
t2 = ccur(1)
tn = ccur(t1 + t2)
end sub
 
public default property get generated
on error resume next
 
generated = ccur(tn)
if err.number <> 0 then
generated = cdbl(tn)
cur_overflow = true
end if
t1 = ccur(t2)
if err.number <> 0 then
t1 = cdbl(t2)
cur_overflow = true
end if
t2 = ccur(tn)
if err.number <> 0 then
t2 = cdbl(tn)
cur_overflow = true
end if
tn = ccur(t1+ t2)
if err.number <> 0 then
tn = cdbl(t1) + cdbl(t2)
cur_overflow = true
end if
on error goto 0
end property
 
public property get overflow
overflow = cur_overflow
end property
 
end class

Invocation:[edit]

dim fib
set fib = new generator
dim i
for i = 1 to 100
wscript.stdout.write " " & fib
if fib.overflow then
wscript.echo
exit for
end if
next

Output:[edit]

 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 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393

Vedit macro language[edit]

Iterative

Calculate fibonacci(#1). Negative values return 0.

:FIBONACCI:
#11 = 0
#12 = 1
Repeat(#1) {
#10 = #11 + #12
#11 = #12
#12 = #10
}
Return(#11)

Visual Basic[edit]

Works with: Visual Basic version 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.

Sub fibonacci()
Const n = 139
Dim i As Integer
Dim f1 As Variant, f2 As Variant, f3 As Variant 'for Decimal
f1 = CDec(0): f2 = CDec(1) 'for Decimal setting
Debug.Print "fibo("; 0; ")="; f1
Debug.Print "fibo("; 1; ")="; f2
For i = 2 To n
f3 = f1 + f2
Debug.Print "fibo("; i; ")="; f3
f1 = f2
f2 = f3
Next i
End Sub 'fibonacci
Output:
fibo( 0 )= 0 
fibo( 1 )= 1 
fibo( 2 )= 1 
...
fibo( 137 )= 19134702400093278081449423917 
fibo( 138 )= 30960598847965113057878492344 
fibo( 139 )= 50095301248058391139327916261 

Visual Basic .NET[edit]

Platform: .NET

Works with: Visual Basic .NET version 9.0+
Function Fib(ByVal n As Integer) As Decimal
Dim fib0, fib1, sum As Decimal
Dim i As Integer
fib0 = 0
fib1 = 1
For i = 1 To n
sum = fib0 + fib1
fib0 = fib1
fib1 = sum
Next
Fib = fib0
End Function

Recursive

Works with: Visual Basic .NET version 9.0+
Function Seq(ByVal Term As Integer)
If Term < 2 Then Return Term
Return Seq(Term - 1) + Seq(Term - 2)
End Function

Wart[edit]

Recursive, all at once[edit]

def (fib n)
if (n < 2)
n
(+ (fib n-1) (fib n-2))

Recursive, using cases[edit]

def (fib n)
(+ (fib n-1) (fib n-2))
 
def (fib n) :case (n < 2)
n

Recursive, using memoization[edit]

def (fib n saved)
# 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

Whitespace[edit]

Iterative[edit]

This program generates Fibonacci numbers until it is forced to terminate.

    

 









It was generated from the following pseudo-Assembly.

push 0
push 1
 
0:
swap
dup
onum
push 10
ochr
copy 1
add
jump 0
Output:
$ wspace fib.ws | head -n 6
0
1
1
2
3
5

Recursive[edit]

This program takes a number n on standard input and outputs the nth member of the Fibonacci sequence.

    








 
 
 















 
; Read n.
push 0
dup
inum
load
 
; Call fib(n), ouput the result and a newline, then exit.
call 0
onum
push 10
ochr
exit
 
0:
dup
push 2
sub
jn 1 ; Return if n < 2.
dup
push 1
sub
call 0 ; Call fib(n - 1).
swap ; Get n back into place.
push 2
sub
call 0 ; Call fib(n - 2).
add ; Leave the sum on the stack.
1:
ret
Output:
$ echo 10 | wspace fibrec.ws
55

Wrapl[edit]

Generator[edit]

DEF fib() (
VAR seq <- [0, 1]; EVERY SUSP seq:values;
REP SUSP seq:put(seq:pop + seq[1])[-1];
);

To get the 17th number:

16 SKIP fib();

To get the list of all 17 numbers:

ALL 17 OF fib();

Iterator[edit]

Using type match signature to ensure integer argument:

TO fib(n @ Integer.T) (
VAR seq <- [0, 1];
EVERY 3:to(n) DO seq:put(seq:pop + seq[1]);
RET seq[-1];
);

x86 Assembly[edit]

Works with: MASM
TITLE i hate visual studio 4			(Fibs.asm)
; __ __/--------\
; >__ \ / | |\
; \ \___/ @ \ / \__________________
; \____ \ / \\\
; \____ Coded with love by: |||
; \ Alexander Alvonellos |||
; | 9/29/2011 / ||
; | | MM
; | |--------------| |
; |< | |< |
; | | | |
; |mmmmmm| |mmmmm|
;; Epic Win.
 
INCLUDE Irvine32.inc
 
.data
BEERCOUNT = 48;
Fibs dd 0, 1, BEERCOUNT DUP(0);
 
.code
main PROC
; I am not responsible for this code.
; They made me write it, against my will.
;Here be dragons
mov esi, offset Fibs; offset array;  ;;were to start (start)
mov ecx, BEERCOUNT; ;;count of items (how many)
mov ebx, 4; ;;size (in number of bytes)
call DumpMem;
 
mov ecx, BEERCOUNT; ;//http://www.wolframalpha.com/input/?i=F ib%5B47%5D+%3E+4294967295
mov esi, offset Fibs
NextPlease:;
mov eax, [esi]; ;//Get me the data from location at ESI
add eax, [esi+4]; ;//add into the eax the data at esi + another double (next mem loc)
mov [esi+8], eax; ;//Move that data into the memory location after the second number
add esi, 4; ;//Update the pointer
loop NextPlease; ;//Thank you sir, may I have another?
 
 
;Here be dragons
mov esi, offset Fibs; offset array;  ;;were to start (start)
mov ecx, BEERCOUNT; ;;count of items (how many)
mov ebx, 4; ;;size (in number of bytes)
call DumpMem;
 
exit ; exit to operating system
main ENDP
 
END main

xEec[edit]

This will display the first 93 numbers of the sequence.

 
h#1 h#1 h#1 o#
h#10 o$ p
>f
o# h#10 o$ p
ma h? jnext p
t
jnf
 

XLISP[edit]

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.

(DEFUN FIBONACCI (N)
(FLOOR (+ (/ (EXPT (/ (+ (SQRT 5) 1) 2) N) (SQRT 5)) 0.5)))

To test it, we'll define a RANGE function and ask for the first 50 numbers in the sequence:

(DEFUN RANGE (X Y)
(IF (<= X Y)
(CONS X (RANGE (+ X 1) Y))))
 
(PRINT (MAPCAR FIBONACCI (RANGE 1 50)))
Output:
(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)

XQuery[edit]

declare function local:fib($n as xs:integer) as xs:integer {
if($n < 2)
then $n
else local:fib($n - 1) + local:fib($n - 2)
};

zkl[edit]

A slight tweak to the task; creates a function that continuously generates fib numbers

var fibShift=fcn(ab){ab.append(ab.sum()).pop(0)}.fp(L(0,1));
zkl: do(15){ fibShift().print(",") }
0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,

zkl: do(5){ fibShift().print(",") }
610,987,1597,2584,4181,
  1. R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Algebra Appl. 62 (1984), 113–137.