# Fibonacci sequence

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

## 0815

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

## ACL2

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

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

## AppleScript

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 integerrepeat 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 ifend repeatreturn item x of fibs

### Recursive

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

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;

Sample output:

 0
1
1
2
3
5
8
13
21
34
55


### Iterative, long integers

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

## Aime

integerfibs(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

### Analytic

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

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

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

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

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

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

## APL

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

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.$

In APL:

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

Plugging in 4 for N gives the following result:

$\begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix}$

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 Fn in order to complete the task. Here's one way:

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

## AutoHotkey

Search autohotkey.com: sequence

### Iterative

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

Source: AutoHotkey forum by Laszlo

/*Important note: the recursive version would be very slowwithout a global or static array. The iterative versionhandles 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 }

## Babel

((main     {{iter fib !}        20 times     collect !    rev     {%d " " . <<}     each}) (collect { -1 take }) (fib  {{dup 2 <}        {fnord}        {dup            <- 2 - fib ! ->            1 - fib !            + }    ifte}))

This code produces the following output when run:

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

## BASIC

Works with: QBasic
Works with: FreeBASIC

### Iterative

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 IFEND 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 neededPRINT 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 SELECTEND FUNCTION

Outputs (unhandled error in final input prevents output):

 0
233
-267914296


### Recursive

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 IFEND FUNCTION

### Array (Table) Lookup

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,-102334155DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986DATA 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),NEXTPRINT'*****sample inputs*****

## Batch File

Recursive version

::fibo.cmd@echo offif "%1" equ "" goto :eofcall :fib %1echo %errorlevel%goto :eof :fibsetlocal enabledelayedexpansionif %1 geq 2 goto :ge2 exit /b %1 :ge2set /a r1 = %1 - 1set /a r2 = %1 - 2call :fib !r1!set r1=%errorlevel%call :fib !r2!set r2=%errorlevel%set /a r0 = r1 + r2exit /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

 // Fibonacci sequence, recursive versionfun 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    endend // vim: set syntax=c ts=4 sw=4 et:

## BBC BASIC

      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

###  iterative

#! /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

## Befunge

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

## Brainf***

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

### Recursive

fib=.!arg:<2|fib$(!arg+-2)+fib$(!arg+-1)
 fib$30 832040  ### Iterative (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

### Recursive

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

### Tail Recursive

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

### Memoization

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

## Burlesque

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

## C

### Recursive

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

### Iterative

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

#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

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

#include <stdlib.h>#include <stdio.h>#include <gmp.h> typedef struct node node;struct node {	int n;	mpz_t v;	node *next;}; #define CSIZE 37node *cache[CSIZE]; // very primitive linked hash tablenode * 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++

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];}

#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

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., 2012int 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

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#

###  Recursive

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

###  Tail-Recursive

 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

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

###  Eager-Generative

 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

 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

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

Algorithm is based on

$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F(n+1)&F(n)\\F(n)&F(n-1)\end{pmatrix}$.

Needs System.Windows.Media.Matrix or similar Matrix class. Calculates in O(n).

 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 O(logn).

 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

 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

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

## Chapel

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

## Chef

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 last1 g this0 g new0 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

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

## Factor

### Iterative

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

### Recursive

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

### Tail-Recursive

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

### Matrix

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

## Fancy

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

### Iterative

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 fibend

### Recursive

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

### Tail Recursive

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

## Fantom

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

 # (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     )       0 1     ) # Now test it:for 0 20 (\n say (fib n)) 

The output is:

 011235813213455891442333776109871597258441816765 

## Forth

: 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 2drophere swap - cell/ Constant #F/64   \ # of fibonacci numbers generated 16 fibonacci . 987  ok#F/64 . 93  ok92 fibonacci . 7540113804746346429  ok   \ largest number generated.

## Fortran

### FORTRAN 77

       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

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

module fibonaccicontains    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

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 fibIend 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

Extended sequence coded big integer.

  'Fibonacci extended'Freebasic version 24  WindowsDim Shared ADDQmod(0 To 19) As UbyteDim Shared ADDbool(0 To 19) As UbyteFor 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 =termEnd Function '==============  EXAMPLE ===============print "THE SEQUENCE TO 10:"printFor n As Integer=1 To 10    Print "term";n;": "; fibonacci(n)Next nprintprint "Selected Fibonacci number"print "Fibonacci 500"printprint 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

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#

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 Systemopen System.Diagnosticsopen 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

###  Recursive

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

###  Tail Recursive

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

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


###  Iterative

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

###  Binet's Formula

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

###  Matrix Exponentiation

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

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

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

Prints the first several fibonacci numbers...

## GML

///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

###  Recursive

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

###  Iterative

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}

## Groovy

###  Recursive

A recursive closure must be pre-declared.

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

###  Iterative

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 ## Haxe ###  Iterative 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 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); ## Haskell ###  With lazy lists 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) 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 With the (rather slow) code from Matrix exponentiation operator import Data.List xs <+> ys = zipWith (+) xs ysxs <*> 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 1fib 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 Using Fib[m=3n+r] recurrence identities: fibsteps (a,b) n | n <= 0 = (a,b) | True = 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) mfibN2 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      d = ( 5*g^3 + if even n then (- 3*g) else 3*g ) -- 3(n+1)   (*)      b = (   g^3 + 3 * g * f^2 - f^3               ) -- 3n+1      c = (   g^3 + 3 * g^2 * f + f^3               ) -- 3n+2 

(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:

## Mathematica / Wolfram Language

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

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

An optimization is to cache the values already calculated:

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

### Iterative

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

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

## UNIX Shell

Works with: bash version 3
#!/bin/bash a=0b=1max=$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

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 %np@t,   (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

Generate n'th fib by using binary recursion

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

## Vala

### Recursive

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

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

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 = fib0End 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

### Non-recursive, object oriented, generator

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:

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:

dim fibset fib = new generatordim ifor i = 1 to 100	wscript.stdout.write " " & fib 	if fib.overflow then		wscript.echo		exit for	end ifnext

#### 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 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

Iterative

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

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

## Visual Basic .NET

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 = fib0End 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

### Recursive, all at once

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

### Recursive, using cases

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

### Recursive, using memoization

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

### Iterative

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



It was generated from the following pseudo-Assembly.

push 0push 1 0:    swap    dup    onum    push 10    ochr    copy 1    add    jump 0
Output:
55

## Wrapl

### Generator

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

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

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); .codemain 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 systemmain ENDP END main

## XQuery

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

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,