Fibonacci sequence
(Redirected from Fibonacci numbers)
You are encouraged to solve this task according to the task description, using any language you may know.
The Fibonacci sequence is a sequence Fn of natural numbers defined recursively:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2, if n>1
- Task
Write a function to generate the nth Fibonacci number.
Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).
The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:
Fn = Fn+2 - Fn+1, if n<0
support for negative n in the solution is optional.
- Related tasks
- References
- Wikipedia, Fibonacci number
- Wikipedia, Lucas number
- MathWorld, Fibonacci Number
- Some identities for r-Fibonacci numbers
- OEIS Fibonacci numbers
- OEIS Lucas numbers
0815[edit]
%<:0D:>~$<:01:~%>=<:a94fad42221f2702:>~>
}:_s:{x{={~$x+%{=>~>x~-x<:0D:~>~>~^:_s:?11l[edit]
F fib_iter(n)
I n < 2
R n
V fib_prev = 1
V fib = 1
L 2 .< n
(fib_prev, fib) = (fib, fib + fib_prev)
R fib
L(i) 1..20
print(fib_iter(i), end' ‘ ’)
print()- Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
360 Assembly[edit]
For maximum compatibility, programs use only the basic instruction set.
using fullword integers[edit]
* Fibonacci sequence 05/11/2014
* integer (31 bits) = 10 decimals -> max fibo(46)
FIBONACC CSECT
USING FIBONACC,R12 base register
SAVEAREA B STM-SAVEAREA(R15) skip savearea
DC 17F'0' savearea
DC CL8'FIBONACC' eyecatcher
STM STM R14,R12,12(R13) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R12,R15 set addressability
* ----
LA R1,0 f(n-2)=0
LA R2,1 f(n-1)=1
LA R4,2 n=2
LA R6,1 step
LH R7,NN limit
LOOP EQU * for n=2 to nn
LR R3,R2 f(n)=f(n-1)
AR R3,R1 f(n)=f(n-1)+f(n-2)
CVD R4,PW n convert binary to packed (PL8)
UNPK ZW,PW packed (PL8) to zoned (ZL16)
MVC CW,ZW zoned (ZL16) to char (CL16)
OI CW+L'CW-1,X'F0' zap sign
MVC WTOBUF+5(2),CW+14 output
CVD R3,PW f(n) binary to packed decimal (PL8)
MVC ZN,EM load mask
ED ZN,PW packed dec (PL8) to char (CL20)
MVC WTOBUF+9(14),ZN+6 output
WTO MF=(E,WTOMSG) write buffer
LR R1,R2 f(n-2)=f(n-1)
LR R2,R3 f(n-1)=f(n)
BXLE R4,R6,LOOP endfor n
* ----
LM R14,R12,12(R13) restore previous savearea pointer
XR R15,R15 return code set to 0
BR R14 return to caller
* ---- DATA
NN DC H'46' nn max n
PW DS PL8 15num
ZW DS ZL16
CW DS CL16
ZN DS CL20
* ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0' 15num
EM DC XL20'402020206B2020206B2020206B2020206B202120' mask
WTOMSG DS 0F
DC H'80',XL2'0000'
* fibo(46)=1836311903
WTOBUF DC CL80'fibo(12)=1234567890'
REGEQU
END FIBONACC- Output:
... fibo(41)= 165,580,141 fibo(42)= 267,914,296 fibo(43)= 433,494,437 fibo(44)= 701,408,733 fibo(45)= 1,134,903,170 fibo(46)= 1,836,311,903
using packed decimals[edit]
* Fibonacci sequence 31/07/2018
* packed dec (PL8) = 15 decimals => max fibo(73)
FIBOWTOP CSECT
USING FIBOWTOP,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
* ----
ZAP FNM2,=P'0' f(0)=0
ZAP FNM1,=P'1' f(1)=1
LA R4,2 n=2
LA R6,1 step
LH R7,NN limit
LOOP EQU * for n=2 to nn
ZAP FN,FNM1 f(n)=f(n-2)
AP FN,FNM2 f(n)=f(n-1)+f(n-2)
CVD R4,PW n
MVC ZN,EM load mask
ED ZN,PW packed dec (PL8) to char (CL16)
MVC WTOBUF+5(2),ZN+L'ZN-2 output
MVC ZN,EM load mask
ED ZN,FN packed dec (PL8) to char (CL16)
MVC WTOBUF+9(L'ZN),ZN output
WTO MF=(E,WTOMSG) write buffer
ZAP FNM2,FNM1 f(n-2)=f(n-1)
ZAP FNM1,FN f(n-1)=f(n)
BXLE R4,R6,LOOP endfor n
* ----
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling sav
* ---- DATA
NN DC H'73' nn
FNM2 DS PL8 f(n-2)
FNM1 DS PL8 f(n-1)
FN DS PL8 f(n)
PW DS PL8 15num
ZN DS CL20
* ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0' 15num
EM DC XL20'402020206B2020206B2020206B2020206B202120' mask
WTOMSG DS 0F
DC H'80',XL2'0000'
* fibo(73)=806515533049393
WTOBUF DC CL80'fibo(12)=123456789012345 '
REGEQU
END FIBOWTOP- Output:
... fibo(68)= 72,723,460,248,141 fibo(69)= 117,669,030,460,994 fibo(70)= 190,392,490,709,135 fibo(71)= 308,061,521,170,129 fibo(72)= 498,454,011,879,264 fibo(73)= 806,515,533,049,393
6502 Assembly[edit]
This subroutine stores the first n—by default the first ten—Fibonacci numbers in memory, beginning (because, why not?) at address 3867 decimal = F1B hex. Intermediate results are stored in three sequential addresses within the low 256 bytes of memory, which are the most economical to access.
The results are calculated and stored, but are not output to the screen or any other physical device: how to do that would depend on the hardware and the operating system.
LDA #0
STA $F0 ; LOWER NUMBER
LDA #1
STA $F1 ; HIGHER NUMBER
LDX #0
LOOP: LDA $F1
STA $0F1B,X
STA $F2 ; OLD HIGHER NUMBER
ADC $F0
STA $F1 ; NEW HIGHER NUMBER
LDA $F2
STA $F0 ; NEW LOWER NUMBER
INX
CPX #$0A ; STOP AT FIB(10)
BMI LOOP
RTS ; RETURN FROM SUBROUTINE68000 Assembly[edit]
Input is in D0, and the output is also in D0. There is no protection from 32-bit overflow, so use at your own risk. (I used this C compiler to create this in ARM Assembly and translated it manually into 68000 Assembly. It wasn't that difficult since both CPUs have similar architectures.)
fib:
MOVEM.L D4-D5,-(SP)
MOVE.L D0,D4
MOVEQ #0,D5
CMP.L #2,D0
BCS .bar
MOVEQ #0,D5
.foo:
MOVE.L D4,D0
SUBQ.L #1,D0
JSR fib
SUBQ.L #2,D4
ADD.L D0,D5
CMP.L #1,D4
BHI .foo
.bar:
MOVE.L D5,D0
ADD.L D4,D0
MOVEM.L (SP)+,D4-D5
RTS
8080 Assembly[edit]
This subroutine expects to be called with the value of in register A, and returns also in A. You may want to take steps to save the previous contents of B, C, and D. The routine only works with fairly small values of .
FIBNCI: MOV C, A ; C will store the counter
DCR C ; decrement, because we know f(1) already
MVI A, 1
MVI B, 0
LOOP: MOV D, A
ADD B ; A := A + B
MOV B, D
DCR C
JNZ LOOP ; jump if not zero
RET ; return from subroutine8086 Assembly[edit]
Calculating the values at runtime[edit]
Is it cheating to write it in C for 64-bit x86 then port it to 16-bit x86?
The max input is 24 before you start having 16-bit overflow.
fib:
; WRITTEN IN C WITH X86-64 CLANG 3.3 AND DOWNGRADED TO 16-BIT X86
; INPUT: DI = THE NUMBER YOU WISH TO CALC THE FIBONACCI NUMBER FOR.
; OUTPUTS TO AX
push BP
push BX
push AX
mov BX, DI ;COPY INPUT TO BX
xor AX, AX ;MOV AX,0
test BX, BX ;SET FLAGS ACCORDING TO BX
je LBB0_4 ;IF BX == 0 RETURN 0
cmp BX, 1 ;IF BX == 1 RETURN 1
jne LBB0_3
mov AX, 1 ;ELSE, SET AX = 1 AND RETURN
jmp LBB0_4
LBB0_3:
lea DI, WORD PTR [BX - 1] ;DI = BX - 1
call fib ;RETURN FIB(BX-1)
mov BP, AX ;STORE THIS IN BP
add BX, -2
mov DI, BX
call fib ;GET FIB(DI - 2)
add AX, BP ;RETURN FIB(DI - 1) + FIB(DI - 2)
LBB0_4:
add sp,2
pop BX
pop BP
ret
Using A Lookup Table[edit]
With old computers it was common to use lookup tables to fetch pre-calculated values that would otherwise take some time to compute. The elements of the table are ordered by index, so you can simply create a function that takes an offset as the parameter and returns the element of the array at that offset.
Although lookup tables are very fast, there are some drawbacks to using them. For one, you end up taking up a lot of space. We're wasting a lot of bytes to store very low numbers at the beginning (each takes up 4 bytes regardless of how many digits you see). Unfortunately, when using lookup tables you have very little choice, since trying to conditionally change the scaling of the index would more than likely take more code than encoding all data as the maximum size regardless of the contents, as was done here. This keeps it simple for the CPU, which isn't aware of the intended size of each entry of the table.
For the purpose of this example, assume that both this code and the table are in the .CODE segment.
getfib:
;input: BX = the desired fibonacci number (in other words, the "n" in "F(n)")
; DS must point to the segment where the fibonacci table is stored
;outputs to DX:AX (DX = high word, AX = low word)
push ds
cmp bx,41 ;bounds check
ja IndexOutOfBounds
shl bx,1
shl bx,1 ;multiply by 4, since this is a table of dwords
mov ax,@code
mov ds,ax
mov si,offset fib
mov ax,[ds:si] ;fetch the low word into AX
mov dx,2[ds:si] ;fetch the high word into DX
pop ds
ret
IndexOutOfBounds:
stc ;set carry to indicate an error
mov ax,0FFFFh ;return FFFF as the error code
pop ds
ret
;table of the first 41 fibonacci numbers
fib dword 0, 1, 1, 2, 3, 5, 8, 13
dword 21, 34, 55, 89, 144, 233, 377, 610
dword 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657
dword 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269
dword 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986
dword 102334155
8th[edit]
An iterative solution:
: fibon \ n -- fib(n)
>r 0 1
( tuck n:+ ) \ fib(n-2) fib(n-1) -- fib(n-1) fib(n)
r> n:1- times ;
: fib \ n -- fib(n)
dup 1 n:= if 1 ;; then
fibon nip ;
ABAP[edit]
Iterative[edit]
FORM fibonacci_iter USING index TYPE i
CHANGING number_fib TYPE i.
DATA: lv_old type i,
lv_cur type i.
Do index times.
If sy-index = 1 or sy-index = 2.
lv_cur = 1.
lv_old = 0.
endif.
number_fib = lv_cur + lv_old.
lv_old = lv_cur.
lv_cur = number_fib.
enddo.
ENDFORM.
Impure Functional[edit]
cl_demo_output=>display( REDUCE #( INIT fibnm = VALUE stringtab( ( |0| ) ( |1| ) )
n TYPE string
x = `0`
y = `1`
FOR i = 1 WHILE i <= 100
NEXT n = ( x + y )
fibnm = VALUE #( BASE fibnm ( n ) )
x = y
y = n ) ).
ACL2[edit]
Fast, tail recursive solution:
(defun fast-fib-r (n a b)
(if (or (zp n) (zp (1- n)))
b
(fast-fib-r (1- n) b (+ a b))))
(defun fast-fib (n)
(fast-fib-r n 1 1))
(defun first-fibs-r (n i)
(declare (xargs :measure (nfix (- n i))))
(if (zp (- n i))
nil
(cons (fast-fib i)
(first-fibs-r n (1+ i)))))
(defun first-fibs (n)
(first-fibs-r n 0))
- Output:
>(first-fibs 20) (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
Action![edit]
Action! language does not support recursion. Therefore an iterative approach has been proposed.
INT FUNC Fibonacci(INT n)
INT curr,prev,tmp
IF n>=-1 AND n<=1 THEN
RETURN (n)
FI
prev=0
IF n>0 THEN
curr=1
DO
tmp=prev
prev=curr
curr==+tmp
n==-1
UNTIL n=1
OD
ELSE
curr=-1
DO
tmp=prev
prev=curr
curr==+tmp
n==+1
UNTIL n=-1
OD
FI
RETURN (curr)
PROC Main()
BYTE n
INT f
Put(125) ;clear screen
FOR n=0 TO 22
DO
f=Fibonacci(n)
Position(2,n+1)
PrintF("Fib(%I)=%I",n,f)
IF n>0 THEN
f=Fibonacci(-n)
Position(21,n+1)
PrintF("Fib(%I)=%I",-n,f)
FI
OD
RETURN- Output:
Screenshot from Atari 8-bit computer
Fib(0)=0 Fib(1)=1 Fib(-1)=-1 Fib(2)=1 Fib(-2)=-1 Fib(3)=2 Fib(-3)=-2 Fib(4)=3 Fib(-4)=-3 Fib(5)=5 Fib(-5)=-5 Fib(6)=8 Fib(-6)=-8 Fib(7)=13 Fib(-7)=-13 Fib(8)=21 Fib(-8)=-21 Fib(9)=34 Fib(-9)=-34 Fib(10)=55 Fib(-10)=-55 Fib(11)=89 Fib(-11)=-89 Fib(12)=144 Fib(-12)=-144 Fib(13)=233 Fib(-13)=-233 Fib(14)=377 Fib(-14)=-377 Fib(15)=610 Fib(-15)=-610 Fib(16)=987 Fib(-16)=-987 Fib(17)=1597 Fib(-17)=-1597 Fib(18)=2584 Fib(-18)=-2584 Fib(19)=4181 Fib(-19)=-4181 Fib(20)=6765 Fib(-20)=-6765 Fib(21)=10946 Fib(-21)=-10946 Fib(22)=17711 Fib(-22)=-17711
ActionScript[edit]
public function fib(n:uint):uint
{
if (n < 2)
return n;
return fib(n - 1) + fib(n - 2);
}
Ada[edit]
Recursive[edit]
with Ada.Text_IO, Ada.Command_Line;
procedure Fib is
X: Positive := Positive'Value(Ada.Command_Line.Argument(1));
function Fib(P: Positive) return Positive is
begin
if P <= 2 then
return 1;
else
return Fib(P-1) + Fib(P-2);
end if;
end Fib;
begin
Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
Ada.Text_IO.Put_Line(Integer'Image(Fib(X)));
end Fib;
Iterative, build-in integers[edit]
with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Fibonacci is
function Fibonacci (N : Natural) return Natural is
This : Natural := 0;
That : Natural := 1;
Sum : Natural;
begin
for I in 1..N loop
Sum := This + That;
That := This;
This := Sum;
end loop;
return This;
end Fibonacci;
begin
for N in 0..10 loop
Put_Line (Positive'Image (Fibonacci (N)));
end loop;
end Test_Fibonacci;
- Output:
0 1 1 2 3 5 8 13 21 34 55
Iterative, long integers[edit]
Using the big integer implementation from a cryptographic library [1].
with Ada.Text_IO, Ada.Command_Line, Crypto.Types.Big_Numbers;
procedure Fibonacci is
X: Positive := Positive'Value(Ada.Command_Line.Argument(1));
Bit_Length: Positive := 1 + (696 * X) / 1000;
-- that number of bits is sufficient to store the full result.
package LN is new Crypto.Types.Big_Numbers
(Bit_Length + (32 - Bit_Length mod 32));
-- the actual number of bits has to be a multiple of 32
use LN;
function Fib(P: Positive) return Big_Unsigned is
Previous: Big_Unsigned := Big_Unsigned_Zero;
Result: Big_Unsigned := Big_Unsigned_One;
Tmp: Big_Unsigned;
begin
-- Result = 1 = Fibonacci(1)
for I in 1 .. P-1 loop
Tmp := Result;
Result := Previous + Result;
Previous := Tmp;
-- Result = Fibonacci(I+1))
end loop;
return Result;
end Fib;
begin
Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
Ada.Text_IO.Put_Line(LN.Utils.To_String(Fib(X)));
end Fibonacci;
- Output:
> ./fibonacci 777 Fibonacci( 777 ) = 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082
Fast method using fast matrix exponentiation[edit]
with ada.text_io;
use ada.text_io;
procedure fast_fibo is
-- We work with biggest natural integers in a 64 bits machine
type Big_Int is mod 2**64;
-- We provide an index type for accessing the fibonacci sequence terms
type Index is new Big_Int;
-- fibo is a generic function that needs a modulus type since it will return
-- the n'th term of the fibonacci sequence modulus this type (use Big_Int to get the
-- expected behaviour in this particular task)
generic
type ring_element is mod <>;
with function "*" (a, b : ring_element) return ring_element is <>;
function fibo (n : Index) return ring_element;
function fibo (n : Index) return ring_element is
type matrix is array (1 .. 2, 1 .. 2) of ring_element;
-- f is the matrix you apply to a column containing (F_n, F_{n+1}) to get
-- the next one containing (F_{n+1},F_{n+2})
-- could be a more general matrix (given as a generic parameter) to deal with
-- other linear sequences of order 2
f : constant matrix := (1 => (0, 1), 2 => (1, 1));
function "*" (a, b : matrix) return matrix is
(1 => (a(1,1)*b(1,1)+a(1,2)*b(2,1), a(1,1)*b(1,2)+a(1,2)*b(2,2)),
2 => (a(2,1)*b(1,1)+a(2,2)*b(2,1), a(2,1)*b(1,2)+a(2,2)*b(2,2)));
function square (m : matrix) return matrix is (m * m);
-- Fast_Pow could be non recursive but it doesn't really matter since
-- the number of calls is bounded up by the size (in bits) of Big_Int (e.g 64)
function fast_pow (m : matrix; n : Index) return matrix is
(if n = 0 then (1 => (1, 0), 2 => (0, 1)) -- = identity matrix
elsif n mod 2 = 0 then square (fast_pow (m, n / 2))
else m * square (fast_pow (m, n / 2)));
begin
return fast_pow (f, n)(2, 1);
end fibo;
function Big_Int_Fibo is new fibo (Big_Int);
begin
-- calculate instantly F_n with n=10^15 (modulus 2^64 )
put_line (Big_Int_Fibo (10**15)'img);
end fast_fibo;
AdvPL[edit]
Recursive[edit]
#include "totvs.ch"
User Function fibb(a,b,n)
return(if(--n>0,fibb(b,a+b,n),a))Iterative[edit]
#include "totvs.ch"
User Function fibb(n)
local fnow:=0, fnext:=1, tempf
while (--n>0)
tempf:=fnow+fnext
fnow:=fnext
fnext:=tempf
end while
return(fnext)Agda[edit]
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[edit]
integer
fibs(integer n)
{
integer w;
if (n == 0) {
w = 0;
} elif (n == 1) {
w = 1;
} else {
integer a, b, i;
i = 1;
a = 0;
b = 1;
while (i < n) {
w = a + b;
a = b;
b = w;
i += 1;
}
}
return w;
}ALGOL 60[edit]
begin
comment Fibonacci sequence;
integer procedure fibonacci(n); value n; integer n;
begin
integer i, fn, fn1, fn2;
fn2 := 1;
fn1 := 0;
fn := 0;
for i := 1 step 1 until n do begin
fn := fn1 + fn2;
fn2 := fn1;
fn1 := fn
end;
fibonacci := fn
end fibonacci;
integer i;
for i := 0 step 1 until 20 do outinteger(1,fibonacci(i))
end- Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
ALGOL 68[edit]
Analytic[edit]
PROC analytic fibonacci = (LONG INT n)LONG INT:(
LONG REAL sqrt 5 = long sqrt(5);
LONG REAL p = (1 + sqrt 5) / 2;
LONG REAL q = 1/p;
ROUND( (p**n + q**n) / sqrt 5 )
);
FOR i FROM 1 TO 30 WHILE
print(whole(analytic fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)- Output:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
Iterative[edit]
PROC iterative fibonacci = (INT n)INT:
CASE n+1 IN
0, 1, 1, 2, 3, 5
OUT
INT even:=3, odd:=5;
FOR i FROM odd+1 TO n DO
(ODD i|odd|even) := odd + even
OD;
(ODD n|odd|even)
ESAC;
FOR i FROM 0 TO 30 WHILE
print(whole(iterative fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)- Output:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
Recursive[edit]
PROC recursive fibonacci = (INT n)INT:
( n < 2 | n | fib(n-1) + fib(n-2));Generative[edit]
MODE YIELDINT = PROC(INT)VOID;
PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (
INT even:=0, odd:=1;
yield(even);
yield(odd);
FOR i FROM odd+1 TO n DO
yield( (ODD i|odd|even) := odd + even )
OD
);
main:(
# FOR INT n IN # gen fibonacci(30, # ) DO ( #
## (INT n)VOID:(
print((" ",whole(n,0)))
# OD # ));
print(new line)
)- Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
Array (Table) Lookup[edit]
This uses a pre-generated list, requiring much less run-time processor usage, but assumes that INT is only 31 bits wide.
[]INT const fibonacci = []INT( -1836311903, 1134903170,
-701408733, 433494437, -267914296, 165580141, -102334155,
63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
3524578, -2178309, 1346269, -832040, 514229, -317811, 196418,
-121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181,
-2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13,
-8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
701408733, 1134903170, 1836311903
)[@-46];
PROC VOID value error := stop;
PROC lookup fibonacci = (INT i)INT: (
IF LWB const fibonacci <= i AND i<= UPB const fibonacci THEN
const fibonacci[i]
ELSE
value error; SKIP
FI
);
FOR i FROM 0 TO 30 WHILE
print(whole(lookup fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)- Output:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
ALGOL W[edit]
begin
% return the nth Fibonacci number %
integer procedure Fibonacci( integer value n ) ;
begin
integer fn, fn1, fn2;
fn2 := 1;
fn1 := 0;
fn := 0;
for i := 1 until n do begin
fn := fn1 + fn2;
fn2 := fn1;
fn1 := fn
end ;
fn
end Fibonacci ;
for i := 0 until 10 do writeon( i_w := 3, s_w := 0, Fibonacci( i ) )
end.- Output:
0 1 1 2 3 5 8 13 21 34 55
ALGOL-M[edit]
Note that the 21st Fibonacci number (= 10946) is the largest that can be calculated without overflowing ALGOL-M's integer data type.
Iterative[edit]
INTEGER FUNCTION FIBONACCI( X ); INTEGER X;
BEGIN
INTEGER M, N, A, I;
M := 0;
N := 1;
FOR I := 2 STEP 1 UNTIL X DO
BEGIN
A := N;
N := M + N;
M := A;
END;
FIBONACCI := N;
END;Naively recursive[edit]
INTEGER FUNCTION FIBONACCI( X ); INTEGER X;
BEGIN
IF X < 3 THEN
FIBONACCI := 1
ELSE
FIBONACCI := FIBONACCI( X - 2 ) + FIBONACCI( X - 1 );
END;Alore[edit]
def fib(n as Int) as Int
if n < 2
return 1
end
return fib(n-1) + fib(n-2)
endAmazing Hopper[edit]
Analitic, Recursive and Iterative mode.
#include <hbasic.h>
#define TERM1 1.61803398874989
#define TERM2 -0.61803398874989
#context get Fibonacci number with analitic mode
GetArgs(n)
get Inv of (M_SQRT5), Mul by( Pow (TERM 1, n), Minus( Pow(TERM 2, n) ) );
then Return\\
#proto fibonacci_recursive(__X__)
#synon _fibonacci_recursive getFibonaccinumberwithrecursivemodeof
#proto fibonacci_iterative(__X__)
#synon _fibonacci_iterative getFibonaccinumberwithiterativemodeof
Begin
Option Stack 1024
get Arg Number(2, n), and Take( n );
then, get Fibonacci number with analitic mode, and Print It with a Newl.
secondly, get Fibonacci number with recursive mode of(n), and Print It with a Newl.
finally, get Fibonacci number with iterative mode of (n), and Print It with a Newl.
End
Subrutines
fibonacci_recursive(n)
Iif ( var(n) Is Le? (2), 1 , \
get Fibonacci number with recursive mode of( var(n) Minus (1));\
get Fibonacci number with recursive mode of( var(n) Minus (2)); and Add It )
Return
fibonacci_iterative(n)
A=0
B=1
For Up( I:=2, n, 1 )
C=B
Let ( B: = var(A) Plus (B) )
A=C
Next
Return(B)- Output:
$ hopper src/fibo1.bas 25 75025 75025 75025
AntLang[edit]
/Sequence
fib:{<0;1> {x,<x[-1]+x[-2]>}/ range[x]}
/nth
fibn:{fib[x][x]}Apex[edit]
/*
author: snugsfbay
date: March 3, 2016
description: Create a list of x numbers in the Fibonacci sequence.
- user may specify the length of the list
- enforces a minimum of 2 numbers in the sequence because any fewer is not a sequence
- enforces a maximum of 47 because further values are too large for integer data type
- Fibonacci sequence always starts with 0 and 1 by definition
*/
public class FibNumbers{
final static Integer MIN = 2; //minimum length of sequence
final static Integer MAX = 47; //maximum length of sequence
/*
description: method to create a list of numbers in the Fibonacci sequence
param: user specified integer representing length of sequence should be 2-47, inclusive.
- Sequence starts with 0 and 1 by definition so the minimum length could be as low as 2.
- For 48th number in sequence or greater, code would require a Long data type rather than an Integer.
return: list of integers in sequence.
*/
public static List<Integer> makeSeq(Integer len){
List<Integer> fib = new List<Integer>{0,1}; // initialize list with first two values
Integer i;
if(len<MIN || len==null || len>MAX) {
if (len>MAX){
len=MAX; //set length to maximum if user entered too high a value
}else{
len=MIN; //set length to minimum if user entered too low a value or none
}
} //This could be refactored using teneray operator, but we want code coverage to be reflected for each condition
//start with initial list size to find previous two values in the sequence, continue incrementing until list reaches user defined length
for(i=fib.size(); i<len; i++){
fib.add(fib[i-1]+fib[i-2]); //create new number based on previous numbers and add that to the list
}
return fib;
}
}APL[edit]
Naive Recursive[edit]
fib←{⍵≤1:⍵ ⋄ (∇ ⍵-1)+∇ ⍵-2}
Read this as: In the variable "fib", store the function that says, if the argument is less than or equal to 1, return the argument. Else, calculate the value you get when you recursively call the current function with the argument of the current argument minus one and add that to the value you get when you recursively call the current function with the argument of the current function minus two.
This naive solution requires Dyalog APL because GNU APL does not support this syntax for conditional guards.
Array[edit]
Since APL is an array language we'll use the following identity:
In APL:
↑+.×/N/⊂2 2⍴1 1 1 0
Plugging in 4 for N gives the following result:
Here's what happens: We replicate the 2-by-2 matrix N times and then apply inner product-replication. The First removes the shell from the Enclose. At this point we're basically done, but we need to pick out only in order to complete the task. Here's one way:
↑0 1↓↑+.×/N/⊂2 2⍴1 1 1 0
Analytic[edit]
An alternative approach, using Binet's formula (which was apparently known long before Binet):
⌊.5+(((1+PHI)÷2)*⍳N)÷PHI←5*.5
AppleScript[edit]
Imperative[edit]
set fibs to {}
set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3"))
set x to x as integer
repeat with y from 1 to x
if (y = 1 or y = 2) then
copy 1 to the end of fibs
else
copy ((item (y - 1) of fibs) + (item (y - 2) of fibs)) to the end of fibs
end if
end repeat
return item x of fibs
Functional[edit]
The simple recursive version is famously slow:
on fib(n)
if n < 1 then
0
else if n < 3 then
1
else
fib(n - 2) + fib(n - 1)
end if
end fib
but we can combine enumFromTo(m, n) with the accumulator of a higher-order fold/reduce function to memoize the series:
(ES6 memoized fold example) (Memoized fold example)-------------------- FIBONACCI SEQUENCE --------------------
-- fib :: Int -> Int
on fib(n)
-- lastTwo : (Int, Int) -> (Int, Int)
script lastTwo
on |λ|([a, b])
[b, a + b]
end |λ|
end script
item 1 of foldl(lastTwo, {0, 1}, enumFromTo(1, n))
end fib
--------------------------- TEST ---------------------------
on run
fib(32)
--> 2178309
end run
-------------------- GENERIC FUNCTIONS ---------------------
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
lst
else
{}
end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
- Output:
2178309
Arendelle[edit]
( fibonacci , 1; 1 ) [ 98 , // 100 numbers of fibonacci ( fibonacci[ @fibonacci? ] , @fibonacci[ @fibonacci - 1 ] + @fibonacci[ @fibonacci - 2 ] ) "Index: | @fibonacci? | => | @fibonacci[ @fibonacci? - 1 ] |" ]
ARM Assembly[edit]
Expects to be called with in R0, and will return in the same register.
fibonacci:
push {r1-r3}
mov r1, #0
mov r2, #1
fibloop:
mov r3, r2
add r2, r1, r2
mov r1, r3
sub r0, r0, #1
cmp r0, #1
bne fibloop
mov r0, r2
pop {r1-r3}
mov pc, lrArnoldC[edit]
IT'S SHOWTIME
HEY CHRISTMAS TREE f1
YOU SET US UP @I LIED
TALK TO THE HAND f1
HEY CHRISTMAS TREE f2
YOU SET US UP @NO PROBLEMO
HEY CHRISTMAS TREE f3
YOU SET US UP @I LIED
STICK AROUND @NO PROBLEMO
GET TO THE CHOPPER f3
HERE IS MY INVITATION f1
GET UP f2
ENOUGH TALK
TALK TO THE HAND f3
GET TO THE CHOPPER f1
HERE IS MY INVITATION f2
ENOUGH TALK
GET TO THE CHOPPER f2
HERE IS MY INVITATION f3
ENOUGH TALK
CHILL
YOU HAVE BEEN TERMINATEDArturo[edit]
Recursive[edit]
fib: $[x][
if? x<2 [1]
else [(fib x-1) + (fib x-2)]
]
loop 1..25 [x][
print ["Fibonacci of" x "=" fib x]
]AsciiDots[edit]
/--#$--\
| |
>-*>{+}/
| \+-/
1 |
# 1
| #
| |
. .ATS[edit]
Recursive[edit]
fun fib_rec(n: int): int =
if n >= 2 then fib_rec(n-1) + fib_rec(n-2) else nIterative[edit]
(*
** This one is also referred to as being tail-recursive
*)
fun
fib_trec(n: int): int =
if
n > 0
then (fix loop (i:int, r0:int, r1:int): int => if i > 1 then loop (i-1, r1, r0+r1) else r1)(n, 0, 1)
else 0Iterative and Verified[edit]
(*
** This implementation is verified!
*)
dataprop FIB (int, int) =
| FIB0 (0, 0) | FIB1 (1, 1)
| {n:nat} {r0,r1:int} FIB2 (n+2, r0+r1) of (FIB (n, r0), FIB (n+1, r1))
// end of [FIB] // end of [dataprop]
fun
fibats{n:nat}
(n: int (n))
: [r:int] (FIB (n, r) | int r) = let
fun loop
{i:nat | i <= n}{r0,r1:int}
(
pf0: FIB (i, r0), pf1: FIB (i+1, r1)
| ni: int (n-i), r0: int r0, r1: int r1
) : [r:int] (FIB (n, r) | int r) =
if (ni > 0)
then loop{i+1}(pf1, FIB2 (pf0, pf1) | ni - 1, r1, r0 + r1)
else (pf0 | r0)
// end of [if]
// end of [loop]
in
loop {0} (FIB0 (), FIB1 () | n, 0, 1)
end // end of [fibats]Matrix-based[edit]
(* ****** ****** *)
//
// How to compile:
// patscc -o fib fib.dats
//
(* ****** ****** *)
//
#include
"share/atspre_staload.hats"
//
(* ****** ****** *)
//
abst@ype
int3_t0ype =
(int, int, int)
//
typedef int3 = int3_t0ype
//
(* ****** ****** *)
extern
fun int3 : (int, int, int) -<> int3
extern
fun int3_1 : int3 -<> int
extern
fun mul_int3_int3: (int3, int3) -<> int3
(* ****** ****** *)
local
assume
int3_t0ype = (int, int, int)
in (* in-of-local *)
//
implement
int3 (x, y, z) = @(x, y, z)
//
implement int3_1 (xyz) = xyz.1
//
implement
mul_int3_int3
(
@(a,b,c), @(d,e,f)
) =
(a*d + b*e, a*e + b*f, b*e + c*f)
//
end // end of [local]
(* ****** ****** *)
//
implement
gnumber_int<int3> (n) = int3(n, 0, n)
//
implement gmul_val<int3> = mul_int3_int3
//
(* ****** ****** *)
//
fun
fib (n: intGte(0)): int =
int3_1(gpow_int_val<int3> (n, int3(1, 1, 0)))
//
(* ****** ****** *)
implement
main0 () =
{
//
val N = 10
val () = println! ("fib(", N, ") = ", fib(N))
val N = 20
val () = println! ("fib(", N, ") = ", fib(N))
val N = 30
val () = println! ("fib(", N, ") = ", fib(N))
val N = 40
val () = println! ("fib(", N, ") = ", fib(N))
//
} (* end of [main0] *)AutoHotkey[edit]
Search autohotkey.com: sequence
Iterative[edit]
Loop, 5
MsgBox % fib(A_Index)
Return
fib(n)
{
If (n < 2)
Return n
i := last := this := 1
While (i <= n)
{
new := last + this
last := this
this := new
i++
}
Return this
}
Recursive and iterative[edit]
Source: AutoHotkey forum by Laszlo
/*
Important note: the recursive version would be very slow
without a global or static array. The iterative version
handles also negative arguments properly.
*/
FibR(n) { ; n-th Fibonacci number (n>=0, recursive with static array Fibo)
Static
Return n<2 ? n : Fibo%n% ? Fibo%n% : Fibo%n% := FibR(n-1)+FibR(n-2)
}
Fib(n) { ; n-th Fibonacci number (n < 0 OK, iterative)
a := 0, b := 1
Loop % abs(n)-1
c := b, b += a, a := c
Return n=0 ? 0 : n>0 || n&1 ? b : -b
}
AutoIt[edit]
Iterative[edit]
#AutoIt Version: 3.2.10.0
$n0 = 0
$n1 = 1
$n = 10
MsgBox (0,"Iterative Fibonacci ", it_febo($n0,$n1,$n))
Func it_febo($n_0,$n_1,$N)
$first = $n_0
$second = $n_1
$next = $first + $second
$febo = 0
For $i = 1 To $N-3
$first = $second
$second = $next
$next = $first + $second
Next
if $n==0 Then
$febo = 0
ElseIf $n==1 Then
$febo = $n_0
ElseIf $n==2 Then
$febo = $n_1
Else
$febo = $next
EndIf
Return $febo
EndFunc
Recursive[edit]
#AutoIt Version: 3.2.10.0
$n0 = 0
$n1 = 1
$n = 10
MsgBox (0,"Recursive Fibonacci ", rec_febo($n0,$n1,$n))
Func rec_febo($r_0,$r_1,$R)
if $R<3 Then
if $R==2 Then
Return $r_1
ElseIf $R==1 Then
Return $r_0
ElseIf $R==0 Then
Return 0
EndIf
Return $R
Else
Return rec_febo($r_0,$r_1,$R-1) + rec_febo($r_0,$r_1,$R-2)
EndIf
EndFunc
AWK[edit]
As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout.
$ awk 'func fib(n){return(n<2?n:fib(n-1)+fib(n-2))}{print "fib("$1")="fib($1)}'
10
fib(10)=55
Axe[edit]
A recursive solution is not practical in Axe because there is no concept of variable scope in Axe.
Iterative solution:
Lbl FIB
r₁→N
0→I
1→J
For(K,1,N)
I+J→T
J→I
T→J
End
J
ReturnBabel[edit]
In Babel, we can define fib using a stack-based approach that is not recursive:
fib { <- 0 1 { dup <- + -> swap } -> times zap } <foo x < puts x in foo. In this case, x is the code list between the curly-braces. This is how you define callable code in Babel. The definition works by initializing the stack with 0, 1. On each iteration of the times loop, the function duplicates the top element. In the first iteration, this gives 0, 1, 1. Then it moves down the stack with the <- operator, giving 0, 1 again. It adds, giving 1. then it moves back up the stack, giving 1, 1. Then it swaps. On the next iteration this gives:
1, 1, 1 (dup) 1, 1, (<-) 2 (+) 2, 1 (->) 1, 2 (swap)
And so on. To test fib:
{19 iter - fib !} 20 times collect ! lsnum !- Output:
( 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 )
bash[edit]
Iterative[edit]
$ fib=1;j=1;while((fib<100));do echo $fib;((k=fib+j,fib=j,j=k));done
1 1 2 3 5 8 13 21 34 55 89
Recursive[edit]
fib()
{
if [ $1 -le 0 ]
then
echo 0
return 0
fi
if [ $1 -le 2 ]
then
echo 1
else
a=$(fib $[$1-1])
b=$(fib $[$1-2])
echo $(($a+$b))
fi
}
BASIC[edit]
Applesoft BASIC[edit]
Same code as Commodore BASIC
Entering a value of N > 183, produces an error message:
?OVERFLOW ERROR IN 220
BASIC256[edit]
# Basic-256 ver 1.1.4
# iterative Fibonacci sequence
# Matches sequence A000045 in the OEIS, https://oeis.org/A000045/list
# Return the Nth Fibonacci number
input "N = ",f
limit = 500 # set upper limit - can be changed, removed
f = int(f)
if f > limit then f = limit
a = 0 : b = 1 : c = 0 : n = 0 # initial values
while n < f
print n + chr(9) + c # chr(9) = tab
a = b
b = c
c = a + b
n += 1
end while
print " "
print n + chr(9) + cBBC BASIC[edit]
PRINT FNfibonacci_r(1), FNfibonacci_i(1)
PRINT FNfibonacci_r(13), FNfibonacci_i(13)
PRINT FNfibonacci_r(26), FNfibonacci_i(26)
END
DEF FNfibonacci_r(N)
IF N < 2 THEN = N
= FNfibonacci_r(N-1) + FNfibonacci_r(N-2)
DEF FNfibonacci_i(N)
LOCAL F, I, P, T
IF N < 2 THEN = N
P = 1
FOR I = 1 TO N
T = F
F += P
P = T
NEXT
= F
- Output:
1 1
233 233
121393 121393
Chipmunk Basic[edit]
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[edit]
100 PRINT CHR$(147); CHR$(18); "**** FIBONACCI GENERATOR ****"
110 INPUT "MIN, MAX"; N1, N2
120 IF N1 > N2 THEN T = N1: N1 = N2: N2 = T
130 A = 0: B = 1: S = SGN(N1)
140 FOR I = S TO N1 STEP S
150 : IF S > 0 THEN T = A + B: A = B: B = T
160 : IF S < 0 THEN T = B - A: B = A: A = T
170 NEXT I
180 PRINT
190 PRINT STR$(A); : REM STR$() PREVENTS TRAILING SPACE
200 IF N2 = N1 THEN 250
210 FOR I = N1 + 1 TO N2
220 : T = A + B: A = B: B = T
230 : PRINT ","; STR$(A);
240 NEXT I
250 PRINT
- Output:
**** FIBONACCI GENERATOR **** MIN, MAX? -6,6 -8, 5,-3, 2,-1, 1, 0, 1, 1, 2, 3, 5, 8 READY.
Craft Basic[edit]
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
end
FreeBASIC[edit]
Extended sequence coded big integer.
'Fibonacci extended
'Freebasic version 24 Windows
Dim Shared ADDQmod(0 To 19) As Ubyte
Dim Shared ADDbool(0 To 19) As Ubyte
For z As Integer=0 To 19
ADDQmod(z)=(z Mod 10+48)
ADDbool(z)=(-(10<=z))
Next z
Function plusINT(NUM1 As String,NUM2 As String) As String
Dim As Byte flag
#macro finish()
three=Ltrim(three,"0")
If three="" Then Return "0"
If flag=1 Then Swap NUM2,NUM1
Return three
Exit Function
#endmacro
var lenf=Len(NUM1)
var lens=Len(NUM2)
If lens>lenf Then
Swap NUM2,NUM1
Swap lens,lenf
flag=1
End If
var diff=lenf-lens-Sgn(lenf-lens)
var three="0"+NUM1
var two=String(lenf-lens,"0")+NUM2
Dim As Integer n2
Dim As Ubyte addup,addcarry
addcarry=0
For n2=lenf-1 To diff Step -1
addup=two[n2]+NUM1[n2]-96
three[n2+1]=addQmod(addup+addcarry)
addcarry=addbool(addup+addcarry)
Next n2
If addcarry=0 Then
finish()
End If
If n2=-1 Then
three[0]=addcarry+48
finish()
End If
For n2=n2 To 0 Step -1
addup=two[n2]+NUM1[n2]-96
three[n2+1]=addQmod(addup+addcarry)
addcarry=addbool(addup+addcarry)
Next n2
three[0]=addcarry+48
finish()
End Function
Function fibonacci(n As Integer) As String
Dim As String sl,l,term
sl="0": l="1"
If n=1 Then Return "0"
If n=2 Then Return "1"
n=n-2
For x As Integer= 1 To n
term=plusINT(l,sl)
sl=l
l=term
Next x
Function =term
End Function
'============== EXAMPLE ===============
print "THE SEQUENCE TO 10:"
print
For n As Integer=1 To 10
Print "term";n;": "; fibonacci(n)
Next n
print
print "Selected Fibonacci number"
print "Fibonacci 500"
print
print fibonacci(500)
Sleep
- Output:
THE SEQUENCE TO 10: term 1: 0 term 2: 1 term 3: 1 term 4: 2 term 5: 3 term 6: 5 term 7: 8 term 8: 13 term 9: 21 term 10: 34 Selected Fibonacci number Fibonacci 500 86168291600238450732788312165664788095941068326060883324529903470149056115823592 713458328176574447204501
FTCBASIC[edit]
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[edit]
Iterative[edit]
window 1, @"Fibonacci Sequence", (0,0,480,620)
local fn Fibonacci( n as long ) as long
static long s1
static long s2
long temp
if ( n < 2 )
s1 = n
exit fn
else
temp = s1 + s2
s2 = s1
s1 = temp
exit fn
end if
end fn = s1
long i
CFTimeInterval t
t = fn CACurrentMediaTime
for i = 0 to 40
print i;@".\t";fn Fibonacci(i)
next i
print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000
HandleEventsOutput:
0. 0 1. 1 2. 1 3. 2 4. 3 5. 5 6. 8 7. 13 8. 21 9. 34 10. 55 11. 89 12. 144 13. 233 14. 377 15. 610 16. 987 17. 1597 18. 2584 19. 4181 20. 6765 21. 10946 22. 17711 23. 28657 24. 46368 25. 75025 26. 121393 27. 196418 28. 317811 29. 514229 30. 832040 31. 1346269 32. 2178309 33. 3524578 34. 5702887 35. 9227465 36. 14930352 37. 24157817 38. 39088169 39. 63245986 40. 102334155 Compute time: 2.143 ms
Recursive[edit]
Cost is a time penalty
local fn Fibonacci( n as NSInteger ) as NSInteger
NSInteger result
if n < 2 then result = n : exit fn
result = fn Fibonacci( n-1 ) + fn Fibonacci( n-2 )
end fn = result
window 1
NSInteger i
CFTimeInterval t
t = fn CACurrentMediaTime
for i = 0 to 40
print i;@".\t";fn Fibonacci(i)
next
print : printf @"Compute time: %.3f ms",(fn CACurrentMediaTime-t)*1000
HandleEvents- Output:
0. 0 1. 1 2. 1 3. 2 4. 3 5. 5 6. 8 7. 13 8. 21 9. 34 10. 55 11. 89 12. 144 13. 233 14. 377 15. 610 16. 987 17. 1597 18. 2584 19. 4181 20. 6765 21. 10946 22. 17711 23. 28657 24. 46368 25. 75025 26. 121393 27. 196418 28. 317811 29. 514229 30. 832040 31. 1346269 32. 2178309 33. 3524578 34. 5702887 35. 9227465 36. 14930352 37. 24157817 38. 39088169 39. 63245986 40. 102334155 Compute time: 2844.217 ms
GFA Basic[edit]
'
' Compute nth Fibonacci number
'
' open a window for display
OPENW 1
CLEARW 1
' Display some fibonacci numbers
' Fib(46) is the largest number GFA Basic can reach
' (long integers are 4 bytes)
FOR i%=0 TO 46
PRINT "fib(";i%;")=";@fib(i%)
NEXT i%
' wait for a key press and tidy up
~INP(2)
CLOSEW 1
'
' Function to compute nth fibonacci number
' n must be in range 0 to 46, inclusive
'
FUNCTION fib(n%)
LOCAL n0%,n1%,nn%,i%
n0%=0
n1%=1
SELECT n%
CASE 0
RETURN n0%
CASE 1
RETURN n1%
DEFAULT
FOR i%=2 TO n%
nn%=n0%+n1%
n0%=n1%
n1%=nn%
NEXT i%
RETURN nn%
ENDSELECT
ENDFUNC
GW-BASIC[edit]
Iterative[edit]
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[edit]
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[edit]
Only works with quite small values of .
10 INPUT N
20 A=0
30 B=1
40 FOR I=2 TO N
50 C=B
60 B=A+B
70 A=C
80 NEXT I
90 PRINT B
100 END
IS-BASIC[edit]
100 PROGRAM "Fibonac.bas"
110 FOR I=0 TO 20
120 PRINT "F";I,FIB(I)
130 NEXT
140 DEF FIB(N)
150 NUMERIC I
160 LET A=0:LET B=1
170 FOR I=1 TO N
180 LET T=A+B:LET A=B:LET B=T
190 NEXT
200 LET FIB=A
210 END DEFLiberty BASIC[edit]
Iterative/Recursive[edit]
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[edit]
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[edit]
Iterative[edit]
' 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[edit]
' 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[edit]
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[edit]
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[edit]
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[edit]
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
STATIC fibNum() 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 FUNCTIONPureBasic[edit]
Macro based calculation[edit]
Macro Fibonacci (n)
Int((Pow(((1+Sqr(5))/2),n)-Pow(((1-Sqr(5))/2),n))/Sqr(5))
EndMacro
Recursive[edit]
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[edit]
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[edit]
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[edit]
Iterative[edit]
FUNCTION itFib (n)
n1 = 0
n2 = 1
FOR k = 1 TO ABS(n)
sum = n1 + n2
n1 = n2
n2 = sum
NEXT k
IF n < 0 THEN
itFib = n1 * ((-1) ^ ((-n) + 1))
ELSE
itFib = n1
END IF
END FUNCTION
Next version calculates each value once, as needed, and stores the results in an array for later retreival (due to the use of REDIM PRESERVE, it requires QuickBASIC 4.5 or newer):
DECLARE FUNCTION fibonacci& (n AS INTEGER)
REDIM SHARED fibNum(1) AS LONG
fibNum(1) = 1
'*****sample inputs*****
PRINT fibonacci(0) 'no calculation needed
PRINT fibonacci(13) 'figure F(2)..F(13)
PRINT fibonacci(-42) 'figure F(14)..F(42)
PRINT fibonacci(47) 'error: too big
'*****sample inputs*****
FUNCTION fibonacci& (n AS INTEGER)
DIM a AS INTEGER
a = ABS(n)
SELECT CASE a
CASE 0 TO 46
SHARED fibNum() AS LONG
DIM u AS INTEGER, L0 AS INTEGER
u = UBOUND(fibNum)
IF a > u THEN
REDIM PRESERVE fibNum(a) AS LONG
FOR L0 = u + 1 TO a
fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
NEXT
END IF
IF n < 0 THEN
fibonacci = fibNum(a) * ((-1) ^ (a + 1))
ELSE
fibonacci = fibNum(n)
END IF
CASE ELSE
'limited to signed 32-bit int (LONG)
'F(47)=&hB11924E1
ERROR 6 'overflow
END SELECT
END FUNCTION
- Output:
0 233 -267914296
Recursive[edit]
This example can't handle n < 0.
FUNCTION recFib (n)
IF (n < 2) THEN
recFib = n
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF
END FUNCTION
Array (Table) Lookup[edit]
This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.)
DATA -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155
DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309
DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711
DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3
DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765
DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269
DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986
DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903
DIM fibNum(-46 TO 46) AS LONG
FOR n = -46 TO 46
READ fibNum(n)
NEXT
'*****sample inputs*****
FOR n = -46 TO 46
PRINT fibNum(n),
NEXT
PRINT
'*****sample inputs*****
Quite BASIC[edit]
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[edit]
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 functionS-BASIC[edit]
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[edit]
Analytic[edit]
10 INPUT N
20 PRINT INT (0.5+(((SQR 5+1)/2)**N)/SQR 5)
Iterative[edit]
10 INPUT N
20 LET A=0
30 LET B=1
40 FOR I=2 TO N
50 LET C=B
60 LET B=A+B
70 LET A=C
80 NEXT I
90 PRINT B
Tail recursive[edit]
10 INPUT N
20 LET A=0
30 LET B=1
40 GOSUB 70
50 PRINT B
60 STOP
70 IF N=1 THEN RETURN
80 LET C=B
90 LET B=A+B
100 LET A=C
110 LET N=N-1
120 GOSUB 70
130 RETURN
smart BASIC[edit]
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[edit]
Iterative[edit]
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[edit]
Sequence table[edit]
[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 144Iterative[edit]
{0,1
While 1
Disp Ans(1
{Ans(2),sum(Ans
EndBinet's formula[edit]
Prompt N
.5(1+√(5 //golden ratio
(Ans^N–(-Ans)^-N)/√(5TI-89 BASIC[edit]
Recursive[edit]
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[edit]
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
EndFuncTiny BASIC[edit]
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[edit]
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[edit]
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[edit]
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 FunctionWith Long type, maximum value is fibo(46).
VBScript[edit]
Non-recursive, object oriented, generator[edit]
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:[edit]
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:[edit]
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[edit]
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[edit]
Platform: .NET
Iterative[edit]
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[edit]
Function Seq(ByVal Term As Integer)
If Term < 2 Then Return Term
Return Seq(Term - 1) + Seq(Term - 2)
End Function
BigInteger[edit]
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[edit]
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[edit]
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[edit]
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 subZX Spectrum Basic[edit]
Iterative[edit]
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[edit]
10 DEF FN f(x)=INT (0.5+(((SQR 5+1)/2)^x)/SQR 5)
Batch File[edit]
Recursive version
::fibo.cmd
@echo off
if "%1" equ "" goto :eof
call :fib %1
echo %errorlevel%
goto :eof
:fib
setlocal enabledelayedexpansion
if %1 geq 2 goto :ge2
exit /b %1
:ge2
set /a r1 = %1 - 1
set /a r2 = %1 - 2
call :fib !r1!
set r1=%errorlevel%
call :fib !r2!
set r2=%errorlevel%
set /a r0 = r1 + r2
exit /b !r0!
- Output:
>for /L %i in (1,5,20) do fibo.cmd %i >fibo.cmd 1 1 >fibo.cmd 6 8 >fibo.cmd 11 89 >fibo.cmd 16 987
Battlestar[edit]
// Fibonacci sequence, recursive version
fun fibb
loop
a = funparam[0]
break (a < 2)
a--
// Save "a" while calling fibb
a -> stack
// Set the parameter and call fibb
funparam[0] = a
call fibb
// Handle the return value and restore "a"
b = funparam[0]
stack -> a
// Save "b" while calling fibb again
b -> stack
a--
// Set the parameter and call fibb
funparam[0] = a
call fibb
// Handle the return value and restore "b"
c = funparam[0]
stack -> b
// Sum the results
b += c
a = b
funparam[0] = a
break
end
end
// vim: set syntax=c ts=4 sw=4 et:
bc[edit]
iterative[edit]
#! /usr/bin/bc -q
define fib(x) {
if (x <= 0) return 0;
if (x == 1) return 1;
a = 0;
b = 1;
for (i = 1; i < x; i++) {
c = a+b; a = b; b = c;
}
return c;
}
fib(1000)
quit
BCPL[edit]
get "libhdr"
let fib(n) = n<=1 -> n, valof
$( let a=0 and b=1
for i=2 to n
$( let c=a
a := b
b := a+c
$)
resultis b
$)
let start() be
for i=0 to 10 do
writef("F_%N*T= %N*N", i, fib(i))- Output:
F_0 = 0 F_1 = 1 F_2 = 1 F_3 = 2 F_4 = 3 F_5 = 5 F_6 = 8 F_7 = 13 F_8 = 21 F_9 = 34 F_10 = 55
beeswax[edit]
#>'#{;
_`Enter n: `TN`Fib(`{`)=`X~P~K#{;
#>~P~L#MM@>+@'q@{;
b~@M<Example output:
Notice the UInt64 wrap-around at Fib(94)!
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i0
Fib(0)=0
Program finished!
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i10
Fib(10)=55
Program finished!
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i92
Fib(92)=7540113804746346429
Program finished!
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i93
Fib(93)=12200160415121876738
Program finished!
julia> beeswax("n-th Fibonacci number.bswx")
Enter n: i94
Fib(94)=1293530146158671551
Program finished!
Befunge[edit]
00:.1:.>:"@"8**++\1+:67+`#@_v
^ .:\/*8"@"\%*8"@":\ <
BlitzMax[edit]
local a:int = 0, b:int = 1, c:int = 1, n:int
n = int(input( "Enter n: "))
if n = 0 then
print 0
end
else if n = 1
print 1
end
end if
while n>2
a = b
b = c
c = a + b
n = n - 1
wend
print c
Blue[edit]
: fib ( nth:ecx -- result:edi ) 1 0
: compute ( times:ecx accum:eax scratch:edi -- result:edi ) xadd latest loop ;
: example ( -- ) 11 fib drop ;BQN[edit]
All given functions return the nth element in the sequence.
Recursive[edit]
A primitive recursive can be done with predicates:
Fib ← {𝕩>1 ? (𝕊 𝕩-1) + 𝕊 𝕩-2; 𝕩}Or, it can be done with the Choose(◶) modifier:
Fib2 ← {(𝕩-1) (𝕩>1)◶⟨𝕩, +○𝕊⟩ 𝕩-2}Iterative[edit]
An iterative solution can be made with the Repeat(⍟) modifier:
{⊑(+`⌽)⍟𝕩 0‿1}Bracmat[edit]
Recursive[edit]
fib=.!arg:<2|fib$(!arg+-2)+fib$(!arg+-1)fib$30 832040
Iterative[edit]
(fib=
last i this new
. !arg:<2
| 0:?last:?i
& 1:?this
& whl
' ( !i+1:<!arg:?i
& !last+!this:?new
& !this:?last
& !new:?this
)
& !this
)fib$777 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082
Brainf***[edit]
The first cell contains n (10), the second cell will contain fib(n) (55), and the third cell will contain fib(n-1) (34).
++++++++++
>>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]
The following generates n fibonacci numbers and prints them, though not in ascii. It does have a limit due to the cells usually being 1 byte in size.
+++++ +++++ #0 set to n
>> + Init #2 to 1
<<
[
- #Decrement counter in #0
>>. Notice: This doesn't print it in ascii
To look at results you can pipe into a file and look with a hex editor
Copying sequence to save #2 in #4 using #5 as restore space
>>[-] Move to #4 and clear
>[-] Clear #5
<<< #2
[ Move loop
- >> + > + <<< Subtract #2 and add #4 and #5
]
>>>
[ Restore loop
- <<< + >>> Subtract from #5 and add to #2
]
<<<< Back to #1
Non destructive add sequence using #3 as restore value
[ Loop to add
- > + > + << Subtract #1 and add to value #2 and restore space #3
]
>>
[ Loop to restore #1 from #3
- << + >> Subtract from restore space #3 and add in #1
]
<< [-] Clear #1
>>>
[ Loop to move #4 to #1
- <<< + >>> Subtract from #4 and add to #1
]
<<<< Back to #0
]
Brat[edit]
Recursive[edit]
fibonacci = { x |
true? x < 2, x, { fibonacci(x - 1) + fibonacci(x - 2) }
}Tail Recursive[edit]
fib_aux = { x, next, result |
true? x == 0,
result,
{ fib_aux x - 1, next + result, next }
}
fibonacci = { x |
fib_aux x, 1, 0
}Memoization[edit]
cache = hash.new
fibonacci = { x |
true? cache.key?(x)
{ cache[x] }
{true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}
}Burlesque[edit]
{0 1}{^^++[+[-^^-]\/}30.*\[e!vv0 1{{.+}c!}{1000.<}w!C[edit]
Recursive[edit]
long long fibb(long long a, long long b, int n) {
return (--n>0)?(fibb(b, a+b, n)):(a);
}
Iterative[edit]
long long int fibb(int n) {
int fnow = 0, fnext = 1, tempf;
while(--n>0){
tempf = fnow + fnext;
fnow = fnext;
fnext = tempf;
}
return fnext;
}
Analytic[edit]
#include <tgmath.h>
#define PHI ((1 + sqrt(5))/2)
long long unsigned fib(unsigned n) {
return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );
}
Generative[edit]
#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 *)λ iterator; bool lambda(i)
#define DO {
#define YIELD(x) if(!yield(x))return
#define BREAK return false
#define CONTINUE return true
#define OD CONTINUE; } }
static volatile void *yield_init; /* not thread safe */
#define YIELDS(type) bool (*yield)(type) = yield_init
iterator fibonacci(int stop){
YIELDS(int);
int f[] = {0, 1};
int i;
for(i=0; i<stop; i++){
YIELD(f[i%2]);
f[i%2]=f[0]+f[1];
}
}
main(){
printf("fibonacci: ");
FOR(int i, fibonacci(16)) DO
printf("%d, ",i);
OD;
printf("...\n");
}
- Output:
fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
Fast method for a single large value[edit]
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
typedef struct node node;
struct node {
int n;
mpz_t v;
node *next;
};
#define CSIZE 37
node *cache[CSIZE];
// very primitive linked hash table
node * find_cache(int n)
{
int idx = n % CSIZE;
node *p;
for (p = cache[idx]; p && p->n != n; p = p->next);
if (p) return p;
p = malloc(sizeof(node));
p->next = cache[idx];
cache[idx] = p;
if (n < 2) {
p->n = n;
mpz_init_set_ui(p->v, 1);
} else {
p->n = -1; // -1: value not computed yet
mpz_init(p->v);
}
return p;
}
mpz_t tmp1, tmp2;
mpz_t *fib(int n)
{
int x;
node *p = find_cache(n);
if (p->n < 0) {
p->n = n;
x = n / 2;
mpz_mul(tmp1, *fib(x-1), *fib(n - x - 1));
mpz_mul(tmp2, *fib(x), *fib(n - x));
mpz_add(p->v, tmp1, tmp2);
}
return &p->v;
}
int main(int argc, char **argv)
{
int i, n;
if (argc < 2) return 1;
mpz_init(tmp1);
mpz_init(tmp2);
for (i = 1; i < argc; i++) {
n = atoi(argv[i]);
if (n < 0) {
printf("bad input: %s\n", argv[i]);
continue;
}
// about 75% of time is spent in printing
gmp_printf("%Zd\n", *fib(n));
}
return 0;
}
- Output:
% ./a.out 0 1 2 3 4 5 1 1 2 3 5 8 % ./a.out 10000000 | wc -c # count length of output, including the newline 1919488
C#[edit]
Recursive[edit]
public static ulong Fib(uint n) {
return (n < 2)? n : Fib(n - 1) + Fib(n - 2);
}
Tail-Recursive[edit]
public static ulong Fib(uint n) {
return Fib(0, 1, n);
}
private static ulong Fib(ulong a, ulong b, uint n) {
return (n < 1)? a :(n == 1)? b : Fib(b, a + b, n - 1);
}
Iterative[edit]
public static ulong Fib(uint x) {
if (x == 0) return 0;
ulong prev = 0;
ulong next = 1;
for (int i = 1; i < x; i++)
{
ulong sum = prev + next;
prev = next;
next = sum;
}
return next;
}
Iterative[edit]
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[edit]
public static IEnumerable<long> Fibs(uint x) {
IList<ulong> fibs = new List<ulong>();
ulong prev = -1;
ulong next = 1;
for (int i = 0; i < x; i++)
{
long sum = prev + next;
prev = next;
next = sum;
fibs.Add(sum);
}
return fibs;
}
Lazy-Generative[edit]
public static IEnumerable<ulong> Fibs(uint x) {
ulong prev = -1;
ulong next = 1;
for (uint i = 0; i < x; i++) {
ulong sum = prev + next;
prev = next;
next = sum;
yield return sum;
}
}
Analytic[edit]
This returns digits up to the 93rd Fibonacci number, but the digits become inaccurate past the 71st. There is custom rounding applied to the result that allows the function to be accurate at the 71st number instead of topping out at the 70th.
static double r5 = Math.Sqrt(5.0), Phi = (r5 + 1.0) / 2.0;
static ulong fib(uint n) {
if (n > 71) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 72.");
double r = Math.Pow(Phi, n) / r5;
return (ulong)(n < 64 ? Math.Round(r) : Math.Floor(r)); }
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)); }
If one allows the fib() function to return the decimal type, one can reach the 138th Fibonacci number. However, the accuracy is lost after the 128th.
static decimal Sqrt_dec(decimal x, decimal g) { decimal t, lg;
do { t = x / g; lg = g; g = (t + g) / 2M; } while (lg != g);
return g; }
static decimal Pow_dec (decimal bas, uint exp) {
if (exp == 0) return 1M;
decimal tmp = Pow_dec(bas, exp >> 1); tmp *= tmp;
if ((exp & 1) == 1) tmp *= bas; return tmp; }
static decimal r5 = Sqrt_dec(5.0M, (decimal)Math.Sqrt(5.0)),
Phi = (r5 + 1.0M) / 2.0M;
static decimal fib(uint n) {
if (n > 128) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 129.");
decimal r = Pow_dec(Phi, n) / r5;
return n < 64 ? Math.Round(r) : Math.Floor(r); }
Matrix[edit]
Algorithm is based on
- .
Needs System.Windows.Media.Matrix or similar Matrix class.
Calculates in .
public static ulong Fib(uint n) {
var M = new Matrix(1,0,0,1);
var N = new Matrix(1,1,1,0);
for (uint i = 1; i < n; i++) M *= N;
return (ulong)M[0][0];
}
Needs System.Windows.Media.Matrix or similar Matrix class.
Calculates in .
private static Matrix M;
private static readonly Matrix N = new Matrix(1,1,1,0);
public static ulong Fib(uint n) {
M = new Matrix(1,0,0,1);
MatrixPow(n-1);
return (ulong)M[0][0];
}
private static void MatrixPow(double n){
if (n > 1) {
MatrixPow(n/2);
M *= M;
}
if (n % 2 == 0) M *= N;
}
Array (Table) Lookup[edit]
private static int[] fibs = new int[]{ -1836311903, 1134903170,
-701408733, 433494437, -267914296, 165580141, -102334155,
63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
3524578, -2178309, 1346269, -832040, 514229, -317811, 196418,
-121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181,
-2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13,
-8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
701408733, 1134903170, 1836311903};
public static int Fib(int n) {
if(n < -46 || n > 46) throw new ArgumentOutOfRangeException("n", n, "Has to be between -46 and 47.")
return fibs[n+46];
}
Arbitrary Precision[edit]
This large step recurrence routine can calculate the two millionth Fibonacci number in under 1 / 5 second at tio.run. This routine can generate the fifty millionth Fibonacci number in under 30 seconds at tio.run. The unused conventional iterative method times out at two million on tio.run, you can only go to around 1,290,000 or so to keep the calculation time (plus string conversion time) under the 60 second timeout limit there. When using this large step recurrence method, it takes around 5 seconds to convert the two millionth Fibonacci number (417975 digits) into a string (so that one may count those digits).
using System;
using System.Collections.Generic;
using BI = System.Numerics.BigInteger;
class Program
{
// A sparse array of values calculated along the way
static SortedList<int, BI> sl = new SortedList<int, BI>();
// This routine is semi-recursive, but doesn't need to evaluate every number up to n.
// Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
static BI Fsl(int n)
{
if (n < 2) return n;
int n2 = n >> 1, pm = n2 + ((n & 1) << 1) - 1; IfNec(n2); IfNec(pm);
return n2 > pm ? (2 * sl[pm] + sl[n2]) * sl[n2] : sqr(sl[n2]) + sqr(sl[pm]);
// Helper routine for Fsl(). It adds an entry to the sorted list when necessary
void IfNec(int x) { if (!sl.ContainsKey(x)) sl.Add(x, Fsl(x)); }
// Helper function to square a BigInteger
BI sqr(BI x) { return x * x; }
}
// Conventional iteration method (not used here)
public static BI Fm(BI n)
{
if (n < 2) return n; BI cur = 0, pre = 1;
for (int i = 0; i <= n - 1; i++) { BI sum = cur + pre; pre = cur; cur = sum; }
return cur;
}
public static void Main()
{
int num = 2_000_000, digs = 35, vlen;
var sw = System.Diagnostics.Stopwatch.StartNew(); var v = Fsl(num); sw.Stop();
Console.Write("{0:n3} ms to calculate the {1:n0}th Fibonacci number, ",
sw.Elapsed.TotalMilliseconds, num);
Console.WriteLine("number of digits is {0}", vlen = (int)Math.Ceiling(BI.Log10(v)));
if (vlen < 10000) {
sw.Restart(); Console.WriteLine(v); sw.Stop();
Console.WriteLine("{0:n3} ms to write it to the console.", sw.Elapsed.TotalMilliseconds);
} else
Console.Write("partial: {0}...{1}", v / BI.Pow(10, vlen - digs), v % BI.Pow(10, digs));
}
}
- Output:
137.209 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975 partial: 85312949175076415430516606545038251...91799493108960825129188777803453125
Shift PowerMod[edit]
Illustrated here is an algorithm to compute a Fibonacci number directly, without needing to calculate any of the Fibonacci numbers less than the desired result. It uses shifting and the power mod function (BigInteger.ModPow() in C#). It calculates more quickly than the large step recurrence routine (illustrated above) for smaller Fibonacci numbers (less than 2800 digits or so, around Fibonacci(13000)), but gets slower for larger ones, as the intermediate BigIntegers created are very large, much larger than the Fibonacci result.
Also included is a routine that returns an array of Fibonacci numbers (fibTab()). It reuses the intermediate large shifted BigIntegers on suceeding iterations, therfore it is a little more efficient than calling the oneshot (oneFib()) routine repeatedly from a loop.
using System;
using BI = System.Numerics.BigInteger;
class Program {
// returns the nth Fibonacci number without calculating 0..n-1
static BI oneFib(int n) {
BI z = (BI)1 << ++n;
return BI.ModPow(z, n, (z << n) - z - 1) % z;
}
// returns an array of Fibonacci numbers from the 0th to the nth
static BI[] fibTab(int n) {
var res = new BI[++n];
BI z = (BI)1 << 1, zz = z << 1;
for (int i = 0; i < n; ) {
res[i] = BI.ModPow(z, ++i, zz - z - 1) % z;
z <<= 1; zz <<= 2;
}
return res;
}
static void Main(string[] args) {
int n = 20;
Console.WriteLine("Fibonacci numbers 0..{0}: {1}", n, string.Join(" ",fibTab(n)));
n = 1000;
Console.WriteLine("Fibonacci({0}): {1}", n, oneFib(n));
}
}
- Output:
Fibonacci numbers 0..20: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 Fibonacci(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
C++[edit]
Using unsigned int, this version only works up to 48 before fib overflows.
#include <iostream>
int main()
{
unsigned int a = 1, b = 1;
unsigned int target = 48;
for(unsigned int n = 3; n <= target; ++n)
{
unsigned int fib = a + b;
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
return 0;
}
This version does not have an upper bound.
#include <iostream>
#include <gmpxx.h>
int main()
{
mpz_class a = mpz_class(1), b = mpz_class(1);
mpz_class target = mpz_class(100);
for(mpz_class n = mpz_class(3); n <= target; ++n)
{
mpz_class fib = b + a;
if ( fib < b )
{
std::cout << "Overflow at " << n << std::endl;
break;
}
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
return 0;
}
Version using transform:
#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0;
std::vector<int> v(n+1);
v[1] = 1;
transform(v.begin(), v.end()-2, v.begin()+1, v.begin()+2, std::plus<int>());
// "v" now contains the Fibonacci sequence from 0 up
return v[n];
}
Far-fetched version using adjacent_difference:
#include <numeric>
#include <vector>
#include <functional>
#include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0;
std::vector<int> v(n, 1);
adjacent_difference(v.begin(), v.end()-1, v.begin()+1, std::plus<int>());
// "array" now contains the Fibonacci sequence from 1 up
return v[n-1];
}
Version which computes at compile time with metaprogramming:
#include <iostream>
template <int n> struct fibo
{
enum {value=fibo<n-1>::value+fibo<n-2>::value};
};
template <> struct fibo<0>
{
enum {value=0};
};
template <> struct fibo<1>
{
enum {value=1};
};
int main(int argc, char const *argv[])
{
std::cout<<fibo<12>::value<<std::endl;
std::cout<<fibo<46>::value<<std::endl;
return 0;
}
The following version is based on fast exponentiation:
#include <iostream>
inline void fibmul(int* f, int* g)
{
int tmp = f[0]*g[0] + f[1]*g[1];
f[1] = f[0]*g[1] + f[1]*(g[0] + g[1]);
f[0] = tmp;
}
int fibonacci(int n)
{
int f[] = { 1, 0 };
int g[] = { 0, 1 };
while (n > 0)
{
if (n & 1) // n odd
{
fibmul(f, g);
--n;
}
else
{
fibmul(g, g);
n >>= 1;
}
}
return f[1];
}
int main()
{
for (int i = 0; i < 20; ++i)
std::cout << fibonacci(i) << " ";
std::cout << std::endl;
}
- Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Using Zeckendorf Numbers[edit]
The nth fibonacci is represented as Zeckendorf 1 followed by n-1 zeroes. Here I define a class N which defines the operations increment ++() and comparison <=(other N) for Zeckendorf Numbers.
// Use Zeckendorf numbers to display Fibonacci sequence.
// Nigel Galloway October 23rd., 2012
int main(void) {
char NG[22] = {'1',0};
int x = -1;
N G;
for (int fibs = 1; fibs <= 20; fibs++) {
for (;G <= N(NG); ++G) x++;
NG[fibs] = '0';
NG[fibs+1] = 0;
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
- Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
Using Standard Template Library[edit]
Possibly less "Far-fetched version".
// Use Standard Template Library to display Fibonacci sequence.
// Nigel Galloway March 30th., 2013
#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
int x = 1, y = 1;
generate_n(std::ostream_iterator<int>(std::cout, " "), 21, [&]{int n=x; x=y; y+=n; return n;});
return 0;
}
- Output:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
Cat[edit]
define fib {
dup 1 <=
[]
[dup 1 - fib swap 2 - fib +]
if
}Chapel[edit]
iter fib() {
var a = 0, b = 1;
while true {
yield a;
(a, b) = (b, b + a);
}
}
Chef[edit]
Stir-Fried Fibonacci Sequence.
An unobfuscated iterative implementation.
It prints the first N + 1 Fibonacci numbers,
where N is taken from standard input.
Ingredients.
0 g last
1 g this
0 g new
0 g input
Method.
Take input from refrigerator.
Put this into 4th mixing bowl.
Loop the input.
Clean the 3rd mixing bowl.
Put last into 3rd mixing bowl.
Add this into 3rd mixing bowl.
Fold new into 3rd mixing bowl.
Clean the 1st mixing bowl.
Put this into 1st mixing bowl.
Fold last into 1st mixing bowl.
Clean the 2nd mixing bowl.
Put new into 2nd mixing bowl.
Fold this into 2nd mixing bowl.
Put new into 4th mixing bowl.
Endloop input until looped.
Pour contents of the 4th mixing bowl into baking dish.
Serves 1.Clio[edit]
Clio is pure and functions are lazy and memoized by default
fn fib n:
if n < 2: n
else: (n - 1 -> fib) + (n - 2 -> fib)
[0:100] -> * fib -> * printClojure[edit]
Lazy Sequence[edit]
This is implemented idiomatically as an infinitely long, lazy sequence of all Fibonacci numbers:
(defn fibs []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
Thus to get the nth one:
(nth (fibs) 5)
So long as one does not hold onto the head of the sequence, this is unconstrained by length.
The one-line implementation may look confusing at first, but on pulling it apart it actually solves the problem more "directly" than a more explicit looping construct.
(defn fibs []
(map first ;; throw away the "metadata" (see below) to view just the fib numbers
(iterate ;; create an infinite sequence of [prev, curr] pairs
(fn [[a b]] ;; to produce the next pair, call this function on the current pair
[b (+ a b)]) ;; new prev is old curr, new curr is sum of both previous numbers
[0 1]))) ;; recursive base case: prev 0, curr 1
A more elegant solution is inspired by the Haskell implementation of an infinite list of Fibonacci numbers:
(def fib (lazy-cat [0 1] (map + fib (rest fib))))
Then, to see the first ten,
user> (take 10 fib)
(0 1 1 2 3 5 8 13 21 34)
Iterative[edit]
Here's a simple interative process (using a recursive function) that carries state along with it (as args) until it reaches a solution:
;; max is which fib number you'd like computed (0th, 1st, 2nd, etc.)
;; n is which fib number you're on for this call (0th, 1st, 2nd, etc.)
;; j is the nth fib number (ex. when n = 5, j = 5)
;; i is the nth - 1 fib number
(defn- fib-iter
[max n i j]
(if (= n max)
j
(recur max
(inc n)
j
(+ i j))))
(defn fib
[max]
(if (< max 2)
max
(fib-iter max 1 0N 1N)))
"defn-" means that the function is private (for use only inside this library). The "N" suffixes on integers tell Clojure to use arbitrary precision ints for those.
Doubling Algorithm (Fast)[edit]
Based upon the doubling algorithm which computes in O(log (n)) time as described here https://www.nayuki.io/page/fast-fibonacci-algorithms Implementation credit: https://stackoverflow.com/questions/27466311/how-to-implement-this-fast-doubling-fibonacci-algorithm-in-clojure/27466408#27466408
(defn fib [n]
(letfn [(fib* [n]
(if (zero? n)
[0 1]
(let [[a b] (fib* (quot n 2))
c (*' a (-' (*' 2 b) a))
d (+' (*' b b) (*' a a))]
(if (even? n)
[c d]
[d (+' c d)]))))]
(first (fib* n))))
Recursive[edit]
A naive slow recursive solution:
(defn fib [n]
(case n
0 0
1 1
(+ (fib (- n 1))
(fib (- n 2)))))
This can be improved to an O(n) solution, like the iterative solution, by memoizing the function so that numbers that have been computed are cached. Like a lazy sequence, this also has the advantage that subsequent calls to the function use previously cached results rather than recalculating.
(def fib
(memoize
(fn [n]
(case n
0 0
1 1
(+ (fib (- n 1))
(fib (- n 2)))))))
Using core.async[edit]
(ns fib.core)
(require '[clojure.core.async
:refer [<! >! >!! <!! timeout chan alt! go]])
(defn fib [c]
(loop [a 0 b 1]
(>!! c a)
(recur b (+ a b))))
(defn -main []
(let [c (chan)]
(go (fib c))
(dorun
(for [i (range 10)]
(println (<!! c))))))
CLU[edit]
% Generate Fibonacci numbers
fib = iter () yields (int)
a: int := 0
b: int := 1
while true do
yield (a)
a, b := b, a+b
end
end fib
% Grab the n'th value from an iterator
nth = proc [T: type] (g: itertype () yields (T), n: int) returns (T)
for v: T in g() do
if n<=0 then return (v) end
n := n-1
end
end nth
% Print a few values
start_up = proc ()
po: stream := stream$primary_output()
% print values coming out of the fibonacci iterator
% (which are generated one after the other without delay)
count: int := 0
for f: int in fib() do
stream$putl(po, "F(" || int$unparse(count) || ") = " || int$unparse(f))
count := count + 1
if count = 15 then break end
end
% print a few random fibonacci numbers
% (to do this it has to restart at the beginning for each
% number, making it O(N))
fibs: sequence[int] := sequence[int]$[20,30,50]
for n: int in sequence[int]$elements(fibs) do
stream$putl(po, "F(" || int$unparse(n) || ") = "
|| int$unparse(nth[int](fib, n)))
end
end start_up- Output:
F(0) = 0 F(1) = 1 F(2) = 1 F(3) = 2 F(4) = 3 F(5) = 5 F(6) = 8 F(7) = 13 F(8) = 21 F(9) = 34 F(10) = 55 F(11) = 89 F(12) = 144 F(13) = 233 F(14) = 377 F(20) = 6765 F(30) = 832040 F(50) = 12586269025
CMake[edit]
Iteration uses a while() loop. Memoization uses global properties.
set_property(GLOBAL PROPERTY fibonacci_0 0)
set_property(GLOBAL PROPERTY fibonacci_1 1)
set_property(GLOBAL PROPERTY fibonacci_next 2)
# var = nth number in Fibonacci sequence.
function(fibonacci var n)
# If the sequence is too short, compute more Fibonacci numbers.
get_property(next GLOBAL PROPERTY fibonacci_next)
if(NOT next GREATER ${n})
# a, b = last 2 Fibonacci numbers
math(EXPR i "${next} - 2")
get_property(a GLOBAL PROPERTY fibonacci_${i})
math(EXPR i "${next} - 1")
get_property(b GLOBAL PROPERTY fibonacci_${i})
while(NOT next GREATER ${n})
math(EXPR i "${a} + ${b}") # i = next Fibonacci number
set_property(GLOBAL PROPERTY fibonacci_${next} ${i})
set(a ${b})
set(b ${i})
math(EXPR next "${next} + 1")
endwhile()
set_property(GLOBAL PROPERTY fibonacci_next ${next})
endif()
get_property(answer GLOBAL PROPERTY fibonacci_${n})
set(${var} ${answer} PARENT_SCOPE)
endfunction(fibonacci)
# Test program: print 0th to 9th and 25th to 30th Fibonacci numbers.
set(s "")
foreach(i RANGE 0 9)
fibonacci(f ${i})
set(s "${s} ${f}")
endforeach(i)
set(s "${s} ... ")
foreach(i RANGE 25 30)
fibonacci(f ${i})
set(s "${s} ${f}")
endforeach(i)
message(${s})
0 1 1 2 3 5 8 13 21 34 ... 75025 121393 196418 317811 514229 832040
COBOL[edit]
Iterative[edit]
Program-ID. Fibonacci-Sequence.
Data Division.
Working-Storage Section.
01 FIBONACCI-PROCESSING.
05 FIBONACCI-NUMBER PIC 9(36) VALUE 0.
05 FIB-ONE PIC 9(36) VALUE 0.
05 FIB-TWO PIC 9(36) VALUE 1.
01 DESIRED-COUNT PIC 9(4).
01 FORMATTING.
05 INTERM-RESULT PIC Z(35)9.
05 FORMATTED-RESULT PIC X(36).
05 FORMATTED-SPACE PIC x(35).
Procedure Division.
000-START-PROGRAM.
Display "What place of the Fibonacci Sequence would you like (<173)? " with no advancing.
Accept DESIRED-COUNT.
If DESIRED-COUNT is less than 1
Stop run.
If DESIRED-COUNT is less than 2
Move FIBONACCI-NUMBER to INTERM-RESULT
Move INTERM-RESULT to FORMATTED-RESULT
Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT
Display FORMATTED-RESULT
Stop run.
Subtract 1 from DESIRED-COUNT.
Move FIBONACCI-NUMBER to INTERM-RESULT.
Move INTERM-RESULT to FORMATTED-RESULT.
Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT.
Display FORMATTED-RESULT.
Perform 100-COMPUTE-FIBONACCI until DESIRED-COUNT = zero.
Stop run.
100-COMPUTE-FIBONACCI.
Compute FIBONACCI-NUMBER = FIB-ONE + FIB-TWO.
Move FIB-TWO to FIB-ONE.
Move FIBONACCI-NUMBER to FIB-TWO.
Subtract 1 from DESIRED-COUNT.
Move FIBONACCI-NUMBER to INTERM-RESULT.
Move INTERM-RESULT to FORMATTED-RESULT.
Unstring FORMATTED-RESULT delimited by all spaces into FORMATTED-SPACE,FORMATTED-RESULT.
Display FORMATTED-RESULT.
Recursive[edit]
>>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci-main.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 num PIC 9(6) COMP.
01 fib-num PIC 9(6) COMP.
PROCEDURE DIVISION.
ACCEPT num
CALL "fibonacci" USING CONTENT num RETURNING fib-num
DISPLAY fib-num
.
END PROGRAM fibonacci-main.
IDENTIFICATION DIVISION.
PROGRAM-ID. fibonacci RECURSIVE.
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 1-before PIC 9(6) COMP.
01 2-before PIC 9(6) COMP.
LINKAGE SECTION.
01 num PIC 9(6) COMP.
01 fib-num PIC 9(6) COMP BASED.
PROCEDURE DIVISION USING num RETURNING fib-num.
ALLOCATE fib-num
EVALUATE num
WHEN 0
MOVE 0 TO fib-num
WHEN 1
MOVE 1 TO fib-num
WHEN OTHER
SUBTRACT 1 FROM num
CALL "fibonacci" USING CONTENT num RETURNING 1-before
SUBTRACT 1 FROM num
CALL "fibonacci" USING CONTENT num RETURNING 2-before
ADD 1-before TO 2-before GIVING fib-num
END-EVALUATE
.
END PROGRAM fibonacci.
CoffeeScript[edit]
Analytic[edit]
fib_ana = (n) ->
sqrt = Math.sqrt
phi = ((1 + sqrt(5))/2)
Math.round((Math.pow(phi, n)/sqrt(5)))
Iterative[edit]
fib_iter = (n) ->
return n if n < 2
[prev, curr] = [0, 1]
[prev, curr] = [curr, curr + prev] for i in [1..n]
curr
Recursive[edit]
fib_rec = (n) ->
if n < 2 then n else fib_rec(n-1) + fib_rec(n-2)
Comefrom0x10[edit]
Recursion is is not possible in Comefrom0x10.
Iterative[edit]
stop = 6
a = 1
i = 1 # start
a # print result
fib
comefrom if i is 1 # start
b = 1
comefrom fib # start of loop
i = i + 1
next_b = a + b
a = b
b = next_b
comefrom fib if i > stopCommon Lisp[edit]
Note that Common Lisp uses bignums, so this will never overflow.
Iterative[edit]
(defun fibonacci-iterative (n &aux (f0 0) (f1 1))
(case n
(0 f0)
(1 f1)
(t (loop for n from 2 to n
for a = f0 then b and b = f1 then result
for result = (+ a b)
finally (return result)))))
Simpler one:
(defun fibonacci (n)
(let ((a 0) (b 1) (c n))
(loop for i from 2 to n do
(setq c (+ a b)
a b
b c))
c))
for var = loop:(loop for x = 0 then y and y = 1 then (+ x y) do (print x))
Recursive[edit]
(defun fibonacci-recursive (n)
(if (< n 2)
n
(+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))
(defun fibonacci-tail-recursive ( n &optional (a 0) (b 1))
(if (= n 0)
a
(fibonacci-tail-recursive (- n 1) b (+ a b))))
Tail recursive and squaring:
(defun fib (n &optional (a 1) (b 0) (p 0) (q 1))
(if (= n 1) (+ (* b p) (* a q))
(fib (ash n -1)
(if (evenp n) a (+ (* b q) (* a (+ p q))))
(if (evenp n) b (+ (* b p) (* a q)))
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))))) ;p is Fib(2^n-1), q is Fib(2^n).
(print (fib 100000))
Alternate solution[edit]
I use Allegro CL 10.1
;; Project : Fibonacci sequence
(defun fibonacci (nr)
(cond ((= nr 0) 1)
((= nr 1) 1)
(t (+ (fibonacci (- nr 1))
(fibonacci (- nr 2))))))
(format t "~a" "First 10 Fibonacci numbers")
(dotimes (n 10)
(if (< n 1) (terpri))
(if (< n 9) (format t "~a" " "))
(write(+ n 1)) (format t "~a" ": ")
(write (fibonacci n)) (terpri))
Output:
First 10 Fibonacci numbers 1: 1 2: 1 3: 2 4: 3 5: 5 6: 8 7: 13 8: 21 9: 34 10: 55
Solution with methods and eql specializers[edit]
(defmethod fib (n)
(declare ((integer 0 *) n))
(+ (fib (- n 1))
(fib (- n 2))))
(defmethod fib ((n (eql 0))) 0)
(defmethod fib ((n (eql 1))) 1)
List-based iterative[edit]
This solution uses a list to keep track of the Fibonacci sequence for 0 or a positive integer.
(defun fibo (n)
(cond ((< n 0) nil)
((< n 2) n)
(t (let ((leo '(1 0)))
(loop for i from 2 upto n do
(setf leo (cons (+ (first leo)
(second leo))
leo))
finally (return (first leo)))))))
- Output:
> (fibo 0) 0 > (fibo 1) 1 > (fibo 10) 55 > (fibo 100) 354224848179261915075 > (fibo 1000) 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 > (fibo -10) NIL
List-based recursive[edit]
This solution computes Fibonacci numbers as either:
- a list starting from the first element;
- a single number;
- an interval from i-th to j-th element.
Options #2 and #3 can take negative parameters,
but i (lowest index in range) must be greater
than j (highest index in range).
Values are represented internally by a reversed list that grows from the head (and that's why we reverse it back when we return it).
(defparameter *fibo-start* '(1 1)) ; elements 1 and 2
;;; Helper functions
(defun grow-fibo (fibo)
(cons (+ (first fibo) (second fibo)) fibo))
(defun generate-fibo (fibo n) ; n must be > 1
(if (equal (list-length fibo) n)
fibo
(generate-fibo (grow-fibo fibo) n)))
;;; User functions
(defun fibo (n)
(cond ((= n 0) 0)
((= (abs n) 1) 1)
(t (let ((result (first (generate-fibo *fibo-start* (abs n)))))
(if (and (< n -1) (evenp n))
(- result)
result)))))
(defun fibo-list (n)
(cond ((< n 1) nil)
((= n 1) '(1))
(t (reverse (generate-fibo *fibo-start* n)))))
(defun fibo-range (lower upper)
(if (<= upper lower)
nil
(reverse (generate-fibo
(list
(fibo (1+ lower))
(fibo lower))
(1+ (- upper lower))))))
- Output:
> (fibo 100) 354224848179261915075 > (fibo -150) -9969216677189303386214405760200 > (fibo-list 20) (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765) > (fibo-range -10 15) (-55 34 -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610) > (fibo-range 0 20) (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
Computer/zero Assembly[edit]
To find the th Fibonacci number, set the initial value of count equal to –2 and run the program. The machine will halt with the answer stored in the accumulator. Since Computer/zero's word length is only eight bits, the program will not work with values of greater than 13.
loop: LDA y ; higher No.
STA temp
ADD x ; lower No.
STA y
LDA temp
STA x
LDA count
SUB one
BRZ done
STA count
JMP loop
done: LDA y
STP
one: 1
count: 8 ; n = 10
x: 1
y: 1
temp: 0Coq[edit]
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[edit]
print Fibonacci Sequence:
var previous = 1
var number = 0
var temp = (blank)
:fib
if number > 50000000000:kill
print (number)
set temp = (add number previous)
set previous = (number)
set number = (temp)
goto fib
:kill
stopCowgol[edit]
include "cowgol.coh";
sub fibonacci(n: uint32): (a: uint32) is
a := 0;
var b: uint32 := 1;
while n > 0 loop
var c := a + b;
a := b;
b := c;
n := n - 1;
end loop;
end sub;
# test
var i: uint32 := 0;
while i < 20 loop
print_i32(fibonacci(i));
print_char(' ');
i := i + 1;
end loop;
print_nl();- Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Crystal[edit]
Recursive[edit]
def fib(n)
n < 2 ? n : fib(n - 1) + fib(n - 2)
end
Iterative[edit]
def fibIterative(n, prevFib = 0, fib = 1)
return n if n < 2
n.times do
prevFib, fib = fib, prevFib + fib
end
prevFib
end
Tail Recursive[edit]
def fibTailRecursive(n, prevFib = 0, fib = 1)
n == 0 ? prevFib : fibTailRecursive(n - 1, fib, prevFib + fib)
end
Analytic[edit]
def fibBinet(n)
(((5 ** 0.5 + 1) / 2) ** n / 5 ** 0.5).round.to_i
end
D[edit]
Here are four versions of Fibonacci Number calculating functions. FibD has an argument limit of magnitude 84 due to floating point precision, the others have a limit of 92 due to overflow (long).The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results. A Fibonacci Number generating function is added. All functions have support for negative arguments.
import std.stdio, std.conv, std.algorithm, std.math;
long sgn(alias unsignedFib)(int n) { // break sign manipulation apart
immutable uint m = (n >= 0) ? n : -n;
if (n < 0 && (n % 2 == 0))
return -unsignedFib(m);
else
return unsignedFib(m);
}
long fibD(uint m) { // Direct Calculation, correct for abs(m) <= 84
enum sqrt5r = 1.0L / sqrt(5.0L); // 1 / sqrt(5)
enum golden = (1.0L + sqrt(5.0L)) / 2.0L; // (1 + sqrt(5)) / 2
return roundTo!long(pow(golden, m) * sqrt5r);
}
long fibI(in uint m) pure nothrow { // Iterative
long thisFib = 0;
long nextFib = 1;
foreach (i; 0 .. m) {
long tmp = nextFib;
nextFib += thisFib;
thisFib = tmp;
}
return thisFib;
}
long fibR(uint m) { // Recursive
return (m < 2) ? m : fibR(m - 1) + fibR(m - 2);
}
long fibM(uint m) { // memoized Recursive
static long[] fib = [0, 1];
while (m >= fib.length )
fib ~= fibM(m - 2) + fibM(m - 1);
return fib[m];
}
alias sgn!fibD sfibD;
alias sgn!fibI sfibI;
alias sgn!fibR sfibR;
alias sgn!fibM sfibM;
auto fibG(in int m) { // generator(?)
immutable int sign = (m < 0) ? -1 : 1;
long yield;
return new class {
final int opApply(int delegate(ref int, ref long) dg) {
int idx = -sign; // prepare for pre-increment
foreach (f; this)
if (dg(idx += sign, f))
break;
return 0;
}
final int opApply(int delegate(ref long) dg) {
long f0, f1 = 1;
foreach (p; 0 .. m * sign + 1) {
if (sign == -1 && (p % 2 == 0))
yield = -f0;
else
yield = f0;
if (dg(yield)) break;
auto temp = f1;
f1 = f0 + f1;
f0 = temp;
}
return 0;
}
};
}
void main(in string[] args) {
int k = args.length > 1 ? to!int(args[1]) : 10;
writefln("Fib(%3d) = ", k);
writefln("D : %20d <- %20d + %20d",
sfibD(k), sfibD(k - 1), sfibD(k - 2));
writefln("I : %20d <- %20d + %20d",
sfibI(k), sfibI(k - 1), sfibI(k - 2));
if (abs(k) < 36 || args.length > 2)
// set a limit for recursive version
writefln("R : %20d <- %20d + %20d",
sfibR(k), sfibM(k - 1), sfibM(k - 2));
writefln("O : %20d <- %20d + %20d",
sfibM(k), sfibM(k - 1), sfibM(k - 2));
foreach (i, f; fibG(-9))
writef("%d:%d | ", i, f);
}
- Output:
Fib( 85) = D : 259695496911122586 <- 160500643816367088 + 99194853094755497 I : 259695496911122585 <- 160500643816367088 + 99194853094755497 O : 259695496911122585 <- 160500643816367088 + 99194853094755497 0:0 | -1:1 | -2:-1 | -3:2 | -4:-3 | -5:5 | -6:-8 | -7:13 | -8:-21 | -9:34 |
Matrix Exponentiation Version[edit]
import std.bigint;
T fibonacciMatrix(T=BigInt)(size_t n) {
int[size_t.sizeof * 8] binDigits;
size_t nBinDigits;
while (n > 0) {
binDigits[nBinDigits] = n % 2;
n /= 2;
nBinDigits++;
}
T x=1, y, z=1;
foreach_reverse (b; binDigits[0 .. nBinDigits]) {
if (b) {
x = (x + z) * y;
y = y ^^ 2 + z ^^ 2;
} else {
auto x_old = x;
x = x ^^ 2 + y ^^ 2;
y = (x_old + z) * y;
}
z = x + y;
}
return y;
}
void main() {
10_000_000.fibonacciMatrix;
}
Faster Version[edit]
For N = 10_000_000 this is about twice faster (run-time about 2.20 seconds) than the matrix exponentiation version.
import std.bigint, std.math;
// Algorithm from: Takahashi, Daisuke,
// "A fast algorithm for computing large Fibonacci numbers".
// Information Processing Letters 75.6 (30 November 2000): 243-246.
// Implementation from:
// pythonista.wordpress.com/2008/07/03/pure-python-fibonacci-numbers
BigInt fibonacci(in ulong n)
in {
assert(n > 0, "fibonacci(n): n must be > 0.");
} body {
if (n <= 2)
return 1.BigInt;
BigInt F = 1;
BigInt L = 1;
int sign = -1;
immutable uint n2 = cast(uint)n.log2.floor;
auto mask = 2.BigInt ^^ (n2 - 1);
foreach (immutable i; 1 .. n2) {
auto temp = F ^^ 2;
F = (F + L) / 2;
F = 2 * F ^^ 2 - 3 * temp - 2 * sign;
L = 5 * temp + 2 * sign;
sign = 1;
if (n & mask) {
temp = F;
F = (F + L) / 2;
L = F + 2 * temp;
sign = -1;
}
mask /= 2;
}
if ((n & mask) == 0) {
F *= L;
} else {
F = (F + L) / 2;
F = F * L - sign;
}
return F;
}
void main() {
10_000_000.fibonacci;
}
Dart[edit]
int fib(int n) {
if (n==0 || n==1) {
return n;
}
var prev=1;
var current=1;
for (var i=2; i<n; i++) {
var next = prev + current;
prev = current;
current = next;
}
return current;
}
int fibRec(int n) => n==0 || n==1 ? n : fibRec(n-1) + fibRec(n-2);
main() {
print(fib(11));
print(fibRec(11));
}
Datalog[edit]
Simple recurive implementation for Souffle.
.decl Fib(i:number, x:number)
Fib(0, 0).
Fib(1, 1).
Fib(i+2,x+y) :- Fib(i+1, x), Fib(i, y), i+2<=40, i+2>=2.
Fib(i-2,y-x) :- Fib(i-1, x), Fib(i, y), i-2>=-40, i-2<0.DBL[edit]
;
; Fibonacci sequence for DBL version 4 by Dario B.
;
RECORD
FIB1, D10
FIB2, D10
FIBN, D10
J, D5
A2, A2
A5, A5
PROC
;----------------------------------------------------------------
XCALL FLAGS (0007000000,1) ;Suppress STOP message
OPEN (1,O,'TT:')
DISPLAY (1,'First 10 Fibonacci Numbers:',10)
FIB2=1
FOR J=1 UNTIL 10
DO BEGIN
FIBN=FIB1+FIB2
A2=J,'ZX'
A5=FIBN,'ZZZZX'
DISPLAY (1,A2,' : ',A5,10)
FIB1=FIB2
FIB2=FIBN
END
CLOSE 1
END
Dc[edit]
This needs a modern Dc with r (swap) and # (comment).
It easily can be adapted to an older Dc, but it will impact readability a lot.
[ # todo: n(<2) -- 1 and break 2 levels
d - # 0
1 + # 1
q
] s1
[ # todo: n(>-1) -- F(n)
d 0=1 # n(!=0)
d 1=1 # n(!in {0,1})
2 - d 1 + # (n-2) (n-1)
lF x # (n-2) F(n-1)
r # F(n-1) (n-2)
lF x # F(n-1)+F(n-2)
+
] sF
33 lF x f- Output:
5702887
Delphi[edit]
Iterative[edit]
function FibonacciI(N: Word): UInt64;
var
Last, New: UInt64;
I: Word;
begin
if N < 2 then
Result := N
else begin
Last := 0;
Result := 1;
for I := 2 to N do
begin
New := Last + Result;
Last := Result;
Result := New;
end;
end;
end;
Recursive[edit]
function Fibonacci(N: Word): UInt64;
begin
if N < 2 then
Result := N
else
Result := Fibonacci(N - 1) + Fibonacci(N - 2);
end;
Matrix[edit]
Algorithm is based on
- .
function fib(n: Int64): Int64;
type TFibMat = array[0..1] of array[0..1] of Int64;
function FibMatMul(a,b: TFibMat): TFibMat;
var i,j,k: integer;
tmp: TFibMat;
begin
for i := 0 to 1 do
for j := 0 to 1 do
begin
tmp[i,j] := 0;
for k := 0 to 1 do tmp[i,j] := tmp[i,j] + a[i,k] * b[k,j];
end;
FibMatMul := tmp;
end;
function FibMatExp(a: TFibMat; n: Int64): TFibmat;
begin
if n <= 1 then fibmatexp := a
else if (n mod 2 = 0) then FibMatExp := FibMatExp(FibMatMul(a,a), n div 2)
else if (n mod 2 = 1) then FibMatExp := FibMatMul(a, FibMatExp(FibMatMul(a,a), n div 2));
end;
var
matrix: TFibMat;
begin
matrix[0,0] := 1;
matrix[0,1] := 1;
matrix[1,0] := 1;
matrix[1,1] := 0;
if n > 1 then
matrix := fibmatexp(matrix,n-1);
fib := matrix[0,0];
end;
DIBOL-11[edit]
START ;First 10 Fibonacci NUmbers
RECORD
FIB1, D10, 0
FIB2, D10, 1
FIBNEW, D10
LOOPCNT, D2, 1
RECORD HEADER
, A32, "First 10 Fibonacci Numbers."
RECORD OUTPUT
LOOPOUT, A2
, A3, " : "
FIBOUT, A10
PROC
OPEN(8,O,'TT:')
WRITES(8,HEADER)
LOOP,
FIBNEW = FIB1 + FIB2
LOOPOUT = LOOPCNT, 'ZX'
FIBOUT = FIBNEW, 'ZZZZZZZZZX'
WRITES(8,OUTPUT)
FIB1 = FIB2
FIB2 = FIBNEW
LOOPCNT = LOOPCNT + 1
IF LOOPCNT .LE. 10 GOTO LOOP
CLOSE 8
ENDDWScript[edit]
function fib(N : Integer) : Integer;
begin
if N < 2 then Result := 1
else Result := fib(N-2) + fib(N-1);
End;
Dyalect[edit]
func fib(n) {
if n < 2 {
return n
} else {
return fib(n - 1) + fib(n - 2)
}
}
print(fib(30))E[edit]
def fib(n) {
var s := [0, 1]
for _ in 0..!n {
def [a, b] := s
s := [b, a+b]
}
return s[0]
}(This version defines fib(0) = 0 because OEIS A000045 does.)
EasyLang[edit]
proc fib n . res .
if n < 2
res = n
.
prev = 0
val = 1
for _ = 0 to n - 2
res = prev + val
prev = val
val = res
.
.
call fib 36 r
print r
Recursive (inefficient):
proc fib n . res .
if n < 2
res = n
else
call fib n - 1 a
call fib n - 2 b
res = a + b
.
.
call fib 36 r
print r
EchoLisp[edit]
Use memoization with the recursive version.
(define (fib n)
(if (< n 2) n
(+ (fib (- n 2)) (fib (1- n)))))
(remember 'fib #(0 1))
(for ((i 12)) (write (fib i)))
0 1 1 2 3 5 8 13 21 34 55 89
ECL[edit]
Analytic[edit]
//Calculates Fibonacci sequence up to n steps using Binet's closed form solution
FibFunction(UNSIGNED2 n) := FUNCTION
REAL Sqrt5 := Sqrt(5);
REAL Phi := (1+Sqrt(5))/2;
REAL Phi_Inv := 1/Phi;
UNSIGNED FibValue := ROUND( ( POWER(Phi,n)-POWER(Phi_Inv,n) ) /Sqrt5);
RETURN FibValue;
END;
FibSeries(UNSIGNED2 n) := FUNCTION
Fib_Layout := RECORD
UNSIGNED5 FibNum;
UNSIGNED5 FibValue;
END;
FibSeq := DATASET(n+1,
TRANSFORM
( Fib_Layout
, SELF.FibNum := COUNTER-1
, SELF.FibValue := IF(SELF.FibNum<2,SELF.FibNum, FibFunction(SELF.FibNum) )
)
);
RETURN FibSeq;
END; }
EDSAC order code[edit]
This program calculates the nth—by default the tenth—number in the Fibonacci sequence and displays it (in binary) in the first word of storage tank 3.
[ Fibonacci sequence
==================
A program for the EDSAC
Calculates the nth Fibonacci
number and displays it at the
top of storage tank 3
The default value of n is 10
To calculate other Fibonacci
numbers, set the starting value
of the count to n-2
Works with Initial Orders 2 ]
T56K [ set load point ]
GK [ set theta ]
[ Orders ]
[ 0 ] T20@ [ a = 0 ]
A17@ [ a += y ]
U18@ [ temp = a ]
A16@ [ a += x ]
T17@ [ y = a; a = 0 ]
A18@ [ a += temp ]
T16@ [ x = a; a = 0 ]
A19@ [ a = count ]
S15@ [ a -= 1 ]
U19@ [ count = a ]
E@ [ if a>=0 go to θ ]
T20@ [ a = 0 ]
A17@ [ a += y ]
T96F [ C(96) = a; a = 0]
ZF [ halt ]
[ Data ]
[ 15 ] P0D [ const: 1 ]
[ 16 ] P0F [ var: x = 0 ]
[ 17 ] P0D [ var: y = 1 ]
[ 18 ] P0F [ var: temp = 0 ]
[ 19 ] P4F [ var: count = 8 ]
[ 20 ] P0F [ used to clear a ]
EZPF [ begin execution ]- Output:
00000000000110111
Eiffel[edit]
class
APPLICATION
create
make
feature
fibonacci (n: INTEGER): INTEGER
require
non_negative: n >= 0
local
i, n2, n1, tmp: INTEGER
do
n2 := 0