Fibonacci sequence

From Rosetta Code
Task
Fibonacci sequence
You are encouraged to solve this task according to the task description, using any language you may know.

The Fibonacci sequence is a sequence   Fn   of natural numbers defined recursively:

      F0 = 0 
      F1 = 1 
      Fn = Fn-1 + Fn-2, if n>1 


Task

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.


Related tasks


References



0815[edit]

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

11l[edit]

Translation of: Python
F fib_iter(n)
   I n < 2
      R n
   V fib_prev = 1
   V fib = 1
   L 2 .< n
      (fib_prev, fib) = (fib, fib + fib_prev)
   R fib

L(i) 1..20
   print(fib_iter(i), end' ‘ ’)
print()
Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

360 Assembly[edit]

For maximum compatibility, programs use only the basic instruction set.

using fullword integers[edit]

*        Fibonacci sequence    05/11/2014
*        integer (31 bits) = 10 decimals -> max fibo(46)
FIBONACC CSECT
         USING FIBONACC,R12    base register
SAVEAREA B     STM-SAVEAREA(R15) skip savearea
         DC    17F'0'          savearea
         DC    CL8'FIBONACC'   eyecatcher
STM      STM   R14,R12,12(R13) save previous context
         ST    R13,4(R15)      link backward
         ST    R15,8(R13)      link forward
         LR    R12,R15         set addressability
*        ----
         LA    R1,0            f(n-2)=0
         LA    R2,1            f(n-1)=1
         LA    R4,2            n=2 
         LA    R6,1            step
         LH    R7,NN           limit
LOOP     EQU   *               for n=2 to nn
         LR    R3,R2             f(n)=f(n-1)
         AR    R3,R1             f(n)=f(n-1)+f(n-2)
         CVD   R4,PW             n  convert binary to packed (PL8)
         UNPK  ZW,PW             packed (PL8) to zoned (ZL16)
         MVC   CW,ZW             zoned (ZL16) to  char (CL16)
         OI    CW+L'CW-1,X'F0'   zap sign
         MVC   WTOBUF+5(2),CW+14 output
         CVD   R3,PW             f(n) binary to packed decimal (PL8)
         MVC   ZN,EM             load mask
         ED    ZN,PW             packed dec (PL8) to char (CL20)
         MVC   WTOBUF+9(14),ZN+6 output
         WTO   MF=(E,WTOMSG)     write buffer
         LR    R1,R2             f(n-2)=f(n-1)
         LR    R2,R3             f(n-1)=f(n)
         BXLE  R4,R6,LOOP      endfor n
*        ----
         LM    R14,R12,12(R13) restore previous savearea pointer
         XR    R15,R15         return code set to 0
         BR    R14             return to caller
*        ----  DATA
NN       DC    H'46'           nn max n
PW       DS    PL8             15num
ZW       DS    ZL16
CW       DS    CL16
ZN       DS    CL20
*                  ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15num
EM       DC    XL20'402020206B2020206B2020206B2020206B202120'  mask
WTOMSG   DS    0F
         DC    H'80',XL2'0000'
*                   fibo(46)=1836311903         
WTOBUF   DC    CL80'fibo(12)=1234567890'
         REGEQU
         END   FIBONACC
Output:
...
fibo(41)=   165,580,141
fibo(42)=   267,914,296
fibo(43)=   433,494,437
fibo(44)=   701,408,733
fibo(45)= 1,134,903,170
fibo(46)= 1,836,311,903

using packed decimals[edit]

*        Fibonacci sequence        31/07/2018
*        packed dec (PL8) = 15 decimals => max fibo(73)
FIBOWTOP CSECT
         USING  FIBOWTOP,R13       base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         SAVE   (14,12)            save previous context
         ST     R13,4(R15)         link backward
         ST     R15,8(R13)         link forward
         LR     R13,R15            set addressability
*        ----
         ZAP    FNM2,=P'0'         f(0)=0
         ZAP    FNM1,=P'1'         f(1)=1
         LA     R4,2               n=2 
         LA     R6,1               step
         LH     R7,NN              limit
LOOP     EQU    *                  for n=2 to nn
         ZAP    FN,FNM1              f(n)=f(n-2)
         AP     FN,FNM2              f(n)=f(n-1)+f(n-2)
         CVD    R4,PW                n 
         MVC    ZN,EM                load mask
         ED     ZN,PW                packed dec (PL8) to char (CL16)
         MVC    WTOBUF+5(2),ZN+L'ZN-2  output
         MVC    ZN,EM                load mask
         ED     ZN,FN                packed dec (PL8) to char (CL16)
         MVC    WTOBUF+9(L'ZN),ZN        output
         WTO    MF=(E,WTOMSG)        write buffer
         ZAP    FNM2,FNM1            f(n-2)=f(n-1)
         ZAP    FNM1,FN              f(n-1)=f(n)
         BXLE   R4,R6,LOOP         endfor n
*        ----
         L      R13,4(0,R13)       restore previous savearea pointer
         RETURN (14,12),RC=0       restore registers from calling sav
*        ----   DATA
NN       DC     H'73'              nn
FNM2     DS     PL8                f(n-2)
FNM1     DS     PL8                f(n-1)
FN       DS     PL8                f(n)
PW       DS     PL8                15num
ZN       DS     CL20
*                   ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15num
EM       DC     XL20'402020206B2020206B2020206B2020206B202120'  mask
WTOMSG   DS     0F
         DC     H'80',XL2'0000'
*                    fibo(73)=806515533049393
WTOBUF   DC     CL80'fibo(12)=123456789012345 '
         REGEQU  
         END    FIBOWTOP
Output:
...
fibo(68)=  72,723,460,248,141
fibo(69)= 117,669,030,460,994
fibo(70)= 190,392,490,709,135
fibo(71)= 308,061,521,170,129
fibo(72)= 498,454,011,879,264
fibo(73)= 806,515,533,049,393

6502 Assembly[edit]

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

The results are calculated and stored, but are not output to the screen or any other physical device: how to do that would depend on the hardware and the operating system.

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

68000 Assembly[edit]

Translation of: ARM Assembly

Input is in D0, and the output is also in D0. There is no protection from 32-bit overflow, so use at your own risk. (I used this C compiler to create this in ARM Assembly and translated it manually into 68000 Assembly. It wasn't that difficult since both CPUs have similar architectures.)

fib:
	MOVEM.L D4-D5,-(SP)
		MOVE.L D0,D4
		MOVEQ #0,D5
		CMP.L #2,D0
		BCS .bar
		MOVEQ #0,D5
.foo:
		MOVE.L D4,D0
		SUBQ.L #1,D0
		JSR fib
		SUBQ.L #2,D4
		ADD.L D0,D5
		CMP.L #1,D4
		BHI .foo
.bar:
		MOVE.L D5,D0
		ADD.L D4,D0
	MOVEM.L (SP)+,D4-D5
	RTS

8080 Assembly[edit]

This subroutine expects to be called with the value of in register A, and returns also in A. You may want to take steps to save the previous contents of B, C, and D. The routine only works with fairly small values of .

FIBNCI: MOV  C,  A  ; C will store the counter
        DCR  C      ; decrement, because we know f(1) already
        MVI  A,  1
        MVI  B,  0
LOOP:   MOV  D,  A
        ADD  B      ; A := A + B
        MOV  B,  D
        DCR  C
        JNZ  LOOP   ; jump if not zero
        RET         ; return from subroutine

8086 Assembly[edit]

Calculating the values at runtime[edit]

Is it cheating to write it in C for 64-bit x86 then port it to 16-bit x86?

The max input is 24 before you start having 16-bit overflow.

fib:
; 	WRITTEN IN C WITH X86-64 CLANG 3.3 AND DOWNGRADED TO 16-BIT X86
; 	INPUT: DI = THE NUMBER YOU WISH TO CALC THE FIBONACCI NUMBER FOR.
;	OUTPUTS TO AX
                                 
        push    BP
        push    BX
        push    AX
        mov     BX, DI			;COPY INPUT TO BX
        xor     AX, AX			;MOV AX,0
        test    BX, BX			;SET FLAGS ACCORDING TO BX
        je      LBB0_4			;IF BX == 0 RETURN 0
        cmp     BX, 1			;IF BX == 1 RETURN 1
        jne     LBB0_3
        mov     AX, 1			;ELSE, SET AX = 1 AND RETURN
        jmp     LBB0_4
LBB0_3:
        lea     DI, WORD PTR [BX - 1]   ;DI = BX - 1
        call    fib			;RETURN FIB(BX-1)
        mov     BP, AX			;STORE THIS IN BP
        add     BX, -2
        mov     DI, BX	
        call    fib			;GET FIB(DI - 2)
        add     AX, BP		        ;RETURN FIB(DI - 1) + FIB(DI - 2)
LBB0_4:

	add sp,2
        pop     BX
        pop     BP
        ret

Using A Lookup Table[edit]

With old computers it was common to use lookup tables to fetch pre-calculated values that would otherwise take some time to compute. The elements of the table are ordered by index, so you can simply create a function that takes an offset as the parameter and returns the element of the array at that offset.

Although lookup tables are very fast, there are some drawbacks to using them. For one, you end up taking up a lot of space. We're wasting a lot of bytes to store very low numbers at the beginning (each takes up 4 bytes regardless of how many digits you see). Unfortunately, when using lookup tables you have very little choice, since trying to conditionally change the scaling of the index would more than likely take more code than encoding all data as the maximum size regardless of the contents, as was done here. This keeps it simple for the CPU, which isn't aware of the intended size of each entry of the table.


For the purpose of this example, assume that both this code and the table are in the .CODE segment.

getfib:
;input: BX = the desired fibonacci number (in other words, the "n" in "F(n)")
;       DS must point to the segment where the fibonacci table is stored
;outputs to DX:AX (DX = high word, AX = low word)
  push ds
    cmp bx,41  ;bounds check
    ja IndexOutOfBounds
    shl bx,1
    shl bx,1 ;multiply by 4, since this is a table of dwords
    mov ax,@code
    mov ds,ax
    mov si,offset fib
    mov ax,[ds:si]    ;fetch the low word into AX
    mov dx,2[ds:si]   ;fetch the high word into DX
  pop ds
  ret


IndexOutOfBounds:
     stc             ;set carry to indicate an error
     mov ax,0FFFFh   ;return FFFF as the error code
   pop ds
   ret

;table of the first 41 fibonacci numbers
fib dword 0, 1, 1, 2, 3, 5, 8, 13 
    dword 21, 34, 55, 89, 144, 233, 377, 610
    dword 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657
    dword 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269
    dword 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986
    dword 102334155

8th[edit]

An iterative solution:

: fibon \ n -- fib(n)
  >r 0 1 
  ( tuck n:+ ) \ fib(n-2) fib(n-1) -- fib(n-1) fib(n)
  r> n:1- times ;

: fib \ n -- fib(n)
  dup 1 n:= if 1 ;; then
  fibon nip ;

ABAP[edit]

Iterative[edit]

FORM fibonacci_iter USING index TYPE i
                    CHANGING number_fib TYPE i.
  DATA: lv_old type i,
        lv_cur type i.
  Do index times.
    If sy-index = 1 or sy-index = 2.
      lv_cur = 1.
      lv_old = 0.
    endif.
    number_fib = lv_cur + lv_old.
    lv_old = lv_cur.
    lv_cur = number_fib.
  enddo.
ENDFORM.

Impure Functional[edit]

Works with: ABAP version 7.4 SP08 Or above only
cl_demo_output=>display( REDUCE #( INIT fibnm = VALUE stringtab( ( |0| ) ( |1| ) )
                                        n TYPE string
                                        x = `0`
                                        y = `1`
                                      FOR i = 1 WHILE i <= 100
                                     NEXT n = ( x + y )
                                          fibnm = VALUE #( BASE fibnm ( n ) )
                                          x = y
                                          y = n ) ).

ACL2[edit]

Fast, tail recursive solution:

(defun fast-fib-r (n a b)
   (if (or (zp n) (zp (1- n)))
       b
       (fast-fib-r (1- n) b (+ a b))))

(defun fast-fib (n)
   (fast-fib-r n 1 1))

(defun first-fibs-r (n i)
   (declare (xargs :measure (nfix (- n i))))
   (if (zp (- n i))
       nil
       (cons (fast-fib i)
             (first-fibs-r n (1+ i)))))

(defun first-fibs (n)
   (first-fibs-r n 0))
Output:
>(first-fibs 20)
(1 1 2 3 5 8 13 21 34 55 89
   144 233 377 610 987 1597 2584 4181 6765)

Action![edit]

Action! language does not support recursion. Therefore an iterative approach has been proposed.

INT FUNC Fibonacci(INT n)
  INT curr,prev,tmp

  IF n>=-1 AND n<=1 THEN
    RETURN (n)
  FI

  prev=0
  IF n>0 THEN
    curr=1
    DO
      tmp=prev
      prev=curr
      curr==+tmp
      n==-1
    UNTIL n=1
    OD
  ELSE
    curr=-1
    DO
      tmp=prev
      prev=curr
      curr==+tmp
      n==+1
    UNTIL n=-1
    OD
  FI
RETURN (curr)

PROC Main()
  BYTE n
  INT f

  Put(125) ;clear screen

  FOR n=0 TO 22
  DO
    f=Fibonacci(n)
    Position(2,n+1)
    PrintF("Fib(%I)=%I",n,f)

    IF n>0 THEN
      f=Fibonacci(-n)
      Position(21,n+1)
      PrintF("Fib(%I)=%I",-n,f)
    FI
  OD
RETURN
Output:

Screenshot from Atari 8-bit computer

Fib(0)=0
Fib(1)=1           Fib(-1)=-1
Fib(2)=1           Fib(-2)=-1
Fib(3)=2           Fib(-3)=-2
Fib(4)=3           Fib(-4)=-3
Fib(5)=5           Fib(-5)=-5
Fib(6)=8           Fib(-6)=-8
Fib(7)=13          Fib(-7)=-13
Fib(8)=21          Fib(-8)=-21
Fib(9)=34          Fib(-9)=-34
Fib(10)=55         Fib(-10)=-55
Fib(11)=89         Fib(-11)=-89
Fib(12)=144        Fib(-12)=-144
Fib(13)=233        Fib(-13)=-233
Fib(14)=377        Fib(-14)=-377
Fib(15)=610        Fib(-15)=-610
Fib(16)=987        Fib(-16)=-987
Fib(17)=1597       Fib(-17)=-1597
Fib(18)=2584       Fib(-18)=-2584
Fib(19)=4181       Fib(-19)=-4181
Fib(20)=6765       Fib(-20)=-6765
Fib(21)=10946      Fib(-21)=-10946
Fib(22)=17711      Fib(-22)=-17711

ActionScript[edit]

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

Ada[edit]

Recursive[edit]

with Ada.Text_IO, Ada.Command_Line;

procedure Fib is

   X: Positive := Positive'Value(Ada.Command_Line.Argument(1));

   function Fib(P: Positive) return Positive is
   begin
      if P <= 2 then
         return 1;
      else
         return Fib(P-1) + Fib(P-2);
      end if;
   end Fib;

begin
   Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
   Ada.Text_IO.Put_Line(Integer'Image(Fib(X)));
end Fib;

Iterative, build-in integers[edit]

with Ada.Text_IO;  use Ada.Text_IO;

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

Iterative, long integers[edit]

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

with Ada.Text_IO, Ada.Command_Line, Crypto.Types.Big_Numbers;

procedure Fibonacci is

   X: Positive := Positive'Value(Ada.Command_Line.Argument(1));

   Bit_Length: Positive := 1 + (696 * X) / 1000;
   -- that number of bits is sufficient to store the full result.

   package LN is new Crypto.Types.Big_Numbers
     (Bit_Length + (32 - Bit_Length mod 32));
     -- the actual number of bits has to be a multiple of 32
   use LN;

   function Fib(P: Positive) return Big_Unsigned is
      Previous: Big_Unsigned := Big_Unsigned_Zero;
      Result:   Big_Unsigned := Big_Unsigned_One;
      Tmp:      Big_Unsigned;
   begin
      -- Result = 1 = Fibonacci(1)
      for I in 1 .. P-1 loop
         Tmp := Result;
         Result := Previous + Result;
         Previous := Tmp;
         -- Result = Fibonacci(I+1))
      end loop;
      return Result;
   end Fib;

begin
   Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
   Ada.Text_IO.Put_Line(LN.Utils.To_String(Fib(X)));
end Fibonacci;
Output:
> ./fibonacci 777
Fibonacci( 777 ) = 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082

Fast method using fast matrix exponentiation[edit]

with ada.text_io;
use  ada.text_io;

procedure fast_fibo is 
	-- We work with biggest natural integers in a 64 bits machine 
	type Big_Int is mod 2**64;

	-- We provide an index type for accessing the fibonacci sequence terms 
	type Index is new Big_Int;

	-- fibo is a generic function that needs a modulus type since it will return
	-- the n'th term of the fibonacci sequence modulus this type (use Big_Int to get the	
	-- expected behaviour in this particular task)
	generic
		type ring_element is mod <>;
		with function "*" (a, b : ring_element) return ring_element is <>;
		function fibo (n : Index) return ring_element;
	function fibo (n : Index) return ring_element is

		type matrix is array (1 .. 2, 1 .. 2) of ring_element;

		-- f is the matrix you apply to a column containing (F_n, F_{n+1}) to get 
		-- the next one containing (F_{n+1},F_{n+2})
		-- could be a more general matrix (given as a generic parameter) to deal with 
		-- other linear sequences of order 2
		f : constant matrix := (1 => (0, 1), 2 => (1, 1));

		function "*" (a, b : matrix) return matrix is
		(1 => (a(1,1)*b(1,1)+a(1,2)*b(2,1), a(1,1)*b(1,2)+a(1,2)*b(2,2)),
		 2 => (a(2,1)*b(1,1)+a(2,2)*b(2,1), a(2,1)*b(1,2)+a(2,2)*b(2,2)));

		function square (m : matrix) return matrix is (m * m);

		-- Fast_Pow could be non recursive but it doesn't really matter since
		-- the number of calls is bounded up by the size (in bits) of Big_Int (e.g 64)
		function fast_pow (m : matrix; n : Index) return matrix is
		(if n = 0 then (1 => (1, 0), 2 => (0, 1)) -- = identity matrix
		 elsif n mod 2 = 0 then square (fast_pow (m, n / 2)) 
		 else m * square (fast_pow (m, n / 2)));

	begin
		return fast_pow (f, n)(2, 1);
	end fibo;

	function Big_Int_Fibo is new fibo (Big_Int);
begin
	-- calculate instantly F_n with n=10^15 (modulus 2^64 )
	put_line (Big_Int_Fibo (10**15)'img);
end fast_fibo;

AdvPL[edit]

Recursive[edit]

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

Iterative[edit]

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

Aime[edit]

integer
fibs(integer n)
{
    integer w;

    if (n == 0) {
        w = 0;
    } elif (n == 1) {
        w = 1;
    } else {
        integer a, b, i;

        i = 1;
        a = 0;
        b = 1;
        while (i < n) {
            w = a + b;
            a = b;
            b = w;
            i += 1;
        }
    }

    return w;
}

ALGOL 60[edit]

Works with: A60
begin
    comment Fibonacci sequence;
    integer procedure fibonacci(n); value n; integer n;
    begin
        integer i, fn, fn1, fn2;
        fn2 := 1;
        fn1 := 0;
        fn  := 0;
        for i := 1 step 1 until n do begin
            fn  := fn1 + fn2;
            fn2 := fn1;
            fn1 := fn
        end;
        fibonacci := fn
    end fibonacci;
 
    integer i;
    for i := 0 step 1 until 20 do outinteger(1,fibonacci(i))
end
Output:
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  6765


ALGOL 68[edit]

Analytic[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC analytic fibonacci = (LONG INT n)LONG INT:(
  LONG REAL sqrt 5 = long sqrt(5);
  LONG REAL p = (1 + sqrt 5) / 2;
  LONG REAL q = 1/p;
  ROUND( (p**n + q**n) / sqrt 5 )
);

FOR i FROM 1 TO 30 WHILE
  print(whole(analytic fibonacci(i),0));
# WHILE # i /= 30 DO
  print(", ")
OD;
print(new line)
Output:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040

Iterative[edit]

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC iterative fibonacci = (INT n)INT: 
  CASE n+1 IN
    0, 1, 1, 2, 3, 5
  OUT
    INT even:=3, odd:=5;
    FOR i FROM odd+1 TO n DO
      (ODD i|odd|even) := odd + even
    OD;
    (ODD n|odd|even)
  ESAC;

FOR i FROM 0 TO 30 WHILE
  print(whole(iterative fibonacci(i),0));
# WHILE # i /= 30 DO
  print(", ")
OD;
print(new line)
Output:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040

Recursive[edit]

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

Generative[edit]

Translation of: Python – Note: This specimen retains the original Python coding style.
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
MODE YIELDINT = PROC(INT)VOID;

PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (
  INT even:=0, odd:=1;
  yield(even);
  yield(odd);
  FOR i FROM odd+1 TO n DO
    yield( (ODD i|odd|even) := odd + even )
  OD
);

main:(
  # FOR INT n IN # gen fibonacci(30, # ) DO ( #
  ##   (INT n)VOID:(
        print((" ",whole(n,0)))
  # OD # ));
    print(new line)
)
Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040

Array (Table) Lookup[edit]

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

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

[]INT const fibonacci = []INT( -1836311903, 1134903170,
  -701408733, 433494437, -267914296, 165580141, -102334155,
  63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
  3524578, -2178309, 1346269, -832040, 514229, -317811, 196418,
  -121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181,
  -2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13,
  -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
  144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
  28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
  1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
  39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
  701408733, 1134903170, 1836311903
)[@-46];

PROC VOID value error := stop;

PROC lookup fibonacci = (INT i)INT: (
  IF LWB const fibonacci <= i AND i<= UPB const fibonacci THEN
    const fibonacci[i]
  ELSE
    value error; SKIP
  FI
);

FOR i FROM 0 TO 30 WHILE
  print(whole(lookup fibonacci(i),0));
# WHILE # i /= 30 DO
  print(", ")
OD;
print(new line)
Output:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040

ALGOL W[edit]

begin
    % return the nth Fibonacci number %
    integer procedure Fibonacci( integer value n ) ;
        begin
            integer fn, fn1, fn2;
            fn2 := 1;
            fn1 := 0;
            fn  := 0;
            for i := 1 until n do begin
                fn  := fn1 + fn2;
                fn2 := fn1;
                fn1 := fn
            end ;
            fn
        end Fibonacci ;

    for i := 0 until 10 do writeon( i_w := 3, s_w := 0, Fibonacci( i ) )

end.
Output:
  0  1  1  2  3  5  8 13 21 34 55

ALGOL-M[edit]

Note that the 21st Fibonacci number (= 10946) is the largest that can be calculated without overflowing ALGOL-M's integer data type.

Iterative[edit]

INTEGER FUNCTION FIBONACCI( X ); INTEGER X;
BEGIN
    INTEGER M, N, A, I;
    M := 0;
    N := 1;
    FOR I := 2 STEP 1 UNTIL X DO
    BEGIN
        A := N;
        N := M + N;
        M := A;
    END;
    FIBONACCI := N;
END;

Naively recursive[edit]

INTEGER FUNCTION FIBONACCI( X ); INTEGER X;
BEGIN
    IF X < 3 THEN
        FIBONACCI := 1
    ELSE
        FIBONACCI := FIBONACCI( X - 2 ) + FIBONACCI( X - 1 );
END;

Alore[edit]

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

Amazing Hopper[edit]

Analitic, Recursive and Iterative mode.

#include <hbasic.h>

#define TERM1    1.61803398874989
#define TERM2    -0.61803398874989

#context get Fibonacci number with analitic mode
  GetArgs(n) 
  get Inv of (M_SQRT5), Mul by( Pow (TERM 1, n), Minus( Pow(TERM 2, n) )  );
  then Return\\

#proto fibonacci_recursive(__X__)
#synon _fibonacci_recursive    getFibonaccinumberwithrecursivemodeof

#proto fibonacci_iterative(__X__)
#synon _fibonacci_iterative    getFibonaccinumberwithiterativemodeof

Begin
  Option Stack 1024

  get Arg Number(2, n), and Take( n );
  then, get Fibonacci number with analitic mode, and Print It with a Newl.
  secondly, get Fibonacci number with recursive mode of(n), and Print It with a Newl.
  finally, get Fibonacci number with iterative mode of (n), and Print It with a Newl.
End

Subrutines

fibonacci_recursive(n)
   Iif ( var(n) Is Le? (2), 1 , \
         get Fibonacci number with recursive mode of( var(n) Minus (1));\
         get Fibonacci number with recursive mode of( var(n) Minus (2)); and Add It )
Return

fibonacci_iterative(n)
  A=0
  B=1
  For Up( I:=2, n, 1 )
    C=B
    Let ( B: = var(A) Plus (B) )
    A=C
  Next
Return(B)
Output:
$ hopper src/fibo1.bas 25
75025
75025
75025

AntLang[edit]

/Sequence
fib:{<0;1> {x,<x[-1]+x[-2]>}/ range[x]}
/nth
fibn:{fib[x][x]}

Apex[edit]

/*
 author: snugsfbay
 date: March 3, 2016
 description: Create a list of x numbers in the Fibonacci sequence.
     - user may specify the length of the list 
     - enforces a minimum of 2 numbers in the sequence because any fewer is not a sequence
     - enforces a maximum of 47 because further values are too large for integer data type 
     - Fibonacci sequence always starts with 0 and 1 by definition
*/
public class FibNumbers{

final static Integer MIN = 2; //minimum length of sequence
final static Integer MAX = 47; //maximum length of sequence

/* 
  description: method to create a list of numbers in the Fibonacci sequence 
  param: user specified integer representing length of sequence should be 2-47, inclusive.
      - Sequence starts with 0 and 1 by definition so the minimum length could be as low as 2.
      - For 48th number in sequence or greater, code would require a Long data type rather than an Integer.
  return: list of integers in sequence.
*/
public static List<Integer> makeSeq(Integer len){

  List<Integer> fib = new List<Integer>{0,1}; // initialize list with first two values
  Integer i;
  
  if(len<MIN || len==null || len>MAX) {
      if (len>MAX){
          len=MAX; //set length to maximum if user entered too high a value
      }else{
          len=MIN; //set length to minimum if user entered too low a value or none
      }
  } //This could be refactored using teneray operator, but we want code coverage to be reflected for each condition
  
  //start with initial list size to find previous two values in the sequence, continue incrementing until list reaches user defined length
  for(i=fib.size(); i<len; i++){ 
    fib.add(fib[i-1]+fib[i-2]); //create new number based on previous numbers and add that to the list
  }

  return fib; 
  }
  
}

APL[edit]

Naive Recursive[edit]

Works with: Dyalog APL
fib{1:⍵  ( -1)+ -2}

Read this as: In the variable "fib", store the function that says, if the argument is less than or equal to 1, return the argument. Else, calculate the value you get when you recursively call the current function with the argument of the current argument minus one and add that to the value you get when you recursively call the current function with the argument of the current function minus two.

This naive solution requires Dyalog APL because GNU APL does not support this syntax for conditional guards.

Array[edit]

Works with: Dyalog APL
Works with: GNU APL

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

In APL:

↑+.×/N/2 21 1 1 0

Plugging in 4 for N gives the following result:

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

0 1↓↑+.×/N/2 21 1 1 0

Analytic[edit]

Works with: Dyalog APL
Works with: GNU APL

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

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

AppleScript[edit]

Imperative[edit]

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


Functional[edit]

The simple recursive version is famously slow:

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

but we can combine enumFromTo(m, n) with the accumulator of a higher-order fold/reduce function to memoize the series:

Translation of: JavaScript
(ES6 memoized fold example)
Translation of: Haskell
(Memoized fold example)
-------------------- FIBONACCI SEQUENCE --------------------

-- fib :: Int -> Int
on fib(n)
    
    -- lastTwo : (Int, Int) -> (Int, Int)
    script lastTwo
        on |λ|([a, b])
            [b, a + b]
        end |λ|
    end script
    
    item 1 of foldl(lastTwo, {0, 1}, enumFromTo(1, n))
end fib


--------------------------- TEST ---------------------------
on run
    
    fib(32)
    
    --> 2178309
end run

-------------------- GENERIC FUNCTIONS ---------------------

-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
    if m  n then
        set lst to {}
        repeat with i from m to n
            set end of lst to i
        end repeat
        lst
    else
        {}
    end if
end enumFromTo

-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from 1 to lng
            set v to |λ|(v, item i of xs, i, xs)
        end repeat
        return v
    end tell
end foldl

-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: Handler -> Script
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn
Output:
2178309

Arendelle[edit]

( fibonacci , 1; 1 )

[ 98 , // 100 numbers of fibonacci

	( fibonacci[ @fibonacci? ] ,

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

	)

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

ARM Assembly[edit]

Expects to be called with in R0, and will return in the same register.

fibonacci:
        push  {r1-r3}
        mov   r1,  #0
        mov   r2,  #1
        
fibloop:
        mov   r3,  r2
        add   r2,  r1,  r2
        mov   r1,  r3
        sub   r0,  r0,  #1
        cmp   r0,  #1
        bne   fibloop
        
        mov   r0,  r2
        pop   {r1-r3}
        mov   pc,  lr

ArnoldC[edit]

IT'S SHOWTIME

HEY CHRISTMAS TREE f1
YOU SET US UP @I LIED
TALK TO THE HAND f1

HEY CHRISTMAS TREE f2
YOU SET US UP @NO PROBLEMO

HEY CHRISTMAS TREE f3
YOU SET US UP @I LIED

STICK AROUND @NO PROBLEMO

GET TO THE CHOPPER f3
HERE IS MY INVITATION f1
GET UP f2
ENOUGH TALK
TALK TO THE HAND f3

GET TO THE CHOPPER f1
HERE IS MY INVITATION f2
ENOUGH TALK

GET TO THE CHOPPER f2
HERE IS MY INVITATION f3
ENOUGH TALK

CHILL

YOU HAVE BEEN TERMINATED

Arturo[edit]

Recursive[edit]

fib: $[x][
	if? x<2 [1]
	else [(fib x-1) + (fib x-2)]
]

loop 1..25 [x][
	print ["Fibonacci of" x "=" fib x]
]

AsciiDots[edit]

/--#$--\
|      |
>-*>{+}/
| \+-/
1  |
#  1
|  #
|  |
.  .

ATS[edit]

Recursive[edit]

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

Iterative[edit]

(*
** This one is also referred to as being tail-recursive 
*)
fun
fib_trec(n: int): int =
if
n > 0
then (fix loop (i:int, r0:int, r1:int): int => if i > 1 then loop (i-1, r1, r0+r1) else r1)(n, 0, 1)
else 0

Iterative and Verified[edit]

(*
** This implementation is verified!
*)

dataprop FIB (int, int) =
  | FIB0 (0, 0) | FIB1 (1, 1)
  | {n:nat} {r0,r1:int} FIB2 (n+2, r0+r1) of (FIB (n, r0), FIB (n+1, r1))
// end of [FIB] // end of [dataprop]

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

Matrix-based[edit]

(* ****** ****** *)
//
// How to compile:
// patscc -o fib fib.dats
//
(* ****** ****** *)
//
#include
"share/atspre_staload.hats"
//
(* ****** ****** *)
//
abst@ype
int3_t0ype =
  (int, int, int)
//
typedef int3 = int3_t0ype
//
(* ****** ****** *)

extern
fun int3 : (int, int, int) -<> int3
extern
fun int3_1 : int3 -<> int
extern
fun mul_int3_int3: (int3, int3) -<> int3

(* ****** ****** *)

local

assume
int3_t0ype = (int, int, int)

in (* in-of-local *)
//
implement
int3 (x, y, z) = @(x, y, z)
//
implement int3_1 (xyz) = xyz.1
//
implement
mul_int3_int3
(
  @(a,b,c), @(d,e,f)
) =
  (a*d + b*e, a*e + b*f, b*e + c*f)
//
end // end of [local]

(* ****** ****** *)
//
implement
gnumber_int<int3> (n) = int3(n, 0, n)
//
implement gmul_val<int3> = mul_int3_int3
//
(* ****** ****** *)
//
fun
fib (n: intGte(0)): int =
  int3_1(gpow_int_val<int3> (n, int3(1, 1, 0)))
//
(* ****** ****** *)

implement
main0 () =
{
//
val N = 10
val () = println! ("fib(", N, ") = ", fib(N))
val N = 20
val () = println! ("fib(", N, ") = ", fib(N))
val N = 30
val () = println! ("fib(", N, ") = ", fib(N))
val N = 40
val () = println! ("fib(", N, ") = ", fib(N))
//
} (* end of [main0] *)

AutoHotkey[edit]

Search autohotkey.com: sequence

Iterative[edit]

Translation of: C
Loop, 5
  MsgBox % fib(A_Index)
Return

fib(n)
{
  If (n < 2) 
    Return n
  i := last := this := 1
  While (i <= n)
  {
    new := last + this
    last := this
    this := new
    i++
  }
  Return this
}

Recursive and iterative[edit]

Source: AutoHotkey forum by Laszlo

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

FibR(n) {       ; n-th Fibonacci number (n>=0, recursive with static array Fibo) 
   Static 
   Return n<2 ? n : Fibo%n% ? Fibo%n% : Fibo%n% := FibR(n-1)+FibR(n-2) 
} 

Fib(n) {        ; n-th Fibonacci number (n < 0 OK, iterative) 
   a := 0, b := 1 
   Loop % abs(n)-1 
      c := b, b += a, a := c 
   Return n=0 ? 0 : n>0 || n&1 ? b : -b 
}

AutoIt[edit]

Iterative[edit]

#AutoIt Version: 3.2.10.0
$n0 = 0
$n1 = 1
$n = 10
MsgBox (0,"Iterative Fibonacci ", it_febo($n0,$n1,$n))

Func it_febo($n_0,$n_1,$N)
   $first = $n_0
   $second = $n_1
   $next = $first + $second
   $febo = 0
   For $i = 1 To $N-3
      $first = $second
      $second = $next
      $next = $first + $second
   Next
   if $n==0 Then
      $febo = 0
   ElseIf $n==1 Then
      $febo = $n_0
   ElseIf $n==2 Then
      $febo = $n_1
   Else
      $febo = $next
   EndIf
   Return $febo
EndFunc

Recursive[edit]

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

AWK[edit]

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

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

Axe[edit]

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

Iterative solution:

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

Babel[edit]

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

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

foo x < puts x in foo. In this case, x is the code list between the curly-braces. This is how you define callable code in Babel. The definition works by initializing the stack with 0, 1. On each iteration of the times loop, the function duplicates the top element. In the first iteration, this gives 0, 1, 1. Then it moves down the stack with the <- operator, giving 0, 1 again. It adds, giving 1. then it moves back up the stack, giving 1, 1. Then it swaps. On the next iteration this gives:

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

And so on. To test fib:

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

bash[edit]

Iterative[edit]

$ fib=1;j=1;while((fib<100));do echo $fib;((k=fib+j,fib=j,j=k));done
1
1
2
3
5
8
13
21
34
55
89

Recursive[edit]

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

BASIC[edit]

Applesoft BASIC[edit]

Same code as Commodore BASIC

Entering a value of N > 183, produces an error message:

?OVERFLOW ERROR IN 220

BASIC256[edit]

# Basic-256 ver 1.1.4
# iterative Fibonacci sequence
# Matches sequence A000045 in the OEIS, https://oeis.org/A000045/list

# Return the Nth Fibonacci number

input "N = ",f
limit = 500                        # set upper limit - can be changed, removed
f = int(f)
if f > limit then f = limit        
a = 0 : b = 1 : c = 0 : n = 0      # initial values


while n < f
    print n + chr(9) + c   # chr(9) = tab
    a = b
    b = c
    c = a + b  
    n += 1
        
end while

print " "
print n + chr(9) + c

Commodore BASIC[edit]

100 PRINT CHR$(147); CHR$(18); "****      FIBONACCI GENERATOR       ****"
110 INPUT "MIN, MAX"; N1, N2
120 IF N1 > N2 THEN T = N1: N1 = N2: N2 = T
130 A = 0: B = 1: S = SGN(N1)
140 FOR I = S TO N1 STEP S
150 : IF S > 0 THEN T = A + B: A = B: B = T
160 : IF S < 0 THEN T = B - A: B = A: A = T
170 NEXT I
180 PRINT
190 PRINT STR$(A); : REM STR$() PREVENTS TRAILING SPACE
200 IF N2 = N1 THEN 250
210 FOR I = N1 + 1 TO N2
220 : T = A + B: A = B: B = T
230 : PRINT ","; STR$(A);
240 NEXT I
250 PRINT
Output:
****      FIBONACCI GENERATOR       ****

MIN, MAX? -6,6

-8, 5,-3, 2,-1, 1, 0, 1, 1, 2, 3, 5, 8

READY.

Integer BASIC[edit]

Only works with quite small values of .

 10 INPUT N
 20 A=0
 30 B=1
 40 FOR I=2 TO N
 50 C=B
 60 B=A+B
 70 A=C
 80 NEXT I
 90 PRINT B
100 END

IS-BASIC[edit]

100 PROGRAM "Fibonac.bas"
110 FOR I=0 TO 20
120   PRINT "F";I,FIB(I)
130 NEXT
140 DEF FIB(N)
150   NUMERIC I
160   LET A=0:LET B=1
170   FOR I=1 TO N
180     LET T=A+B:LET A=B:LET B=T
190   NEXT
200   LET FIB=A
210 END DEF

QBasic[edit]

Works with: QBasic
Works with: FreeBASIC

Iterative[edit]

FUNCTION itFib (n)
    n1 = 0
    n2 = 1
    FOR k = 1 TO ABS(n)
        sum = n1 + n2
        n1 = n2
        n2 = sum
    NEXT k
    IF n < 0 THEN
        itFib = n1 * ((-1) ^ ((-n) + 1))
    ELSE
        itFib = n1
    END IF
END FUNCTION

Next version calculates each value once, as needed, and stores the results in an array for later retreival (due to the use of REDIM PRESERVE, it requires QuickBASIC 4.5 or newer):

DECLARE FUNCTION fibonacci& (n AS INTEGER)

REDIM SHARED fibNum(1) AS LONG

fibNum(1) = 1

'*****sample inputs*****
PRINT fibonacci(0)      'no calculation needed
PRINT fibonacci(13)     'figure F(2)..F(13)
PRINT fibonacci(-42)    'figure F(14)..F(42)
PRINT fibonacci(47)     'error: too big
'*****sample inputs*****

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

Recursive[edit]

This example can't handle n < 0.

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

Array (Table) Lookup[edit]

This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.)

DATA -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155
DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309
DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711
DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3
DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765
DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269
DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986
DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903

DIM fibNum(-46 TO 46) AS LONG

FOR n = -46 TO 46
    READ fibNum(n)
NEXT

'*****sample inputs*****
FOR n = -46 TO 46
    PRINT fibNum(n),
NEXT
PRINT
'*****sample inputs*****

QB64[edit]

Fibonacci from Russia

DIM F(80) AS DOUBLE 'FibRus.bas DANILIN
F(1) = 0: F(2) = 1
'OPEN "FibRus.txt" FOR OUTPUT AS #1
FOR i = 3 TO 80
    F(i) = F(i-1)+F(i-2)
NEXT i

FOR i = 1 TO 80
    f$ = STR$(F(i)): LF = 22 - LEN(f$)
    n$ = ""
    FOR j = 1 TO LF: n$ = " " + n$: NEXT
    f$ = n$ + f$
    PRINT i, f$: ' PRINT #1, i, f$
NEXT i
Output:
1                                 0
2                                 1
3                                 1
4                                 2
5                                 3
6                                 5
7                                 8
8                                13
9                                21
...
24                            28657
25                            46368
26                            75025
...
36                          9227465
37                         14930352
38                         24157817
...
48                       2971215073
49                       4807526976
50                       7778742049
...
60                     956722026041
61                    1548008755920
62                    2504730781961
...
76                 2111485077978050
77                 3416454622906707
78                 5527939700884757
79                 8944394323791464
80            1.447233402467622D+16

Sinclair ZX81 BASIC[edit]

Analytic[edit]

 10 INPUT N
 20 PRINT INT (0.5+(((SQR 5+1)/2)**N)/SQR 5)

Iterative[edit]

 10 INPUT N
 20 LET A=0
 30 LET B=1
 40 FOR I=2 TO N
 50 LET C=B
 60 LET B=A+B
 70 LET A=C
 80 NEXT I
 90 PRINT B

Tail recursive[edit]

 10 INPUT N
 20 LET A=0
 30 LET B=1
 40 GOSUB 70
 50 PRINT B
 60 STOP
 70 IF N=1 THEN RETURN
 80 LET C=B
 90 LET B=A+B
100 LET A=C
110 LET N=N-1
120 GOSUB 70
130 RETURN

Batch File[edit]

Recursive version

::fibo.cmd
@echo off
if "%1" equ "" goto :eof
call :fib %1
echo %errorlevel%
goto :eof

:fib
setlocal enabledelayedexpansion
if %1 geq 2 goto :ge2 
exit /b %1

:ge2
set /a r1 = %1 - 1
set /a r2 = %1 - 2
call :fib !r1!
set r1=%errorlevel%
call :fib !r2!
set r2=%errorlevel%
set /a r0 = r1 + r2
exit /b !r0!
Output:
>for /L %i in (1,5,20) do fibo.cmd %i

>fibo.cmd 1
1

>fibo.cmd 6
8

>fibo.cmd 11
89

>fibo.cmd 16
987

Battlestar[edit]

// Fibonacci sequence, recursive version
fun fibb
    loop
        a = funparam[0]
        break (a < 2)

        a--

        // Save "a" while calling fibb
        a -> stack

        // Set the parameter and call fibb
        funparam[0] = a
        call fibb

        // Handle the return value and restore "a"
        b = funparam[0]
        stack -> a

        // Save "b" while calling fibb again
        b -> stack

        a--

        // Set the parameter and call fibb
        funparam[0] = a
        call fibb

        // Handle the return value and restore "b"
        c = funparam[0]
        stack -> b

        // Sum the results
        b += c
        a = b

        funparam[0] = a

        break
    end
end

// vim: set syntax=c ts=4 sw=4 et:

BBC BASIC[edit]

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

bc[edit]

iterative[edit]

#! /usr/bin/bc -q

define fib(x) {
    if (x <= 0) return 0;
    if (x == 1) return 1;

    a = 0;
    b = 1;
    for (i = 1; i < x; i++) {
        c = a+b; a = b; b = c;
    }
    return c;
}
fib(1000)
quit

BCPL[edit]

get "libhdr"

let fib(n) = n<=1 -> n, valof
$(  let a=0 and b=1
    for i=2 to n
    $(  let c=a
        a := b
        b := a+c
    $)
    resultis b
$)

let start() be
    for i=0 to 10 do
        writef("F_%N*T= %N*N", i, fib(i))
Output:
F_0     = 0
F_1     = 1
F_2     = 1
F_3     = 2
F_4     = 3
F_5     = 5
F_6     = 8
F_7     = 13
F_8     = 21
F_9     = 34
F_10    = 55

beeswax[edit]

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

Example output:

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

julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i0

Fib(0)=0
Program finished!

julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i10
         
Fib(10)=55
Program finished!

julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i92

Fib(92)=7540113804746346429
Program finished!

julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i93
                                                                             
Fib(93)=12200160415121876738                                                 
Program finished!                                                            

julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i94                                                                 
                                                                             
Fib(94)=1293530146158671551                                                  
Program finished!

Befunge[edit]

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

BlitzMax[edit]

local a:int = 0, b:int = 1, c:int = 1, n:int

n = int(input( "Enter n: "))
if n = 0 then
    print 0
    end
else if n = 1
    print 1
    end
end if

while n>2
    a = b
    b = c
    c = a + b
    n = n - 1
wend
print c

Blue[edit]

: fib ( nth:ecx -- result:edi ) 1 0 
: compute ( times:ecx accum:eax scratch:edi -- result:edi ) xadd latest loop ;

: example ( -- ) 11 fib drop ;

BQN[edit]

All given functions return the nth element in the sequence.

Recursive[edit]

A primitive recursive can be done with predicates:

Fib ← {𝕩>1 ? (𝕊 𝕩-1) + 𝕊 𝕩-2; 𝕩}

Or, it can be done with the Choose() modifier:

Fib2 ← {(𝕩-1) (𝕩>1)◶⟨𝕩, +○𝕊⟩ 𝕩-2}

Iterative[edit]

An iterative solution can be made with the Repeat() modifier:

{⊑(+`⌽)⍟𝕩 0‿1}

Bracmat[edit]

Recursive[edit]

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

Iterative[edit]

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

Brainf***[edit]

Works with: Brainf*** version implementations with unbounded cell size

The first cell contains n (10), the second cell will contain fib(n) (55), and the third cell will contain fib(n-1) (34).

++++++++++
>>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]

The following generates n fibonacci numbers and prints them, though not in ascii. It does have a limit due to the cells usually being 1 byte in size.

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

	<<<<	Back to #1
		Non destructive add sequence using #3 as restore value
	[	Loop to add
		- > + > + <<	Subtract #1 and add to value #2 and restore space #3
	]
	>>
	[	Loop to restore #1 from #3
		- << + >>	Subtract from restore space #3 and add in #1
	]
	
	<< [-]	Clear #1
	>>>
	[	Loop to move #4 to #1
		- <<< + >>>	Subtract from #4 and add to #1
	]
	<<<<	Back to #0
]

Brat[edit]

Recursive[edit]

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

Tail Recursive[edit]

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

fibonacci = { x |
  fib_aux x, 1, 0
}

Memoization[edit]

cache = hash.new

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

Burlesque[edit]

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

C[edit]

Recursive[edit]

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

Iterative[edit]

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

Analytic[edit]

#include <tgmath.h>
#define PHI ((1 + sqrt(5))/2)

long long unsigned fib(unsigned n) {
    return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );
}

Generative[edit]

Translation of: Python
Works with: gcc version version 4.1.2 20080704 (Red Hat 4.1.2-44)
#include <stdio.h>
typedef enum{false=0, true=!0} bool;
typedef void iterator;

#include <setjmp.h>
/* declare label otherwise it is not visible in sub-scope */
#define LABEL(label) jmp_buf label; if(setjmp(label))goto label;
#define GOTO(label) longjmp(label, true)

/* the following line is the only time I have ever required "auto" */
#define FOR(i, iterator) { auto bool lambda(i); yield_init = (void *)&lambda; iterator; bool lambda(i)
#define DO {
#define     YIELD(x) if(!yield(x))return
#define     BREAK    return false
#define     CONTINUE return true
#define OD CONTINUE; } }

static volatile void *yield_init; /* not thread safe */
#define YIELDS(type) bool (*yield)(type) = yield_init

iterator fibonacci(int stop){
    YIELDS(int);
    int f[] = {0, 1};
    int i;
    for(i=0; i<stop; i++){
        YIELD(f[i%2]);
        f[i%2]=f[0]+f[1];
    }
}

main(){
  printf("fibonacci: ");
  FOR(int i, fibonacci(16)) DO
    printf("%d, ",i);
  OD;
  printf("...\n");
}
Output:
fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Fast method for a single large value[edit]

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

typedef struct node node;
struct node {
	int n;
	mpz_t v;
	node *next;
};

#define CSIZE 37
node *cache[CSIZE];

// very primitive linked hash table
node * find_cache(int n)
{
	int idx = n % CSIZE;
	node *p;

	for (p = cache[idx]; p && p->n != n; p = p->next);
	if (p) return p;

	p = malloc(sizeof(node));
	p->next = cache[idx];
	cache[idx] = p;

	if (n < 2) {
		p->n = n;
		mpz_init_set_ui(p->v, 1);
	} else {
		p->n = -1; // -1: value not computed yet
		mpz_init(p->v);
	}
	return p;
}

mpz_t tmp1, tmp2;
mpz_t *fib(int n)
{
	int x;
	node *p = find_cache(n);

	if (p->n < 0) {
		p->n = n;
		x = n / 2;

		mpz_mul(tmp1, *fib(x-1), *fib(n - x - 1));
		mpz_mul(tmp2, *fib(x), *fib(n - x));
		mpz_add(p->v, tmp1, tmp2);
	}
	return &p->v;
}

int main(int argc, char **argv)
{
	int i, n;
	if (argc < 2) return 1;

	mpz_init(tmp1);
	mpz_init(tmp2);

	for (i = 1; i < argc; i++) {
		n = atoi(argv[i]);
		if (n < 0) {
			printf("bad input: %s\n", argv[i]);
			continue;
		}

		// about 75% of time is spent in printing
		gmp_printf("%Zd\n", *fib(n));
	}
	return 0;
}
Output:
% ./a.out 0 1 2 3 4 5
1
1
2
3
5
8
% ./a.out 10000000 | wc -c    # count length of output, including the newline
1919488

C#[edit]

Recursive[edit]

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

Tail-Recursive[edit]

public static ulong Fib(uint n) {
    return Fib(0, 1, n);
}

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

Iterative[edit]

public static ulong Fib(uint x) {
    if (x == 0) return 0;

    ulong prev = 0;
    ulong next = 1;
    for (int i = 1; i < x; i++)
    {
        ulong sum = prev + next;
        prev = next;
        next = sum;
    }
    return next;
}

Eager-Generative[edit]

public static IEnumerable<long> Fibs(uint x) {
    IList<ulong> fibs = new List<ulong>();

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

Lazy-Generative[edit]

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

Analytic[edit]

This returns digits up to the 93rd Fibonacci number, but the digits become inaccurate past the 71st. There is custom rounding applied to the result that allows the function to be accurate at the 71st number instead of topping out at the 70th.

static double r5 = Math.Sqrt(5.0), Phi = (r5 + 1.0) / 2.0;

static ulong fib(uint n) {
    if (n > 71) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 72."); 
    double r = Math.Pow(Phi, n) / r5; 
    return (ulong)(n < 64 ? Math.Round(r) : Math.Floor(r)); }
To get to the 93rd Fibonacci number, one must use the decimal type, rather than the double type, like this:
static decimal Sqrt_dec(decimal x, decimal g) { decimal t, lg;
    do { t = x / g; lg = g; g = (t + g) / 2M; } while (lg != g);
    return g; }

static decimal Pow_dec (decimal bas, uint exp) {
    if (exp == 0) return 1M;
    decimal tmp = Pow_dec(bas, exp >> 1); tmp *= tmp;
    if ((exp & 1) == 1) tmp *= bas; return tmp; }

static decimal r5 = Sqrt_dec(5.0M, (decimal)Math.Sqrt(5.0)),
               Phi = (r5 + 1.0M) / 2.0M;

static ulong fib(uint n) {
    if (n > 93) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 94."); 
    decimal r = Pow_dec(Phi, n) / r5; 
    return (ulong)(n < 64 ? Math.Round(r) : Math.Floor(r)); }
Note that the Math.Pow() function and the Math.Sqrt() function must be replaced with ones returning the decimal type.

If one allows the fib() function to return the decimal type, one can reach the 138th Fibonacci number. However, the accuracy is lost after the 128th.
static decimal Sqrt_dec(decimal x, decimal g) { decimal t, lg;
    do { t = x / g; lg = g; g = (t + g) / 2M; } while (lg != g);
    return g; }

static decimal Pow_dec (decimal bas, uint exp) {
    if (exp == 0) return 1M;
    decimal tmp = Pow_dec(bas, exp >> 1); tmp *= tmp;
    if ((exp & 1) == 1) tmp *= bas; return tmp; }

static decimal r5 = Sqrt_dec(5.0M, (decimal)Math.Sqrt(5.0)),
               Phi = (r5 + 1.0M) / 2.0M;

static decimal fib(uint n) {
    if (n > 128) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 129."); 
    decimal r = Pow_dec(Phi, n) / r5; 
    return n < 64 ? Math.Round(r) : Math.Floor(r); }

Matrix[edit]

Algorithm is based on

.

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

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

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

private static Matrix M;
private static readonly Matrix N = new Matrix(1,1,1,0);

public static ulong Fib(uint n) {
    M = new Matrix(1,0,0,1);
    MatrixPow(n-1);
    return (ulong)M[0][0];
}

private static void MatrixPow(double n){
    if (n > 1) {
        MatrixPow(n/2);
        M *= M;
    }
    if (n % 2 == 0) M *= N;
}

Array (Table) Lookup[edit]

private static int[] fibs = new int[]{ -1836311903, 1134903170, 
  -701408733, 433494437, -267914296, 165580141, -102334155, 
  63245986, -39088169, 24157817, -14930352, 9227465, -5702887, 
  3524578, -2178309, 1346269, -832040, 514229, -317811, 196418, 
  -121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181, 
  -2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13, 
  -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 
  144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
  28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
  1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
  39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
  701408733, 1134903170, 1836311903};

public static int Fib(int n) {
    if(n < -46 || n > 46) throw new ArgumentOutOfRangeException("n", n, "Has to be between -46 and 47.")
    return fibs[n+46];
}

Arbitrary Precision[edit]

This large step recurrence routine can calculate the two millionth Fibonacci number in under 1 / 5 second at tio.run. This routine can generate the fifty millionth Fibonacci number in under 30 seconds at tio.run. The unused conventional iterative method times out at two million on tio.run, you can only go to around 1,290,000 or so to keep the calculation time (plus string conversion time) under the 60 second timeout limit there. When using this large step recurrence method, it takes around 5 seconds to convert the two millionth Fibonacci number (417975 digits) into a string (so that one may count those digits).

using System;
using System.Collections.Generic;
using BI = System.Numerics.BigInteger;
 
class Program
{
    // A sparse array of values calculated along the way
    static SortedList<int, BI> sl = new SortedList<int, BI>();
 
    // This routine is semi-recursive, but doesn't need to evaluate every number up to n.
    // Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
    static BI Fsl(int n)
    {
        if (n < 2) return n;
        int n2 = n >> 1, pm = n2 + ((n & 1) << 1) - 1; IfNec(n2); IfNec(pm);
        return n2 > pm ? (2 * sl[pm] + sl[n2]) * sl[n2] : sqr(sl[n2]) + sqr(sl[pm]);
        // Helper routine for Fsl(). It adds an entry to the sorted list when necessary
        void IfNec(int x) { if (!sl.ContainsKey(x)) sl.Add(x, Fsl(x)); }
        // Helper function to square a BigInteger
        BI sqr(BI x) { return x * x; }
    }
 
    // Conventional iteration method (not used here)
    public static BI Fm(BI n)
    {
        if (n < 2) return n; BI cur = 0, pre = 1;
        for (int i = 0; i <= n - 1; i++) { BI sum = cur + pre; pre = cur; cur = sum; }
        return cur;
    }
 
    public static void Main()
    {
        int num = 2_000_000, digs = 35, vlen;
        var sw = System.Diagnostics.Stopwatch.StartNew(); var v = Fsl(num); sw.Stop();
        Console.Write("{0:n3} ms to calculate the {1:n0}th Fibonacci number, ",
          sw.Elapsed.TotalMilliseconds, num);
        Console.WriteLine("number of digits is {0}", vlen = (int)Math.Ceiling(BI.Log10(v)));
        if (vlen < 10000) {
            sw.Restart(); Console.WriteLine(v); sw.Stop();
            Console.WriteLine("{0:n3} ms to write it to the console.", sw.Elapsed.TotalMilliseconds);
        } else
            Console.Write("partial: {0}...{1}", v / BI.Pow(10, vlen - digs), v % BI.Pow(10, digs));
    }
}
Output:
137.209 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975
partial: 85312949175076415430516606545038251...91799493108960825129188777803453125

Shift PowerMod[edit]

Illustrated here is an algorithm to compute a Fibonacci number directly, without needing to calculate any of the Fibonacci numbers less than the desired result. It uses shifting and the power mod function (BigInteger.ModPow() in C#). It calculates more quickly than the large step recurrence routine (illustrated above) for smaller Fibonacci numbers (less than 2800 digits or so, around Fibonacci(13000)), but gets slower for larger ones, as the intermediate BigIntegers created are very large, much larger than the Fibonacci result.

Also included is a routine that returns an array of Fibonacci numbers (fibTab()). It reuses the intermediate large shifted BigIntegers on suceeding iterations, therfore it is a little more efficient than calling the oneshot (oneFib()) routine repeatedly from a loop.

using System;
using BI = System.Numerics.BigInteger;

class Program {
  
  // returns the nth Fibonacci number without calculating 0..n-1
  static BI oneFib(int n) {
    BI z = (BI)1 << ++n;
    return BI.ModPow(z, n, (z << n) - z - 1) % z;
  }

  // returns an array of Fibonacci numbers from the 0th to the nth
  static BI[] fibTab(int n) {
    var res = new BI[++n];
    BI z = (BI)1 << 1, zz = z << 1;
    for (int i = 0; i < n; ) {
      res[i] = BI.ModPow(z, ++i, zz - z - 1) % z;
      z <<= 1; zz <<= 2;
    }
    return res;
  }
  
  static void Main(string[] args) {
    int n = 20;
    Console.WriteLine("Fibonacci numbers 0..{0}: {1}", n, string.Join(" ",fibTab(n)));
    n = 1000;
    Console.WriteLine("Fibonacci({0}): {1}", n, oneFib(n));
  }
}
Output:
Fibonacci numbers 0..20: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Fibonacci(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

C++[edit]

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

#include <iostream>

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

        return 0;
}


Library: GMP

This version does not have an upper bound.

#include <iostream>
#include <gmpxx.h>

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

Version using transform:

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

Far-fetched version using adjacent_difference:

#include <numeric>
#include <vector>
#include <functional>
#include <iostream>

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

Version which computes at compile time with metaprogramming:

#include <iostream>

template <int n> struct fibo
{
    enum {value=fibo<n-1>::value+fibo<n-2>::value};
};
 
template <> struct fibo<0>
{
    enum {value=0};
};

template <> struct fibo<1>
{
    enum {value=1};
};


int main(int argc, char const *argv[])
{
    std::cout<<fibo<12>::value<<std::endl;
    std::cout<<fibo<46>::value<<std::endl;
    return 0;
}

The following version is based on fast exponentiation:

#include <iostream>

inline void fibmul(int* f, int* g)
{
  int tmp = f[0]*g[0] + f[1]*g[1];
  f[1] = f[0]*g[1] + f[1]*(g[0] + g[1]);
  f[0] = tmp;
}

int fibonacci(int n)
{
  int f[] = { 1, 0 };
  int g[] = { 0, 1 };
  while (n > 0)
  {
    if (n & 1) // n odd
    {
      fibmul(f, g);
      --n;
    }
    else
    {
      fibmul(g, g);
      n >>= 1;
    }
  }
  return f[1];
}

int main()
{
  for (int i = 0; i < 20; ++i)
    std::cout << fibonacci(i) << " ";
  std::cout << std::endl;
}
Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Using Zeckendorf Numbers[edit]

The nth fibonacci is represented as Zeckendorf 1 followed by n-1 zeroes. Here I define a class N which defines the operations increment ++() and comparison <=(other N) for Zeckendorf Numbers.

// Use Zeckendorf numbers to display Fibonacci sequence.
// Nigel Galloway October 23rd., 2012
int main(void) {
  char NG[22] = {'1',0};
  int x = -1;
  N G;
  for (int fibs = 1; fibs <= 20; fibs++) {
   for (;G <= N(NG); ++G) x++;
   NG[fibs] = '0';
   NG[fibs+1] = 0;
   std::cout << x << " ";
  }
  std::cout << std::endl;
  return 0;
}
Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946

Using Standard Template Library[edit]

Possibly less "Far-fetched version".

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

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

Cat[edit]

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

Chapel[edit]

iter fib() {
        var a = 0, b = 1;

        while true {
                yield a;
                (a, b) = (b, b + a);
        }
}

Chef[edit]

Stir-Fried Fibonacci Sequence.

An unobfuscated iterative implementation.
It prints the first N + 1 Fibonacci numbers,
where N is taken from standard input.

Ingredients.
0 g last
1 g this
0 g new
0 g input

Method.
Take input from refrigerator.
Put this into 4th mixing bowl.
Loop the input.
Clean the 3rd mixing bowl.
Put last into 3rd mixing bowl.
Add this into 3rd mixing bowl.
Fold new into 3rd mixing bowl.
Clean the 1st mixing bowl.
Put this into 1st mixing bowl.
Fold last into 1st mixing bowl.
Clean the 2nd mixing bowl.
Put new into 2nd mixing bowl.
Fold this into 2nd mixing bowl.
Put new into 4th mixing bowl.
Endloop input until looped.
Pour contents of the 4th mixing bowl into baking dish.

Serves 1.

Clio[edit]

Clio is pure and functions are lazy and memoized by default

fn fib n:
  if n < 2: n
  else: (n - 1 -> fib) + (n - 2 -> fib)

[0:100] -> * fib -> * print

Clojure[edit]

Lazy Sequence[edit]

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

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

Thus to get the nth one:

(nth (fibs) 5)

So long as one does not hold onto the head of the sequence, this is unconstrained by length.

The one-line implementation may look confusing at first, but on pulling it apart it actually solves the problem more "directly" than a more explicit looping construct.

(defn fibs []
  (map first ;; throw away the "metadata" (see below) to view just the fib numbers
       (iterate ;; create an infinite sequence of [prev, curr] pairs
         (fn [[a b]] ;; to produce the next pair, call this function on the current pair
           [b (+ a b)]) ;; new prev is old curr, new curr is sum of both previous numbers
         [0 1]))) ;; recursive base case: prev 0, curr 1

A more elegant solution is inspired by the Haskell implementation of an infinite list of Fibonacci numbers:

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

Then, to see the first ten,

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

Iterative[edit]

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

;; max is which fib number you'd like computed (0th, 1st, 2nd, etc.)
;; n is which fib number you're on for this call (0th, 1st, 2nd, etc.)
;; j is the nth fib number (ex. when n = 5, j = 5)
;; i is the nth - 1 fib number
(defn- fib-iter
  [max n i j]
  (if (= n max)
    j
    (recur max
           (inc n)
           j
           (+ i j))))

(defn fib
  [max]
  (if (< max 2)
    max
    (fib-iter max 1 0N 1N)))

"defn-" means that the function is private (for use only inside this library). The "N" suffixes on integers tell Clojure to use arbitrary precision ints for those.

Doubling Algorithm (Fast)[edit]

Based upon the doubling algorithm which computes in O(log (n)) time as described here https://www.nayuki.io/page/fast-fibonacci-algorithms Implementation credit: https://stackoverflow.com/questions/27466311/how-to-implement-this-fast-doubling-fibonacci-algorithm-in-clojure/27466408#27466408

(defn fib [n]
  (letfn [(fib* [n]
            (if (zero? n)
              [0 1]
              (let [[a b] (fib* (quot n 2))
                    c (*' a (-' (*' 2 b) a))
                    d (+' (*' b b) (*' a a))]
                (if (even? n)
                  [c d]
                  [d (+' c d)]))))]
    (first (fib* n))))

Recursive[edit]

A naive slow recursive solution:

(defn fib [n]
  (case n
    0 0
    1 1
    (+ (fib (- n 1))
       (fib (- n 2)))))

This can be improved to an O(n) solution, like the iterative solution, by memoizing the function so that numbers that have been computed are cached. Like a lazy sequence, this also has the advantage that subsequent calls to the function use previously cached results rather than recalculating.

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

Using core.async[edit]

(ns fib.core)
(require '[clojure.core.async
           :refer [<! >! >!! <!! timeout chan alt! go]])

(defn fib [c]
  (loop [a 0 b 1]
    (>!! c a)
    (recur b (+ a b))))


(defn -main []
  (let [c (chan)]
    (go (fib c))
    (dorun
      (for [i (range 10)]
        (println (<!! c))))))

CLU[edit]

% Generate Fibonacci numbers
fib = iter () yields (int)
    a: int := 0
    b: int := 1
    
    while true do
        yield (a)
        a, b := b, a+b
    end
end fib

% Grab the n'th value from an iterator 
nth = proc [T: type] (g: itertype () yields (T), n: int) returns (T)
    for v: T in g() do
        if n<=0 then return (v) end
        n := n-1
    end
end nth

% Print a few values
start_up = proc ()
    po: stream := stream$primary_output()
    
    % print values coming out of the fibonacci iterator
    % (which are generated one after the other without delay)
    count: int := 0
    for f: int in fib() do 
        stream$putl(po, "F(" || int$unparse(count) || ") = " || int$unparse(f))
        count := count + 1
        if count = 15 then break end
    end
    
    % print a few random fibonacci numbers
    % (to do this it has to restart at the beginning for each 
    % number, making it O(N))
    fibs: sequence[int] := sequence[int]$[20,30,50]
    for n: int in sequence[int]$elements(fibs) do
        stream$putl(po, "F(" || int$unparse(n) || ") = "
                             || int$unparse(nth[int](fib, n)))
    end
end start_up
Output:
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55
F(11) = 89
F(12) = 144
F(13) = 233
F(14) = 377
F(20) = 6765
F(30) = 832040
F(50) = 12586269025

CMake[edit]

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

set_property(GLOBAL PROPERTY fibonacci_0 0)
set_property(GLOBAL PROPERTY fibonacci_1 1)
set_property(GLOBAL PROPERTY fibonacci_next 2)

# var = nth number in Fibonacci sequence.
function(fibonacci var n)
  # If the sequence is too short, compute more Fibonacci numbers.
  get_property(next GLOBAL PROPERTY fibonacci_next)
  if(NOT next GREATER ${n})
    # a, b = last 2 Fibonacci numbers
    math(EXPR i "${next} - 2")
    get_property(a GLOBAL PROPERTY fibonacci_${i})
    math(EXPR i "${next} - 1")
    get_property(b GLOBAL PROPERTY fibonacci_${i})

    while(NOT next GREATER ${n})
      math(EXPR i "${a} + ${b}")  # i = next Fibonacci number
      set_property(GLOBAL PROPERTY fibonacci_${next} ${i})
      set(a ${b})
      set(b ${i})
      math(EXPR next "${next} + 1")
    endwhile()
    set_property(GLOBAL PROPERTY fibonacci_next ${next})
  endif()

  get_property(answer GLOBAL PROPERTY fibonacci_${n})
  set(${var} ${answer} PARENT_SCOPE)
endfunction(fibonacci)
# Test program: print 0th to 9th and 25th to 30th Fibonacci numbers.
set(s "")
foreach(i RANGE 0 9)
  fibonacci(f ${i})
  set(s "${s} ${f}")
endforeach(i)
set(s "${s} ... ")
foreach(i RANGE 25 30)
  fibonacci(f ${i})
  set(s "${s} ${f}")
endforeach(i)
message(${s})
 0 1 1 2 3 5 8 13 21 34 ... 75025 121393 196418 317811 514229 832040

COBOL[edit]

Iterative[edit]

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

Recursive[edit]

Works with: GNU Cobol version 2.0
       >>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci-main.

DATA DIVISION.
WORKING-STORAGE SECTION.
01  num                                 PIC 9(6) COMP.
01  fib-num                             PIC 9(6) COMP.

PROCEDURE DIVISION.
    ACCEPT num
    CALL "fibonacci" USING CONTENT num RETURNING fib-num
    DISPLAY fib-num
    .
END PROGRAM fibonacci-main.

IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci RECURSIVE.

DATA DIVISION.
LOCAL-STORAGE SECTION.
01  1-before                            PIC 9(6) COMP.
01  2-before                            PIC 9(6) COMP.

LINKAGE SECTION.
01  num                                 PIC 9(6) COMP.

01  fib-num                             PIC 9(6) COMP BASED.

PROCEDURE DIVISION USING num RETURNING fib-num.
    ALLOCATE fib-num
    EVALUATE num
        WHEN 0
            MOVE 0 TO fib-num
        WHEN 1
            MOVE 1 TO fib-num
        WHEN OTHER
            SUBTRACT 1 FROM num
            CALL "fibonacci" USING CONTENT num RETURNING 1-before
            SUBTRACT 1 FROM num
            CALL "fibonacci" USING CONTENT num RETURNING 2-before
            ADD 1-before TO 2-before GIVING fib-num
    END-EVALUATE
    .
END PROGRAM fibonacci.

CoffeeScript[edit]

Analytic[edit]

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

Iterative[edit]

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

Recursive[edit]

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

Comefrom0x10[edit]

Recursion is is not possible in Comefrom0x10.

Iterative[edit]

stop = 6
a = 1
i = 1  # start
a      # print result

fib
  comefrom if i is 1  # start
  b = 1
  comefrom fib        # start of loop
  i = i + 1
  next_b = a + b
  a = b
  b = next_b

  comefrom fib if i > stop

Common Lisp[edit]

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

Iterative[edit]

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

Simpler one:

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

Recursive[edit]

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


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

Tail recursive and squaring:

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

(print (fib 100000))

Alternate solution[edit]

I use Allegro CL 10.1

;; Project : Fibonacci sequence

(defun fibonacci (nr)
           (cond ((= nr 0) 1)
           ((= nr 1) 1)
           (t (+ (fibonacci (- nr 1))
           (fibonacci (- nr 2))))))
(format t "~a" "First 10 Fibonacci numbers") 
(dotimes (n 10) 
(if (< n 1) (terpri))
(if (< n 9) (format t "~a" " "))
(write(+ n 1)) (format t "~a" ": ")
(write (fibonacci n)) (terpri))

Output:

First 10 Fibonacci numbers
 1: 1
 2: 1
 3: 2
 4: 3
 5: 5
 6: 8
 7: 13
 8: 21
 9: 34
10: 55

Solution with methods and eql specializers[edit]

(defmethod fib (n)
  (declare ((integer 0 *) n))
  (+ (fib (- n 1))
     (fib (- n 2))))

(defmethod fib ((n (eql 0))) 0)

(defmethod fib ((n (eql 1))) 1)

List-based iterative[edit]

This solution uses a list to keep track of the Fibonacci sequence for 0 or a positive integer.

(defun fibo (n)
  (cond ((< n 0) nil)
        ((< n 2) n)
        (t (let ((leo '(1 0)))
             (loop for i from 2 upto n do
               (setf leo (cons (+ (first leo) 
                                  (second leo))
                               leo))
               finally (return (first leo)))))))
Output:
> (fibo 0)
0
> (fibo 1)
1
> (fibo 10)
55
> (fibo 100)
354224848179261915075
> (fibo 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
> (fibo -10)
NIL

List-based recursive[edit]

This solution computes Fibonacci numbers as either:

  1. a list starting from the first element;
  2. a single number;
  3. an interval from i-th to j-th element.


Options #2 and #3 can take negative parameters, but i (lowest index in range) must be greater than j (highest index in range).

Values are represented internally by a reversed list that grows from the head (and that's why we reverse it back when we return it).

(defparameter *fibo-start* '(1 1)) ; elements 1 and 2

;;; Helper functions
(defun grow-fibo (fibo)
    (cons (+ (first fibo) (second fibo)) fibo))

(defun generate-fibo (fibo n) ; n must be > 1
    (if (equal (list-length fibo) n)
        fibo
        (generate-fibo (grow-fibo fibo)  n)))

;;; User functions
(defun fibo (n)
    (cond ((= n 0) 0)
          ((= (abs n) 1) 1)
          (t (let ((result (first (generate-fibo *fibo-start* (abs n)))))
               (if (and (< n -1) (evenp n))
                 (- result)
                 result)))))

(defun fibo-list (n)
    (cond ((< n 1) nil)
          ((= n 1) '(1))
          (t (reverse (generate-fibo *fibo-start* n)))))

(defun fibo-range (lower upper)
   (if (<= upper lower)
     nil
     (reverse (generate-fibo
                 (list
                    (fibo (1+ lower))
                    (fibo  lower))
                 (1+ (- upper lower))))))
Output:
> (fibo 100)
354224848179261915075
> (fibo -150)
-9969216677189303386214405760200
> (fibo-list 20)
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
> (fibo-range -10 15)
(-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)
> (fibo-range 0 20)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Computer/zero Assembly[edit]

To find the th Fibonacci number, set the initial value of count equal to –2 and run the program. The machine will halt with the answer stored in the accumulator. Since Computer/zero's word length is only eight bits, the program will not work with values of greater than 13.

loop:   LDA  y      ; higher No.
        STA  temp
        ADD  x      ; lower No.
        STA  y
        LDA  temp
        STA  x

        LDA  count
        SUB  one
        BRZ  done

        STA  count
        JMP  loop

done:   LDA  y
        STP

one:         1
count:       8      ; n = 10
x:           1
y:           1
temp:        0

Corescript[edit]

print Fibonacci Sequence:
var previous = 1
var number = 0
var temp = (blank)

:fib
if number > 50000000000:kill
print (number)
set temp = (add number previous)
set previous = (number)
set number = (temp)
goto fib

:kill
stop

Cowgol[edit]

include "cowgol.coh";

sub fibonacci(n: uint32): (a: uint32) is
    a := 0;
    var b: uint32 := 1;
    while n > 0 loop
        var c := a + b;
        a := b;
        b := c;
        n := n - 1;
    end loop;
end sub;

# test
var i: uint32 := 0;
while i < 20 loop
    print_i32(fibonacci(i));
    print_char(' ');
    i := i + 1;
end loop;
print_nl();
Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Crystal[edit]

Recursive[edit]

def fib(n)
  n < 2 ? n : fib(n - 1) + fib(n - 2)
end

Iterative[edit]

def fibIterative(n, prevFib = 0, fib = 1)
  return n if n < 2

  n.times do
    prevFib, fib = fib, prevFib + fib
  end

  prevFib
end

Tail Recursive[edit]

def fibTailRecursive(n, prevFib = 0, fib = 1)
  n == 0 ? prevFib : fibTailRecursive(n - 1, fib, prevFib + fib)
end

Analytic[edit]

def fibBinet(n)
  (((5 ** 0.5 + 1) / 2) ** n / 5 ** 0.5).round.to_i
end

D[edit]

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

import std.stdio, std.conv, std.algorithm, std.math;

long sgn(alias unsignedFib)(int n) { // break sign manipulation apart
    immutable uint m = (n >= 0) ? n : -n;
    if (n < 0 && (n % 2 == 0))
        return -unsignedFib(m);
    else
        return unsignedFib(m);
}

long fibD(uint m) { // Direct Calculation, correct for abs(m) <= 84
    enum sqrt5r =  1.0L / sqrt(5.0L);         //  1 / sqrt(5)
    enum golden = (1.0L + sqrt(5.0L)) / 2.0L; // (1 + sqrt(5)) / 2
    return roundTo!long(pow(golden, m) * sqrt5r);
}

long fibI(in uint m) pure nothrow { // Iterative
    long thisFib = 0;
    long nextFib = 1;
    foreach (i; 0 .. m) {
        long tmp = nextFib;
        nextFib += thisFib;
        thisFib  = tmp;
    }
    return thisFib;
}

long fibR(uint m) { // Recursive
    return (m < 2) ? m : fibR(m - 1) + fibR(m - 2);
}

long fibM(uint m) { // memoized Recursive
    static long[] fib = [0, 1];
    while (m >= fib.length )
        fib ~= fibM(m - 2) + fibM(m - 1);
    return fib[m];
}

alias sgn!fibD sfibD;
alias sgn!fibI sfibI;
alias sgn!fibR sfibR;
alias sgn!fibM sfibM;

auto fibG(in int m) { // generator(?)
    immutable int sign = (m < 0) ? -1 : 1;
    long yield;
    
    return new class {
        final int opApply(int delegate(ref int, ref long) dg) {
            int idx = -sign; // prepare for pre-increment
            foreach (f; this)
                if (dg(idx += sign, f))
                    break;
            return 0;
        }
        
        final int opApply(int delegate(ref long) dg) {
            long f0, f1 = 1;
            foreach (p; 0 .. m * sign + 1) {
                if (sign == -1 && (p % 2 == 0))
                    yield = -f0;
                else
                    yield = f0;
                if (dg(yield)) break;
                auto temp = f1;
                f1 = f0 + f1;
                f0 = temp;
            }
            return 0;
        }
    };
}

void main(in string[] args) {
    int k = args.length > 1 ? to!int(args[1]) : 10;
    writefln("Fib(%3d) = ", k);
    writefln("D : %20d <- %20d + %20d",
             sfibD(k), sfibD(k - 1), sfibD(k - 2));
    writefln("I : %20d <- %20d + %20d",
             sfibI(k), sfibI(k - 1), sfibI(k - 2));
    if (abs(k) < 36 || args.length > 2)
        // set a limit for recursive version
        writefln("R : %20d <- %20d + %20d",
                 sfibR(k), sfibM(k - 1), sfibM(k - 2));
    writefln("O : %20d <- %20d + %20d",
             sfibM(k), sfibM(k - 1), sfibM(k - 2));
    foreach (i, f; fibG(-9))
        writef("%d:%d | ", i, f);
}
Output:
for n = 85
Fib( 85) = 
D :   259695496911122586 <-   160500643816367088 +    99194853094755497
I :   259695496911122585 <-   160500643816367088 +    99194853094755497
O :   259695496911122585 <-   160500643816367088 +    99194853094755497
0:0 | -1:1 | -2:-1 | -3:2 | -4:-3 | -5:5 | -6:-8 | -7:13 | -8:-21 | -9:34 | 

Matrix Exponentiation Version[edit]

import std.bigint;

T fibonacciMatrix(T=BigInt)(size_t n) {
    int[size_t.sizeof * 8] binDigits;
    size_t nBinDigits;
    while (n > 0) {
        binDigits[nBinDigits] = n % 2;
        n /= 2;
        nBinDigits++;
    }

    T x=1, y, z=1;
    foreach_reverse (b; binDigits[0 .. nBinDigits]) {
        if (b) {
            x = (x + z) * y;
            y = y ^^ 2 + z ^^ 2;
        } else {
            auto x_old = x;
            x = x ^^ 2 + y ^^ 2;
            y = (x_old + z) * y;
        }
        z = x + y;
    }

    return y;
}

void main() {
    10_000_000.fibonacciMatrix;
}

Faster Version[edit]

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

import std.bigint, std.math;

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

void main() {
    10_000_000.fibonacci;
}

Dart[edit]

int fib(int n) {
  if (n==0 || n==1) {
    return n;
  }
  var prev=1;
  var current=1;
  for (var i=2; i<n; i++) {
    var next = prev + current;
    prev = current;
    current = next;    
  }
  return current;
}

int fibRec(int n) => n==0 || n==1 ? n : fibRec(n-1) + fibRec(n-2);

main() {
  print(fib(11));
  print(fibRec(11));
}

Datalog[edit]

Simple recurive implementation for Souffle.

.decl Fib(i:number, x:number)
Fib(0, 0). 
Fib(1, 1). 
Fib(i+2,x+y) :- Fib(i+1, x), Fib(i, y), i+2<=40, i+2>=2.
Fib(i-2,y-x) :- Fib(i-1, x), Fib(i, y), i-2>=-40, i-2<0.

DBL[edit]

;
;       Fibonacci sequence for DBL version 4 by Dario B.
;
        RECORD

FIB1,  D10
FIB2,  D10
FIBN,  D10

J,     D5
A2,    A2
A5,    A5
                                PROC
;----------------------------------------------------------------
        XCALL FLAGS (0007000000,1)         ;Suppress STOP message

        OPEN (1,O,'TT:')
        DISPLAY (1,'First 10 Fibonacci Numbers:',10)
 
        FIB2=1

        FOR J=1 UNTIL 10
        DO BEGIN
                FIBN=FIB1+FIB2

                A2=J,'ZX'
                A5=FIBN,'ZZZZX'
                DISPLAY (1,A2,' : ',A5,10)

                FIB1=FIB2
                FIB2=FIBN
            END
 
        CLOSE 1
END

Dc[edit]

This needs a modern Dc with r (swap) and # (comment). It easily can be adapted to an older Dc, but it will impact readability a lot.

[               # todo: n(<2) -- 1 and break 2 levels
  d -           # 0
  1 +           # 1
  q
] s1

[               # todo: n(>-1) -- F(n)
  d 0=1         # n(!=0)
  d 1=1         # n(!in {0,1})
  2 - d 1 +     # (n-2) (n-1)
  lF x          # (n-2) F(n-1)
  r             # F(n-1) (n-2)
  lF x          # F(n-1)+F(n-2)
  +
] sF

33 lF x f
Output:
5702887

Delphi[edit]

Iterative[edit]

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

Recursive[edit]

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

Matrix[edit]

Algorithm is based on

.
function fib(n: Int64): Int64;

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

var 
  matrix: TFibMat;
	
begin
  matrix[0,0] := 1;
  matrix[0,1] := 1;
  matrix[1,0] := 1;
  matrix[1,1] := 0;
  if n > 1 then
    matrix := fibmatexp(matrix,n-1);
  fib := matrix[0,0];
end;

DIBOL-11[edit]

      START    ;First 10 Fibonacci NUmbers


      RECORD
              FIB1,    D10,   0
              FIB2,    D10,   1
              FIBNEW,  D10
              LOOPCNT, D2,    1

       RECORD HEADER
,            A32, "First 10 Fibonacci Numbers."

       RECORD OUTPUT
             LOOPOUT, A2
,         A3, " : "
              FIBOUT, A10

      PROC

      OPEN(8,O,'TT:')

      WRITES(8,HEADER)

     LOOP,
             FIBNEW = FIB1 + FIB2
             LOOPOUT = LOOPCNT, 'ZX'
             FIBOUT = FIBNEW, 'ZZZZZZZZZX'

             WRITES(8,OUTPUT)

             FIB1 = FIB2
             FIB2 = FIBNEW
             
             LOOPCNT = LOOPCNT + 1
             IF LOOPCNT .LE. 10 GOTO LOOP

             CLOSE 8
             END

DWScript[edit]

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

Dyalect[edit]

func fib(n) {
    if n < 2 {
        return n
    } else {
        return fib(n - 1) + fib(n - 2)
    }
}

print(fib(30))

E[edit]

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

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

EasyLang[edit]

func fib n . res .
  if n < 2
    res = n
  .
  prev = 0
  val = 1
  for _ range n - 1
    res = prev + val
    prev = val
    val = res
  .
.
call fib 36 r
print r

Recursive (inefficient):

func fib n . res .
  if n < 2
    res = n
  else
    call fib n - 1 a 
    call fib n - 2 b 
    res = a + b
  .
.
call fib 36 r
print r

EchoLisp[edit]

Use memoization with the recursive version.

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

(remember 'fib #(0 1))

(for ((i 12)) (write (fib i)))
0 1 1 2 3 5 8 13 21 34 55 89

ECL[edit]

Analytic[edit]

//Calculates Fibonacci sequence up to n steps using Binet's closed form solution


FibFunction(UNSIGNED2 n) := FUNCTION
	REAL Sqrt5 := Sqrt(5); 
	REAL Phi := (1+Sqrt(5))/2;
	REAL Phi_Inv := 1/Phi; 
	UNSIGNED FibValue := ROUND( ( POWER(Phi,n)-POWER(Phi_Inv,n) ) /Sqrt5); 
	RETURN FibValue; 
	END;  

 FibSeries(UNSIGNED2 n) := FUNCTION
 
 Fib_Layout := RECORD
 UNSIGNED5 FibNum;
 UNSIGNED5 FibValue; 
 END; 
 
 FibSeq := DATASET(n+1,
  TRANSFORM 
 ( Fib_Layout 
 , SELF.FibNum := COUNTER-1
 , SELF.FibValue := IF(SELF.FibNum<2,SELF.FibNum, FibFunction(SELF.FibNum) )
 ) 
 ); 
 
 RETURN FibSeq; 
 
 END; }

EDSAC order code[edit]

This program calculates the nth—by default the tenth—number in the Fibonacci sequence and displays it (in binary) in the first word of storage tank 3.

[ Fibonacci sequence
  ==================
  
  A program for the EDSAC
  
  Calculates the nth Fibonacci
  number and displays it at the
  top of storage tank 3
  
  The default value of n is 10
  
  To calculate other Fibonacci
  numbers, set the starting value
  of the count to n-2
  
  Works with Initial Orders 2 ]


        T56K  [ set load point  ]
        GK    [ set theta       ]
        
[ Orders ]

[  0 ]  T20@  [ a = 0           ]
        A17@  [ a += y          ]
        U18@  [ temp = a        ]
        A16@  [ a += x          ]
        T17@  [ y = a; a = 0    ]
        A18@  [ a += temp       ]
        T16@  [ x = a; a = 0    ]
        
        A19@  [ a = count       ]
        S15@  [ a -= 1          ]
        U19@  [ count = a       ]
        E@    [ if a>=0 go to θ ]
        
        T20@  [ a = 0           ]
        A17@  [ a += y          ]
        T96F  [ C(96) = a; a = 0]
        
        ZF    [ halt ]
        
[ Data ]
        
[ 15 ]  P0D   [ const: 1        ]
[ 16 ]  P0F   [ var: x = 0      ]
[ 17 ]  P0D   [ var: y = 1      ]
[ 18 ]  P0F   [ var: temp = 0   ]
[ 19 ]  P4F   [ var: count = 8  ]
[ 20 ]  P0F   [ used to clear a ]

        EZPF  [ begin execution ]
Output:
00000000000110111

Eiffel[edit]

class
	APPLICATION

create
	make

feature

	fibonacci (n: INTEGER): INTEGER
		require
			non_negative: n >= 0
		local
			i, n2, n1, tmp: INTEGER
		do
			n2 := 0
			n1 := 1
			from
				i := 1
			until
				i >= n
			loop
				tmp := n1
				n1 := n2 + n1
				n2 := tmp
				i := i + 1
			end
			Result := n1
			if n = 0 then
				Result := 0
			end
		end

feature {NONE} -- Initialization

	make
			-- Run application.
		do
			print (fibonacci (0))
			print (" ")
			print (fibonacci (1))
			print (" ")
			print (fibonacci (2))
			print (" ")
			print (fibonacci (3))
			print (" ")
			print (fibonacci (4))
			print ("%N")
		end

end

Ela[edit]

Tail-recursive function:

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

Infinite (lazy) list:

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

Elena[edit]

Translation of: Smalltalk

ELENA 5.0 :

import extensions;
 
fibu(n)
{
    int[] ac := new int[]{ 0,1 };
    if (n < 2) 
    {
        ^ ac[n] 
    }
    else
    {
        for(int i := 2, i <= n, i+=1)
        {
            int t := ac[1];
            ac[1] := ac[0] + ac[1];
            ac[0] := t
        };
 
        ^ ac[1]
    }
}
 
public program()
{
    for(int i := 0, i <= 10, i+=1)
    {
        console.printLine(fibu(i))
    }
}
Output:
0
1
1
2
3
5
8
13
21
34
55

Alternative version using yieldable method[edit]

import extensions;

public FibonacciGenerator
{
    yieldable next()
    {
        long n_2 := 1l; 
        long n_1 := 1l;

        yield:n_2;             
        yield:n_1;

        while(true)
        {
            long n := n_2 + n_1;

            yield:n;

            n_2 := n_1;
            n_1 := n
        }
    }
}

public program()
{
    auto e := new FibonacciGenerator();
    
    for(int i := 0, i < 10, i += 1) {
        console.printLine(e.next())
    };
    
    console.readChar()
}

Elixir[edit]

defmodule Fibonacci do
    def fib(0), do: 0
    def fib(1), do: 1
    def fib(n), do: fib(0, 1, n-2)
    
    def fib(_, prv, -1), do: prv
    def fib(prvprv, prv, n) do
        next = prv + prvprv
        fib(prv, next, n-1)
    end
end

IO.inspect Enum.map(0..10, fn i-> Fibonacci.fib(i) end)

Using Stream:

Stream.unfold({0,1}, fn {a,b} -> {a,{b,a+b}} end) |> Enum.take(10)
Output:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Elm[edit]

Naïve recursive implementation.

fibonacci : Int -> Int
fibonacci n = if n < 2 then
        n
    else
        fibonacci(n - 2) + fibonacci(n - 1)

Emacs Lisp[edit]

version 1[edit]

(defun fib (n a b c)
  (cond
   ((< c n) (fib n b (+ a b) (+ 1 c)))
   ((= c n) b)
   (t a)))

(defun fibonacci (n)
  (if (< n 2)
      n
    (fib n 0 1 1)))

version 2[edit]

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

Eval:

(insert
 (mapconcat (lambda (n) (format "%d" (fibonacci n)))
            (number-sequence 0 15) " "))
Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Erlang[edit]

Recursive[edit]

-module(fib).
-export([fib/1]).

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

Iterative[edit]

-module(fiblin).
-export([fib/1])

fib(0) -> 0;
fib(1) -> 1;
fib(2) -> 1;
fib(3) -> 2;
fib(4) -> 3;
fib(5) -> 5;

fib(N) when is_integer(N) -> fib(N - 6, 5, 8).
fib(N, A, B) -> if N < 1 -> B; true -> fib(N-1, B, A+B) end.

Evaluate:

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

Output:

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

Iterative 2[edit]

fib(N) -> fib(N, 0, 1).

fib(0, Result, _Next) -> Result;
fib(Iter, Result, Next) -> fib(Iter-1, Next, Result+Next).

ERRE[edit]

!-------------------------------------------
! derived from my book "PROGRAMMARE IN ERRE"
! iterative solution
!-------------------------------------------

PROGRAM FIBONACCI

!$DOUBLE

!VAR F1#,F2#,TEMP#,COUNT%,N%

BEGIN    !main
   INPUT("Number",N%)
   F1=0
   F2=1
   REPEAT
      TEMP=F2
      F2=F1+F2
      F1=TEMP
      COUNT%=COUNT%+1
   UNTIL COUNT%=N%
   PRINT("FIB(";N%;")=";F2)

   ! Obviously a FOR loop or a WHILE loop can
   ! be used to solve this problem

END PROGRAM
Output:
Number? 20
FIB( 20 )= 6765

Euphoria[edit]

'Recursive' version[edit]

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

'Iterative' version[edit]

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

'Tail recursive' version[edit]

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

-- example:
? fibot(10) -- says 55

'Paper tape' version[edit]

Works with: Euphoria version 4.0.0
include std/mathcons.e -- for PINF constant

enum ADD, MOVE, GOTO, OUT, TEST, TRUETO

global sequence tape = { 0, 
			 1, 
		       { ADD, 2, 1 }, 
		       { TEST, 1, PINF }, 
		       { TRUETO, 0 }, 
		       { OUT, 1, "%.0f\n" }, 
		       { MOVE, 2, 1 }, 
		       { MOVE, 0, 2 }, 
		       { GOTO, 3  } }

global integer ip
global integer test
global atom accum

procedure eval( sequence cmd )
	atom i = 1
	while i <= length( cmd ) do
		switch cmd[ i ] do
			case ADD then
				accum = tape[ cmd[ i + 1 ] ] + tape[ cmd[ i + 2 ] ]
				i += 2

			case OUT then
				printf( 1, cmd[ i + 2], tape[ cmd[ i + 1 ] ] ) 
				i += 2

			case MOVE then
				if cmd[ i + 1 ] = 0 then
					tape[ cmd[ i + 2 ] ] = accum
				else
					tape[ cmd[ i + 2 ] ] = tape[ cmd[ i + 1 ] ]
				end if
				i += 2

			case GOTO then
				ip = cmd[ i + 1 ] - 1 -- due to ip += 1 in main loop
				i += 1

			case TEST then
				if tape[ cmd[ i + 1 ] ] = cmd[ i + 2 ] then
					test = 1
				else
					test = 0
				end if
				i += 2

			case TRUETO then
				if test then
					if cmd[ i + 1 ] = 0 then
						abort(0)
					else
						ip = cmd[ i + 1 ] - 1
					end if
				end if

		end switch
		i += 1
	end while
end procedure

test = 0
accum = 0
ip = 1

while 1 do

	-- embedded sequences (assumed to be code) are evaluated
	-- atoms (assumed to be data) are ignored

	if sequence( tape[ ip ] ) then
		eval( tape[ ip ] ) 
	end if
	ip += 1
end while

Excel[edit]

LAMBDA[edit]

Binding the name FIBONACCI to the following lambda in the Excel worksheet Name Manager:

(See The LAMBDA worksheet function)

FIBONACCI
=LAMBDA(n,
    APPLYN(n - 2)(
        LAMBDA(xs,
            APPENDROWS(xs)(
                SUM(
                    LASTNROWS(2)(xs)
                )
            )
        )
    )({1;1})
)

And assuming that the following names are also bound to reusable generic lambdas in the Name manager:

APPENDROWS
=LAMBDA(xs,
    LAMBDA(ys,
        LET(
            nx, ROWS(xs),
            rowIndexes, SEQUENCE(nx + ROWS(ys)),
            colIndexes, SEQUENCE(
                1,
                MAX(COLUMNS(xs), COLUMNS(ys))
            ),

            IFERROR(
                IF(rowIndexes <= nx,
                    INDEX(xs, rowIndexes, colIndexes),
                    INDEX(ys, rowIndexes - nx, colIndexes)
                ),
                NA()
            )
        )
    )
)


APPLYN
=LAMBDA(n,
    LAMBDA(f,
        LAMBDA(x,
            IF(0 < n,
                APPLYN(n - 1)(f)(
                    f(x)
                ),
                x
            )
        )
    )
)

LASTNROWS
=LAMBDA(n,
    LAMBDA(xs,
        LET(
            nRows, COUNTA(xs),
            x, MIN(nRows, n),

            IF(0 < n,
                INDEX(
                    xs,
                    SEQUENCE(
                        x, 1,
                        1 + nRows - x,  1
                    )
                ),
                NA()
            )
        )
    )
)
Output:

The FIBONACCI(n) lambda defines a column of integers.

Here we obtain a row, by composing FIBONACCI with the built-in TRANSPOSE function:

fx =TRANSPOSE(FIBONACCI(15))
A B C D E F G H I J K L M N O P
1
2 15 Fibonacci terms: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Or as a fold, obtaining just the Nth term of the Fibonacci series:

FIBONACCI2
=LAMBDA(n,
    INDEX(
        FOLDL(
            LAMBDA(ab,
                LAMBDA(_,
                    APPEND(INDEX(ab, 2))(SUM(ab))
                )
            )
        )({0;1})(
            ENUMFROMTO(1)(n)
        ),
        1
    )
)

Assuming the following generic bindings in the Excel worksheet Name manager:

APPEND
=LAMBDA(xs,
    LAMBDA(ys,
        LET(
            nx, ROWS(xs),
            rowIndexes, SEQUENCE(nx + ROWS(ys)),
            colIndexes, SEQUENCE(
                1,
                MAX(COLUMNS(xs), COLUMNS(ys))
            ),
            IF(rowIndexes <= nx,
                INDEX(xs, rowIndexes, colIndexes),
                INDEX(ys, rowIndexes - nx, colIndexes)
            )
        )
    )
)


ENUMFROMTO
=LAMBDA(a,
    LAMBDA(z,
        SEQUENCE(1 + z - a, 1, a, 1)
    )
)


FOLDL
=LAMBDA(op,
    LAMBDA(a,
        LAMBDA(xs,
            IF(
                2 > ROWS(xs),
                op(a)(xs),
                FOLDL(op)(
                    op(a)(
                        HEAD(xs)
                    )
                )(
                    TAIL(xs)
                )
            )
        )
    )
)


HEAD
=LAMBDA(xs,
    INDEX(xs, 1, SEQUENCE(1, COLUMNS(xs)))
)


TAIL
=LAMBDA(xs,
    INDEX(
        xs,
        SEQUENCE(ROWS(xs) - 1, 1, 2, 1),
        SEQUENCE(1, COLUMNS(xs))
    )
)
Output:
fx =FIBONACCI2(A2)
A B
1 N Fibonacci
2 32 2178309
3 64 10610209857723

F#[edit]

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

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

Lazy evaluated using sequence workflow:

let rec fib = seq { yield! [0;1];
                    for (a,b) in Seq.zip fib (Seq.skip 1 fib) -> a+b}

The above is extremely slow due to the nested recursions on sequences, which aren't very efficient at the best of times. The above takes seconds just to compute the 30th Fibonacci number!

Lazy evaluation using the sequence unfold anamorphism is much much better as to efficiency:

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

Approach similar to the Matrix algorithm in C#, with some shortcuts involved. Since it uses exponentiation by squaring, calculations of fib(n) where n is a power of 2 are particularly quick. Eg. fib(2^20) was calculated in a little over 4 seconds on this poster's laptop.

open System
open System.Diagnostics
open System.Numerics

/// Finds the highest power of two which is less than or equal to a given input.
let inline prevPowTwo (x : int) =
    let mutable n = x
    n <- n - 1
    n <- n ||| (n >>> 1)
    n <- n ||| (n >>> 2)
    n <- n ||| (n >>> 4)
    n <- n ||| (n >>> 8)
    n <- n ||| (n >>> 16)
    n <- n + 1
    match x with
    | x when x = n -> x
    | _ -> n/2

/// Evaluates the nth Fibonacci number using matrix arithmetic and
/// exponentiation by squaring.
let crazyFib (n : int) =
    let powTwo = prevPowTwo n

    /// Applies 2n rule repeatedly until another application of the rule would
    /// go over the target value (or the target value has been reached).
    let rec iter1 i q r s =
        match i with
        | i when i < powTwo ->
            iter1 (i*2) (q*q + r*r) (r * (q+s)) (r*r + s*s)
        | _ -> i, q, r, s

    /// Applies n+1 rule until the target value is reached.
    let rec iter2 (i, q, r, s) =
        match i with
        | i when i < n -> 
            iter2 ((i+1), (q+r), q, r)
        | _ -> q

    match n with
    | 0 -> 1I
    | _ ->
        iter1 1 1I 1I 0I
        |> iter2

Factor[edit]

Iterative[edit]

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

Recursive[edit]

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

Tail-Recursive[edit]

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

Matrix[edit]

Translation of: Ruby
USE: math.matrices

: fib ( n -- m )
    dup 2 < [
        [ { { 0 1 } { 1 1 } } ] dip 1 - m^n
        second second
    ] unless ;

Falcon[edit]

Iterative[edit]

function fib_i(n)

    if n < 2: return n

    fibPrev = 1
    fib = 1
    for i in [2:n]
        tmp = fib
        fib += fibPrev
        fibPrev = tmp
    end
    return fib
end

Recursive[edit]

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

Tail Recursive[edit]

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

FALSE[edit]

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

Fancy[edit]

class Fixnum {
  def fib {
    match self -> {
      case 0 -> 0
      case 1 -> 1
      case _ -> self - 1 fib + (self - 2 fib)
    }
  }
}

15 times: |x| {
  x fib println
}

Fantom[edit]

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

class Main
{
  static Int fib (Int n) 
  {
    if (n < 2) return n
    fibNums := [1, 0]
    while (fibNums.size <= n)
    {
      fibNums.insert (0, fibNums[0] + fibNums[1])
    }
    return fibNums.first
  }

  public static Void main ()
  {
    20.times |n| 
    {
      echo ("Fib($n) is ${fib(n)}")
    }
  }
}

Fermat[edit]

Func Fibonacci(n) = if n<0 then -(-1)^n*Fibonacci(-n) else if n<2 then n else 
    Array fib[n+1];
    fib[1] := 0;
    fib[2] := 1;
    for i = 2, n do 
    fib[i+1]:=fib[i]+fib[i-1]
    od;
    Return(fib[n+1]);
    fi;
    fi;
    .

Fexl[edit]

# (fib n) = the nth Fibonacci number
\fib=
    (
    \loop==
        (\x\y\n
        le n 0 x;
        \z=(+ x y)
        \n=(- n 1)
        loop y z n
        )
    loop 0 1
    )


# Now test it:
for 0 20 (\n say (fib n))
Output:
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765

Fish[edit]

Outputs Fibonacci numbers until stopped.

10::n' 'o&+&$10.

FOCAL[edit]

01.10 TYPE "FIBONACCI NUMBERS" !
01.20 ASK "N =", N
01.30 SET A=0
01.40 SET B=1
01.50 FOR I=2,N; DO 2.0
01.60 TYPE "F(N) ", %8, B, !
01.70 QUIT

02.10 SET T=B
02.20 SET B=A+B
02.30 SET A=T
Output:
FIBONACCI NUMBERS
N =:20
F(N) =    6765

Forth[edit]

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

Or, for negative-index support:

: fib ( n -- Fn ) 0 1 begin
  rot dup 0 = if drop drop exit then
  dup 0 > if   1 - rot rot dup rot +
          else 1 + rot rot over - swap then 
again ;

Since there are only a fixed and small amount of Fibonacci numbers that fit in a machine word, this FORTH version creates a table of Fibonacci numbers at compile time. It stops compiling numbers when there is arithmetic overflow (the number turns negative, indicating overflow.)

: F-start,  here 1 0 dup , ;
: F-next,   over + swap
            dup 0> IF  dup , true  ELSE  false  THEN ;

: computed-table  ( compile: 'start 'next / run: i -- x )
   create
      >r execute
      BEGIN  r@ execute not  UNTIL  rdrop
   does> 
       swap cells + @ ;

' F-start, ' F-next,  computed-table fibonacci 2drop
here swap - cell/ Constant #F/64   \ # of fibonacci numbers generated

16 fibonacci . 987  ok
#F/64 . 93  ok
92 fibonacci . 7540113804746346429  ok   \ largest number generated.

Fortran[edit]

FORTRAN IV[edit]

C     FIBONACCI SEQUENCE - FORTRAN IV
      NN=46
      DO 1 I=0,NN
    1 WRITE(*,300) I,IFIBO(I)
  300 FORMAT(1X,I2,1X,I10)
      END
C
      FUNCTION IFIBO(N)
      IF(N) 9,1,2
    1 IFN=0
      GOTO 9
    2 IF(N-1) 9,3,4
    3 IFN=1
      GOTO 9
    4 IFNM1=0
      IFN=1
      DO 5 I=2,N
      IFNM2=IFNM1
      IFNM1=IFN
    5 IFN=IFNM1+IFNM2
    9 IFIBO=IFN
      END
Output:
  0          0
  1          1
  2          1
  3          2
  4          3
  5          5
  6          8
  7         13
  8         21
  9         34
 10         55
...
 45 1134903170
 46 1836311903

FORTRAN 77[edit]

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

Test program

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

Recursive[edit]

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

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

Iterative[edit]

In ISO Fortran 90 or later:

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

Test program

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

Free Pascal[edit]

See also: Pascal

type
	/// domain for Fibonacci function
	/// where result is within nativeUInt
	// You can not name it fibonacciDomain,
	// since the Fibonacci function itself
	// is defined for all whole numbers
	// but the result beyond F(n) exceeds high(nativeUInt).
	fibonacciLeftInverseRange =
		{$ifdef CPU64} 0..93 {$else} 0..47 {$endif};

{**
	implements Fibonacci sequence iteratively
	
	\param n the index of the Fibonacci number to calculate
	\returns the Fibonacci value at n
}
function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
type
	/// more meaningful identifiers than simple integers
	relativePosition = (previous, current, next);
var
	/// temporary iterator variable
	i: longword;
	/// holds preceding fibonacci values
	f: array[relativePosition] of nativeUInt;
begin
	f[previous] := 0;
	f[current] := 1;
	
	// note, in Pascal for-loop-limits are inclusive
	for i := 1 to n do
	begin
		f[next] := f[previous] + f[current];
		f[previous] := f[current];
		f[current] := f[next];
	end;
	
	// assign to previous, bc f[current] = f[next] for next iteration
	fibonacci := f[previous];
end;

FreeBASIC[edit]

Extended sequence coded big integer.

'Fibonacci extended
'Freebasic version 24  Windows
Dim Shared ADDQmod(0 To 19) As Ubyte
Dim Shared ADDbool(0 To 19) As Ubyte

For z As Integer=0 To 19
    ADDQmod(z)=(z Mod 10+48)
    ADDbool(z)=(-(10<=z))
Next z 

Function plusINT(NUM1 As String,NUM2 As String) As String
    Dim As Byte flag
    #macro finish()
    three=Ltrim(three,"0")
    If three="" Then Return "0"
    If flag=1 Then Swap NUM2,NUM1
    Return three
    Exit Function
    #endmacro
    var lenf=Len(NUM1)
    var lens=Len(NUM2)
    If lens>lenf Then 
        Swap NUM2,NUM1
        Swap lens,lenf
        flag=1
    End If
    
    var diff=lenf-lens-Sgn(lenf-lens)
    var three="0"+NUM1
    var two=String(lenf-lens,"0")+NUM2
    Dim As Integer n2
    Dim As Ubyte addup,addcarry
    
    addcarry=0
    
    For n2=lenf-1 To diff Step -1 
        addup=two[n2]+NUM1[n2]-96
        three[n2+1]=addQmod(addup+addcarry)
        addcarry=addbool(addup+addcarry)
    Next n2 
    If addcarry=0 Then 
        finish()
    End If
    If n2=-1 Then 
        three[0]=addcarry+48
        finish()
    End If
    
    For n2=n2 To 0 Step -1 
        addup=two[n2]+NUM1[n2]-96
        three[n2+1]=addQmod(addup+addcarry)
        addcarry=addbool(addup+addcarry)
    Next n2
    three[0]=addcarry+48
    finish()
End Function

Function  fibonacci(n As Integer) As String
    Dim As String sl,l,term
    sl="0": l="1"
    If n=1 Then Return "0"
    If n=2 Then Return "1"
    n=n-2
    For x As Integer= 1 To n
        term=plusINT(l,sl)
        sl=l
        l=term
    Next x
    Function =term
End Function

'==============  EXAMPLE ===============
print "THE SEQUENCE TO 10:"
print
For n As Integer=1 To 10
    Print "term";n;": "; fibonacci(n)
Next n
print
print "Selected Fibonacci number"
print "Fibonacci 500"
print
print fibonacci(500)
Sleep
Output:
THE SEQUENCE TO 10:

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

Selected Fibonacci number
Fibonacci 500

86168291600238450732788312165664788095941068326060883324529903470149056115823592
713458328176574447204501

Frink[edit]

All of Frink's integers can be arbitrarily large.

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

FRISC Assembly[edit]

To find the nth Fibonacci number, call this subroutine with n in register R0: the answer will be returned in R0 too. Contents of other registers are preserved.

FIBONACCI   PUSH   R1
            PUSH   R2
            PUSH   R3

            MOVE   0,  R1
            MOVE   1,  R2

FIB_LOOP    SUB    R0,  1, R0
            JP_Z   FIB_DONE

            MOVE   R2, R3
            ADD    R1, R2, R2
            MOVE   R3, R1

            JP     FIB_LOOP

FIB_DONE    MOVE   R2, R0

            POP    R3
            POP    R2
            POP    R1

            RET

FunL[edit]

Recursive[edit]

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

Tail Recursive[edit]

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

  _fib( n, 0, 1 )

Lazy List[edit]

val fib =
  def _fib( a, b ) = a # _fib( b, a + b )

  _fib( 0, 1 )

println( fib(10000) )
Output:
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

Iterative[edit]

def fib( n ) =
  a, b = 0, 1

  for i <- 1..n
    a, b = b, a+b

  a

Binet's Formula[edit]

import math.sqrt

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

Matrix Exponentiation[edit]

def mul( a, b ) =
  res = array( a.length(), b(0).length() )

  for i <- 0:a.length(), j <- 0:b(0).length()
    res( i, j ) = sum( a(i, k)*b(k, j) | k <- 0:b.length() )

  vector( res )

def
  pow( _, 0 ) = ((1, 0), (0, 1))
  pow( x, 1 ) = x
  pow( x, n )
    | 2|n = pow( mul(x, x), n\2 )
    | otherwise = mul(x, pow( mul(x, x), (n - 1)\2 ) )

def fib( n ) = pow( ((0, 1), (1, 1)), n )(0, 1)

for i <- 0..10
  println( fib(i) )
Output:
0
1
1
2
3
5
8
13
21
34
55

Futhark[edit]

Iterative[edit]

fun main(n: int): int =
  loop((a,b) = (0,1)) = for _i < n do
    (b, a + b)
  in a

FutureBasic[edit]

Iterative[edit]

window 1, @"Fibonacci Sequence", (0,0,480,620)

local fn Fibonacci( n as long ) as long
  static long s1
  static long s2
  long        temp
  
  if ( n < 2 )
    s1 = n
    exit fn
  else
    temp = s1 + s2
    s2 = s1
    s1 = temp
    exit fn
  end if
end fn = s1

long i
CFTimeInterval t

t = fn CACurrentMediaTime

for i = 0 to 40
  print i;@".\t";fn Fibonacci(i)
next i

print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000

HandleEvents

Output:

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

Compute time: 2.143 ms

Recursive[edit]

Cost is a time penalty

local fn Fibonacci( n as NSInteger ) as NSInteger
NSInteger result
if n < 2 then result = n : exit fn
result = fn Fibonacci( n-1 ) + fn Fibonacci( n-2 )
end fn = result

window 1

NSInteger i
CFTimeInterval t

t = fn CACurrentMediaTime
for i = 0 to 40
print i;@".\t";fn Fibonacci(i)
next
print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000

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

Compute time: 2844.217 ms

Fōrmulæ[edit]

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.

In this page you can see the program(s) related to this task and their results.

GAP[edit]

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

GAP has also a buit-in function for that.

Fibonacci(n);

Gecho[edit]

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

Prints the first several fibonacci numbers...

GFA Basic[edit]

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

GML[edit]

///fibonacci(n)
//Returns the nth fibonacci number

var n, numb;
n = argument0;

if (n == 0)
    {
    numb = 0;
    }
else
    {
    var fm2, fm1;
    fm2 = 0;
    fm1 = 1;
    numb = 1;
    repeat(n-1)
        {
        numb = fm2+fm1;
        fm2 = fm1;
        fm1 = numb;
        }
    }

return numb;

Go[edit]

Recursive[edit]

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

Iterative[edit]

import (
	"math/big"
)

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

Iterative using a closure[edit]

func fibNumber() func() int {
	fib1, fib2 := 0, 1
	return func() int {
		fib1, fib2 = fib2, fib1 + fib2
		return fib1
	}
}

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

Using a goroutine and channel[edit]

func fib(c chan int) {
	a, b := 0, 1
	for {
		c <- a
		a, b = b, a+b
	}
}

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

Groovy[edit]

Full "extra credit" solutions.

Recursive[edit]

A recursive closure must be pre-declared.

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

Iterative[edit]

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

Analytic[edit]

final φ = (1 + 5**(1/2))/2
def aFib = { (φ**it - (-φ)**(-it))/(5**(1/2)) as BigInteger }

Test program:

def time = { Closure c ->
    def start = System.currentTimeMillis()
    def result = c()
    def elapsedMS = (System.currentTimeMillis() - start)/1000
    printf '(%6.4fs elapsed)', elapsedMS
    result
}

print "  F(n)      elapsed time   "; (-10..10).each { printf ' %3d', it }; println()
print "--------- -----------------"; (-10..10).each { print ' ---' }; println()
[recursive:rFib, iterative:iFib, analytic:aFib].each { name, fib ->
    printf "%9s ", name
    def fibList = time { (-10..10).collect {fib(it)} }
    fibList.each { printf ' %3d', it }
    println()
}
Output:
  F(n)      elapsed time    -10  -9  -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6   7   8   9  10
--------- ----------------- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
recursive (0.0080s elapsed) -55  34 -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8  13  21  34  55
iterative (0.0040s elapsed) -55  34 -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8  13  21  34  55
 analytic (0.0030s elapsed) -55  34 -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8  13  21  34  55

Harbour[edit]

Recursive[edit]

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

Iterative[edit]

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

Haskell[edit]

Analytic[edit]

Works with: exact-real version 0.12.5.1

Using Binet's formula and exact real arithmetic library we can calculate arbitrary Fibonacci number exactly.

import Data.CReal

phi = (1 + sqrt 5) / 2

fib :: (Integral b) => b -> CReal 0
fib n = (phi^^n - (-phi)^^(-n))/sqrt 5

Let's try it for large numbers:

λ> fib 10 :: CReal 0
55
(0.01 secs, 137,576 bytes)
λ> fib 100 :: CReal 0
354224848179261915075
(0.01 secs, 253,152 bytes)
λ> fib 10000 :: CReal 0
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
(0.02 secs, 4,847,128 bytes)
λ> fib (-10) :: CReal 0
-55
(0.01 secs, 138,408 bytes)

Recursive[edit]

Simple definition, very inefficient.

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

Recursive with Memoization[edit]

Very fast.

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

Recursive with Memoization using memoized library[edit]

Even faster and simpler is to use a defined memoizer (e.g. from MemoTrie package):

import Data.MemoTrie
fib :: Integer -> Integer
fib = memo f where
   f 0 = 0
   f 1 = 1
   f n = fib (n-1) + fib (n-2)

You can rewrite this without introducing f explicitly

import Data.MemoTrie
fib :: Integer -> Integer
fib = memo $ \x -> case x of
   0 -> 0
   1 -> 1
   n -> fib (n-1) + fib (n-2)

Or using LambdaCase extension you can write it even shorter:

{-# Language LambdaCase #-}
import Data.MemoTrie
fib :: Integer -> Integer
fib = memo $ \case 
   0 -> 0
   1 -> 1
   n -> fib (n-1) + fib (n-2)

The version that supports negative numbers:

{-# Language LambdaCase #-}
import Data.MemoTrie
fib :: Integer -> Integer
fib = memo $ \case 
   0 -> 0
   1 -> 1
   n | n>0 -> fib (n-1) + fib (n-2)
     | otherwise -> fib (n+2) - fib (n+1)

Iterative[edit]

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

With lazy lists[edit]

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

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

Or alternatively:

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

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

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

Also

fib = 0 : scanl (+) 1 fib

As a fold[edit]

Accumulator holds last two members of the series:

import Data.List (foldl') --'

fib :: Integer -> Integer
fib n =
  fst $
  foldl' --'
    (\(a, b) _ -> (b, a + b))
    (0, 1)
    [1 .. n]

With matrix exponentiation[edit]

Adapting the (rather slow) code from Matrix exponentiation operator, we can simply write:

import Data.List (transpose)

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

-- Code adapted from Matrix exponentiation operator task ---------------------
(<+>)
  :: Num c
  => [c] -> [c] -> [c]
(<+>) = zipWith (+)

(<*>)
  :: Num a
  => [a] -> [a] -> a
(<*>) = (sum .) . zipWith (*)

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 Main.<*> ys -- to distinguish from standard applicative operator
        | ys <- transpose $ unMat ym ]
      | xs <- unMat xm ]
  fromInteger n = Mat [[fromInteger n]]
  abs = undefined
  signum = undefined

-- TEST ----------------------------------------------------------------------
main :: IO ()
main = (print . take 10 . show . fib) (10 ^ 5)

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

Output:
"2597406934"

With recurrence relations[edit]

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

import Control.Arrow ((&&&))

fibstep :: (Integer, Integer) -> (Integer, Integer)
fibstep (a, b) = (b, a + b)

fibnums :: [Integer]
fibnums = map fst $ iterate fibstep (0, 1)

fibN2 :: Integer -> (Integer, Integer)
fibN2 m
  | m < 10 = iterate fibstep (0, 1) !! fromIntegral m
fibN2 m = fibN2_next (n, r) (fibN2 n)
  where
    (n, r) = quotRem m 3

fibN2_next (n, r) (f, g)
  | r == 0 = (a, b) -- 3n  ,3n+1
  | r == 1 = (b, c) -- 3n+1,3n+2
  | r == 2 = (c, d) -- 3n+2,3n+3   (*)
  where
    a =
      5 * f ^ 3 +
      if even n
        then 3 * f
        else (-3 * f) -- 3n
    b = g ^ 3 + 3 * g * f ^ 2 - f ^ 3 -- 3n+1
    c = g ^ 3 + 3 * g ^ 2 * f + f ^ 3 -- 3n+2
    d =
      5 * g ^ 3 +
      if even n
        then (-3 * g)
        else 3 * g -- 3(n+1)   (*)

main :: IO ()
main = print $ (length &&& take 20) . show . fst $ fibN2 (10 ^ 2)
Output:
(21,"35422484817926191507")

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

 *Main> (length &&& take 20) . show . fst $ fibN2 (10^6)
(208988,"19532821287077577316")

The above should take less than 0.1s to calculate on a modern box.

Other identities that could also be used are here. In particular, for (n-1,n) ---> (2n-1,2n) transition which is equivalent to the matrix exponentiation scheme, we have

f (n,(a,b)) = (2*n,(a*a+b*b,2*a*b+b*b))     -- iterate f (1,(0,1)) ; b is nth

and for (n,n+1) ---> (2n,2n+1) (derived from d'Ocagne's identity, for example),

g (n,(a,b)) = (2*n,(2*a*b-a*a,a*a+b*b))     -- iterate g (1,(1,1)) ; a is nth

Haxe[edit]

Iterative[edit]

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

		var temp = current + next;
		current = next;
		next = temp;
	}
	handler(current);
}

As Iterator[edit]

class FibIter
{
	private var current = 0;
	private var nextItem = 1;
	private var limit:Int;
	
	public function new(limit) 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);

HicEst[edit]

REAL :: Fibonacci(10)

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

Hoon[edit]

|=  n=@ud
=/  a=@ud  0
=/  b=@ud  1
|-
?:  =(n 0)  a
$(a b, b (add a b), n (dec n))

Hope[edit]

Recursive[edit]

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

Tail-recursive[edit]

dec fib : num -> num;
--- fib n <= l (1, 0, n)
    whererec l == \(a,b,succ c) => if c<1 then a else l((a+b),a,c)
                  |(a,b,0) => 0;

With lazy lists[edit]

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

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

The nth Fibonacci number is then just fibs @ n.

Hy[edit]

Recursive implementation.

(defn fib [n]
    (if (< n 2)
        n
        (+ (fib (- n 2)) (fib (- n 1)))))

Icon and Unicon[edit]

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

procedure main(args)
    write(fib(integer(!args) | 1000)
end

procedure fib(n)
    static fCache
    initial {
        fCache := table()
        fCache[0] := 0
        fCache[1] := 1
        }
    /fCache[n] := fib(n-1) + fib(n-2)
    return fCache[n]
end

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

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

procedure main(args)
    write(fib(integer(!args) | 1000000))
end

procedure fib(n)
    return fibMat(n)[1]
end

procedure fibMat(n)
    if n <= 0 then return [0,0]
    if n  = 1 then return [1,0]
    fp := fibMat(n/2)
    c := fp[1]*fp[1] + fp[2]*fp[2]
    d := fp[1]*(fp[1]+2*fp[2])
    if n%2 = 1 then return [c+d, d]
    else return [d, c]
end

IDL[edit]

Recursive[edit]

function fib,n
   if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)
end

Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo.

Iterative[edit]

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

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

Analytic[edit]

function fib,n
  q=1/( p=(1+sqrt(5))/2 ) 
  return,round((p^n+q^n)/sqrt(5))
end

Execution time O(1), only limited by the range of LongInts to fib(48).

Idris[edit]

Analytic[edit]

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

Recursive[edit]

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

Iterative[edit]

fibIterative : Nat -> Nat
fibIterative n = fibIterative' n Z (S Z)
  where fibIterative' : Nat -> Nat -> Nat -> Nat
        fibIterative' Z a _ = a
        fibIterative' (S n) a b = fibIterative' n b (a + b)

Lazy[edit]

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

J[edit]

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

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

Examples:

   fibN 12
144
   fibN  i.31
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040

(This implementation is doubly recursive except that results are cached across function calls.)

Java[edit]

Iterative[edit]

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

    long i = (int) (n - 1);
    long a = 1, b = 0, c = 0, d = 1, tmp1,tmp2;

    while (i > 0) {
	if (i % 2 != 0) {
            tmp1 = d * b + c * a;
	    tmp2 = d * (b + a) + c * b;
	    a = tmp1;
	    b = tmp2;
	}

        tmp1 = (long) (Math.pow(c, 2) + Math.pow(d, 2));
        tmp2 = d * (2 * c + d);
			
        c = tmp1;
        d = tmp2;

        i = i / 2;
    }
    return a + b;
}

Recursive[edit]

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

Caching-recursive[edit]

A variant on recursive, that caches previous results, reducing complexity from O(n2) to simply O(n). Leveraging Java’s Map.computeIfAbsent makes this thread-safe, and the implementation pretty trivial.

public class Fibonacci {

    static final Map<Integer, Long> cache = new HashMap<>();
    static {
        cache.put(1, 1L);
        cache.put(2, 1L);
    }

    public static long get(int n)
    {
        return (n < 2) ? n : impl(n);
    }
    
    private static long impl(int n)
    {
        return cache.computeIfAbsent(n, k -> impl(k-1) + impl(k-2));
    }
}

Analytic[edit]

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

public static long anFibN(final long n)
{
 double p = (1 + Math.sqrt(5)) / 2;
 double q = 1 / p;
 return (long) ((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5));
}

Tail-recursive[edit]

public static long fibTailRec(final int n)
{
 return fibInner(0, 1, n);
}

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

Streams[edit]

import java.util.function.LongUnaryOperator;
import java.util.stream.LongStream;

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

JavaScript[edit]

ES5[edit]

Recursive[edit]

Basic recursive function:

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

Can be rewritten as:

function fib(n) {
 if (n<2) { return n; } else { return fib(n-1)+fib(n-2); }
}

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

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

Iterative[edit]

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

Memoization[edit]

With the keys of a dictionary,

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

with the indices of an array,

(function () {
    'use strict';

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

    return fib(32);

})();


Output:
2178309

Y-Combinator[edit]

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

Generators[edit]

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

ES6[edit]

Memoized[edit]

If we want access to the whole preceding series, as well as a memoized route to a particular member, we can use an accumulating fold.

(() => {
    'use strict';

    // Nth member of fibonacci series

    // fib :: Int -> Int
    function fib(n) {
        return mapAccumL(([a, b]) => [
            [b, a + b], b
        ], [0, 1], range(1, n))[0][0];
    };

    // GENERIC FUNCTIONS

    // mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
    let mapAccumL = (f, acc, xs) => {
        return xs.reduce((a, x) => {
            let pair = f(a[0], x);

            return [pair[0], a[1].concat(pair[1])];
        }, [acc, []]);
    }

    // range :: Int -> Int -> Maybe Int -> [Int]
    let range = (m, n) =>
        Array.from({
            length: Math.floor(n - m) + 1
        }, (_, i) => m + i);


    // TEST
    return fib(32);

    // --> 2178309
})();

Otherwise, a simple fold will suffice.

Translation of: Haskell
(Memoized fold example)
(() => {
    'use strict';

    // fib :: Int -> Int
    let fib = n => range(1, n)
        .reduce(([a, b]) => [b, a + b], [0, 1])[0];


    // GENERIC [m..n]

    // range :: Int -> Int -> [Int]
    let range = (m, n) =>
        Array.from({
            length: Math.floor(n - m) + 1
        }, (_, i) => m + i);


    // TEST
    return fib(32);

    // --> 2178309
})();
Output:
2178309

Joy[edit]

Recursive[edit]

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

Iterative[edit]

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

jq[edit]

Works with: jq

Works with gojq, the Go implementation of jq

The C implementation of jq does not (yet) have infinite-precision integer arithmetic, and so using it, the following algorithms only give exact answers up to fib(78). By contrast, using the Go implementation of jq and the definition of nth_fib given below:

nth_fib(pow(2;20)) | tostring | [length, .[:10], .[-10:]]

yields

[219140,"1186800606","0691163707"]

in about 20 seconds on a 3GHz machine.

Using either the C or Go implementations, at a certain point, integers are converted to floats, but floating point precision for fib(n) fails after n = 1476: in jq, fib(1476) evaluates to 1.3069892237633987e+308

Recursive[edit]

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

Tail Recursive[edit]

Recent versions of jq (after July 1, 2014) include basic optimizations for tail recursion, and nth_fib is defined here to take advantage of TCO. For example, nth_fib(10000000) completes with only 380KB (that's K) of memory. However nth_fib can also be used with earlier versions of jq.

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

Binet's Formula[edit]

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

Generator[edit]

The following is a jq generator which produces the first n terms of the Fibonacci sequence efficiently, one by one. Notice that it is simply a variant of the above tail-recursive function. The function is in effect turned into a generator by changing "( _ | fib )" to "$sum, (_ | fib)".
# Generator
def fibonacci(n):
  # input: [f(i-2), f(i-1), countdown]
  def fib: (.[0] + .[1]) as $sum
           | if .[2] == 0 then $sum
             else $sum, ([ .[1], $sum, .[2] - 1 ] | fib)
             end;
  [-1, 1, n] | fib;

Julia[edit]

Recursive[edit]

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

Iterative[edit]

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

Matrix form[edit]

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

K[edit]

Recursive[edit]

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

Recursive with memoization[edit]

Using a (global) dictionary c.

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

Analytic[edit]

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

Sequence to n[edit]

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

Kabap[edit]

Sequence to n[edit]

// Calculate the $n'th Fibonacci number

// Set this to how many in the sequence to generate
$n = 10;

// These are what hold the current calculation
$a = 0;
$b = 1;

// This holds the complete sequence that is generated
$sequence = "";

// Prepare a loop
$i = 0;
:calcnextnumber;
	$i = $i++;

	// Do the calculation for this loop iteration
	$b = $a + $b;
	$a = $b - $a;

	// Add the result to the sequence
	$sequence = $sequence << $a;

	// Make the loop run a fixed number of times
	if $i < $n; {
		$sequence = $sequence << ", ";
		goto calcnextnumber;
	}

// Use the loop counter as the placeholder
$i--;

// Return the sequence
return = "Fibonacci number " << $i << " is " << $a << " (" << $sequence << ")";

Klingphix[edit]

:Fibonacci
    dup 0 less
    ( ["Invalid argument"]
      [1 1 rot 2 sub [drop over over add] for]
    ) if
;

30 Fibonacci pstack print nl

msec print nl
"bertlham " input

Kotlin[edit]

enum class Fibonacci {
    ITERATIVE {
        override fun get(n: Int): Long = if (n < 2) {
            n.toLong()
        } else {
            var n1 = 0L
            var n2 = 1L
            repeat(n) {
                val sum = n1 + n2
                n1 = n2
                n2 = sum
            }
            n1
        }
    },
    RECURSIVE {
        override fun get(n: Int): Long = if (n < 2) n.toLong() else this[n - 1] + this[n - 2]
    },
    CACHING {
        val cache: MutableMap<Int, Long> = mutableMapOf(0 to 0L, 1 to 1L)
        override fun get(n: Int): Long = if (n < 2) n.toLong() else impl(n)
        private fun impl(n: Int): Long = cache.computeIfAbsent(n) { impl(it-1) + impl(it-2) }
    },
    ;
 
    abstract operator fun get(n: Int): Long
}
 
fun main() {
    val r = 0..30
    for (fib in Fibonacci.values()) {
        print("${fib.name.padEnd(10)}:")
        for (i in r) { print(" " + fib[i]) }
        println()
    }
}
Output:
ITERATIVE:  0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
RECURSIVE:  0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
CACHING   : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040

L++[edit]

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

LabVIEW[edit]

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

lambdatalk[edit]

1) basic version 
{def fib1 
 {lambda {:n}
  {if {< :n 3}
   then 1
   else {+ {fib1 {- :n 1}} {fib1 {- :n 2}}} }}}

{fib1 16} -> 987   (CPU ~ 16ms)
{fib1 30} = 832040 (CPU > 12000ms)

2) tail-recursive version
{def fib2
 {def fib2.r 
  {lambda {:a :b :i}
   {if {< :i 1} 
    then :a 
    else {fib2.r :b {+ :a :b} {- :i 1}} }}}
 {lambda {:n} {fib2.r 0 1 :n}}}

{fib2 16} -> 987    (CPU ~ 1ms)
{fib2 30} -> 832040 (CPU ~2ms)
{fib2 1000} -> 4.346655768693743e+208 (CPU ~ 22ms)  

3) Dijkstra Algorithm
{def fib3
 {def fib3.r
  {lambda {:a :b :p :q :count}
   {if {= :count 0}
    then :b
    else {if {= {% :count 2} 0}
    then {fib3.r :a :b
                {+ {* :p :p} {* :q :q}}
                {+ {* :q :q} {* 2 :p :q}}
                {/ :count 2}}
    else {fib3.r {+ {* :b :q} {* :a :q} {* :a :p}}
                {+ {* :b :p} {* :a :q}}
                :p :q
                {- :count 1}} }}}}
 {lambda {:n}
  {fib3.r 1 0 0 1 :n} }}

{fib3 16} -> 987    (CPU ~ 2ms)
{fib3 30} -> 832040 (CPU ~ 2ms)
{fib3 1000} -> 4.346655768693743e+208 (CPU ~ 3ms)  

4) memoization
{def fib4
 {def fib4.m {array.new}}    // init an empty array
 {def fib4.r {lambda {:n}
  {if {< :n 2}
   then {array.get {array.set! {fib4.m} :n 1} :n}      // init with 1,1
   else {if {equal? {array.get {fib4.m} :n} undefined} // if not exists
   then {array.get {array.set! {fib4.m} :n
                        {+ {fib4.r {- :n 1}}
                           {fib4.r {- :n 2}}}} :n}   // compute it
   else {array.get {fib4.m} :n} }}}}                   // else get it
 {lambda {:n}
  {fib4.r :n} 
  {fib4.m} }} // display the number AND all its predecessors
-> fib4
{fib4 90}  
-> 4660046610375530000 
[1,1,2,3,5,8,13,21,34,55,89,144,233,