I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Fibonacci sequence

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

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

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


Write a function to generate the   nth   Fibonacci number.

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

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

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


support for negative     n     in the solution is optional.

References

## 0815

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

## 11l

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

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

### using fullword integers

*        Fibonacci sequence    05/11/2014*        integer (31 bits) = 10 decimals -> max fibo(46)FIBONACC CSECT         USING FIBONACC,R12    base registerSAVEAREA B     STM-SAVEAREA(R15) skip savearea         DC    17F'0'          savearea         DC    CL8'FIBONACC'   eyecatcherSTM      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           limitLOOP     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*        ----  DATANN       DC    H'46'           nn max nPW       DS    PL8             15numZW       DS    ZL16CW       DS    CL16ZN       DS    CL20*                  ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15numEM       DC    XL20'402020206B2020206B2020206B2020206B202120'  maskWTOMSG   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

*        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              limitLOOP     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*        ----   DATANN       DC     H'73'              nnFNM2     DS     PL8                f(n-2)FNM1     DS     PL8                f(n-1)FN       DS     PL8                f(n)PW       DS     PL8                15numZN       DS     CL20*                   ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15numEM       DC     XL20'402020206B2020206B2020206B2020206B202120'  maskWTOMSG   DS     0F         DC     H'80',XL2'0000'*                    fibo(73)=806515533049393WTOBUF   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

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  #0LOOP:  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

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

This subroutine expects to be called with the value of ${\displaystyle n}$ in register A, and returns ${\displaystyle f(n)}$ 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 ${\displaystyle n}$.

FIBNCI: MOV  C,  A  ; C will store the counter        DCR  C      ; decrement, because we know f(1) already        MVI  A,  1        MVI  B,  0LOOP:   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

### Calculating the values at runtime

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

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

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

### Iterative

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

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

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!

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  FIRETURN (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  ODRETURN
Output:
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

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

### Recursive

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

### Iterative, build-in integers

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


### Iterative, long integers

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

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

### Fast method using fast matrix exponentiation

 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;

### Recursive

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

### Iterative

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

## Aime

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

## ALGOL 60

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

### Analytic

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC analytic fibonacci = (LONG INT n)LONG INT:(  LONG REAL sqrt 5 = long sqrt(5);  LONG REAL p = (1 + sqrt 5) / 2;  LONG REAL q = 1/p;  ROUND( (p**n + q**n) / sqrt 5 )); FOR i FROM 1 TO 30 WHILE  print(whole(analytic fibonacci(i),0));# WHILE # i /= 30 DO  print(", ")OD;print(new line)
Output:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040


### Iterative

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC iterative fibonacci = (INT n)INT:   CASE n+1 IN    0, 1, 1, 2, 3, 5  OUT    INT even:=3, odd:=5;    FOR i FROM odd+1 TO n DO      (ODD i|odd|even) := odd + even    OD;    (ODD n|odd|even)  ESAC; FOR i FROM 0 TO 30 WHILE  print(whole(iterative fibonacci(i),0));# WHILE # i /= 30 DO  print(", ")OD;print(new line)
Output:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040


### Recursive

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

### Generative

Translation of: Python – Note: This specimen retains the original Python coding style.
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
MODE YIELDINT = PROC(INT)VOID; PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (  INT even:=0, odd:=1;  yield(even);  yield(odd);  FOR i FROM odd+1 TO n DO    yield( (ODD i|odd|even) := odd + even )  OD); main:(  # FOR INT n IN # gen fibonacci(30, # ) DO ( #  ##   (INT n)VOID:(        print((" ",whole(n,0)))  # OD # ));    print(new line))
Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040


### Array (Table) Lookup

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

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

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


## ALGOL W

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

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

#### Iterative

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

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

## Alore

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

## Amazing Hopper

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  NextReturn(B)
Output:

## AsciiDots

### Recursive

#AutoIt Version: 3.2.10.0$n0 = 0$n1 = 1$n = 10MsgBox (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)   EndIfEndFunc

## AWK

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

## BASIC

### Applesoft BASIC

Same code as Commodore BASIC

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

?OVERFLOW ERROR IN 220

### BASIC256

 # 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 = ",flimit = 500                        # set upper limit - can be changed, removedf = 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

100 PRINT CHR$(147); CHR$(18); "****      FIBONACCI GENERATOR       ****"110 INPUT "MIN, MAX"; N1, N2120 IF N1 > N2 THEN T = N1: N1 = N2: N2 = T130 A = 0: B = 1: S = SGN(N1)140 FOR I = S TO N1 STEP S150 : IF S > 0 THEN T = A + B: A = B: B = T160 : IF S < 0 THEN T = B - A: B = A: A = T170 NEXT I180 PRINT190 PRINT STR$(A); : REM STR$() PREVENTS TRAILING SPACE200 IF N2 = N1 THEN 250210 FOR I = N1 + 1 TO N2220 : T = A + B: A = B: B = T230 : PRINT ","; STR$(A);240 NEXT I250 PRINT Output: **** FIBONACCI GENERATOR **** MIN, MAX? -6,6 -8, 5,-3, 2,-1, 1, 0, 1, 1, 2, 3, 5, 8 READY. ### Integer BASIC Only works with quite small values of ${\displaystyle n}$.  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 B100 END ### IS-BASIC 100 PROGRAM "Fibonac.bas"110 FOR I=0 TO 20120 PRINT "F";I,FIB(I)130 NEXT140 DEF FIB(N)150 NUMERIC I160 LET A=0:LET B=1170 FOR I=1 TO N180 LET T=A+B:LET A=B:LET B=T190 NEXT200 LET FIB=A210 END DEF ### QBasic Works with: QBasic Works with: FreeBASIC #### Iterative FUNCTION itFib (n) n1 = 0 n2 = 1 FOR k = 1 TO ABS(n) sum = n1 + n2 n1 = n2 n2 = sum NEXT k IF n < 0 THEN itFib = n1 * ((-1) ^ ((-n) + 1)) ELSE itFib = n1 END IFEND FUNCTION Next version calculates each value once, as needed, and stores the results in an array for later retreival (due to the use of REDIM PRESERVE, it requires QuickBASIC 4.5 or newer): DECLARE FUNCTION fibonacci& (n AS INTEGER) REDIM SHARED fibNum(1) AS LONG fibNum(1) = 1 '*****sample inputs*****PRINT fibonacci(0) 'no calculation neededPRINT fibonacci(13) 'figure F(2)..F(13)PRINT fibonacci(-42) 'figure F(14)..F(42)PRINT fibonacci(47) 'error: too big'*****sample inputs***** FUNCTION fibonacci& (n AS INTEGER) DIM a AS INTEGER a = ABS(n) SELECT CASE a CASE 0 TO 46 SHARED fibNum() AS LONG DIM u AS INTEGER, L0 AS INTEGER u = UBOUND(fibNum) IF a > u THEN REDIM PRESERVE fibNum(a) AS LONG FOR L0 = u + 1 TO a fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2) NEXT END IF IF n < 0 THEN fibonacci = fibNum(a) * ((-1) ^ (a + 1)) ELSE fibonacci = fibNum(n) END IF CASE ELSE 'limited to signed 32-bit int (LONG) 'F(47)=&hB11924E1 ERROR 6 'overflow END SELECTEND FUNCTION Output: (unhandled error in final input prevents output):  0 233 -267914296  #### Recursive This example can't handle n < 0. FUNCTION recFib (n) IF (n < 2) THEN recFib = n ELSE recFib = recFib(n - 1) + recFib(n - 2) END IFEND FUNCTION #### Array (Table) Lookup This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.) DATA -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903 DIM fibNum(-46 TO 46) AS LONG FOR n = -46 TO 46 READ fibNum(n)NEXT '*****sample inputs*****FOR n = -46 TO 46 PRINT fibNum(n),NEXTPRINT'*****sample inputs***** #### QB64 Fibonacci from Russia DIM F(80) AS DOUBLE 'FibRus.bas DANILINF(1) = 0: F(2) = 1'OPEN "FibRus.txt" FOR OUTPUT AS #1FOR 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

#### Analytic

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

#### Iterative

 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

 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+B100 LET A=C110 LET N=N-1120 GOSUB 70130 RETURN

## Batch File

Recursive version

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

>fibo.cmd 1
1

>fibo.cmd 6
8

>fibo.cmd 11
89

>fibo.cmd 16
987

## Battlestar

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

## BBC BASIC

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

## bc

### iterative

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

## BCPL

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

                        #>'#{;_Enter n: TNFib({)=X~P~K#{;                         #>~P~L#[email protected]>[email protected]'[email protected]{;                                    [email protected]<

Example output:

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

julia> beeswax("n-th Fibonacci number.bswx")Enter n: i0 Fib(0)=0Program finished! julia> beeswax("n-th Fibonacci number.bswx")Enter n: i10 Fib(10)=55Program finished! julia> beeswax("n-th Fibonacci number.bswx")Enter n: i92 Fib(92)=7540113804746346429Program 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

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

## BlitzMax

local a:int = 0, b:int = 1, c:int = 1, n:int n = int(input( "Enter n: "))if n = 0 then    print 0    endelse if n = 1    print 1    endend if while n>2    a = b    b = c    c = a + b    n = n - 1wendprint c

## Blue

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

## BQN

All given functions return the nth element in the sequence.

### Recursive

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

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

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

## Bracmat

### Recursive

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


## Brainf***

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

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

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

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

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

## Brat

### Recursive

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

### Tail Recursive

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

### Memoization

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

## Burlesque

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

## C

### Recursive

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

### Iterative

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

### Analytic

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

### Generative

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


### Fast method for a single large value

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


## C#

### Recursive

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

### Tail-Recursive

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

### Iterative

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

### Eager-Generative

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

### Lazy-Generative

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

### Analytic

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

Algorithm is based on

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

Needs System.Windows.Media.Matrix or similar Matrix class. Calculates in ${\displaystyle O(n)}$.

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

Needs System.Windows.Media.Matrix or similar Matrix class. Calculates in ${\displaystyle O(\log {n})}$.

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

### Array (Table) Lookup

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

### Arbitrary Precision

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


## C++

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

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

Library: GMP

This version does not have an upper bound.

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

Version using transform:

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

Far-fetched version using adjacent_difference:

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

Version which computes at compile time with metaprogramming:

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

The following version is based on fast exponentiation:

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


### Using Zeckendorf Numbers

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

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


### Using Standard Template Library

Possibly less "Far-fetched version".

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

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

## Cat

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

## Chapel

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

## Chef

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

## Clio

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

### Lazy Sequence

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

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

Thus to get the nth one:

(nth (fibs) 5)

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

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

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

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

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

Then, to see the first ten,

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

### Iterative

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

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

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

### Doubling Algorithm (Fast)

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

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

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

% Generate Fibonacci numbersfib = iter () yields (int)    a: int := 0    b: int := 1     while true do        yield (a)        a, b := b, a+b    endend 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    endend nth % Print a few valuesstart_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))) endend 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 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

### Iterative

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

### Recursive

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

## CoffeeScript

### Analytic

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

### Iterative

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

### Recursive

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

## Comefrom0x10

Recursion is is not possible in Comefrom0x10.

### Iterative

stop = 6a = 1i = 1  # starta      # 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

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

### Iterative

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

Simpler one:

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

### Recursive

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

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

Tail recursive and squaring:

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

### Alternate solution

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

 (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

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

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

To find the ${\displaystyle n}$th Fibonacci number, set the initial value of count equal to ${\displaystyle n}$–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 ${\displaystyle n}$ 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:         1count:       8      ; n = 10x:           1y:           1temp:        0

## Corescript

print Fibonacci Sequence:var previous = 1var number = 0var temp = (blank) :fibif number > 50000000000:killprint (number)set temp = (add number previous)set previous = (number)set number = (temp)goto fib :killstop

## Cowgol

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

### Recursive

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

### Iterative

def fibIterative(n, prevFib = 0, fib = 1)  return n if n < 2   n.times do    prevFib, fib = fib, prevFib + fib  end   prevFibend

### Tail Recursive

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

### Analytic

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

## D

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

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

### Matrix Exponentiation Version

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

### Faster Version

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

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

## Dart

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

## Datalog

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

;;       Fibonacci sequence for DBL version 4 by Dario B.;        RECORD FIB1,  D10FIB2,  D10FIBN,  D10 J,     D5A2,    A2A5,    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 1END

## Dc

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

### Iterative

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

### Recursive

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

### Matrix

Algorithm is based on

${\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F(n+1)&F(n)\\F(n)&F(n-1)\end{pmatrix}}}$.
 function fib(n: Int64): Int64;   type TFibMat = array[0..1] of array[0..1] of Int64;   function FibMatMul(a,b: TFibMat): TFibMat;  var i,j,k: integer;      tmp: TFibMat;  begin    for i := 0 to 1 do      for j := 0 to 1 do      begin	tmp[i,j] := 0;	for k := 0 to 1 do tmp[i,j] := tmp[i,j] + a[i,k] * b[k,j];      end;    FibMatMul := tmp;  end;   function FibMatExp(a: TFibMat; n: Int64): TFibmat;  begin    if n <= 1 then fibmatexp := a    else if (n mod 2 = 0) then FibMatExp := FibMatExp(FibMatMul(a,a), n div 2)    else if (n mod 2 = 1) then FibMatExp := FibMatMul(a, FibMatExp(FibMatMul(a,a), n div 2));  end; var   matrix: TFibMat; 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

        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

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

## Dyalect

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

## E

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

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

## EasyLang

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 rprint 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 rprint r

## EchoLisp

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

### Analytic

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

## EDSAC order code

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 ]  [email protected]  [ a = 0           ]        [email protected]  [ a += y          ]        [email protected]  [ temp = a        ]        [email protected]  [ a += x          ]        [email protected]  [ y = a; a = 0    ]        [email protected]  [ a += temp       ]        [email protected]  [ x = a; a = 0    ]         [email protected]  [ a = count       ]        [email protected]  [ a -= 1          ]        [email protected]  [ count = a       ]        [email protected]    [ if a>=0 go to θ ]         [email protected]  [ a = 0           ]        [email protected]  [ 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

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

## Ela

Tail-recursive function:

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

Infinite (lazy) list:

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

## Elena

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

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

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

Naïve recursive implementation.

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

## Emacs Lisp

### version 1

(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

(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

### Recursive

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

### Iterative

 -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

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

## FOCAL

01.10 TYPE "FIBONACCI NUMBERS" !01.20 ASK "N =", N01.30 SET A=001.40 SET B=101.50 FOR I=2,N; DO 2.001.60 TYPE "F(N) ", %8, B, !01.70 QUIT 02.10 SET T=B02.20 SET B=A+B02.30 SET A=T
Output:
FIBONACCI NUMBERS
N =:20
F(N) =    6765

## Forth

: 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  [email protected] execute not  UNTIL  rdrop   does>        swap cells + @ ; ' F-start, ' F-next,  computed-table fibonacci 2drophere swap - cell/ Constant #F/64   \ # of fibonacci numbers generated 16 fibonacci . 987  ok#F/64 . 93  ok92 fibonacci . 7540113804746346429  ok   \ largest number generated.

## Fortran

### FORTRAN IV

C     FIBONACCI SEQUENCE - FORTRAN IV      NN=46      DO 1 I=0,NN    1 WRITE(*,300) I,IFIBO(I)  300 FORMAT(1X,I2,1X,I10)      ENDC      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

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

Test program

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


### Recursive

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

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

### Iterative

In ISO Fortran 90 or later:

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

Test program

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


## Free 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 Extended sequence coded big integer. 'Fibonacci extended'Freebasic version 24 WindowsDim Shared ADDQmod(0 To 19) As UbyteDim 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 =termEnd Function '============== EXAMPLE ===============print "THE SEQUENCE TO 10:"printFor n As Integer=1 To 10 Print "term";n;": "; fibonacci(n)Next nprintprint "Selected Fibonacci number"print "Fibonacci 500"printprint fibonacci(500)Sleep Output: THE SEQUENCE TO 10: term 1: 0 term 2: 1 term 3: 1 term 4: 2 term 5: 3 term 6: 5 term 7: 8 term 8: 13 term 9: 21 term 10: 34 Selected Fibonacci number Fibonacci 500 86168291600238450732788312165664788095941068326060883324529903470149056115823592 713458328176574447204501 ## Frink All of Frink's integers can be arbitrarily large.  fibonacciN[n] :={ a = 0 b = 1 count = 0 while count < n { [a,b] = [b, a + b] count = count + 1 } return a}  ## FRISC Assembly To find the nth Fibonacci number, call this subroutine with n in register R0: the answer will be returned in R0 too. Contents of other registers are preserved. 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 ### Recursive def fib( 0 ) = 0 fib( 1 ) = 1 fib( n ) = fib( n - 1 ) + fib( n - 2 ) ### Tail Recursive def fib( n ) = def _fib( 0, prev, _ ) = prev _fib( 1, _, next ) = next _fib( n, prev, next ) = _fib( n - 1, next, next + prev ) _fib( n, 0, 1 ) ### Lazy List val fib = def _fib( a, b ) = a # _fib( b, a + b ) _fib( 0, 1 ) println( fib(10000) ) Output: 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875  ### Iterative def fib( n ) = a, b = 0, 1 for i <- 1..n a, b = b, a+b a ### Binet's Formula import math.sqrt def fib( n ) = phi = (1 + sqrt( 5 ))/2 int( (phi^n - (-phi)^-n)/sqrt(5) + .5 ) ### Matrix Exponentiation def mul( a, b ) = res = array( a.length(), b(0).length() ) for i <- 0:a.length(), j <- 0:b(0).length() res( i, j ) = sum( a(i, k)*b(k, j) | k <- 0:b.length() ) vector( res ) def pow( _, 0 ) = ((1, 0), (0, 1)) pow( x, 1 ) = x pow( x, n ) | 2|n = pow( mul(x, x), n\2 ) | otherwise = mul(x, pow( mul(x, x), (n - 1)\2 ) ) def fib( n ) = pow( ((0, 1), (1, 1)), n )(0, 1) for i <- 0..10 println( fib(i) ) Output: 0 1 1 2 3 5 8 13 21 34 55  ## Futhark ### Iterative  fun main(n: int): int = loop((a,b) = (0,1)) = for _i < n do (b, a + b) in a  ## FutureBasic ### Iterative 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 ifend fn = s1 long iCFTimeInterval 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 Cost is a time penalty  local fn Fibonacci( n as NSInteger ) as NSIntegerNSInteger resultif n < 2 then result = n : exit fnresult = fn Fibonacci( n-1 ) + fn Fibonacci( n-2 )end fn = result window 1 NSInteger iCFTimeInterval t t = fn CACurrentMediaTimefor i = 0 to 40print i;@".\t";fn Fibonacci(i)nextprint : 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æ 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 fib := function(n) local a; a := [[0, 1], [1, 1]]^n; return a[1][2];end; GAP has also a buit-in function for that. Fibonacci(n); ## Gecho 0 1 dup wover + dup wover + dup wover + dup wover + Prints the first several fibonacci numbers... ## GFA Basic  '' Compute nth Fibonacci number'' open a window for displayOPENW 1CLEARW 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% ENDSELECTENDFUNC  ## GML ///fibonacci(n)//Returns the nth fibonacci number var n, numb;n = argument0; if (n == 0) { numb = 0; }else { var fm2, fm1; fm2 = 0; fm1 = 1; numb = 1; repeat(n-1) { numb = fm2+fm1; fm2 = fm1; fm1 = numb; } } return numb; ## Go ### Recursive func fib(a int) int { if a < 2 { return a } return fib(a - 1) + fib(a - 2)} ### Iterative import ( "math/big") func fib(n uint64) *big.Int { if n < 2 { return big.NewInt(int64(n)) } a, b := big.NewInt(0), big.NewInt(1) for n--; n > 0; n-- { a.Add(a, b) a, b = b, a } return b} ### Iterative using a closure 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 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 Full "extra credit" solutions. ### Recursive A recursive closure must be pre-declared. def rFibrFib = { it == 0 ? 0 : it == 1 ? 1 : it > 1 ? rFib(it-1) + rFib(it-2) /*it < 0*/: rFib(it+2) - rFib(it+1) } ### Iterative 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 final φ = (1 + 5**(1/2))/2def 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 ### Recursive  #include "harbour.ch"Function fibb(a,b,n)return(if(--n>0,fibb(b,a+b,n),a))  ### Iterative  #include "harbour.ch"Function fibb(n) local fnow:=0, fnext:=1, tempf while (--n>0) tempf:=fnow+fnext fnow:=fnext fnext:=tempf end whilereturn(fnext)  ## Haskell ### Analytic 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 0fib n = (phi^^n - (-phi)^^(-n))/sqrt 5  Let's try it for large numbers:  λ> fib 10 :: CReal 055(0.01 secs, 137,576 bytes)λ> fib 100 :: CReal 0354224848179261915075(0.01 secs, 253,152 bytes)λ> fib 10000 :: CReal 033644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875(0.02 secs, 4,847,128 bytes)λ> fib (-10) :: CReal 0-55(0.01 secs, 138,408 bytes)  ### Recursive 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 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 Even faster and simpler is to use a defined memoizer (e.g. from MemoTrie package): import Data.MemoTriefib :: Integer -> Integerfib = 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.MemoTriefib :: Integer -> Integerfib = 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.MemoTriefib :: Integer -> Integerfib = memo $\case 0 -> 0 1 -> 1 n -> fib (n-1) + fib (n-2) The version that supports negative numbers: {-# Language LambdaCase #-}import Data.MemoTriefib :: Integer -> Integerfib = memo$ \case    0 -> 0   1 -> 1   n | n>0 -> fib (n-1) + fib (n-2)     | otherwise -> fib (n+2) - fib (n+1)

### Iterative

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

#### With lazy lists

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

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

Accumulator holds last two members of the series:

## Klingphix

: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

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++ (defn int fib (int n) (return (? (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))(main (prn (fib 30))) ## LabVIEW 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. ## lambdatalk  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,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676220,23416728348467684,37889062373143900,61305790721611580,99194853094755490,160500643816367070,259695496911122560,420196140727489660,679891637638612200,1100087778366101900,1779979416004714000,2880067194370816000,4660046610375530000] 5) Binet's formula (non recursive){def fib5 {lambda {:n} {let { {:n :n} {:sqrt5 {sqrt 5}} } {round {/ {- {pow {/ {+ 1 :sqrt5} 2} :n} {pow {/ {- 1 :sqrt5} 2} :n}} :sqrt5}}} }} {fib5 16} -> 987 (CPU ~ 1ms) {fib5 30} -> 832040 (CPU ~ 1ms){fib5 1000} -> 4.346655768693743e+208 (CPU ~ 1ms)  ## Lang5 [] '__A set : dip swap __A swap 2 compress collapse '__A set execute __A -1 extract nip ; : nip swap drop ; : tuck swap over ;: -rot rot rot ; : 0= 0 == ; : 1+ 1 + ; : 1- 1 - ; : sum '+ reduce ;: bi 'keep dip execute ; : keep over 'execute dip ; : fib dup 1 > if dup 1- fib swap 2 - fib + then ;: fib dup 1 > if "1- fib" "2 - fib" bi + then ; ## langur val .fibonacci = f if(.x < 2: .x ; self(.x - 1) + self(.x - 2)) writeln map .fibonacci, series 2..20 Output: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] ## Lasso  define fibonacci(n::integer) => { #n < 1 ? return false local( swap = 0, n1 = 0, n2 = 1 ) loop(#n) => { #swap = #n1 + #n2; #n2 = #n1; #n1 = #swap; } return #n1 } fibonacci(0) //->output falsefibonacci(1) //->output 1fibonacci(2) //->output 1fibonacci(3) //->output 2  ## Latitude ### Recursive fibo := { takes '[n]. if { n <= 1. } then { n. } else { fibo (n - 1) + fibo (n - 2). }.}. ### Memoization fibo := { takes '[n]. cache := here cache. { cache slot? (n ordinal). } ifFalse { cache slot (n ordinal) = if { n <= 1. } then { n. } else { fibo (n - 1) + fibo (n - 2). }. }. cache slot (n ordinal).} tap { ;; Attach the cache to the method object itself. #'self cache := Object clone.}. ## Lean It runs on Lean 3.4.2:  -- Our first implementation is the usual recursive definition:def fib1 : ℕ → ℕ | 0 := 0| 1 := 1| (n + 2) := fib1 n + fib1 (n + 1) -- We can give a second more efficient implementation using an auxiliary function:def fib_aux : ℕ → ℕ → ℕ → ℕ | 0 a b := b| (n + 1) a b := fib_aux n (a + b) a def fib2 : ℕ → ℕ | n := fib_aux n 1 0 -- Use #eval to check computations:#eval fib1 20#eval fib2 20 It runs on Lean 4:  -- Naive versiondef fib1 (n : Nat) : Nat := match n with | 0 => 0 | 1 => 1 | (k + 2) => fib1 k + fib1 (k + 1) -- More efficient versiondef fib_aux (n : Nat) (a : Nat) (b : Nat) : Nat := match n with | 0 => b | (k + 1) => fib_aux k (a + b) a def fib2 (n : Nat) : Nat := fib_aux n 1 0 -- Examples#eval fib1 20#eval fib2 20  ## LFE ### Recursive  (defun fib ((0) 0) ((1) 1) ((n) (+ (fib (- n 1)) (fib (- n 2)))))  ### Iterative  (defun fib ((n) (when (>= n 0)) (fib n 0 1))) (defun fib ((0 result _) result) ((n result next) (fib (- n 1) next (+ result next))))  ## Liberty BASIC ### Iterative/Recursive  for i = 0 to 15 print fiboR(i),fiboI(i)next i function fiboR(n) if n <= 1 then fiboR = n else fiboR = fiboR(n-1) + fiboR(n-2) end ifend function function fiboI(n) a = 0 b = 1 for i = 1 to n temp = a + b a = b b = temp next i fiboI = aend function  Output: 0 0 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55 89 89 144 144 233 233 377 377 610 610  ### Iterative/Negative  print "Rosetta Code - Fibonacci sequence": printprint " n Fn"for x=-12 to 12 '68 max print using("### ", x); using("##############", FibonacciTerm(x))next xprint[start]input "Enter a term#: "; n$n$=lower$(trim$(n$))if n$="" then print "Program complete.": endprint FibonacciTerm(val(n$))goto [start] function FibonacciTerm(n)    n=int(n)    FTa=0: FTb=1: FTc=-1    select case        case n=0  : FibonacciTerm=0  : exit function        case n=1  : FibonacciTerm=1  : exit function        case n=-1 : FibonacciTerm=-1 : exit function        case n>1            for x=2 to n                FibonacciTerm=FTa+FTb                FTa=FTb: FTb=FibonacciTerm            next x            exit function        case n<-1            for x=-2 to n step -1                FibonacciTerm=FTa+FTc                FTa=FTc: FTc=FibonacciTerm            next x            exit function    end selectend function 
Output:
Rosetta Code - Fibonacci sequence

n             Fn
-12           -144
-11            -89
-10            -55
-9            -34
-8            -21
-7            -13
-6             -8
-5             -5
-4             -3
-3             -2
-2             -1
-1             -1
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

Enter a term#: 12
144
Enter a term#:
Program complete.


## Lingo

### Recursive

on fib (n)  if n<2 then return n  return fib(n-1)+fib(n-2)end

### Iterative

on fib (n)  if n<2 then return n      fibPrev = 0  fib = 1  repeat with i = 2 to n    tmp = fib    fib = fib + fibPrev    fibPrev = tmp  end repeat  return fibend

### Analytic

on fib (n)  sqrt5 = sqrt(5.0)  p = (1+sqrt5)/2  q = 1 - p  return integer((power(p,n)-power(q,n))/sqrt5)end

## Lisaac

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

## LiveCode

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

## LLVM

; This is not strictly LLVM, as it uses the C library function "printf".; LLVM does not provide a way to print values, so the alternative would be; to just load the string into memory, and that would be boring. ; Additional comments have been inserted, as well as changes made from the output produced by clang such as putting more meaningful labels for the jumps "PRINT_LONG" = comdat any@"PRINT_LONG" = linkonce_odr unnamed_addr constant [5 x i8] c"%ld\0A\00", comdat, align 1 ;--- The declaration for the external C printf function.declare i32 @printf(i8*, ...) ;--------------------------------------------------------------------;-- Function for calculating the nth fibonacci numbers;--------------------------------------------------------------------define i32 @fibonacci(i32) { %2 = alloca i32, align 4 ;-- allocate local copy of n %3 = alloca i32, align 4 ;-- allocate a %4 = alloca i32, align 4 ;-- allocate b store i32 %0, i32* %2, align 4 ;-- store copy of n store i32 0, i32* %3, align 4 ;-- a := 0 store i32 1, i32* %4, align 4 ;-- b := 1 br label %loop loop: %5 = load i32, i32* %2, align 4 ;-- load n %6 = icmp sgt i32 %5, 0 ;-- n > 0 br i1 %6, label %loop_body, label %exit loop_body: %7 = load i32, i32* %3, align 4 ;-- load a %8 = load i32, i32* %4, align 4 ;-- load b %9 = add nsw i32 %7, %8 ;-- t = a + b store i32 %8, i32* %3, align 4 ;-- store a = b store i32 %9, i32* %4, align 4 ;-- store b = t %10 = load i32, i32* %2, align 4 ;-- load n %11 = add nsw i32 %10, -1 ;-- decrement n store i32 %11, i32* %2, align 4 ;-- store n br label %loop exit: %12 = load i32, i32* %3, align 4 ;-- load a ret i32 %12 ;-- return a} ;--------------------------------------------------------------------;-- Main function for printing successive fibonacci numbers;--------------------------------------------------------------------define i32 @main() { %1 = alloca i32, align 4 ;-- allocate index store i32 0, i32* %1, align 4 ;-- index := 0 br label %loop loop: %2 = load i32, i32* %1, align 4 ;-- load index %3 = icmp sle i32 %2, 12 ;-- index <= 12 br i1 %3, label %loop_body, label %exit loop_body: %4 = load i32, i32* %1, align 4 ;-- load index %5 = call i32 @fibonacci(i32 %4) %6 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @"PRINT_LONG", i32 0, i32 0), i32 %5) %7 = load i32, i32* %1, align 4 ;-- load index %8 = add nsw i32 %7, 1 ;-- increment index store i32 %8, i32* %1, align 4 ;-- store index br label %loop exit: ret i32 0 ;-- return EXIT_SUCCESS} Output: 0 1 1 2 3 5 8 13 21 34 55 89 144 ## Logo to fib :n [:a 0] [:b 1] if :n < 1 [output :a] output (fib :n-1 :b :a+:b)end ## LOLCODE  HAI 1.2HOW DUZ I fibonacci YR N EITHER OF BOTH SAEM N AN 1 AN BOTH SAEM N AN 0 O RLY? YA RLY, FOUND YR 1 NO WAI I HAS A N1 I HAS A N2 N1 R DIFF OF N AN 1 N2 R DIFF OF N AN 2 N1 R fibonacci N1 N2 R fibonacci N2 FOUND YR SUM OF N1 AN N2 OICIF U SAY SOKTHXBYE  ## LSL Rez a box on the ground, and add the following as a New Script. integer Fibonacci(integer n) { if(n<2) { return n; } else { return Fibonacci(n-1)+Fibonacci(n-2); }}default { state_entry() { integer x = 0; for(x=0 ; x<35 ; x++) { llOwnerSay("Fibonacci("+(string)x+")="+(string)Fibonacci(x)); } }} Output: Fibonacci(0)=0 Fibonacci(1)=1 Fibonacci(2)=1 Fibonacci(3)=2 Fibonacci(4)=3 Fibonacci(5)=5 Fibonacci(6)=8 Fibonacci(7)=13 Fibonacci(8)=21 Fibonacci(9)=34 Fibonacci(10)=55 Fibonacci(11)=89 Fibonacci(12)=144 Fibonacci(13)=233 Fibonacci(14)=377 Fibonacci(15)=610 Fibonacci(16)=987 Fibonacci(17)=1597 Fibonacci(18)=2584 Fibonacci(19)=4181 Fibonacci(20)=6765 Fibonacci(21)=10946 Fibonacci(22)=17711 Fibonacci(23)=28657 Fibonacci(24)=46368 Fibonacci(25)=75025 Fibonacci(26)=121393 Fibonacci(27)=196418 Fibonacci(28)=317811 Fibonacci(29)=514229 Fibonacci(30)=832040 Fibonacci(31)=1346269 Fibonacci(32)=2178309 Fibonacci(33)=3524578 Fibonacci(34)=5702887  ## Lua ### Recursive  --calculates the nth fibonacci number. Breaks for negative or non-integer n.function fibs(n) return n < 2 and n or fibs(n - 1) + fibs(n - 2) end  ### Pedantic Recursive  --more pedantic version, returns 0 for non-integer nfunction pfibs(n) if n ~= math.floor(n) then return 0 elseif n < 0 then return pfibs(n + 2) - pfibs(n + 1) elseif n < 2 then return n else return pfibs(n - 1) + pfibs(n - 2) endend  ### Tail Recursive  function a(n,u,s) if n<2 then return u+s end return a(n-1,u+s,u) endfunction trfib(i) return a(i-1,1,0) end  ### Table Recursive  fib_n = setmetatable({1, 1}, {__index = function(z,n) return n<=0 and 0 or z[n-1] + z[n-2] end})  ### Table Recursive 2  -- table recursive done properly (values are actually saved into table;-- also the first element of Fibonacci sequence is 0, so the initial table should be {0, 1}).fib_n = setmetatable({0, 1}, { __index = function(t,n) if n <= 0 then return 0 end t[n] = t[n-1] + t[n-2] return t[n] end})  ### Iterative  function ifibs(n) local p0,p1=0,1 for _=1,n do p0,p1 = p1,p0+p1 end return p0end  ## Luck function fib(x: int): int = ( let cache = {} in let fibc x = if x<=1 then x else ( if x not in cache then cache[x] = fibc(x-1) + fibc(x-2); cache[x] ) in fibc(x));;for x in range(10) do print(fib(x)) ## Lush (de fib-rec (n) (if (< n 2) n (+ (fib-rec (- n 2)) (fib-rec (- n 1))))) ## M2000 Interpreter Return decimal type and use an Inventory (as closure) to store known return values. All closures are in scope in every recursive call (we use here lambda(), but we can use fib(), If we make Fib1=fib then we have to use lambda() for recursion.  Inventory K=0:=0,1:=1fib=Lambda K (x as decimal)-> { If Exist(K, x) Then =Eval(K) :Exit Def Ret as Decimal Ret=If(x>1->Lambda(x-1)+Lambda(x-2), x) Append K, x:=Ret =Ret}\\ maximum 139For i=1 to 139 { Print Fib(i)}  Here an example where we use a BigNum class to make a Group which hold a stack of values, and take 14 digits per item in stack. We can use inventory to hold groups, so we use the fast fib() function from code above, where we remove the type definition of Ret variable, and set two first items in inventory as groups.  Class BigNum { a=stack Function Digits { =len(.a)*14-(14-len(str(stackitem(.a,len(.a)) ,"")))      }      Operator "+" (n) {            \\ we get a copy, but .a is pointer             \\ we make a copy, and get a new pointer            .a<=stack(.a)            acc=0            carry=0            const [email protected]                  k=min.data(Len(.a), len(n.a))                  i=each(.a, 1,k )                  j=each(n.a, 1,k)                  while  i, j {                        acc=stackitem(i)+stackitem(j)+carry                        carry= acc div d                        return .a, i^+1:=acc mod d                  }                   if len(.a)<len(n.a) Then  {                        i=each(n.a, k+1, -1)                        while i {                              acc=stackitem(i)+carry                              carry= acc div d                              stack .a  {data acc mod d}                        }                  } ELse.if len(.a)>len(n.a) Then  {                        i=each(.a, k+1, -1)                        while i {                              acc=stackitem(i)+carry                              carry= acc div d                              Return .a, i^+1:=acc mod d                              if carry else exit                        }                       }                  if carry then stack .a { data carry}      }      Function tostring${ if len(.a)=0 then ="0" : Exit if len(.a)=1 then =str$(Stackitem(.a),"") : Exit            document buf$=str$(Stackitem(.a, len(.a)),"")            for i=len(.a)-1 to  1 {                  Stack .a {                        buf$=str$(StackItem(i), "00000000000000")                  }            }            =buf$} class: Module BigNum (s$) {            s$=filter$(s$,"+-.,") if s$<>""  Then {                  repeat {                        If len(s$)<14 then Stack .a { Data val(s$) }: Exit                        Stack .a { Data  val(Right$(s$, 14)) }                        S$=Left$(S$, len(S$)-14)                  } Until S$="" } }} Inventory K=0:=BigNum("0"),1:=BigNum("1")fib=Lambda K (x as decimal)-> { If Exist(K, x) Then =Eval(K) :Exit Ret=If(x>1->Lambda(x-1)+Lambda(x-2), bignum(str$(x,"")))      Append K, x:=Ret      =Ret}\\ Using this to handle form  refresh by codeSet Fast!For i=1 to 4000 {      N=Fib(i)      Print i      Print N.tostring$() Refresh}  ## M4 define(fibo',ifelse(0,$1,0,ifelse(1,$1,1,eval(fibo(decr($1)) + fibo(decr(decr($1))))')')')dnldefine(loop',ifelse($1,$2,,$3($1) loop(incr($1),$2,$3')')')dnlloop(0,15,fibo')

            NORMAL MODE IS INTEGER             INTERNAL FUNCTION(N)            ENTRY TO FIB.            A = 0            B = 1            THROUGH LOOP, FOR N=N, -1, N.E.0            C = A + B            A = BLOOP        B = C            FUNCTION RETURN A            END OF FUNCTION             THROUGH SHOW, FOR I=0, 1, I.GE.20SHOW        PRINT FORMAT FNUM, I, FIB.(I)            VECTOR VALUES FNUM = $4HFIB(,I2,4H) = ,I4*$            END OF PROGRAM
Output:
FIB( 0) =    0
FIB( 1) =    1
FIB( 2) =    1
FIB( 3) =    2
FIB( 4) =    3
FIB( 5) =    5
FIB( 6) =    8
FIB( 7) =   13
FIB( 8) =   21
FIB( 9) =   34
FIB(10) =   55
FIB(11) =   89
FIB(12) =  144
FIB(13) =  233
FIB(14) =  377
FIB(15) =  610
FIB(16) =  987
FIB(17) = 1597
FIB(18) = 2584
FIB(19) = 4181

## Maple

 > f := n -> ifelse(n<3,1,f(n-1)+f(n-2));> f(2);  1> f(3);  2

## Mathematica / Wolfram Language

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

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

An optimization is to cache the values already calculated:

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

The above implementations may be too simplistic, as the first is incredibly slow for any reasonable range due to nested recursions and while the second is faster it uses an increasing amount of memory. The following uses recursion much more effectively while not using memory:

fibi[prvprv_Integer, prv_Integer, rm_Integer] :=  If[rm < 1, prvprv, fibi[prv, prvprv + prv, rm - 1]]fib[n_Integer] := fibi[0, 1, n]

However, the recursive approaches in Mathematica are limited by the limit set for recursion depth (default 1024 or 4096 for the above cases), limiting the range for 'n' to about 1000 or 2000. The following using an iterative approach has an extremely high limit (greater than a million):

fib[n_Integer] := Block[{tmp, prvprv = 0, prv = 1},  For[i = 0, i < n, i++, tmp = prv; prv += prvprv; prvprv = tmp];  Return[prvprv]]

If one wanted a list of Fibonacci numbers, the following is quite efficient:

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

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

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, \1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, \196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, \9227465, 14930352, 24157817, 39088169, 63245986, 102334155, \165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, \2971215073, 4807526976, 7778742049, 12586269025, 20365011074, \32951280099, 53316291173, 86267571272, 139583862445, 225851433717, \365435296162, 591286729879, 956722026041, 1548008755920, \2504730781961, 4052739537881, 6557470319842, 10610209857723, \17167680177565, 27777890035288, 44945570212853, 72723460248141, \117669030460994, 190392490709135, 308061521170129, 498454011879264, \806515533049393, 1304969544928657, 2111485077978050, \3416454622906707, 5527939700884757, 8944394323791464, \14472334024676221, 23416728348467685, 37889062373143906, \61305790721611591, 99194853094755497, 160500643816367088, \259695496911122585, 420196140727489673, 679891637638612258, \1100087778366101931, 1779979416004714189, 2880067194370816120, \4660046610375530309, 7540113804746346429, 12200160415121876738, \19740274219868223167, 31940434634990099905, 51680708854858323072, \83621143489848422977, 135301852344706746049, 218922995834555169026, \354224848179261915075}

The Wolfram Language can also solve recurrence equations using the built-in function RSolve

fib[n] /. RSolve[{fib[n] == fib[n - 1] + fib[n - 2], fib[0] == 0,     fib[1] == 1}, fib[n], n][[1]]

which evaluates to the built-in function Fibonacci[n]

This function can also be expressed as

Fibonacci[n] // FunctionExpand // FullSimplify

which evaluates to

(2^-n ((1 + Sqrt[5])^n - (-1 + Sqrt[5])^n Cos[n π]))/Sqrt[5]

and is defined for all real or complex values of n.

## MATLAB

### Matrix

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

### Iterative

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

### Dramadah Matrix Method

The MATLAB help file suggests an interesting method of generating the Fibonacci numbers. Apparently the determinate of the Dramadah Matrix of type 3 (MATLAB designation) and size n-by-n is the nth Fibonacci number. This method is implimented below.

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

### Tartaglia/Pascal Triangle Method

 function number = fibonacci(n)%construct the Tartaglia/Pascal Triangle    pt=tril(ones(n));    for r = 3 : n    % Every element is the addition of the two elements    % on top of it. That means the previous row.        for c = 2 : r-1            pt(r, c) = pt(r-1, c-1) + pt(r-1, c);        end       end    number=trace(rot90(pt));end

## Maxima

### Tail Recursive

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

## NESL

### Recursive

function fib(n) = if n < 2 then n else fib(n - 2) + fib(n - 1);

## NetRexx

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

## NewLISP

### Iterative

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

### Recursive

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

### Matrix multiplication

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

### With a stack

 ;;;	Global variable (bigints); can be isolated in a namespace if need be(setq stack '(0L 1L));;;;	If the stack is too short, complete it; then read from it;;;	Adding at the end of a list is optimized in NewLisp(define (fib n)	(while (<= (length stack) n)		(push (+ (stack -1) (stack -2)) stack -1))	(stack n));;;; Test (~ 7+ s on my mediocre laptop);(println (time (fib 50000)));;;	or(println (length (fib 50000)));;;	outputs 10450 (digits)

## NGS

### Iterative

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

## Nial

### Iterative

On my machine, about 1.7s for 100,000 iterations, n=92. Maybe a few percent faster than iterative Python. Note that n>92 produces overflow; Python keeps going - single iteration with n=1,000,000 takes it about 15s.

fibi is op n {  if n<2 then     n  else     x1:=0; x2:=1;     for i with tell (n - 1) do       x:=x1+x2;      x1:=x2;      x2:=x;    endfor;    x2  endif};

Iterative using fold. Slightly faster, <1.6s:

fibf is op n {1 pick ((n- 1) fold [1 pick, +] 0 1)};

Tacit verion of above. Slightly faster still, <1.4s:

fibf2 is 1 pick fold [1 pick, +] reverse (0 1 hitch) (-1+);

### Recursive

Really slow (over 8s for single iteration, n=33). (Similar to time for recursive python version with n=37.)

fibr is op n {fork [2>, +, + [fibr (-1 +), fibr (-2 +)]] n};

...or tacit version. More than twice as fast (?) but still slow:

fibr2 is fork [2>, +, + [fibr2 (-1 +), fibr2 (-2 +)]];

### Matrix

Matrix inner product (ip). This appears to be the fastest, about 1.0s for 100,000 iterations, n=92: Note that n>92 produces negative result.

fibm is op n {floor (0 1 pick (reduce ip (n reshape [2 2 reshape 1 1 1 0])))};

Could it look a little more like J? (Maybe 5% slower than above.)

$is reshape;~ is tr f op a b {b f a}; % Goes before verb, rather than after like in J;_ is floor; % Not really J, but J-ish? (Cannot redefine "<.".); fibm2 is _(0 1 pick reduce ip([2 2$1 1 1 0](~$))); Alternate, not involving replicating matrix n times, but maybe 50% slower than the fastest matrix version above - similar speed to iterative: fibm3 is op n {a:=2 2$1 1 1 0; _(0 1 pick ((n- 1) fold (a ip) a))};

## Nim

### Analytic

proc Fibonacci(n: int): int64 =  var fn = float64(n)  var p: float64 = (1.0 + sqrt(5.0)) / 2.0  var q: float64 = 1.0 / p  return int64((pow(p, fn) + pow(q, fn)) / sqrt(5.0))

### Iterative

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

### Recursive

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

### Tail-recursive

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

### Continuations

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

## Nix

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

## Oberon-2

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


## Objeck

### Recursive

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

## Objective-C

### Recursive

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

### Iterative

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

## OCaml

### Iterative

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

### Recursive

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

### Arbitrary Precision

Using OCaml's Num module.

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

compile with:

ocamlopt nums.cmxa -o fib fib.ml

Output:
$./fib 0 0$ ./fib 10
55
$./fib 399 108788617463475645289761992289049744844995705477812699099751202749393926359816304226$ ./fib -6
-8


### O(log(n)) with arbitrary precision

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

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

## Octave

### Recursive

% recursivefunction fibo = recfibo(n)  if ( n < 2 )    fibo = n;  else    fibo = recfibo(n-1) + recfibo(n-2);  endifendfunction

Testing

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

### Iterative

% iterativefunction fibo = iterfibo(n)  if ( n < 2 )    fibo = n;  else    f = zeros(2,1);    f(1) = 0;     f(2) = 1;    for i = 2 : n      t = f(2);      f(2) = f(1) + f(2);      f(1) = t;    endfor    fibo = f(2);  endifendfunction

Testing

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

### Analytic

function retval = fibanalytic(n)  retval = round(((5 .^ 0.5 + 1) / 2) .^ n / 5 .^ 0.5);endfunction

### Tail Recursive

function retval = fibtailrecursive(n, prevfib = 0, fib = 1)  if (n == 0)    retval = prevfib;  else    retval = fibtailrecursive(n - 1, fib, prevfib + fib);  endifendfunction

## Oforth

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

## Ol

Same as Scheme example(s).

## OPL

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

## Order

### Recursive

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

Tail recursive version (example supplied with language):

#include <order/interpreter.h> #define ORDER_PP_DEF_8fib                                         \ORDER_PP_FN(8fn(8N,                                               \                8fib_iter(8N, 0, 1))) #define ORDER_PP_DEF_8fib_iter                                    \ORDER_PP_FN(8fn(8N, 8I, 8J,                                       \                8if(8is_0(8N),                                    \                    8I,                                           \                    8fib_iter(8dec(8N), 8J, 8add(8I, 8J))))) ORDER_PP(8to_lit(8fib(8nat(5,0,0))))

### Memoization

#include <order/interpreter.h> #define ORDER_PP_DEF_8fib_memo                                    \ORDER_PP_FN(8fn(8N,                                               \                8tuple_at(0, 8fib_memo_inner(8N, 8seq))))  #define ORDER_PP_DEF_8fib_memo_inner                                            \ORDER_PP_FN(8fn(8N, 8M,                                                         \                8cond((8less(8N, 8seq_size(8M)), 8pair(8seq_at(8N, 8M), 8M))    \                      (8equal(8N, 0), 8pair(0, 8seq(0)))                        \                      (8equal(8N, 1), 8pair(1, 8seq(0, 1)))                     \                      (8else,                                                   \                        8lets((8S, 8fib_memo_inner(8sub(8N, 2), 8M))            \                              (8T, 8fib_memo_inner(8dec(8N), 8tuple_at(1, 8S))) \                              (8U, 8add(8tuple_at(0, 8S), 8tuple_at(0, 8T))),   \                              8pair(8U,                                         \                                    8seq_append(8tuple_at(1, 8T), 8seq(8U))))))))  ORDER_PP(8for_each_in_range(8fn(8N,                       8print(8to_lit(8fib_memo(8N)) (,) 8space)),                   1, 21))

## Oz

### Iterative

Using mutable references (cells).

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

### Recursive

Inefficient (blows up the stack).

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

### Tail-recursive

Using accumulators.

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

### Lazy-recursive

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

## PARI/GP

### Built-in

fibonocci(n)

### Matrix

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

### Analytic

This uses the Binet form.

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

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

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

### Algebraic

This is an exact version of the above formula. quadgen(5) represents ${\displaystyle \phi }$ and the number is stored in the form ${\displaystyle a+b\phi }$. imag takes the coefficient of ${\displaystyle \phi }$. This uses the relation

${\displaystyle \phi ^{n}=F_{n-1}+F_{n}\phi }$

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

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

A more direct translation (note that ${\displaystyle {\sqrt {5}}=2\phi -1}$) would be

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

### Combinatorial

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

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

### Binary powering

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

### Recursive

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

### Anonymous recursion

Works with: PARI/GP version 2.8.0+

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

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

It can be used without being named:

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

gives

Output:
%1 = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

### Memoization

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

### Iterative

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

### Chebyshev

This solution uses Chebyshev polynomials of the second kind (Chyebyshev U-polynomials).

fib(n)=n--;polchebyshev(n,2,I/2)*I^n;

or

fib(n)=abs(polchebyshev(n-1,2,I/2));

All n×n (0,1) lower Hessenberg matrices have determinant at most F(n). The n×n anti-Hadamard matrix[1] matches this upper bound, and hence can be used as an inefficient method for computing Fibonacci numbers of positive index. These matrices are the same as Matlab's type-3 "Dramadah" matrices, following a naming suggestion of C. L. Mallows according to Graham & Sloane.

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

### Testing adjacent bits

The Fibonacci numbers can be characterized (for n > 0) as the number of n-bit strings starting and ending with 1 without adjacent 0s. This inefficient, exponential-time algorithm demonstrates:

fib(n)={  my(g=2^(n+1)-1);  sum(i=2^(n-1),2^n-1,    bitor(i,i<<1)==g  );}

### One-by-one

This code is purely for amusement and requires n > 1. It tests numbers in order to see if they are Fibonacci numbers, and waits until it has seen n of them.

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

## Pascal

### Analytic

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

### Recursive

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

### Iterative

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