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

## 360 Assembly

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

 FIBONACC CSECT           USING  FIBONACC,R12SAVEAREA 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,NLOOP     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 iENDLOOP  EQU    **        ----   END CODERETURN   EQU    *         LM     R14,R12,12(R13)         XR     R15,R15         BR     R14*        ----   DATAN        DC     H'46'           max i P        DS     PL8Z        DS     ZL16C        DS     CL16WTOMSG   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


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

## bash

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];} 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 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) { 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  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. 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

### Lazy Sequence

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

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

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

## COBOL

### Iterative

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

Works with: GNU Cobol version 2.0
       >>SOURCE FREEIDENTIFICATION 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

### Analytic

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

### Iterative

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

### Recursive

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

## Common Lisp

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

### Iterative

(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

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

### Matrix Multiplication Algorithm

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}$.
(defconstant +2x2-identity+ '(1 0 0 1))(defconstant +fib-seed+ '(1 1 1 0)) (defun multiply-2x2 (matrix-1 matrix-2)  (let* ((a (first matrix-1)) (b (second matrix-1)) (c (third matrix-1)) (d (fourth matrix-1))	 (e (first matrix-2)) (f (second matrix-2)) (g (third matrix-2)) (h (fourth matrix-2))	 (ae (* a e)) (bg (* b g)) (af (* a f)) (bh (* b h)) 	 (ce (* c e)) (dg (* d g)) (cf (* c f)) (dh (* d h)))    (list (+ ae bg) (+ af bh) (+ ce dg) (+ cf dh)))) (defun square-2x2 (matrix)  (multiply-2x2 matrix matrix)) (defun 2x2-exponentiation (matrix n)  (cond ((zerop n) +2x2-identity+)	((eql n 1) matrix)	((evenp n) (square-2x2 (2x2-exponentiation matrix (/ n 2))))	(t (multiply-2x2 (square-2x2 (2x2-exponentiation matrix (/ (1- n) 2))) matrix))))  (defun fib (n)  (car (2x2-exponentiation +fib-seed+ (1- n))))

## D

Here are four versions of Fibonacci Number calculating functions. FibD has an argument limit of magnitude 84 due to floating point precision, the others have a limit of 92 due to overflow (long).The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results. A Fibonacci Number generating function is added. All functions have support for negative arguments.

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

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

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

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

###  Iterative

 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

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

###  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}$.
 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; beginmatrix[0,0]:=1;matrix[0,1]:=1;matrix[1,0]:=1;matrix[1,1]:=0;if n>1 thenmatrix:=fibmatexp(matrix,n-1);fib:=matrix[0,0];end; 

## DWScript

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

## E

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

## ECL

### Analytic

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

 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

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)

## 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)) 
Output:
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765


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

### Matrix

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

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

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 iEnd Sub 'fibonacci
Output:
fibo( 0 )= 0
fibo( 1 )= 1
fibo( 2 )= 1
...
fibo( 137 )= 19134702400093278081449423917
fibo( 138 )= 30960598847965113057878492344
fibo( 139 )= 50095301248058391139327916261 

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