# 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 register
SAVEAREA B     STM-SAVEAREA(R15) skip savearea
DC    17F'0'          savearea
DC    CL8'FIBONACC'   eyecatcher
STM      STM   R14,R12,12(R13) save previous context
*        ----
LA    R1,0            f(n-2)=0
LA    R2,1            f(n-1)=1
LA    R4,2            n=2
LA    R6,1            step
LH    R7,NN           limit
LOOP     EQU   *               for n=2 to nn
LR    R3,R2             f(n)=f(n-1)
AR    R3,R1             f(n)=f(n-1)+f(n-2)
CVD   R4,PW             n  convert binary to packed (PL8)
UNPK  ZW,PW             packed (PL8) to zoned (ZL16)
MVC   CW,ZW             zoned (ZL16) to  char (CL16)
OI    CW+L'CW-1,X'F0'   zap sign
MVC   WTOBUF+5(2),CW+14 output
CVD   R3,PW             f(n) binary to packed decimal (PL8)
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
*        ----  DATA
NN       DC    H'46'           nn max n
PW       DS    PL8             15num
ZW       DS    ZL16
CW       DS    CL16
ZN       DS    CL20
*                  ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15num
WTOMSG   DS    0F
DC    H'80',XL2'0000'
*                   fibo(46)=1836311903
WTOBUF   DC    CL80'fibo(12)=1234567890'
REGEQU
END   FIBONACC
Output:
...
fibo(41)=   165,580,141
fibo(42)=   267,914,296
fibo(43)=   433,494,437
fibo(44)=   701,408,733
fibo(45)= 1,134,903,170
fibo(46)= 1,836,311,903


### using packed decimals

*        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
*        ----
ZAP    FNM2,=P'0'         f(0)=0
ZAP    FNM1,=P'1'         f(1)=1
LA     R4,2               n=2
LA     R6,1               step
LH     R7,NN              limit
LOOP     EQU    *                  for n=2 to nn
ZAP    FN,FNM1              f(n)=f(n-2)
AP     FN,FNM2              f(n)=f(n-1)+f(n-2)
CVD    R4,PW                n
ED     ZN,PW                packed dec (PL8) to char (CL16)
MVC    WTOBUF+5(2),ZN+L'ZN-2  output
ED     ZN,FN                packed dec (PL8) to char (CL16)
MVC    WTOBUF+9(L'ZN),ZN        output
WTO    MF=(E,WTOMSG)        write buffer
ZAP    FNM2,FNM1            f(n-2)=f(n-1)
ZAP    FNM1,FN              f(n-1)=f(n)
BXLE   R4,R6,LOOP         endfor n
*        ----
L      R13,4(0,R13)       restore previous savearea pointer
RETURN (14,12),RC=0       restore registers from calling sav
*        ----   DATA
NN       DC     H'73'              nn
FNM2     DS     PL8                f(n-2)
FNM1     DS     PL8                f(n-1)
FN       DS     PL8                f(n)
PW       DS     PL8                15num
ZN       DS     CL20
*                   ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15num
WTOMSG   DS     0F
DC     H'80',XL2'0000'
*                    fibo(73)=806515533049393
WTOBUF   DC     CL80'fibo(12)=123456789012345 '
REGEQU
END    FIBOWTOP
Output:
...
fibo(68)=  72,723,460,248,141
fibo(69)= 117,669,030,460,994
fibo(70)= 190,392,490,709,135
fibo(71)= 308,061,521,170,129
fibo(72)= 498,454,011,879,264
fibo(73)= 806,515,533,049,393


## 6502 Assembly

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

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

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

## 68000 Assembly

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
CMP.L #1,D4
BHI .foo
.bar:
MOVE.L D5,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,  0
LOOP:   MOV  D,  A
ADD  B      ; A := A + B
MOV  B,  D
DCR  C
JNZ  LOOP   ; jump if not zero
RET         ; return from subroutine

The range may be easily be extended from the 13th (=233) to the 24th (=46368) Fibonacci number with 16-bit addition using DAD. The code here assumes the CP/M operating system.

	;-------------------------------------------------------
; useful equates
;-------------------------------------------------------
bdos	equ 	5	; BDOS entry
cr	    equ 	13	; ASCII carriage return
lf	    equ 	10	; ASCII line feed
space	equ	    32	; ASCII space char
conout	equ 	2	; BDOS console output function
putstr	equ	    9	; BDOS print string function
;-------------------------------------------------------
; program code begins here
;-------------------------------------------------------
org	    100h    ; load point under CP/M
lxi	    h,0		; save command processor's stack
shld	oldstk
lxi	    sp,stack	; set our own stack
lxi	    d,signon	; print signon message
mvi	    c,putstr
call	bdos
mvi 	a,1		; test by displaying first 20
mloop:	push	a		; save our count (putdec will trash)
call 	fib
call	putdec
mvi	    a,space		; separate the numbers
call	putchr
pop	    a		; get our count back
inr	    a		; increase it by one
cpi	    20+1		; have we reached our limit?
jnz	    mloop		; not yet; do another
lhld	oldstk		; we're done - get CP/M's stack back
sphl			; restore it
ret			    ; back to command processor
;-------------------------------------------------------
;  calculate nth Fibonacci number
;  entry: A = n
;  exit:  HL = Fib(n)
;-------------------------------------------------------
fib:	mov 	c,a	; C holds n
lxi 	d,0	; initial value for Fib(n-2)
lxi 	h,1	; intiial value for Fib(n-1)
fib2:	dcr	c
jz	fib3	; we're done
push 	h	; save Fib(n-1)
dad 	d	; HL holds Fib(n)
pop 	d	; Former Fib(n-1) now Fib(n-2)
jmp 	fib2	; loop until done
fib3:	ret
;-------------------------------------------------------
; console output of char in A register
;-------------------------------------------------------
putchr:
push	h
push	d
push	b
mov	    e,a
mvi	    c,conout
call	bdos
pop	b
pop	d
pop	h
ret
;---------------------------------------------------------
; Output decimal number to console
; HL holds 16-bit unsigned binary number to print
;---------------------------------------------------------
putdec: push	b
push	d
push	h
lxi	    b,-10
lxi	    d,-1
putdec2:
inx	    d
jc	    putdec2
lxi	    b,10
xchg
mov	    a,h
ora	    l
cnz	    putdec		; recursive call
mov	    a,e
call	putchr
pop	h
pop	d
pop	b
ret
;-------------------------------------------------------
; message and data area
;-------------------------------------------------------
signon: db	'First 20 Fibonacci numbers:',cr,lf,'$' oldstk: dw 0 stack equ$+128		; 64-level stack
;
end
Output:
First 20 Fibonacci numbers:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765


## 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_4
LBB0_3:
lea     DI, WORD PTR [BX - 1]   ;DI = BX - 1
call    fib			;RETURN FIB(BX-1)
mov     BP, AX			;STORE THIS IN BP
mov     DI, BX
call    fib			;GET FIB(DI - 2)
add     AX, BP		        ;RETURN FIB(DI - 1) + FIB(DI - 2)
LBB0_4:

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


## 8th

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
FI
RETURN (curr)

PROC Main()
BYTE n
INT f

Put(125) ;clear screen

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

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

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) & " ) = ");
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

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) & " ) = ");
end Fibonacci;

Output:
> ./fibonacci 777
Fibonacci( 777 ) = 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082

### Fast method using fast matrix exponentiation

with 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 while
return(fnext)

## Agda

module FibonacciSequence where

open import Data.Nat using (ℕ ; zero ; suc ; _+_)

rec_fib : (m : ℕ) -> (a : ℕ) -> (b : ℕ) -> ℕ
rec_fib zero a b = a
rec_fib (suc k) a b = rec_fib k b (a + b)

fib : (n : ℕ) -> ℕ
fib n = rec_fib n zero (suc zero)


## Aime

integer
fibs(integer n)
{
integer w;

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

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

return w;
}

## ALGOL 60

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
Next
Return(B)
Output:
$hopper src/fibo1.bas 25 75025 75025 75025  ## AntLang /Sequence fib:{<0;1> {x,<x[-1]+x[-2]>}/ range[x]} /nth fibn:{fib[x][x]} ## Apex /* author: snugsfbay date: March 3, 2016 description: Create a list of x numbers in the Fibonacci sequence. - user may specify the length of the list - enforces a minimum of 2 numbers in the sequence because any fewer is not a sequence - enforces a maximum of 47 because further values are too large for integer data type - Fibonacci sequence always starts with 0 and 1 by definition */ public class FibNumbers{ final static Integer MIN = 2; //minimum length of sequence final static Integer MAX = 47; //maximum length of sequence /* description: method to create a list of numbers in the Fibonacci sequence param: user specified integer representing length of sequence should be 2-47, inclusive. - Sequence starts with 0 and 1 by definition so the minimum length could be as low as 2. - For 48th number in sequence or greater, code would require a Long data type rather than an Integer. return: list of integers in sequence. */ public static List<Integer> makeSeq(Integer len){ List<Integer> fib = new List<Integer>{0,1}; // initialize list with first two values Integer i; if(len<MIN || len==null || len>MAX) { if (len>MAX){ len=MAX; //set length to maximum if user entered too high a value }else{ len=MIN; //set length to minimum if user entered too low a value or none } } //This could be refactored using teneray operator, but we want code coverage to be reflected for each condition //start with initial list size to find previous two values in the sequence, continue incrementing until list reaches user defined length for(i=fib.size(); i<len; i++){ fib.add(fib[i-1]+fib[i-2]); //create new number based on previous numbers and add that to the list } return fib; } } ## APL #### Naive Recursive Works with: Dyalog APL fib←{⍵≤1:⍵ ⋄ (∇ ⍵-1)+∇ ⍵-2}  Read this as: In the variable "fib", store the function that says, if the argument is less than or equal to 1, return the argument. Else, calculate the value you get when you recursively call the current function with the argument of the current argument minus one and add that to the value you get when you recursively call the current function with the argument of the current function minus two. This naive solution requires Dyalog APL because GNU APL does not support this syntax for conditional guards. #### Array Works with: Dyalog APL Works with: GNU APL Since APL is an array language we'll use the following identity: ${\displaystyle \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.}$ In APL: ↑+.×/N/⊂2 2⍴1 1 1 0  Plugging in 4 for N gives the following result: ${\displaystyle \begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix}}$ Here's what happens: We replicate the 2-by-2 matrix N times and then apply inner product-replication. The First removes the shell from the Enclose. At this point we're basically done, but we need to pick out only ${\displaystyle F_n}$ in order to complete the task. Here's one way: ↑0 1↓↑+.×/N/⊂2 2⍴1 1 1 0  #### Analytic Works with: Dyalog APL Works with: GNU APL An alternative approach, using Binet's formula (which was apparently known long before Binet): ⌊.5+(((1+PHI)÷2)*⍳N)÷PHI←5*.5  ## AppleScript ### Imperative set fibs to {} set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3")) set x to x as integer repeat with y from 1 to x if (y = 1 or y = 2) then copy 1 to the end of fibs else copy ((item (y - 1) of fibs) + (item (y - 2) of fibs)) to the end of fibs end if end repeat return item x of fibs  ### Functional The simple recursive version is famously slow: on fib(n) if n < 1 then 0 else if n < 3 then 1 else fib(n - 2) + fib(n - 1) end if end fib  but we can combine enumFromTo(m, n) with the accumulator of a higher-order fold/reduce function to memoize the series: Translation of: JavaScript (ES6 memoized fold example) Translation of: Haskell (Memoized fold example) -------------------- FIBONACCI SEQUENCE -------------------- -- fib :: Int -> Int on fib(n) -- lastTwo : (Int, Int) -> (Int, Int) script lastTwo on |λ|([a, b]) [b, a + b] end |λ| end script item 1 of foldl(lastTwo, {0, 1}, enumFromTo(1, n)) end fib --------------------------- TEST --------------------------- on run fib(32) --> 2178309 end run -------------------- GENERIC FUNCTIONS --------------------- -- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m, n) if m ≤ n then set lst to {} repeat with i from m to n set end of lst to i end repeat lst else {} end if end enumFromTo -- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs) tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to |λ|(v, item i of xs, i, xs) end repeat return v end tell end foldl -- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f) if class of f is script then f else script property |λ| : f end script end if end mReturn  Output: 2178309 ## Arendelle ( fibonacci , 1; 1 ) [ 98 , // 100 numbers of fibonacci ( fibonacci[ @fibonacci? ] , @fibonacci[ @fibonacci - 1 ] + @fibonacci[ @fibonacci - 2 ] ) "Index: | @fibonacci? | => | @fibonacci[ @fibonacci? - 1 ] |" ] ## ARM Assembly Expects to be called with ${\displaystyle n}$ in R0, and will return ${\displaystyle f(n)}$ in the same register. fibonacci: push {r1-r3} mov r1, #0 mov r2, #1 fibloop: mov r3, r2 add r2, r1, r2 mov r1, r3 sub r0, r0, #1 cmp r0, #1 bne fibloop mov r0, r2 pop {r1-r3} mov pc, lr ## ArnoldC IT'S SHOWTIME HEY CHRISTMAS TREE f1 YOU SET US UP @I LIED TALK TO THE HAND f1 HEY CHRISTMAS TREE f2 YOU SET US UP @NO PROBLEMO HEY CHRISTMAS TREE f3 YOU SET US UP @I LIED STICK AROUND @NO PROBLEMO GET TO THE CHOPPER f3 HERE IS MY INVITATION f1 GET UP f2 ENOUGH TALK TALK TO THE HAND f3 GET TO THE CHOPPER f1 HERE IS MY INVITATION f2 ENOUGH TALK GET TO THE CHOPPER f2 HERE IS MY INVITATION f3 ENOUGH TALK CHILL YOU HAVE BEEN TERMINATED ## Arturo ### Recursive fib:$[x][
if? x<2 [1]
else [(fib x-1) + (fib x-2)]
]

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

## AsciiDots

/--#$--\ | | >-*>{+}/ | \+-/ 1 | # 1 | # | | . . ## ATS ### Recursive fun fib_rec(n: int): int = if n >= 2 then fib_rec(n-1) + fib_rec(n-2) else n ### Iterative (* ** This one is also referred to as being tail-recursive *) fun fib_trec(n: int): int = if n > 0 then (fix loop (i:int, r0:int, r1:int): int => if i > 1 then loop (i-1, r1, r0+r1) else r1)(n, 0, 1) else 0 ### Iterative and Verified (* ** This implementation is verified! *) dataprop FIB (int, int) = | FIB0 (0, 0) | FIB1 (1, 1) | {n:nat} {r0,r1:int} FIB2 (n+2, r0+r1) of (FIB (n, r0), FIB (n+1, r1)) // end of [FIB] // end of [dataprop] fun fibats{n:nat} (n: int (n)) : [r:int] (FIB (n, r) | int r) = let fun loop {i:nat | i <= n}{r0,r1:int} ( pf0: FIB (i, r0), pf1: FIB (i+1, r1) | ni: int (n-i), r0: int r0, r1: int r1 ) : [r:int] (FIB (n, r) | int r) = if (ni > 0) then loop{i+1}(pf1, FIB2 (pf0, pf1) | ni - 1, r1, r0 + r1) else (pf0 | r0) // end of [if] // end of [loop] in loop {0} (FIB0 (), FIB1 () | n, 0, 1) end // end of [fibats] ### Matrix-based (* ****** ****** *) // // How to compile: // patscc -o fib fib.dats // (* ****** ****** *) // #include "share/atspre_staload.hats" // (* ****** ****** *) // abst@ype int3_t0ype = (int, int, int) // typedef int3 = int3_t0ype // (* ****** ****** *) extern fun int3 : (int, int, int) -<> int3 extern fun int3_1 : int3 -<> int extern fun mul_int3_int3: (int3, int3) -<> int3 (* ****** ****** *) local assume int3_t0ype = (int, int, int) in (* in-of-local *) // implement int3 (x, y, z) = @(x, y, z) // implement int3_1 (xyz) = xyz.1 // implement mul_int3_int3 ( @(a,b,c), @(d,e,f) ) = (a*d + b*e, a*e + b*f, b*e + c*f) // end // end of [local] (* ****** ****** *) // implement gnumber_int<int3> (n) = int3(n, 0, n) // implement gmul_val<int3> = mul_int3_int3 // (* ****** ****** *) // fun fib (n: intGte(0)): int = int3_1(gpow_int_val<int3> (n, int3(1, 1, 0))) // (* ****** ****** *) implement main0 () = { // val N = 10 val () = println! ("fib(", N, ") = ", fib(N)) val N = 20 val () = println! ("fib(", N, ") = ", fib(N)) val N = 30 val () = println! ("fib(", N, ") = ", fib(N)) val N = 40 val () = println! ("fib(", N, ") = ", fib(N)) // } (* end of [main0] *) ## AutoHotkey Search autohotkey.com: sequence ### Iterative Translation of: C Loop, 5 MsgBox % fib(A_Index) Return fib(n) { If (n < 2) Return n i := last := this := 1 While (i <= n) { new := last + this last := this this := new i++ } Return this }  ### Recursive and iterative Source: AutoHotkey forum by Laszlo /* Important note: the recursive version would be very slow without a global or static array. The iterative version handles also negative arguments properly. */ FibR(n) { ; n-th Fibonacci number (n>=0, recursive with static array Fibo) Static Return n<2 ? n : Fibo%n% ? Fibo%n% : Fibo%n% := FibR(n-1)+FibR(n-2) } Fib(n) { ; n-th Fibonacci number (n < 0 OK, iterative) a := 0, b := 1 Loop % abs(n)-1 c := b, b += a, a := c Return n=0 ? 0 : n>0 || n&1 ? b : -b }  ## AutoIt ### Iterative #AutoIt Version: 3.2.10.0$n0 = 0
$n1 = 1$n = 10
MsgBox (0,"Iterative Fibonacci ", it_febo($n0,$n1,$n)) Func it_febo($n_0,$n_1,$N)
$first =$n_0
$second =$n_1
$next =$first + $second$febo = 0
For $i = 1 To$N-3
$first =$second
$second =$next
$next =$first + $second Next if$n==0 Then
$febo = 0 ElseIf$n==1 Then
$febo =$n_0
ElseIf $n==2 Then$febo = $n_1 Else$febo = $next EndIf Return$febo
EndFunc


### Recursive

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


## AWK

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

$awk 'func fib(n){return(n<2?n:fib(n-1)+fib(n-2))}{print "fib("$1")="fib($1)}' 10 fib(10)=55  ## Axe A recursive solution is not practical in Axe because there is no concept of variable scope in Axe. Iterative solution: Lbl FIB r₁→N 0→I 1→J For(K,1,N) I+J→T J→I T→J End J Return ## Babel In Babel, we can define fib using a stack-based approach that is not recursive: fib { <- 0 1 { dup <- + -> swap } -> times zap } < foo x < puts x in foo. In this case, x is the code list between the curly-braces. This is how you define callable code in Babel. The definition works by initializing the stack with 0, 1. On each iteration of the times loop, the function duplicates the top element. In the first iteration, this gives 0, 1, 1. Then it moves down the stack with the <- operator, giving 0, 1 again. It adds, giving 1. then it moves back up the stack, giving 1, 1. Then it swaps. On the next iteration this gives: 1, 1, 1 (dup) 1, 1, (<-) 2 (+) 2, 1 (->) 1, 2 (swap)  And so on. To test fib: {19 iter - fib !} 20 times collect ! lsnum ! Output: ( 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ) ## bash ### Iterative $ fib=1;j=1;while((fib<100));do echo $fib;((k=fib+j,fib=j,j=k));done  1 1 2 3 5 8 13 21 34 55 89  ### Recursive fib() { if [$1 -le 0 ]
then
echo 0
return 0
fi
if [ $1 -le 2 ] then echo 1 else a=$(fib $[$1-1])
b=$(fib$[$1-2]) echo$(($a+$b))
fi
}


## BASIC

### 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 = ",f
limit = 500                        # set upper limit - can be changed, removed
f = int(f)
if f > limit then f = limit
a = 0 : b = 1 : c = 0 : n = 0      # initial values

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

end while

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

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

### Chipmunk Basic

Works with: Chipmunk Basic version 3.6.4
100 cls
110 for i = 0 to 20 : print fibor(i); : next i
120 print
130 for i = 0 to 20 : print fiboi(i); : next i
140 print
150 for i = 0 to 20 : print fiboa(i); : next i
160 end
170 sub fibor(n) : 'Recursive
180   if n < 2 then
190     fibor = n
200   else
210     fibor = fibor(n-1)+fibor(n-2)
220   endif
230 end sub
240 sub fiboi(n) : 'Iterative
250   n1 = 0
260   n2 = 1
270   for k = 1 to abs(n)
280     sum = n1+n2
290     n1 = n2
300     n2 = sum
310   next k
320   if n < 0 then
330     fiboi = n1*((-1)^((-n)+1))
340   else
350     fiboi = n1
360   endif
370 end sub
380 sub fiboa(n) : 'Analytic
390   fiboa = int(0.5+(((sqr 5+1)/2)^n)/sqr 5)
400 end sub

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

### Commodore BASIC

100 PRINT CHR$(147); CHR$(18); "****      FIBONACCI GENERATOR       ****"
110 INPUT "MIN, MAX"; N1, N2
120 IF N1 > N2 THEN T = N1: N1 = N2: N2 = T
130 A = 0: B = 1: S = SGN(N1)
140 FOR I = S TO N1 STEP S
150 : IF S > 0 THEN T = A + B: A = B: B = T
160 : IF S < 0 THEN T = B - A: B = A: A = T
170 NEXT I
180 PRINT
190 PRINT STR$(A); : REM STR$() PREVENTS TRAILING SPACE
200 IF N2 = N1 THEN 250
210 FOR I = N1 + 1 TO N2
220 : T = A + B: A = B: B = T
230 : PRINT ","; STR$(A); 240 NEXT I 250 PRINT  Output: **** FIBONACCI GENERATOR **** MIN, MAX? -6,6 -8, 5,-3, 2,-1, 1, 0, 1, 1, 2, 3, 5, 8 READY. ### Craft Basic let a = 1 let b = 1 print "Fibonacci Sequence" for i = 0 to 20 let s = a + b let a = b let b = s print s next i  Output: Fibonacci Sequence 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657  ### FreeBASIC Extended sequence coded big integer. 'Fibonacci extended 'Freebasic version 24 Windows Dim Shared ADDQmod(0 To 19) As Ubyte Dim Shared ADDbool(0 To 19) As Ubyte For z As Integer=0 To 19 ADDQmod(z)=(z Mod 10+48) ADDbool(z)=(-(10<=z)) Next z Function plusINT(NUM1 As String,NUM2 As String) As String Dim As Byte flag #macro finish() three=Ltrim(three,"0") If three="" Then Return "0" If flag=1 Then Swap NUM2,NUM1 Return three Exit Function #endmacro var lenf=Len(NUM1) var lens=Len(NUM2) If lens>lenf Then Swap NUM2,NUM1 Swap lens,lenf flag=1 End If var diff=lenf-lens-Sgn(lenf-lens) var three="0"+NUM1 var two=String(lenf-lens,"0")+NUM2 Dim As Integer n2 Dim As Ubyte addup,addcarry addcarry=0 For n2=lenf-1 To diff Step -1 addup=two[n2]+NUM1[n2]-96 three[n2+1]=addQmod(addup+addcarry) addcarry=addbool(addup+addcarry) Next n2 If addcarry=0 Then finish() End If If n2=-1 Then three[0]=addcarry+48 finish() End If For n2=n2 To 0 Step -1 addup=two[n2]+NUM1[n2]-96 three[n2+1]=addQmod(addup+addcarry) addcarry=addbool(addup+addcarry) Next n2 three[0]=addcarry+48 finish() End Function Function fibonacci(n As Integer) As String Dim As String sl,l,term sl="0": l="1" If n=1 Then Return "0" If n=2 Then Return "1" n=n-2 For x As Integer= 1 To n term=plusINT(l,sl) sl=l l=term Next x Function =term End Function '============== EXAMPLE =============== print "THE SEQUENCE TO 10:" print For n As Integer=1 To 10 Print "term";n;": "; fibonacci(n) Next n print print "Selected Fibonacci number" print "Fibonacci 500" print print fibonacci(500) Sleep  Output: THE SEQUENCE TO 10: term 1: 0 term 2: 1 term 3: 1 term 4: 2 term 5: 3 term 6: 5 term 7: 8 term 8: 13 term 9: 21 term 10: 34 Selected Fibonacci number Fibonacci 500 86168291600238450732788312165664788095941068326060883324529903470149056115823592 713458328176574447204501 ### FTCBASIC define a = 1, b = 1, s = 0, i = 0 cls print "Fibonacci Sequence" do let s = a + b let a = b let b = s +1 i print s loop i < 20 pause end  ### 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 if end fn = s1 long i CFTimeInterval t t = fn CACurrentMediaTime for i = 0 to 40 print i;@".\t";fn Fibonacci(i) next i print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000 HandleEvents Output: 0. 0 1. 1 2. 1 3. 2 4. 3 5. 5 6. 8 7. 13 8. 21 9. 34 10. 55 11. 89 12. 144 13. 233 14. 377 15. 610 16. 987 17. 1597 18. 2584 19. 4181 20. 6765 21. 10946 22. 17711 23. 28657 24. 46368 25. 75025 26. 121393 27. 196418 28. 317811 29. 514229 30. 832040 31. 1346269 32. 2178309 33. 3524578 34. 5702887 35. 9227465 36. 14930352 37. 24157817 38. 39088169 39. 63245986 40. 102334155 Compute time: 2.143 ms #### Recursive Cost is a time penalty local fn Fibonacci( n as NSInteger ) as NSInteger NSInteger result if n < 2 then result = n : exit fn result = fn Fibonacci( n-1 ) + fn Fibonacci( n-2 ) end fn = result window 1 NSInteger i CFTimeInterval t t = fn CACurrentMediaTime for i = 0 to 40 print i;@".\t";fn Fibonacci(i) next print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000 HandleEvents Output: 0. 0 1. 1 2. 1 3. 2 4. 3 5. 5 6. 8 7. 13 8. 21 9. 34 10. 55 11. 89 12. 144 13. 233 14. 377 15. 610 16. 987 17. 1597 18. 2584 19. 4181 20. 6765 21. 10946 22. 17711 23. 28657 24. 46368 25. 75025 26. 121393 27. 196418 28. 317811 29. 514229 30. 832040 31. 1346269 32. 2178309 33. 3524578 34. 5702887 35. 9227465 36. 14930352 37. 24157817 38. 39088169 39. 63245986 40. 102334155 Compute time: 2844.217 ms  ### GFA Basic ' ' Compute nth Fibonacci number ' ' open a window for display OPENW 1 CLEARW 1 ' Display some fibonacci numbers ' Fib(46) is the largest number GFA Basic can reach ' (long integers are 4 bytes) FOR i%=0 TO 46 PRINT "fib(";i%;")=";@fib(i%) NEXT i% ' wait for a key press and tidy up ~INP(2) CLOSEW 1 ' ' Function to compute nth fibonacci number ' n must be in range 0 to 46, inclusive ' FUNCTION fib(n%) LOCAL n0%,n1%,nn%,i% n0%=0 n1%=1 SELECT n% CASE 0 RETURN n0% CASE 1 RETURN n1% DEFAULT FOR i%=2 TO n% nn%=n0%+n1% n0%=n1% n1%=nn% NEXT i% RETURN nn% ENDSELECT ENDFUNC  ### GW-BASIC Works with: BASICA #### Iterative 10 ' SAVE"FIBONA", A 20 ' Secuencia de Fibonacci 30 ' Var 40 DEFDBL D 50 IMAXFIBO% = 76 60 DNUM1 = 1: DNUM2 = DNUM1 70 CLS 80 PRINT "Este programa calcula la serie de Fibonacci." 90 PRINT DNUM1; DNUM2; 100 FOR I% = 1 TO IMAXFIBO% 110 DNUM3 = DNUM1 + DNUM2 120 PRINT DNUM3; 130 DNUM1 = DNUM2: DNUM2 = DNUM3 140 NEXT I% 150 PRINT 160 PRINT "Fin de la ejecución del programa." 170 END  Output: Este programa calcula la serie de Fibonacci. 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 Fin de la ejecución del programa. Ok  #### Binet formula 10 ' SAVE"FIBINF", A 20 ' Secuencia de Fibonacci mediante la fórmula de Binet 30 ' Var 40 DEFDBL D 50 IMAXFIBO% = 77 60 DSQR5 = SQR(5) 70 DPIV1 = (1 + DSQR5) / 2 80 DPIV2 = (1 - DSQR5) / 2 90 DNUM1 = DPIV1: DNUM2 = DPIV2 100 CLS 110 PRINT "Este programa calcula la serie de Fibonacci." 120 FOR I% = 1 TO IMAXFIBO% 130 DNUM1 = DNUM1 * DPIV1 140 DNUM2 = DNUM2 * DPIV2 150 PRINT FIX(((DNUM1 - DNUM2) / DSQR5)+.5); 160 NEXT I% 170 PRINT 180 PRINT "Fin de la ejecución del programa." 190 END  Output: Este programa calcula la serie de Fibonacci. 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 2178310 3524579 5702889 9227468 14930357 24157826 39088183 63246010 102334195 165580207 267914406 433494620 701409036 1134903671 1836312733 2971216446 4807529247 7778745802 12586275225 20365021312 32951296999 53316319058 86267617266 139583938281 225851558714 365435502118 591287069122 956722584654 1548009675479 2504732295250 4052742027550 6557474414738 10610216591046 17167691246479 27777908226979 44945600103607 72723509350188 117669111103547 190392623123089 308061738545741 498454368657289 806516118510594 1304970505463907 2111486653578091 3416457206941612 5527943938022908 8944401270367342 Fin de la ejecución del programa. Ok  ### 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 B 100 END  ### IS-BASIC 100 PROGRAM "Fibonac.bas" 110 FOR I=0 TO 20 120 PRINT "F";I,FIB(I) 130 NEXT 140 DEF FIB(N) 150 NUMERIC I 160 LET A=0:LET B=1 170 FOR I=1 TO N 180 LET T=A+B:LET A=B:LET B=T 190 NEXT 200 LET FIB=A 210 END DEF ### Liberty BASIC #### Iterative/Recursive Works with: Just BASIC for i = 0 to 15 print fiboR(i),fiboI(i) next i function fiboR(n) if n <= 1 then fiboR = n else fiboR = fiboR(n-1) + fiboR(n-2) end if end function function fiboI(n) a = 0 b = 1 for i = 1 to n temp = a + b a = b b = temp next i fiboI = a end function 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 Works with: Just BASIC print "Rosetta Code - Fibonacci sequence": print print " n Fn" for x=-12 to 12 '68 max print using("### ", x); using("##############", FibonacciTerm(x)) next x print [start] input "Enter a term#: "; n$
n$=lower$(trim$(n$))
if n$="" then print "Program complete.": end print 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 select
end 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.


### Microsoft Small Basic

#### Iterative

' Fibonacci sequence - 31/07/2018
n = 139
f1 = 0
f2 = 1
TextWindow.WriteLine("fibo(0)="+f1)
TextWindow.WriteLine("fibo(1)="+f2)
For i = 2 To n
f3 = f1 + f2
TextWindow.WriteLine("fibo("+i+")="+f3)
f1 = f2
f2 = f3
EndFor
Output:
fibo(139)=50095301248058391139327916261


#### Binet's Formula

' Fibonacci sequence - Binet's Formula - 31/07/2018
n = 69
sq5=Math.SquareRoot(5)
phi1=(1+sq5)/2
phi2=(1-sq5)/2
phi1n=phi1
phi2n=phi2
For i = 2 To n
phi1n=phi1n*phi1
phi2n=phi2n*phi2
TextWindow.Write(Math.Floor((phi1n-phi2n)/sq5)+" ")
EndFor
Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994


### Minimal BASIC

Works with: QBasic
Works with: BASICA
Works with: Chipmunk Basic
Works with: GW-BASIC
Works with: IS-BASIC
Works with: MSX Basic
110 REM THE ARRAY F HOLDS THE FIBONACCI NUMBERS
120 DIM F(22)
130 LET F(0) = 0
140 LET F(1) = 1
150 LET N = 1
160 REM COMPUTE THE NEXT FIBBONACCI NUMBER
170 LET F(N+1) = F(N)+F(N-1)
180 LET N = N+1
190 PRINT F(N-2);
200 REM STOP AFTER PRINTING  20 NUMBERS
210 IF N < 22 THEN 170
220 END


### MSX Basic

Works with: QBasic
Works with: Chipmunk Basic
Works with: GW-BASIC
100 CLS
110 FOR N = 0 TO 15: GOSUB 130: PRINT FIBOI; : NEXT N
120 END
130 REM Iterative Fibonacci sequence
140 N1 = 0
150 N2 = 1
160 FOR K = 1 TO ABS(N)
170   SUM = N1 + N2
180   N1 = N2
190   N2 = SUM
200 NEXT K
210 IF N < 0 THEN FIBOI = N1 * ((-1) ^ ((-N) + 1)) ELSE FIBOI = N1
220 RETURN


### Palo Alto Tiny BASIC

10 REM FIBONACCI SEQUENCE
20 INPUT "ENTER N FOR FIB(N)"N
30 LET A=0,B=1
40 FOR I=2 TO N
50 LET T=B,B=A+B,A=T
60 NEXT I
70 PRINT B
80 STOP

Output:

2 runs.

ENTER N FOR FIB(N):9
34

ENTER N FOR FIB(N):13
233


### PowerBASIC

Translation of: BASIC

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

      actual:             displayed:
F(88) 1100087778366101931 1100087778366101930
F(89) 1779979416004714189 1779979416004714190
F(90) 2880067194370816120 2880067194370816120
F(91) 4660046610375530309 4660046610375530310
F(92) 7540113804746346429 7540113804746346430

FUNCTION fibonacci (n AS LONG) AS QUAD
DIM u AS LONG, a AS LONG, L0 AS LONG, outP AS QUAD

u = UBOUND(fibNum)
a = ABS(n)

IF u < 1 THEN
REDIM fibNum(1)
fibNum(1) = 1
u = 1
END IF

SELECT CASE a
CASE 0 TO 92
IF a > u THEN
REDIM PRESERVE fibNum(a)
FOR L0 = u + 1 TO a
fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
IF 88 = L0 THEN fibNum(88) = fibNum(88) + 1
NEXT
END IF
IF n < 0 THEN
fibonacci = fibNum(a) * ((-1)^(a+1))
ELSE
fibonacci = fibNum(a)
END IF
CASE ELSE
'Even without the above-mentioned bug, we're still limited to
'F(+/-92), due to data type limits. (F(93) = &hA94F AD42 221F 2702)
ERROR 6
END SELECT
END FUNCTION

FUNCTION PBMAIN () AS LONG
DIM n AS LONG
#IF NOT %DEF(%PB_CC32)
OPEN "out.txt" FOR OUTPUT AS 1
#ENDIF
FOR n = -92 TO 92
#IF %DEF(%PB_CC32)
PRINT STR$(n); ": "; FORMAT$(fibonacci(n), "#")
#ELSE
PRINT #1, STR$(n) & ": " & FORMAT$(fibonacci(n), "#")
#ENDIF
NEXT
CLOSE
END FUNCTION

### PureBasic

#### Macro based calculation

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


#### Recursive

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


#### Recursive & optimized with a static hash table

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

Fib(n) Speedup
20           2
25          23
30         217
40       25847
46     1156741

Procedure Fibonacci(n)
Static NewMap Fib.i()
Protected FirstRecursion

If MapSize(Fib())= 0        ; Init the hash table the first run
Fib("0")=0: Fib("1")=1
FirstRecursion = #True
EndIf

If n >= 2
Protected.s s=Str(n)
If Not FindMapElement(Fib(),s)  ; Calculate only needed parts
Fib(s)= Fibonacci(n-1)+Fibonacci(n-2)
EndIf
n = Fib(s)
EndIf
If FirstRecursion ; Free the memory when finalizing the first call
ClearMap(Fib())
EndIf
ProcedureReturn n
EndProcedure


Example

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

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


### QB64

CBTJD: 2020/03/13

_DEFINE F AS _UNSIGNED _INTEGER64
CLS
PRINT
PRINT "Enter 40 to more easily see the difference in calculation speeds."
PRINT
INPUT "Enter n for Fibonacci(n): ", n
PRINT
PRINT " Analytic Method (Fastest): F("; LTRIM$(STR$(n)); ") ="; fA(n)
PRINT "Iterative Method    (Fast): F("; LTRIM$(STR$(n)); ") ="; fI(n)
PRINT "Recursive Method    (Slow): F("; LTRIM$(STR$(n)); ") ="; fR(n)
END

' === Analytic Fibonacci Function (Fastest)
FUNCTION fA (n)
fA = INT(0.5 + (((SQR(5) + 1) / 2) ^ n) / SQR(5))
END FUNCTION

' === Iterative Fibonacci Function (Fast)
FUNCTION fI (n)
FOR i = 1 TO n
IF i < 3 THEN a = 1: b = 1
t = fI + b: fI = b: b = t
NEXT
END FUNCTION

' === Recursive Fibonacci function (Slow)
FUNCTION fR (n)
IF n <= 1 THEN
fR = n
ELSE
fR = fR(n - 1) + fR(n - 2)
END IF
END FUNCTION


Fibonacci from Russia

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

FOR i = 1 TO 80
f$= STR$(F(i)): LF = 22 - LEN(f$) n$ = ""
FOR j = 1 TO LF: n$= " " + n$: NEXT
f$= n$ + f$PRINT i, f$: ' PRINT #1, i, f$NEXT i  Output: 1 0 2 1 3 1 4 2 5 3 6 5 7 8 8 13 9 21 ... 24 28657 25 46368 26 75025 ... 36 9227465 37 14930352 38 24157817 ... 48 2971215073 49 4807526976 50 7778742049 ... 60 956722026041 61 1548008755920 62 2504730781961 ... 76 2111485077978050 77 3416454622906707 78 5527939700884757 79 8944394323791464 80 1.447233402467622D+16 ### 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 IF END FUNCTION  Next version calculates each value once, as needed, and stores the results in an array for later retreival (due to the use of REDIM PRESERVE, it requires QuickBASIC 4.5 or newer): DECLARE FUNCTION fibonacci& (n AS INTEGER) REDIM SHARED fibNum(1) AS LONG fibNum(1) = 1 '*****sample inputs***** PRINT fibonacci(0) 'no calculation needed PRINT fibonacci(13) 'figure F(2)..F(13) PRINT fibonacci(-42) 'figure F(14)..F(42) PRINT fibonacci(47) 'error: too big '*****sample inputs***** FUNCTION fibonacci& (n AS INTEGER) DIM a AS INTEGER a = ABS(n) SELECT CASE a CASE 0 TO 46 SHARED fibNum() AS LONG DIM u AS INTEGER, L0 AS INTEGER u = UBOUND(fibNum) IF a > u THEN REDIM PRESERVE fibNum(a) AS LONG FOR L0 = u + 1 TO a fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2) NEXT END IF IF n < 0 THEN fibonacci = fibNum(a) * ((-1) ^ (a + 1)) ELSE fibonacci = fibNum(n) END IF CASE ELSE 'limited to signed 32-bit int (LONG) 'F(47)=&hB11924E1 ERROR 6 'overflow END SELECT END FUNCTION  Output: (unhandled error in final input prevents output)  0 233 -267914296  #### Recursive This example can't handle n < 0. FUNCTION recFib (n) IF (n < 2) THEN recFib = n ELSE recFib = recFib(n - 1) + recFib(n - 2) END IF END FUNCTION  #### Array (Table) Lookup This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.) DATA -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155 DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309 DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711 DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3 DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765 DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269 DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986 DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903 DIM fibNum(-46 TO 46) AS LONG FOR n = -46 TO 46 READ fibNum(n) NEXT '*****sample inputs***** FOR n = -46 TO 46 PRINT fibNum(n), NEXT PRINT '*****sample inputs*****  ### Quite BASIC 100 CLS 110 rem The array F holds the Fibonacci numbers 120 ARRAY f : rem DIM f(22) para Quite BASIC and MSX-BASIC 130 LET f(0) = 0 140 LET f(1) = 1 150 LET n = 1 160 rem Compute the NEXT Fibbonacci number 170 LET f(n+1) = f(n)+f(n-1) 180 LET n = n+1 190 PRINT f(n-2);" "; 200 rem STOP after printing 20 numbers 210 IF n < 22 THEN GOTO 170  ### Run BASIC for i = 0 to 10 print i;" ";fibR(i);" ";fibI(i) next i end function fibR(n) if n < 2 then fibR = n else fibR = fibR(n-1) + fibR(n-2) end function function fibI(n) b = 1 for i = 1 to n t = a + b a = b b = t next i fibI = a end function ### S-BASIC Note that the 23rd Fibonacci number (=28657) is the largest that can be generated without overflowing S-BASIC's integer data type. rem - iterative function to calculate nth fibonacci number function fibonacci(n = integer) = integer var f, i, p1, p2 = integer p1 = 0 p2 = 1 if n = 0 then f = 0 else for i = 1 to n f = p1 + p2 p2 = p1 p1 = f next i end = f rem - exercise the function var i = integer for i = 0 to 10 print fibonacci(i); next i end  Output:  0 1 1 2 3 5 8 13 21 34 55  ### 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+B 100 LET A=C 110 LET N=N-1 120 GOSUB 70 130 RETURN  ### smart BASIC The Iterative method is slow (relatively) and the Recursive method doubly so since it references the recursion function twice. The N-th Term (fibN) function is much faster as it utilizes Binet's Formula. • fibR: Fibonacci Recursive • fibI: Fibonacci Iterative • fibN: Fibonacci N-th Term FOR i = 0 TO 15 PRINT fibR(i),fibI(i),fibN(i) NEXT i /* Recursive Method */ DEF fibR(n) IF n <= 1 THEN fibR = n ELSE fibR = fibR(n-1) + fibR(n-2) ENDIF END DEF /* Iterative Method */ DEF fibI(n) a = 0 b = 1 FOR i = 1 TO n temp = a + b a = b b = temp NEXT i fibI = a END DEF /* N-th Term Method */ DEF fibN(n) uphi = .5 + SQR(5)/2 lphi = .5 - SQR(5)/2 fibN = (uphi^n-lphi^n)/SQR(5) END DEF  ### Softbridge BASIC #### Iterative Function Fibonacci(n) x = 0 y = 1 i = 0 n = ABS(n) If n < 2 Then Fibonacci = n Else Do Until (i = n) sum = x+y x=y y=sum i=i+1 Loop Fibonacci = x End If End Function  ### TI-83 BASIC #### Sequence table [Y=] nMin=0 u(n)=u(n-1)+u(n-2) u(nMin)={1,0} [TABLE] n u(n) ------- ------- 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 #### Iterative {0,1 While 1 Disp Ans(1 {Ans(2),sum(Ans End #### Binet's formula Prompt N .5(1+√(5 //golden ratio (Ans^N–(-Ans)^-N)/√(5 ### TI-89 BASIC #### Recursive Optimized implementation (too slow to be usable for n higher than about 12). fib(n) when(n<2, n, fib(n-1) + fib(n-2)) #### Iterative Unoptimized implementation (I think the for loop can be eliminated, but I'm not sure). fib(n) Func Local a,b,c,i 0→a 1→b For i,1,n a→c b→a c+b→b EndFor a EndFunc ### Tiny BASIC Works with: TinyBasic 10 LET A = 0 20 LET B = 1 30 PRINT "Which F_n do you want?" 40 INPUT N 50 IF N = 0 THEN GOTO 140 60 IF N = 1 THEN GOTO 120 70 LET C = B + A 80 LET A = B 90 LET B = C 100 LET N = N - 1 110 GOTO 60 120 PRINT B 130 END 140 PRINT 0 150 END  ### Tiny Craft Basic 10 cls 20 let a = 1 30 let b = 1 40 print "Fibonacci Sequence" 50 rem loop 60 let s = a + b 70 let a = b 80 let b = s 90 let i = i + 1 100 print s 120 if i < 20 then 50 130 shell "pause" 140 end  ### True BASIC FUNCTION fibonacci (n) LET n1 = 0 LET n2 = 1 FOR k = 1 TO ABS(n) LET sum = n1 + n2 LET n1 = n2 LET n2 = sum NEXT k IF n < 0 THEN LET fibonacci = n1 * ((-1) ^ ((-n) + 1)) ELSE LET fibonacci = n1 END IF END FUNCTION PRINT fibonacci(0) ! 0 PRINT fibonacci(13) ! 233 PRINT fibonacci(-42) !-267914296 PRINT fibonacci(47) ! 2971215073 END  ### VBA Like Visual Basic .NET, but with keyword "Public" and type Variant (subtype Currency) instead of Decimal: Public Function Fib(ByVal n As Integer) As Variant Dim fib0 As Variant, fib1 As Variant, sum As Variant Dim i As Integer fib0 = 0 fib1 = 1 For i = 1 To n sum = fib0 + fib1 fib0 = fib1 fib1 = sum Next i Fib = fib0 End Function  With Currency type, maximum value is fibo(73). The (slow) recursive version: Public Function RFib(Term As Integer) As Long If Term < 2 Then RFib = Term Else RFib = RFib(Term - 1) + RFib(Term - 2) End Function With Long type, maximum value is fibo(46). ### VBScript #### Non-recursive, object oriented, generator Defines a generator class, with a default Get property. Uses Currency for larger-than-Long values. Tests for overflow and switches to Double. Overflow information also available from class. ##### Class Definition: class generator dim t1 dim t2 dim tn dim cur_overflow Private Sub Class_Initialize cur_overflow = false t1 = ccur(0) t2 = ccur(1) tn = ccur(t1 + t2) end sub public default property get generated on error resume next generated = ccur(tn) if err.number <> 0 then generated = cdbl(tn) cur_overflow = true end if t1 = ccur(t2) if err.number <> 0 then t1 = cdbl(t2) cur_overflow = true end if t2 = ccur(tn) if err.number <> 0 then t2 = cdbl(tn) cur_overflow = true end if tn = ccur(t1+ t2) if err.number <> 0 then tn = cdbl(t1) + cdbl(t2) cur_overflow = true end if on error goto 0 end property public property get overflow overflow = cur_overflow end property end class  ##### Invocation: dim fib set fib = new generator dim i for i = 1 to 100 wscript.stdout.write " " & fib if fib.overflow then wscript.echo exit for end if next  Output:  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 ### Visual Basic Works with: Visual Basic version VB6 Standard Maximum integer value (7*10^28) can be obtained by using decimal type, but decimal type is only a sub type of the variant type. Sub fibonacci() Const n = 139 Dim i As Integer Dim f1 As Variant, f2 As Variant, f3 As Variant 'for Decimal f1 = CDec(0): f2 = CDec(1) 'for Decimal setting Debug.Print "fibo("; 0; ")="; f1 Debug.Print "fibo("; 1; ")="; f2 For i = 2 To n f3 = f1 + f2 Debug.Print "fibo("; i; ")="; f3 f1 = f2 f2 = f3 Next i End Sub 'fibonacci  Output: fibo( 0 )= 0 fibo( 1 )= 1 fibo( 2 )= 1 ... fibo( 137 )= 19134702400093278081449423917 fibo( 138 )= 30960598847965113057878492344 fibo( 139 )= 50095301248058391139327916261  ### Visual Basic .NET Platform: .NET #### Iterative Works with: Visual Basic .NET version 9.0+ With Decimal type, maximum value is fibo(139). Function Fib(ByVal n As Integer) As Decimal Dim fib0, fib1, sum As Decimal Dim i As Integer fib0 = 0 fib1 = 1 For i = 1 To n sum = fib0 + fib1 fib0 = fib1 fib1 = sum Next Fib = fib0 End Function  #### Recursive Works with: Visual Basic .NET version 9.0+ Function Seq(ByVal Term As Integer) If Term < 2 Then Return Term Return Seq(Term - 1) + Seq(Term - 2) End Function  #### BigInteger There is no real maximum value of BigInterger class, except the memory to store the number. Within a minute, fibo(2000000) is a number with 417975 digits.  Function FiboBig(ByVal n As Integer) As BigInteger ' Fibonacci sequence with BigInteger Dim fibn2, fibn1, fibn As BigInteger Dim i As Integer fibn = 0 fibn2 = 0 fibn1 = 1 If n = 0 Then Return fibn2 ElseIf n = 1 Then Return fibn1 ElseIf n >= 2 Then For i = 2 To n fibn = fibn2 + fibn1 fibn2 = fibn1 fibn1 = fibn Next i Return fibn End If Return 0 End Function 'FiboBig Sub fibotest() Dim i As Integer, s As String i = 2000000 ' 2 millions s = FiboBig(i).ToString Console.WriteLine("fibo(" & i & ")=" & s & " - length=" & Len(s)) End Sub 'fibotest  #### BigInteger, speedier method This method doesn't need to iterate the entire list, and is much faster. The 2000000 (two millionth) Fibonacci number can be found in a fraction of a second. Algorithm from here, see section 3, Finding Fibonacci Numbers Fully. Imports System Imports System.Collections.Generic Imports BI = System.Numerics.BigInteger Module Module1 ' A sparse array of values calculated along the way Dim sl As SortedList(Of Integer, BI) = New SortedList(Of Integer, BI)() ' Square a BigInteger Function sqr(ByVal n As BI) As BI Return n * n End Function ' Helper routine for Fsl(). It adds an entry to the sorted list when necessary Sub IfNec(n As Integer) If Not sl.ContainsKey(n) Then sl.Add(n, Fsl(n)) End Sub ' 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 Function Fsl(ByVal n As Integer) As BI If n < 2 Then Return n Dim n2 As Integer = n >> 1, pm As Integer = n2 + ((n And 1) << 1) - 1 : IfNec(n2) : IfNec(pm) Return If(n2 > pm, (2 * sl(pm) + sl(n2)) * sl(n2), sqr(sl(n2)) + sqr(sl(pm))) End Function ' Conventional iteration method (not used here) Function Fm(ByVal n As BI) As BI If n < 2 Then Return n Dim cur As BI = 0, pre As BI = 1 For i As Integer = 0 To n - 1 Dim sum As BI = cur + pre : pre = cur : cur = sum : Next : Return cur End Function Sub Main() Dim vlen As Integer, num As Integer = 2_000_000, digs As Integer = 35 Dim sw As System.Diagnostics.Stopwatch = System.Diagnostics.Stopwatch.StartNew() Dim v As BI = Fsl(num) : sw.[Stop]() Console.Write("{0:n3} ms to calculate the {1:n0}th Fibonacci number, ", sw.Elapsed.TotalMilliseconds, num) vlen = CInt(Math.Ceiling(BI.Log10(v))) : Console.WriteLine("number of digits is {0}", vlen) If vlen < 10000 Then 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 Mod BI.Pow(10, digs)) End If End Sub End Module  Output: 120.374 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975 partial: 85312949175076415430516606545038251...91799493108960825129188777803453125 ### Xojo Pass n to this function where n is the desired number of iterations. This example uses the UInt64 datatype which is as unsigned 64 bit integer. As such, it overflows after the 93rd iteration. Function fibo(n As Integer) As UInt64 Dim noOne As UInt64 = 1 Dim noTwo As UInt64 = 1 Dim sum As UInt64 For i As Integer = 3 To n sum = noOne + noTwo noTwo = noOne noOne = sum Next Return noOne End Function  ### Yabasic sub fibonacci (n) n1 = 0 n2 = 1 for k = 1 to abs(n) sum = n1 + n2 n1 = n2 n2 = sum next k if n < 0 then return n1 * ((-1) ^ ((-n) + 1)) else return n1 end if end sub ### ZX Spectrum Basic #### Iterative 10 REM Only positive numbers 20 LET n=10 30 LET n1=0: LET n2=1 40 FOR k=1 TO n 50 LET sum=n1+n2 60 LET n1=n2 70 LET n2=sum 80 NEXT k 90 PRINT n1  #### Analytic 10 DEF FN f(x)=INT (0.5+(((SQR 5+1)/2)^x)/SQR 5)  ## Batch File Recursive version ::fibo.cmd @echo off if "%1" equ "" goto :eof call :fib %1 echo %errorlevel% goto :eof :fib setlocal enabledelayedexpansion if %1 geq 2 goto :ge2 exit /b %1 :ge2 set /a r1 = %1 - 1 set /a r2 = %1 - 2 call :fib !r1! set r1=%errorlevel% call :fib !r2! set r2=%errorlevel% set /a r0 = r1 + r2 exit /b !r0!  Output: >for /L %i in (1,5,20) do fibo.cmd %i >fibo.cmd 1 1 >fibo.cmd 6 8 >fibo.cmd 11 89 >fibo.cmd 16 987 ## Battlestar // Fibonacci sequence, recursive version fun fibb loop a = funparam[0] break (a < 2) a-- // Save "a" while calling fibb a -> stack // Set the parameter and call fibb funparam[0] = a call fibb // Handle the return value and restore "a" b = funparam[0] stack -> a // Save "b" while calling fibb again b -> stack a-- // Set the parameter and call fibb funparam[0] = a call fibb // Handle the return value and restore "b" c = funparam[0] stack -> b // Sum the results b += c a = b funparam[0] = a break end end // vim: set syntax=c ts=4 sw=4 et:  ## 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
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 37 node *cache[CSIZE]; // very primitive linked hash table node * find_cache(int n) { int idx = n % CSIZE; node *p; for (p = cache[idx]; p && p->n != n; p = p->next); if (p) return p; p = malloc(sizeof(node)); p->next = cache[idx]; cache[idx] = p; if (n < 2) { p->n = n; mpz_init_set_ui(p->v, 1); } else { p->n = -1; // -1: value not computed yet mpz_init(p->v); } return p; } mpz_t tmp1, tmp2; mpz_t *fib(int n) { int x; node *p = find_cache(n); if (p->n < 0) { p->n = n; x = n / 2; mpz_mul(tmp1, *fib(x-1), *fib(n - x - 1)); mpz_mul(tmp2, *fib(x), *fib(n - x)); mpz_add(p->v, tmp1, tmp2); } return &p->v; } int main(int argc, char **argv) { int i, n; if (argc < 2) return 1; mpz_init(tmp1); mpz_init(tmp2); for (i = 1; i < argc; i++) { n = atoi(argv[i]); if (n < 0) { printf("bad input: %s\n", argv[i]); continue; } // about 75% of time is spent in printing gmp_printf("%Zd\n", *fib(n)); } return 0; }  Output: % ./a.out 0 1 2 3 4 5 1 1 2 3 5 8 % ./a.out 10000000 | wc -c # count length of output, including the newline 1919488  ## C# ### 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; }  ### Iterative using System; using System.Text; // FIBRUS.cs Russia namespace Fibrus { class Program { static void Main() { long fi1=1; long fi2=1; long fi3=1; int da; int i; int d; for (da=1; da<=78; da++) // rextester.com/MNGUV70257 { d = 20-Convert.ToInt32((Convert.ToString(fi3)).Length); for (i=1; i<d; i++) Console.Write("."); Console.Write(fi3); Console.Write(" "); Console.WriteLine(da); fi3 = fi2 + fi1; fi1 = fi2; fi2 = fi3; }}}}  Output: ..................1 1 ..................2 2 ..................3 3 ... ...5527939700884757 76 ...8944394323791464 77 ..14472334024676221 78  ### 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  ### Shift PowerMod Illustrated here is an algorithm to compute a Fibonacci number directly, without needing to calculate any of the Fibonacci numbers less than the desired result. It uses shifting and the power mod function (BigInteger.ModPow() in C#). It calculates more quickly than the large step recurrence routine (illustrated above) for smaller Fibonacci numbers (less than 2800 digits or so, around Fibonacci(13000)), but gets slower for larger ones, as the intermediate BigIntegers created are very large, much larger than the Fibonacci result. Also included is a routine that returns an array of Fibonacci numbers (fibTab()). It reuses the intermediate large shifted BigIntegers on suceeding iterations, therfore it is a little more efficient than calling the oneshot (oneFib()) routine repeatedly from a loop. using System; using BI = System.Numerics.BigInteger; class Program { // returns the nth Fibonacci number without calculating 0..n-1 static BI oneFib(int n) { BI z = (BI)1 << ++n; return BI.ModPow(z, n, (z << n) - z - 1) % z; } // returns an array of Fibonacci numbers from the 0th to the nth static BI[] fibTab(int n) { var res = new BI[++n]; BI z = (BI)1 << 1, zz = z << 1; for (int i = 0; i < n; ) { res[i] = BI.ModPow(z, ++i, zz - z - 1) % z; z <<= 1; zz <<= 2; } return res; } static void Main(string[] args) { int n = 20; Console.WriteLine("Fibonacci numbers 0..{0}: {1}", n, string.Join(" ",fibTab(n))); n = 1000; Console.WriteLine("Fibonacci({0}): {1}", n, oneFib(n)); } }  Output: Fibonacci numbers 0..20: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 Fibonacci(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 ## C++ 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., 2012 int main(void) { char NG[22] = {'1',0}; int x = -1; N G; for (int fibs = 1; fibs <= 20; fibs++) { for (;G <= N(NG); ++G) x++; NG[fibs] = '0'; NG[fibs+1] = 0; std::cout << x << " "; } std::cout << std::endl; return 0; } Output: 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946  ### Using Standard Template Library 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 last 1 g this 0 g new 0 g input Method. Take input from refrigerator. Put this into 4th mixing bowl. Loop the input. Clean the 3rd mixing bowl. Put last into 3rd mixing bowl. Add this into 3rd mixing bowl. Fold new into 3rd mixing bowl. Clean the 1st mixing bowl. Put this into 1st mixing bowl. Fold last into 1st mixing bowl. Clean the 2nd mixing bowl. Put new into 2nd mixing bowl. Fold this into 2nd mixing bowl. Put new into 4th mixing bowl. Endloop input until looped. Pour contents of the 4th mixing bowl into baking dish. Serves 1. ## Clio 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)))))) ## CLU % Generate Fibonacci numbers fib = iter () yields (int) a: int := 0 b: int := 1 while true do yield (a) a, b := b, a+b end end fib % Grab the n'th value from an iterator nth = proc [T: type] (g: itertype () yields (T), n: int) returns (T) for v: T in g() do if n<=0 then return (v) end n := n-1 end end nth % Print a few values start_up = proc () po: stream := stream$primary_output()

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

## CMake

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 FREE IDENTIFICATION DIVISION. PROGRAM-ID. fibonacci-main. DATA DIVISION. WORKING-STORAGE SECTION. 01 num PIC 9(6) COMP. 01 fib-num PIC 9(6) COMP. PROCEDURE DIVISION. ACCEPT num CALL "fibonacci" USING CONTENT num RETURNING fib-num DISPLAY fib-num . END PROGRAM fibonacci-main. IDENTIFICATION DIVISION. PROGRAM-ID. fibonacci RECURSIVE. DATA DIVISION. LOCAL-STORAGE SECTION. 01 1-before PIC 9(6) COMP. 01 2-before PIC 9(6) COMP. LINKAGE SECTION. 01 num PIC 9(6) COMP. 01 fib-num PIC 9(6) COMP BASED. PROCEDURE DIVISION USING num RETURNING fib-num. ALLOCATE fib-num EVALUATE num WHEN 0 MOVE 0 TO fib-num WHEN 1 MOVE 1 TO fib-num WHEN OTHER SUBTRACT 1 FROM num CALL "fibonacci" USING CONTENT num RETURNING 1-before SUBTRACT 1 FROM num CALL "fibonacci" USING CONTENT num RETURNING 2-before ADD 1-before TO 2-before GIVING fib-num END-EVALUATE . END PROGRAM fibonacci. ## CoffeeScript ### 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 = 6 a = 1 i = 1 # start a # print result fib comefrom if i is 1 # start b = 1 comefrom fib # start of loop i = i + 1 next_b = a + b a = b b = next_b comefrom fib if i > stop ## Common Lisp 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: 1 count: 8 ; n = 10 x: 1 y: 1 temp: 0 ## Coq Fixpoint rec_fib (m : nat) (a : nat) (b : nat) : nat := match m with | 0 => a | S k => rec_fib k b (a + b) end. Definition fib (n : nat) : nat := rec_fib n 0 1 . ## Corescript print Fibonacci Sequence: var previous = 1 var number = 0 var temp = (blank) :fib if number > 50000000000:kill print (number) set temp = (add number previous) set previous = (number) set number = (temp) goto fib :kill stop ## Cowgol include "cowgol.coh"; sub fibonacci(n: uint32): (a: uint32) is a := 0; var b: uint32 := 1; while n > 0 loop var c := a + b; a := b; b := c; n := n - 1; end loop; end sub; # test var i: uint32 := 0; while i < 20 loop print_i32(fibonacci(i)); print_char(' '); i := i + 1; end loop; print_nl(); Output: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ## Crystal ### 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 prevFib end ### 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_i end ## 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-numbers BigInt fibonacci(in ulong n) in { assert(n > 0, "fibonacci(n): n must be > 0."); } body { if (n <= 2) return 1.BigInt; BigInt F = 1; BigInt L = 1; int sign = -1; immutable uint n2 = cast(uint)n.log2.floor; auto mask = 2.BigInt ^^ (n2 - 1); foreach (immutable i; 1 .. n2) { auto temp = F ^^ 2; F = (F + L) / 2; F = 2 * F ^^ 2 - 3 * temp - 2 * sign; L = 5 * temp + 2 * sign; sign = 1; if (n & mask) { temp = F; F = (F + L) / 2; L = F + 2 * temp; sign = -1; } mask /= 2; } if ((n & mask) == 0) { F *= L; } else { F = (F + L) / 2; F = F * L - sign; } return F; } void main() { 10_000_000.fibonacci; } ## Dart 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, D10 FIB2, D10 FIBN, D10 J, D5 A2, A2 A5, A5 PROC ;---------------------------------------------------------------- XCALL FLAGS (0007000000,1) ;Suppress STOP message OPEN (1,O,'TT:') DISPLAY (1,'First 10 Fibonacci Numbers:',10) FIB2=1 FOR J=1 UNTIL 10 DO BEGIN FIBN=FIB1+FIB2 A2=J,'ZX' A5=FIBN,'ZZZZX' DISPLAY (1,A2,' : ',A5,10) FIB1=FIB2 FIB2=FIBN END CLOSE 1 END ## Dc 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 . if n < 2 return n . prev = 0 val = 1 for i = 2 to n h = prev + val prev = val val = h . return val . print fib 36 Recursive (inefficient): func fib n . if n < 2 return n . return fib (n - 2) + fib (n - 1) . print fib 36 ## 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 ] T20@ [ a = 0 ] A17@ [ a += y ] U18@ [ temp = a ] A16@ [ a += x ] T17@ [ y = a; a = 0 ] A18@ [ a += temp ] T16@ [ x = a; a = 0 ] A19@ [ a = count ] S15@ [ a -= 1 ] U19@ [ count = a ] E@ [ if a>=0 go to θ ] T20@ [ a = 0 ] A17@ [ a += y ] T96F [ C(96) = a; a = 0] ZF [ halt ] [ Data ] [ 15 ] P0D [ const: 1 ] [ 16 ] P0F [ var: x = 0 ] [ 17 ] P0D [ var: y = 1 ] [ 18 ] P0F [ var: temp = 0 ] [ 19 ] P4F [ var: count = 8 ] [ 20 ] P0F [ used to clear a ] EZPF [ begin execution ] Output: 00000000000110111 ## Eiffel 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) end end IO.inspect Enum.map(0..10, fn i-> Fibonacci.fib(i) end) Using Stream: Stream.unfold({0,1}, fn {a,b} -> {a,{b,a+b}} end) |> Enum.take(10) Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]  ## Elm Naïve recursive implementation. fibonacci : Int -> Int fibonacci 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). ## ERRE !------------------------------------------- ! derived from my book "PROGRAMMARE IN ERRE" ! iterative solution !------------------------------------------- PROGRAM FIBONACCI !$DOUBLE

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

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

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

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


## Euphoria

### 'Recursive' version

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

### 'Iterative' version

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

### 'Tail recursive' version

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

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

### 'Paper tape' version

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

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

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

global integer ip
global integer test
global atom accum

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

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

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

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

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

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

end switch
i += 1
end while
end procedure

test = 0
accum = 0
ip = 1

while 1 do

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

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

## Excel

### LAMBDA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

## F#

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

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

Lazy evaluated using sequence workflow:

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

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

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

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

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

open System
open System.Diagnostics
open System.Numerics

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

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

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

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

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

## Factor

### Iterative

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

### Recursive

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

### Tail-Recursive

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

### Matrix

Translation of: Ruby
USE: math.matrices

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

## Falcon

### Iterative

function fib_i(n)

if n < 2: return n

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

### Recursive

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

### Tail Recursive

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

## FOCAL

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

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

## Forth

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

Or, for negative-index support:

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

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

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

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

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

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

## Fortran

### 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)
END
C
FUNCTION IFIBO(N)
IF(N) 9,1,2
1 IFN=0
GOTO 9
2 IF(N-1) 9,3,4
3 IFN=1
GOTO 9
4 IFNM1=0
IFN=1
DO 5 I=2,N
IFNM2=IFNM1
IFNM1=IFN
5 IFN=IFNM1+IFNM2
9 IFIBO=IFN
END
Output:
  0          0
1          1
2          1
3          2
4          3
5          5
6          8
7         13
8         21
9         34
10         55
...
45 1134903170
46 1836311903


### FORTRAN 77

      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 fibonacci
contains
recursive function fibR(n) result(fib)
integer, intent(in) :: n
integer             :: fib

select case (n)
case (:0);      fib = 0
case (1);       fib = 1
case default;   fib = fibR(n-1) + fibR(n-2)
end select
end function fibR

### Iterative

In ISO Fortran 90 or later:

    function fibI(n)
integer, intent(in) :: n
integer, parameter :: fib0 = 0, fib1 = 1
integer            :: fibI, back1, back2, i

select case (n)
case (:0);      fibI = fib0
case (1);       fibI = fib1

case default
fibI = fib1
back1 = fib0
do i = 2, n
back2 = back1
back1 = fibI
fibI   = back1 + back2
end do
end select
end function fibI
end module fibonacci

Test program

program fibTest
use fibonacci

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


## Free Pascal

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; ## 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 ## 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. In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation. ### Recursive Recursive version is slow, it is O(2n), or of exponential order. It is because it makes a lot of recursive calls. To illustrate this, the following is a functions that makes a tree or the recursive calls: ### Iterative (3 variables) It is O(n), or of linear order. ### Iterative (2 variables) It is O(n), or of linear order. ### Iterative, using a list It is O(n), or of linear order. ### Using matrix multiplication ### Divide and conquer It is an optimized version of the matrix multiplication algorithm, with an order of O(lg(n)) ### Closed-form It has an order of O(lg(n)) ## GAP fib := function(n) local a; a := [[0, 1], [1, 1]]^n; return a[1][2]; end; GAP has also a buit-in function for that. Fibonacci(n); ## Gecho 0 1 dup wover + dup wover + dup wover + dup wover + Prints the first several fibonacci numbers... ## GML ///fibonacci(n) //Returns the nth fibonacci number var n, numb; n = argument0; if (n == 0) { numb = 0; } else { var fm2, fm1; fm2 = 0; fm1 = 1; numb = 1; repeat(n-1) { numb = fm2+fm1; fm2 = fm1; fm1 = numb; } } return numb; ## Go ### Recursive func fib(a int) int { if a < 2 { return a } return fib(a - 1) + fib(a - 2) } ### Iterative import ( "math/big" ) func fib(n uint64) *big.Int { if n < 2 { return big.NewInt(int64(n)) } a, b := big.NewInt(0), big.NewInt(1) for n--; n > 0; n-- { a.Add(a, b) a, b = b, a } return b } ### 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) } } ## Grain ### Recursive import String from "string" import File from "sys/file" let rec fib = n => if (n < 2) { n } else { fib(n - 1) + fib(n - 2) } for (let mut i = 0; i <= 20; i += 1) { File.fdWrite(File.stdout, Pervasives.toString(fib(i))) ignore(File.fdWrite(File.stdout, " ")) } ### Iterative import File from "sys/file" let fib = j => { let mut fnow = 0, fnext = 1 for (let mut n = 0; n <= j; n += 1) { if (n == 0 || n == 1) { let output1 = " " ++ toString(n) ignore(File.fdWrite(File.stdout, output1)) } else { let tempf = fnow + fnext fnow = fnext fnext = tempf let output2 = " " ++ toString(fnext) ignore(File.fdWrite(File.stdout, output2)) } } } fib(20) Output: ### Iterative with Buffer import Buffer from "buffer" import String from "string" let fib = j => { // set-up minimal, growable buffer let buf = Buffer.make(j * 2) let mut fnow = 0, fnext = 1 for (let mut n = 0; n <= j; n += 1) { if (n == 0 || n == 1) { Buffer.addChar(' ', buf) Buffer.addString(toString(n), buf) } else { let tempf = fnow + fnext fnow = fnext fnext = tempf Buffer.addChar(' ', buf) Buffer.addString(toString(fnext), buf) } } // stringify buffer and return Buffer.toString(buf) } let output = fib(20) print(output) Output:  0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765  ## Groovy Full "extra credit" solutions. ### Recursive A recursive closure must be pre-declared. def rFib rFib = { it == 0 ? 0 : it == 1 ? 1 : it > 1 ? rFib(it-1) + rFib(it-2) /*it < 0*/: rFib(it+2) - rFib(it+1) } ### Iterative 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))/2 def aFib = { (φ**it - (-φ)**(-it))/(5**(1/2)) as BigInteger } Test program: def time = { Closure c -> def start = System.currentTimeMillis() def result = c() def elapsedMS = (System.currentTimeMillis() - start)/1000 printf '(%6.4fs elapsed)', elapsedMS result } print " F(n) elapsed time "; (-10..10).each { printf ' %3d', it }; println() print "--------- -----------------"; (-10..10).each { print ' ---' }; println() [recursive:rFib, iterative:iFib, analytic:aFib].each { name, fib -> printf "%9s ", name def fibList = time { (-10..10).collect {fib(it)} } fibList.each { printf ' %3d', it } println() } Output:  F(n) elapsed time -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 --------- ----------------- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- recursive (0.0080s elapsed) -55 34 -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 34 55 iterative (0.0040s elapsed) -55 34 -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 34 55 analytic (0.0030s elapsed) -55 34 -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 34 55 ## Harbour ### 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 while return(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 0 fib n = (phi^^n - (-phi)^^(-n))/sqrt 5 Let's try it for large numbers: λ> fib 10 :: CReal 0 55 (0.01 secs, 137,576 bytes) λ> fib 100 :: CReal 0 354224848179261915075 (0.01 secs, 253,152 bytes) λ> fib 10000 :: CReal 0 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875 (0.02 secs, 4,847,128 bytes) λ> fib (-10) :: CReal 0 -55 (0.01 secs, 138,408 bytes) ### Recursive 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.MemoTrie fib :: Integer -> Integer fib = memo f where f 0 = 0 f 1 = 1 f n = fib (n-1) + fib (n-2) You can rewrite this without introducing f explicitly import Data.MemoTrie fib :: Integer -> Integer fib = memo$ \x -> case x of
0 -> 0
1 -> 1
n -> fib (n-1) + fib (n-2)

Or using LambdaCase extension you can write it even shorter:

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

### Iterative

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:

import Data.List (foldl') --'

fib :: Integer -> Integer
fib n =
fst $foldl' --' ($$a, b) _ -> (b, a + b)) (0, 1) [1 .. n] ### With matrix exponentiation Adapting the (rather slow) code from Matrix exponentiation operator, we can simply write: import Data.List (transpose) fib :: (Integral b, Num a) => b -> a fib 0 = 0 -- this line is necessary because "something ^ 0" returns "fromInteger 1", which unfortunately -- in our case is not our multiplicative identity (the identity matrix) but just a 1x1 matrix of 1 fib n = (last . head . unMat) (Mat [[1, 1], [1, 0]] ^ n) -- Code adapted from Matrix exponentiation operator task --------------------- (<+>) :: Num c => [c] -> [c] -> [c] (<+>) = zipWith (+) (<*>) :: Num a => [a] -> [a] -> a (<*>) = (sum .) . zipWith (*) newtype Mat a = Mat { unMat :: [[a]] } deriving (Eq) instance Show a => Show (Mat a) where show xm = "Mat " ++ show (unMat xm) instance Num a => Num (Mat a) where negate xm = Mat map (map negate) unMat xm xm + ym = Mat zipWith (<+>) (unMat xm) (unMat ym) xm * ym = Mat [ [ xs Main.<*> ys -- to distinguish from standard applicative operator | ys <- transpose unMat ym ] | xs <- unMat xm ] fromInteger n = Mat [[fromInteger n]] abs = undefined signum = undefined -- TEST ---------------------------------------------------------------------- main :: IO () main = (print . take 10 . show . fib) (10 ^ 5) So, for example, the hundred-thousandth Fibonacci number starts with the digits: Output: "2597406934" ### With recurrence relations Using Fib[m=3n+r] recurrence identities: import Control.Arrow ((&&&)) fibstep :: (Integer, Integer) -> (Integer, Integer) fibstep (a, b) = (b, a + b) fibnums :: [Integer] fibnums = map fst iterate fibstep (0, 1) fibN2 :: Integer -> (Integer, Integer) fibN2 m | m < 10 = iterate fibstep (0, 1) !! fromIntegral m fibN2 m = fibN2_next (n, r) (fibN2 n) where (n, r) = quotRem m 3 fibN2_next (n, r) (f, g) | r == 0 = (a, b) -- 3n ,3n+1 | r == 1 = (b, c) -- 3n+1,3n+2 | r == 2 = (c, d) -- 3n+2,3n+3 (*) where a = 5 * f ^ 3 + if even n then 3 * f else (-3 * f) -- 3n b = g ^ 3 + 3 * g * f ^ 2 - f ^ 3 -- 3n+1 c = g ^ 3 + 3 * g ^ 2 * f + f ^ 3 -- 3n+2 d = 5 * g ^ 3 + if even n then (-3 * g) else 3 * g -- 3(n+1) (*) main :: IO () main = print (length &&& take 20) . show . fst fibN2 (10 ^ 2) Output: (21,"35422484817926191507") (fibN2 n) directly calculates a pair (f,g) of two consecutive Fibonacci numbers, (Fib[n], Fib[n+1]), from recursively calculated such pair at about n/3:  *Main> (length &&& take 20) . show . fst fibN2 (10^6) (208988,"19532821287077577316") The above should take less than 0.1s to calculate on a modern box. Other identities that could also be used are here. In particular, for (n-1,n) ---> (2n-1,2n) transition which is equivalent to the matrix exponentiation scheme, we have f (n,(a,b)) = (2*n,(a*a+b*b,2*a*b+b*b)) -- iterate f (1,(0,1)) ; b is nth and for (n,n+1) ---> (2n,2n+1) (derived from d'Ocagne's identity, for example), g (n,(a,b)) = (2*n,(2*a*b-a*a,a*a+b*b)) -- iterate g (1,(1,1)) ; a is nth ## Haxe ### Iterative static function fib(steps:Int, handler:Int->Void) { var current = 0; var next = 1; for (i in 1...steps) { handler(current); var temp = current + next; current = next; next = temp; } handler(current); } ### As Iterator class FibIter { private var current = 0; private var nextItem = 1; private var limit:Int; public function new(limit) this.limit = limit; public function hasNext() return limit > 0; public function next() { limit--; var ret = current; var temp = current + nextItem; current = nextItem; nextItem = temp; return ret; } } Used like: for (i in new FibIter(10)) Sys.println(i); ## HicEst REAL :: Fibonacci(10) Fibonacci = (==2) + Fibonacci(-1) + Fibonacci(-2) WRITE(ClipBoard) Fibonacci ! 0 1 1 2 3 5 8 13 21 34 ## Hoon |= n=@ud =/ a=@ud 0 =/ b=@ud 1 |- ?: =(n 0) a (a b, b (add a b), n (dec n)) ## Hope ### Recursive dec f : num -> num; --- f 0 <= 0; --- f 1 <= 1; --- f(n+2) <= f n + f(n+1); ### Tail-recursive dec fib : num -> num; --- fib n <= l (1, 0, n) whererec l == \(a,b,succ c) => if c<1 then a else l((a+b),a,c) |(a,b,0) => 0; ### With lazy lists This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers: dec fibs : list num; --- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs); The nth Fibonacci number is then just fibs @ n. ## Hy Recursive implementation. (defn fib [n] (if (< n 2) n (+ (fib (- n 2)) (fib (- n 1))))) ## Icon and Unicon Icon has built-in support for big numbers. First, a simple recursive solution augmented by caching for non-negative input. This examples computes fib(1000) if there is no integer argument. procedure main(args) write(fib(integer(!args) | 1000) end procedure fib(n) static fCache initial { fCache := table() fCache[0] := 0 fCache[1] := 1 } /fCache[n] := fib(n-1) + fib(n-2) return fCache[n] end The above solution is similar to the one provided fib in memrfncs Now, an O(logN) solution. For large N, it takes far longer to convert the result to a string for output than to do the actual computation. This example computes fib(1000000) if there is no integer argument. procedure main(args) write(fib(integer(!args) | 1000000)) end procedure fib(n) return fibMat(n)[1] end procedure fibMat(n) if n <= 0 then return [0,0] if n = 1 then return [1,0] fp := fibMat(n/2) c := fp[1]*fp[1] + fp[2]*fp[2] d := fp[1]*(fp[1]+2*fp[2]) if n%2 = 1 then return [c+d, d] else return [d, c] end ## IDL ### Recursive function fib,n if n lt 3 then return,1L else return, fib(n-1)+fib(n-2) end Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo. ### Iterative function fib,n psum = (csum = 1uL) if n lt 3 then return,csum for i = 3,n do begin nsum = psum + csum psum = csum csum = nsum endfor return,nsum end Execution time O(n). Limited by size of uLong to fib(49) ### Analytic function fib,n q=1/( p=(1+sqrt(5))/2 ) return,round((p^n+q^n)/sqrt(5)) end Execution time O(1), only limited by the range of LongInts to fib(48). ## Idris ### Analytic fibAnalytic : Nat -> Double fibAnalytic n = floor ((pow goldenRatio n) - (pow (-1.0/goldenRatio) n)) / sqrt(5) where goldenRatio : Double goldenRatio = (1.0 + sqrt(5)) / 2.0 ### Recursive fibRecursive : Nat -> Nat fibRecursive Z = Z fibRecursive (S Z) = (S Z) fibRecursive (S (S n)) = fibRecursive (S n) + fibRecursive n ### Iterative fibIterative : Nat -> Nat fibIterative n = fibIterative' n Z (S Z) where fibIterative' : Nat -> Nat -> Nat -> Nat fibIterative' Z a _ = a fibIterative' (S n) a b = fibIterative' n b (a + b) ### Lazy fibLazy : Lazy (List Nat) fibLazy = 0 :: 1 :: zipWith (+) fibLazy ( case fibLazy of (x::xs) => xs [] => []) ## J The Fibonacci Sequence essay on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number. Here is one:  fibN=: (-&2 +&: -&1)^:(1&<) M."0 Examples:  fibN 12 144 fibN i.31 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 (This implementation is doubly recursive except that results are cached across function calls.) ## Java ### Iterative public static long itFibN(int n) { if (n < 2) return n; long ans = 0; long n1 = 0; long n2 = 1; for(n--; n > 0; n--) { ans = n1 + n2; n1 = n2; n2 = ans; } return ans; } /** * O(log(n)) */ public static long fib(long n) { if (n <= 0) return 0; long i = (int) (n - 1); long a = 1, b = 0, c = 0, d = 1, tmp1,tmp2; while (i > 0) { if (i % 2 != 0) { tmp1 = d * b + c * a; tmp2 = d * (b + a) + c * b; a = tmp1; b = tmp2; } tmp1 = (long) (Math.pow(c, 2) + Math.pow(d, 2)); tmp2 = d * (2 * c + d); c = tmp1; d = tmp2; i = i / 2; } return a + b; } ### Recursive public static long recFibN(final int n) { return (n < 2) ? n : recFibN(n - 1) + recFibN(n - 2); } ### Caching-recursive A variant on recursive, that caches previous results, reducing complexity from O(n2) to simply O(n). Leveraging Java’s Map.computeIfAbsent makes this thread-safe, and the implementation pretty trivial. public class Fibonacci { static final Map<Integer, Long> cache = new HashMap<>(); static { cache.put(1, 1L); cache.put(2, 1L); } public static long get(int n) { return (n < 2) ? n : impl(n); } private static long impl(int n) { return cache.computeIfAbsent(n, k -> impl(k-1) + impl(k-2)); } } ### Analytic This method works up to the 92nd Fibonacci number. After that, it goes out of range. public static long anFibN(final long n) { double p = (1 + Math.sqrt(5)) / 2; double q = 1 / p; return (long) ((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5)); } ### Tail-recursive public static long fibTailRec(final int n) { return fibInner(0, 1, n); } private static long fibInner(final long a, final long b, final int n) { return n < 1 ? a : n == 1 ? b : fibInner(b, a + b, n - 1); } ### Streams import java.util.function.LongUnaryOperator; import java.util.stream.LongStream; public class FibUtil { public static LongStream fibStream() { return LongStream.iterate( 1l, new LongUnaryOperator() { private long lastFib = 0; @Override public long applyAsLong( long operand ) { long ret = operand + lastFib; lastFib = operand; return ret; } }); } public static long fib(long n) { return fibStream().limit( n ).reduce((prev, last) -> last).getAsLong(); } } ## JavaScript ### ES5 #### Recursive Basic recursive function: function fib(n) { return n<2?n:fib(n-1)+fib(n-2); } Can be rewritten as: function fib(n) { if (n<2) { return n; } else { return fib(n-1)+fib(n-2); } } One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion: function fib(n) { return function(n,a,b) { return n>0 ? arguments.callee(n-1,b,a+b) : a; }(n,0,1); } ### Iterative function fib(n) { var a = 0, b = 1, t; while (n-- > 0) { t = a; a = b; b += t; console.log(a); } return a; } #### Memoization With the keys of a dictionary, var fib = (function(cache){ return cache = cache || {}, function(n){ if (cache[n]) return cache[n]; else return cache[n] = n == 0 ? 0 : n < 0 ? -fib(-n) : n <= 2 ? 1 : fib(n-2) + fib(n-1); }; })(); with the indices of an array, (function () { 'use strict'; function fib(n) { return Array.apply(null, Array(n + 1)) .map(function (_, i, lst) { return lst[i] = ( i ? i < 2 ? 1 : lst[i - 2] + lst[i - 1] : 0 ); })[n]; } return fib(32); })(); Output: 2178309 #### Y-Combinator function Y(dn) { return (function(fn) { return fn(fn); }(function(fn) { return dn(function() { return fn(fn).apply(null, arguments); }); })); } var fib = Y(function(fn) { return function(n) { if (n === 0 || n === 1) { return n; } return fn(n - 1) + fn(n - 2); }; }); #### Generators function* fibonacciGenerator() { var prev = 0; var curr = 1; while (true) { yield curr; curr = curr + prev; prev = curr - prev; } } var fib = fibonacciGenerator(); ### ES6 #### Memoized If we want access to the whole preceding series, as well as a memoized route to a particular member, we can use an accumulating fold. (() => { 'use strict'; // Nth member of fibonacci series // fib :: Int -> Int function fib(n) { return mapAccumL(([a, b]) => [ [b, a + b], b ], [0, 1], range(1, n))[0][0]; }; // GENERIC FUNCTIONS // mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) let mapAccumL = (f, acc, xs) => { return xs.reduce((a, x) => { let pair = f(a[0], x); return [pair[0], a[1].concat(pair[1])]; }, [acc, []]); } // range :: Int -> Int -> Maybe Int -> [Int] let range = (m, n) => Array.from({ length: Math.floor(n - m) + 1 }, (_, i) => m + i); // TEST return fib(32); // --> 2178309 })(); Otherwise, a simple fold will suffice. Translation of: Haskell (Memoized fold example) (() => { 'use strict'; // fib :: Int -> Int let fib = n => range(1, n) .reduce(([a, b]) => [b, a + b], [0, 1])[0]; // GENERIC [m..n] // range :: Int -> Int -> [Int] let range = (m, n) => Array.from({ length: Math.floor(n - m) + 1 }, (_, i) => m + i); // TEST return fib(32); // --> 2178309 })(); Output: 2178309 ## Joy ### Recursive DEFINE fib == [small] [] [pred dup pred] [+] binrec. ### Iterative DEFINE fib == [1 0] dip [swap [+] unary] times popd. ## jq Works with: jq Works with gojq, the Go implementation of jq The C implementation of jq does not (yet) have infinite-precision integer arithmetic, and so using it, the following algorithms only give exact answers up to fib(78). By contrast, using the Go implementation of jq and the definition of nth_fib given below: nth_fib(pow(2;20)) | tostring | [length, .[:10], .[-10:]] yields [219140,"1186800606","0691163707"]  in about 20 seconds on a 3GHz machine. Using either the C or Go implementations, at a certain point, integers are converted to floats, but floating point precision for fib(n) fails after n = 1476: in jq, fib(1476) evaluates to 1.3069892237633987e+308 ### Recursive def nth_fib_naive(n): if (n < 2) then n else nth_fib_naive(n - 1) + nth_fib_naive(n - 2) end; ### Tail Recursive Recent versions of jq (after July 1, 2014) include basic optimizations for tail recursion, and nth_fib is defined here to take advantage of TCO. For example, nth_fib(10000000) completes with only 380KB (that's K) of memory. However nth_fib can also be used with earlier versions of jq. def nth_fib(n): # input: [f(i-2), f(i-1), countdown] def fib: (.[0] + .[1]) as sum | .[2] as n | if (n <= 0) then sum else [ .[1], sum, n - 1 ] | fib end; [-1, 1, n] | fib; Example: (range(0;5), 50) | [., nth_fib(.)] yields: [0,0] [1,1] [2,1] [3,2] [4,3] [50,12586269025] ### Binet's Formula def fib_binet(n): (5|sqrt) as rt | ((1 + rt)/2) as phi | ((phi | log) * n | exp) as phin | (if 0 == (n % 2) then 1 else -1 end) as sign | ( (phin - (sign / phin) ) / rt ) + .5 | floor; ### Generator The following is a jq generator which produces the first n terms of the Fibonacci sequence efficiently, one by one. Notice that it is simply a variant of the above tail-recursive function. The function is in effect turned into a generator by changing "( _ | fib )" to "sum, (_ | fib)". # Generator def fibonacci(n): # input: [f(i-2), f(i-1), countdown] def fib: (.[0] + .[1]) as sum | if .[2] == 0 then sum else sum, ([ .[1], sum, .[2] - 1 ] | fib) end; [-1, 1, n] | fib; ## Julia ### Recursive fib(n) = n < 2 ? n : fib(n-1) + fib(n-2) ### Iterative function fib(n) x,y = (0,1) for i = 1:n x,y = (y, x+y) end x end ### Matrix form fib(n) = ([1 1 ; 1 0]^n)[1,2] ## K Works with: Kona ### Recursive {:[x<3;1;_f[x-1]+_f[x-2]]} ### Recursive with memoization Using a (global) dictionary c. {c::.();{v:c[a:x];:[x<3;1;:[_n~v;c[a]:_f[x-1]+_f[x-2];v]]}x} ### Analytic phi:(1+_sqrt(5))%2 {_((phi^x)-((1-phi)^x))%_sqrt[5]} ### Sequence to n Works with: Kona Works with: ngn/k {(x(|+$$\1 1)[;1]} {x{x,+/-2#x}/!2} ## Kabap ### Sequence to n // Calculate the$n'th Fibonacci number

// Set this to how many in the sequence to generate
$n = 10; // These are what hold the current calculation$a = 0;
$b = 1; // This holds the complete sequence that is generated$sequence = "";

// Prepare a loop
$i = 0; :calcnextnumber;$i = $i++; // Do the calculation for this loop iteration$b = $a +$b;
$a =$b - $a; // Add the result to the sequence$sequence = $sequence <<$a;

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

// Use the loop counter as the placeholder
$i--; // Return the sequence return = "Fibonacci number " <<$i << " is " << $a << " (" <<$sequence << ")";

## Klingphix

: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) ## Lang ### Iterative fp.fib = ($n) -> {
if($n < 2) { return$n
}

$prev = 1$cur = 1
$i = 2 while($i < $n) {$tmp = $cur$cur += $prev$prev = $tmp$i += 1
}

return $cur } ### Recursive fp.fib = ($n) -> {
if($n < 2) { return$n
}

return parser.op(fp.fib($n - 1) + fp.fib($n - 2))
}

## 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 = #sw`