Fibonacci sequence
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2, if n>1
Write a function to generate the nth Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). Support for negative n is optional.
References:
[edit] ActionScript
public function fib(n:uint):uint
{
if (n < 2)
return n;
return fib(n - 1) + fib(n - 2);
}
[edit] AppleScript
set fibs to {}
set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3"))
set x to x as 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
[edit] Ada
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;
Sample output:
0 1 1 2 3 5 8 13 21 34 55
[edit] ALGOL 68
[edit] Analytic
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC analytic fibonacci = (LONG INT n)LONG INT:(
LONG REAL sqrt 5 = long sqrt(5);
LONG REAL p = (1 + sqrt 5) / 2;
LONG REAL q = 1/p;
ENTIER( (p**n + q**n) / sqrt 5 )
);
[edit] Iterative
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC iterative fibonacci = (INT n)INT:
CASE n+1 IN
0, 1, 1, 2, 3, 5
OUT
INT even:=3, odd:=5;
FOR i FROM odd+1 TO n DO
(ODD i|odd|even) := odd + even
OD;
(ODD n|odd|even)
ESAC;
FOR i FROM 0 TO 30 WHILE
print(whole(iterative fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)
Output:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
[edit] Recursive
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
PROC recursive fibonacci = (INT n)INT:
( n < 2 | n | fib(n-1) + fib(n-2));
[edit] Generative
Translation of: Python - note: This specimen retains the original Python coding style.
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
MODE YIELDINT = PROC(INT)VOID;
PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (
INT even:=0, odd:=1;
yield(even);
yield(odd);
FOR i FROM odd+1 TO n DO
yield( (ODD i|odd|even) := odd + even )
OD
);
main:(
# FOR INT n IN # gen fibonacci(30, # ) DO ( #
## (INT n)VOID:(
print((" ",whole(n,0)))
# OD # ));
print(new line)
)
Output:
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
[edit] Array (Table) Lookup
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
This uses a pre-generated list, requiring much less run-time processor usage, but assumes that INT is only 31 bits wide.
[]INT const fibonacci = []INT( -1836311903, 1134903170,
-701408733, 433494437, -267914296, 165580141, -102334155,
63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
3524578, -2178309, 1346269, -832040, 514229, -317811, 196418,
-121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181,
-2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13,
-8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
701408733, 1134903170, 1836311903
)[@-46];
PROC VOID value error := stop;
PROC lookup fibonacci = (INT i)INT: (
IF LWB const fibonacci <= i AND i<= UPB const fibonacci THEN
const fibonacci[i]
ELSE
value error; SKIP
FI
);
FOR i FROM 0 TO 30 WHILE
print(whole(lookup fibonacci(i),0));
# WHILE # i /= 30 DO
print(", ")
OD;
print(new line)
Output:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
[edit] AutoHotkey
Search autohotkey.com: sequence
[edit] Iterative
Translation of: C
Loop, 5
MsgBox % fib(A_Index)
Return
fib(n)
{
If (n < 2)
Return n
i := last := this := 1
While (i <= n)
{
new := last + this
last := this
this := new
i++
}
Return this
}
[edit] Recursive and iterative
Source: AutoHotkey forum by Laszlo
/*
Important note: the recursive version would be very slow
without a global or static array. The iterative version
handles also negative arguments properly.
*/
FibR(n) { ; n-th Fibonacci number (n>=0, recursive with static array Fibo)
Static
Return n<2 ? n : Fibo%n% ? Fibo%n% : Fibo%n% := FibR(n-1)+FibR(n-2)
}
Fib(n) { ; n-th Fibonacci number (n < 0 OK, iterative)
a := 0, b := 1
Loop % abs(n)-1
c := b, b += a, a := c
Return n=0 ? 0 : n>0 || n&1 ? b : -b
}
[edit] AWK
As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout.
$ awk 'func fib(n){return(n<2?n:fib(n-1)+fib(n-2))}{print "fib("$1")="fib($1)}'
10
fib(10)=55
[edit] BASIC
Works with: QBasic
Works with: FreeBASIC
[edit] Iterative
FUNCTION itFib (n)
n1 = 0
n2 = 1
FOR k = 1 TO ABS(n)
sum = n1 + n2
n1 = n2
n2 = sum
NEXT k
IF n < 0 THEN
itFib = n1 * ((-1) ^ ((-n) + 1))
ELSE
itFib = n1
END IF
END FUNCTION
This 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
Outputs (unhandled error in final input prevents output):
0 233 -267914296
[edit] Recursive
This example can't handle n < 0.
FUNCTION recFib (n)
IF (n < 2) THEN
recFib = n
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF
END FUNCTION
[edit] Array (Table) Lookup
This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.)
DATA -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155
DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309
DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711
DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3
DATA 2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765
DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269
DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986
DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903
DIM fibNum(-46 TO 46) AS LONG
FOR n = -46 TO 46
READ fibNum(n)
NEXT
'*****sample inputs*****
FOR n = -46 TO 46
PRINT fibNum(n),
NEXT
'*****sample inputs*****
[edit] Batch File
Recursive version
::fibo.cmd
@echo off
if "%1" equ "" goto :eof
call :fib %1
echo %errorlevel%
goto :eof
:fib
setlocal enabledelayedexpansion
if %1 geq 2 goto :ge2
exit /b %1
:ge2
set /a r1 = %1 - 1
set /a r2 = %1 - 2
call :fib !r1!
set r1=%errorlevel%
call :fib !r2!
set r2=%errorlevel%
set /a r0 = r1 + r2
exit /b !r0!
Output:
>for /L %i in (1,5,20) do fibo.cmd %i >fibo.cmd 1 1 >fibo.cmd 6 8 >fibo.cmd 11 89 >fibo.cmd 16 987
[edit] bc
[edit] iterative
#! /usr/bin/bc -q
define fib(x) {
if (x <= 0) return 0;
if (x == 1) return 1;
a = 0;
b = 1;
for (i = 1; i < x; i++) {
c = a+b; a = b; b = c;
}
return c;
}
fib(1000)
quit
[edit] Befunge
00:.1:.>:"@"8**++\1+:67+`#@_v
^ .:\/*8"@"\%*8"@":\ <
[edit] Brainf***
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
]
[edit] C
[edit] Recursive
long long unsigned fib(unsigned n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
[edit] Iterative
long long unsigned fib(unsigned n) {
long long unsigned last = 0, this = 1, new, i;
if (n < 2) return n;
for (i = 1 ; i < n ; ++i) {
new = last + this;
last = this;
this = new;
}
return this;
}
[edit] Analytic
#include <tgmath.h>
#define PHI ((1 + sqrt(5))/2)
long long unsigned fib(unsigned n) {
return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );
}
[edit] Generative
Translation of: Python
Works with: gcc version version 4.1.2 20080704 (Red Hat 4.1.2-44)
#include <stdio.h>
typedef enum{false=0, true=!0} bool;
typedef void iterator;
#include <setjmp.h>
/* declare label otherwise it is not visible in sub-scope */
#define LABEL(label) jmp_buf label; if(setjmp(label))goto label;
#define GOTO(label) longjmp(label, true)
/* the following line is the only time I have ever required "auto" */
#define FOR(i, iterator) { auto bool lambda(i); yield_init = (void *)λ 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, ...
[edit] C++
Using unsigned int, this version only works up to 48 before fib overflows.
#include <iostream>
int main()
{
unsigned int a = 1, b = 1;
unsigned int target = 48;
for(unsigned int n = 3; n <= target; ++n)
{
unsigned int fib = a + b;
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
return 0;
}
Library: GMP This version does not have an upper bound.
#include <iostream>
#include <gmpxx.h>
int main()
{
mpz_class a = mpz_class(1), b = mpz_class(1);
mpz_class target = mpz_class(100);
for(mpz_class n = mpz_class(3); n <= target; ++n)
{
mpz_class fib = b + a;
if ( fib < b )
{
std::cout << "Overflow at " << n << std::endl;
break;
}
std::cout << "F("<< n << ") = " << fib << std::endl;
a = b;
b = fib;
}
return 0;
}
Version using transform:
#include <algorithm>
#include <functional>
#include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0;
int *array = new int[n+1];
array[0] = 0;
array[1] = 1;
std::transform(array, array+n-1, array+1, array+2, std::plus<int>());
// "array" now contains the Fibonacci sequence from 0 up
int result = array[n];
delete [] array;
return result;
}
Far-fetched version using adjacent_difference:
#include <numeric>
#include <functional>
#include <iostream>
unsigned int fibonacci(unsigned int n) {
if (n == 0) return 0;
int *array = new int[n];
array[0] = 1;
std::adjacent_difference(array, array+n-1, array+1, std::plus<int>());
// "array" now contains the Fibonacci sequence from 1 up
int result = array[n-1];
delete [] array;
return result;
}
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;
}
[edit] C#
[edit] Recursive
static long recFib(int n) {
if (n < 2) return n;
return recFib(n - 1) + recFib(n - 2);
}
[edit] Cat
define fib {
dup 1 <=
[]
[dup 1 - fib swap 2 - fib +]
if
}
[edit] Chef
Stir-Fried Fibonacci Sequence.
An unobfuscated iterative implementation.
It prints the first N + 1 Fibonacci numbers,
where N is taken from standard input.
Ingredients.
0 g last
1 g this
0 g new
0 g input
Method.
Take input from refrigerator.
Put this into 4th mixing bowl.
Loop the input.
Clean the 3rd mixing bowl.
Put last into 3rd mixing bowl.
Add this into 3rd mixing bowl.
Fold new into 3rd mixing bowl.
Clean the 1st mixing bowl.
Put this into 1st mixing bowl.
Fold last into 1st mixing bowl.
Clean the 2nd mixing bowl.
Put new into 2nd mixing bowl.
Fold this into 2nd mixing bowl.
Put new into 4th mixing bowl.
Endloop input until looped.
Pour contents of the 4th mixing bowl into baking dish.
Serves 1.
[edit] Clojure
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.
[edit] Common Lisp
Note that Common Lisp uses bignums, so this will never overflow.
(defun fibonacci-recursive (n)
(if (< n 2)
n
(+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))
(defun fibonacci-iterative (n)
(if (< n 2)
n
(let ((result 0)
(a 1)
(b 1))
(loop for n from (- n 2) downto 1
do (setq result (+ a b)
a b
b result))
result)))
(defun fibonacci-dynamic-recursive ( n &optional (a 0) (b 1))
(if (= n 0)
b
(fibonacci-dynamic-recursive (- n 1) b (+ a b))))
[edit] D
Here are four versions of Fibonacci Number generating functions.
FibD has an argument limit of magnitude 82 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.
All four functions have support for negative arguments.
module fibonacci ;
import std.stdio ;
import std.math ;
import std.conv ;
long FibD(int m) { // Direct Calculation, correct for abs(m) <= 82
const real sqrt5r = 0.44721359549995793928L ; // 1 / sqrt(5)
const real golden = 1.6180339887498948482L ; // (1 + sqrt(5)) / 2 ;
real sign = (m < 0) && (1 & m ^ 1) ? -1.0L : 1.0L ;
return rndtol(pow(golden, abs(m)) * sign * sqrt5r) ;
}
long FibI(int m) { // Iterative
int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
int n = m < 0 ? -m : m ;
if (n < 2)
return n ;
long prevFib = 0 ;
long thisFib = 1 ;
for(int i = 1 ; i < n ;i++) {
long tmp = thisFib ;
thisFib += prevFib ;
prevFib = tmp ;
}
return thisFib*sign ;
}
long FibR(int m) { // Recursive
if (m == 0 || m == 1) return m ;
return (m >= 0) ? FibR(m-1) + FibR(m-2) : (1 & m ^ 1) ? - FibR(-m) : FibR(-m) ;
}
long FibO(int m) { // Optimized Recursive
static long[] fib = [0,1] ;
int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
int n = m < 0 ? -m : m ;
if(n >= fib.length )
fib ~= FibO(n-2) + FibO(n-1) ;
return fib[n]*sign ;
}
void main(string[] args) {
int k = args.length > 1 ? toInt(args[1]) : 10 ;
writefln("Fib(%3d) = ", k) ;
writefln("D : %20d <- %20d + %20d", FibD(k), FibD(k - 1), FibD(k - 2) ) ;
writefln("I : %20d <- %20d + %20d", FibI(k), FibI(k - 1), FibI(k - 2) ) ;
if( abs(k) < 36 || args.length > 2) // set a limit for recursive version
writefln("R : %20d <- %20d + %20d", FibR(k), FibO(k - 1), FibO(k - 2) ) ;
writefln("O : %20d <- %20d + %20d", FibO(k), FibO(k - 1), FibO(k - 2) ) ;
}
Output for n = 83:
Fib( 83) = D : 99194853094755496 <- 61305790721611591 + 37889062373143906 I : 99194853094755497 <- 61305790721611591 + 37889062373143906 O : 99194853094755497 <- 61305790721611591 + 37889062373143906
[edit] E
def fib(n) {
var s := [0, 1]
for _ in 0..!n {
def [a, b] := s
s := [b, a+b]
}
return s[0]
}
(This version defines fib(0) = 0 because OEIS A000045 does.)
[edit] Erlang
Recursive:
fib(0) -> 0;
fib(1) -> 1;
fib(N) when N > 1 -> fib(N-1) + fib(N-2).
Tail-recursive (iterative):
fib(N) -> fib(N,0,1).
fib(0,Res,_) -> Res;
fib(N,Res,Next) when N > 0 -> fib(N-1, Next, Res+Next).
[edit] FALSE
[0 1[@$][1-@@\$@@+\]#%%]f:
[edit] Factor
[edit] Iterative
: fib ( n -- m )
dup 2 < [
[ 0 1 ] dip [ swap [ + ] keep ] times
drop
] unless ;
[edit] Recursive
: fib ( n -- m )
dup 2 < [
[ 1 - fib ] [ 2 - fib ] bi +
] unless ;
[edit] Matrix
Translation of: Ruby
USE: math.matrices
: fib ( n -- m )
dup 2 < [
[ { { 0 1 } { 1 1 } } ] dip 1 - m^n
second second
] unless ;
[edit] Fancy
def class Number {
def fib {
self == 0 if_true: {
0
} else: {
self == 1 if_true: {
1
} else: {
self - 1 fib + (self - 2 fib)
}
}
}
};
# example usage:
15 times: |x| {
x fib println
}
[edit] Falcon
[edit] Iterative
function fib_i(n)
if n < 2: return n
fibPrev = 1
fib = 1
for i in [2:n]
tmp = fib
fib += fibPrev
fibPrev = tmp
end
return fib
end
[edit] Recursive
function fib_r(n)
if n < 2 : return n
return fib_r(n-1) + fib_r(n-2)
end
[edit] Tail Recursive
function fib_tr(n)
return fib_aux(n,0,1)
end
function fib_aux(n,a,b)
switch n
case 0 : return a
default: return fib_aux(n-1,a+b,a)
end
end
[edit] Forth
: fib ( n -- fib )
0 1 rot 0 ?do over + swap loop drop ;
[edit] Fortran
[edit] Recursive
In ISO Fortran 90 or later, use a RECURSIVE function:
module fibonacci
contains
recursive function fibR(n) result(fib)
integer, intent(in) :: n
integer :: fib
select case (n)
case (:0); fib = 0
case (1); fib = 1
case default; fib = fibR(n-1) + fibR(n-2)
end select
end function fibR
[edit] Iterative
In ISO Fortran 90 or later:
function fibI(n)
integer, intent(in) :: n
integer, parameter :: fib0 = 0, fib1 = 1
integer :: fibI, back1, back2, i
select case (n)
case (:0); fibI = fib0
case (1); fibI = fib1
case default
fibI = fib1
back1 = fib0
do i = 2, n
back2 = back1
back1 = fibI
fibI = back1 + back2
end do
end select
end function fibI
end module fibonacci
Test program
program fibTest
use fibonacci
do i = 0, 10
print *, fibr(i), fibi(i)
end do
end program fibTest
Output
0 0 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55
[edit] F#
This is a fast [tail-recursive] approach using the F# big integer support.
#light
open Microsoft.FSharp.Math
let fibonacci n : bigint =
let rec f a b n =
match n with
| 0I -> a
| 1I -> b
| n -> (f b (a + b) (n - 1I))
f 0I 1I n
> fibonacci 100I ;;
val it : bigint = 354224848179261915075I
Lazy evaluated using sequence
let rec fib = seq { yield! [0;1];
for (a,b) in Seq.zip fib (Seq.skip 1 fib) -> a+b}
[edit] Go
[edit] Recursive
func fib(a int) int {
if a < 2 {
return a
}
return fib(a - 1) + fib(a - 2)
}
[edit] Groovy
[edit] Recursive
A recursive closure must be pre-declared.
def rFib
rFib = { it < 1 ? 0 : it == 1 ? 1 : rFib(it-1) + rFib(it-2) }
[edit] Iterative
def iFib = { it < 1 ? 0 : it == 1 ? 1 : (2..it).inject([0,1]){i, j -> [i[1], i[0]+i[1]]}[1] }
Test program:
(0..20).each { println "${it}: ${rFib(it)} ${iFib(it)}" }
Output:
0: 0 0 1: 1 1 2: 1 1 3: 2 2 4: 3 3 5: 5 5 6: 8 8 7: 13 13 8: 21 21 9: 34 34 10: 55 55 11: 89 89 12: 144 144 13: 233 233 14: 377 377 15: 610 610 16: 987 987 17: 1597 1597 18: 2584 2584 19: 4181 4181 20: 6765 6765
[edit] HaXe
[edit] Iterative
static function fib(steps:Int, handler:Int->Void)
{
var current = 0;
var next = 1;
for (i in 1...steps)
{
handler(current);
var temp = current + next;
current = next;
next = temp;
}
handler(current);
}
[edit] As Iterator
class FibIter
{
public var current:Int;
private var nextItem:Int;
private var limit:Int;
public function new(limit) {
current = 0;
nextItem = 1;
this.limit = limit;
}
public function hasNext() return limit > 0
public function next() {
limit--;
var ret = current;
var temp = current + nextItem;
current = nextItem;
nextItem = temp;
return ret;
}
}
Used like:
for (i in new FibIter(10))
Lib.println(i);
[edit] Haskell
[edit] With lazy lists
This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:
fib = 0 : 1 : zipWith (+) fib (tail fib)
The nth Fibonacci number is then just fib !! n.
[edit] With matrix exponentiation
With the (rather slow) code from Matrix exponentiation operator
import Data.List
xs <+> ys = zipWith (+) xs ys
xs <*> ys = sum $ zipWith (*) xs ys
newtype Mat a = Mat {unMat :: [[a]]} deriving Eq
instance Show a => Show (Mat a) where
show xm = "Mat " ++ show (unMat xm)
instance Num a => Num (Mat a) where
negate xm = Mat $ map (map negate) $ unMat xm
xm + ym = Mat $ zipWith (<+>) (unMat xm) (unMat ym)
xm * ym = Mat [[xs <*> ys | ys <- transpose $ unMat ym] | xs <- unMat xm]
fromInteger n = Mat [[fromInteger n]]
we can simply write
fib 0 = 0 -- this line is necessary because "something ^ 0" returns "fromInteger 1", which unfortunately
-- in our case is not our multiplicative identity (the identity matrix) but just a 1x1 matrix of 1
fib n = last $ head $ unMat $ (Mat [[1,1],[1,0]]) ^ n
So, for example, the hundred-thousandth Fibonacci number starts with the digits
*Main> take 10 $ show $ fib (10^5) "2597406934"
[edit] Hope
[edit] Recursive
dec f : num -> num;
--- f 0 <= 0;
--- f 1 <= 1;
--- f(n+2) <= f n + f(n+1);
[edit] Tail-recursive
dec fib : num -> num;
--- fib n <= l (1, 0, n)
whererec l == \(a,b,succ c) => if c<1 then a else l((a+b),a,c)
|(a,b,0) => 0;
[edit] With lazy lists
This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers:
dec fibs : list num;
--- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs);
The nth Fibonacci number is then just fibs @ n.
[edit] HicEst
REAL :: Fibonacci(10)
Fibonacci = ($==2) + Fibonacci($-1) + Fibonacci($-2)
WRITE(ClipBoard) Fibonacci ! 0 1 1 2 3 5 8 13 21 34
[edit] Icon and Unicon
[edit] Icon
Icon has built-in support for big numbers. First, a simple recursive solution augmented by caching for non-negative input. This examples computes fib(1000) if there is no integer argument.
procedure main(args)
write(fib(integer(!args) | 1000)
end
procedure fib(n)
static fCache
initial {
fCache := table()
fCache[0] := 0
fCache[1] := 1
}
/fCache[n] := fib(n-1) + fib(n-2)
return fCache[n]
end
Library: Icon Programming Library The above solution is similar to the one provided fib in memrfncs
Now, an O(logN) solution. For large N, it takes far longer to convert the result to a string for output than to do the actual computation. This example computes fib(1000000) if there is no integer argument.
procedure main(args)
write(fib(integer(!args) | 1000000))
end
procedure fib(n)
return fibMat(n)[1]
end
procedure fibMat(n)
if n <= 0 then return [0,0]
if n = 1 then return [1,0]
fp := fibMat(n/2)
c := fp[1]*fp[1] + fp[2]*fp[2]
d := fp[1]*(fp[1]+2*fp[2])
if n%2 = 1 then return [c+d, d]
else return [d, c]
end
[edit] Unicon
This Icon solution works in Unicon.
[edit] IDL
[edit] Recursive
function fib,n
if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)
end
Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo.
[edit] Iterative
function fib,n
psum = (csum = 1uL)
if n lt 3 then return,csum
for i = 3,n do begin
nsum = psum + csum
psum = csum
csum = nsum
endfor
return,nsum
end
Execution time O(n). Limited by size of uLong to fib(49)
[edit] Analytic
function fib,n
q=1/( p=(1+sqrt(5))/2 )
return,round((p^n+q^n)/sqrt(5))
end
Execution time O(1), only limited by the range of LongInts to fib(48).
[edit] J
The Fibonacci Sequence essay on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number. Here is one:
fibN=: (-&2 +&$: -&1)^:(1&<) M.
Examples:
fibN 12
144
fibN"0 >:i.30
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
[edit] Java
[edit] Iterative
public static long itFibN(int n){
if(n < 2)return n;
long ans = 0;
long n1 = 0;
long n2 = 1;
for(n--;n > 0;n--){
ans = n1 + n2;
n1 = n2;
n2 = ans;
}
return ans;
}
[edit] Recursive
public static long recFibN(int n){
if(n < 2) return n;
return recFibN(n-1) + recFibN(n-2);
}
[edit] Analytic
This method works up to the 92nd Fibonacci number. After that, it goes out of range.
public static long anFibN(long n){
double p= (1 + Math.sqrt(5)) / 2;
double q= 1 / p;
return (long)((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5));
}
[edit] Tail-recursive
public static long fibTailRec(int n) {
return fibInner(0, 1, n);
}
private static long fibInner(long a, long b, int n) {
if (n < 1) {
return a;
} else if (n == 1) {
return b;
} else {
return fibInner(b, a + b, n - 1);
}
}
[edit] JavaScript
[edit] Recursive
One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion:
function fib(n) {
return function(n,a,b) {
return n>0 ? arguments.callee(n-1,b,a+b) : a;
}(n,0,1);
}
[edit] Iterative
function fib(n) {
var a=0, b=1, t;
while (n-- > 0) {
t = a;
a = b;
b += t;
}
return a;
}
for (var i=0; i<10; ++i) alert(fib(i));
[edit] Joy
[edit] Recursive
DEFINE fib == [small]
[]
[pred dup pred]
[+]
binrec .
[edit] Iterative
DEFINE f == [1 0] dip [swap [+] unary] times popd .
[edit] Lisaac
- fib(n : UINTEGER_32) : UINTEGER_64 <- (
+ result : UINTEGER_64;
(n < 2).if {
result := n;
} else {
result := fib(n - 1) + fib(n - 2);
};
result
);
[edit] Logo
to fib :n [:a 0] [:b 1]
if :n < 1 [output :a]
output (fib :n-1 :b :a+:b)
end
[edit] Lua
--calculates the nth fibonacci number. Breaks for negative or non-integer n.
function fibs(n)
return n < 2 and n or fibs(n - 1) + fibs(n - 2)
end
--more pedantic version, returns 0 for non-integer n
function pfibs(n)
if n ~= math.floor(n) then return 0
elseif n < 0 then return pfibs(n + 2) - pfibs(n + 1)
elseif n < 2 then return n
else return pfibs(n - 1) + pfibs(n - 2)
end
end
--tail-recursive
function tfibs(i)
return (function a(n, u, s) return a(n-1,u+s,u) end)(i,1,0)
end
--table-recursive
fib_n = setmetatable({1, 1}, {__index = function(z,n) return z[n-1] + z[n-2] end})
[edit] M4
define(`fibo',`ifelse(0,$1,0,`ifelse(1,$1,1,
`eval(fibo(decr($1)) + fibo(decr(decr($1))))')')')dnl
define(`loop',`ifelse($1,$2,,`$3($1) loop(incr($1),$2,`$3')')')dnl
loop(0,15,`fibo')
[edit] Mathematica
Mathematica already has a built-in function Fibonacci, but a simple recursive implementation would be
fib[0] = 0
fib[1] = 1
fib[n_Integer] := fib[n - 1] + fib[n - 2]
An optimization is to cache the values already calculated:
fib[0] = 0
fib[1] = 1
fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]
[edit] MAXScript
[edit] Iterative
fn fibIter n =
(
if n < 2 then
(
n
)
else
(
fib = 1
fibPrev = 1
for num in 3 to n do
(
temp = fib
fib += fibPrev
fibPrev = temp
)
fib
)
)
[edit] Recursive
fn fibRec n =
(
if n < 2 then
(
n
)
else
(
fibRec (n - 1) + fibRec (n - 2)
)
)
[edit] Metafont
vardef fibo(expr n) =
if n=0: 0
elseif n=1: 1
else:
fibo(n-1) + fibo(n-2)
fi
enddef;
for i=0 upto 10: show fibo(i); endfor
end
[edit] Modula-3
[edit] Recursive
PROCEDURE Fib(n: INTEGER): INTEGER =
BEGIN
IF n < 2 THEN
RETURN n;
ELSE
RETURN Fib(n-1) + Fib(n-2);
END;
END Fib;
[edit] MUMPS
[edit] Iterative
FIBOITER(N)
;Iterative version to get the Nth Fibonacci number
;N must be a positive integer
;F is the tree containing the values
;I is a loop variable.
QUIT:(N\1'=N)!(N<0) "Error: "_N_" is not a positive integer."
NEW F,I
SET F(0)=0,F(1)=1
QUIT:N<2 F(N)
FOR I=2:1:N SET F(I)=F(I-1)+F(I-2)
QUIT F(N)
USER>W $$FIBOITER^ROSETTA(30) 832040
[edit] NewLISP
[edit] Recursive
(define (fibonacci n)
(if (< n 2) 1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
(print(fibonacci 10)) ;;89
[edit] Nimrod
[edit] Analytic
proc Fibonacci(n: int): int64 =
var fn = float64(n)
var p: float64 = (1.0 + sqrt(5.0)) / 2.0
var q: float64 = 1.0 / p
return int64((pow(p, fn) + pow(q, fn)) / sqrt(5.0))
[edit] Iterative
proc Fibonacci(n: int): int64 =
var first: int64 = 0
var second: int64 = 1
var t: int64 = 0
while n > 1:
t = first + second
first = second
second = t
dec(n)
result = second
[edit] Recursive
proc Fibonacci(n: int): int64 =
if n <= 2:
result = 1
else:
result = Fibonacci(n - 1) + Fibonacci(n - 2)
[edit] Tail-recursive
proc Fibonacci(n: int, current: int64, next: int64): int64 =
if n == 0:
result = current
else:
result = Fibonacci(n - 1, next, current + next)
proc Fibonacci(n: int): int64 =
result = Fibonacci(n, 0, 1)
[edit] Objeck
[edit] Recursive
bundle Default {
class Fib {
function : Main(args : String[]), Nil {
for(i := 0; i <= 10; i += 1;) {
Fib(i)->PrintLine();
};
}
function : native : Fib(n : Int), Int {
if(n < 2) {
return n;
};
return Fib(n-1) + Fib(n-2);
}
}
}
[edit] OCaml
[edit] Iterative
let fib_iter n =
if n < 2 then
n
else let fib_prev = ref 1
and fib = ref 1 in
for num = 2 to n - 1 do
let temp = !fib in
fib := !fib + !fib_prev;
fib_prev := temp
done;
!fib
[edit] Recursive
let rec fib_rec n =
if n < 2 then
n
else
fib_rec (n - 1) + fib_rec (n - 2)
The previous way is the naive form, because for most n the fib_rec is called twice, and it is not tail recursive because it adds the result of two function calls. The next version resolves these problems:
let fib n =
let rec fib_aux n a b =
match n with
| 0 -> a
| _ -> fib_aux (n-1) (a+b) a
in
fib_aux n 0 1
[edit] Arbitrary Precision
Using OCaml's Num module.
open Num
let fib n =
let rec fib_aux f0 f1 count =
match count with
| 0 -> f0
| 1 -> f1
| _ -> fib_aux f1 (f1 +/ f0) (count - 1)
in
fib_aux (num_of_int 0) (num_of_int 1) n
compile with:
ocamlopt nums.cmxa -o fib fib.ml
[edit] Octave
Recursive
% recursive
function fibo = recfibo(n)
if ( n < 2 )
fibo = n;
else
fibo = recfibo(n-1) + recfibo(n-2);
endif
endfunction
Iterative
% iterative
function fibo = iterfibo(n)
if ( n < 2 )
fibo = n;
else
f = zeros(2,1);
f(1) = 0;
f(2) = 1;
for i = 2 : n
t = f(2);
f(2) = f(1) + f(2);
f(1) = t;
endfor
fibo = f(2);
endif
endfunction
Testing
% testing
for i = 0 : 20
printf("%d %d\n", iterfibo(i), recfibo(i));
endfor
[edit] Oz
[edit] Iterative
Using mutable references (cells).
fun{FibI N}
Temp = {NewCell 0}
A = {NewCell 0}
B = {NewCell 1}
in
for I in 1..N do
Temp := @A + @B
A := @B
B := @Temp
end
@A
end
[edit] Recursive
Inefficient (blows up the stack).
fun{FibR N}
if N < 2 then N
else {FibR N-1} + {FibR N-2}
end
end
[edit] Tail-recursive
Using accumulators.
fun{Fib N}
fun{Loop N A B}
if N == 0 then
B
else
{Loop N-1 A+B A}
end
end
in
{Loop N 1 0}
end
[edit] Lazy-recursive
declare
fun lazy {FiboSeq}
{LazyMap
{Iterate fun {$ [A B]} [B A+B] end [0 1]}
Head}
end
fun {Head A|_} A end
fun lazy {Iterate F I}
I|{Iterate F {F I}}
end
fun lazy {LazyMap Xs F}
case Xs of X|Xr then {F X}|{LazyMap Xr F}
[] nil then nil
end
end
in
{Show {List.take {FiboSeq} 8}}
[edit] Pascal
[edit] Recursive
function fib(n: integer): integer;
begin
if (n = 0) or (n = 1)
then
fib := n
else
fib := fib(n-1) + fib(n-2)
end;
[edit] Iterative
function fib(n: integer): integer;
var
f0, f1, fm1, k: integer;
begin
f0 := 0;
fm1 := 1;
for k := 1 to n do
begin
f1:= fm1 + f0;
fm1 := f0;
f0 := f1
end;
fib := f0
end;
[edit] Perl
[edit] Iterative
sub fibIter {
my $n = shift;
if ($n < 2) {
return $n;
}
my $fibPrev = 1;
my $fib = 1;
for (2..$n-1) {
($fibPrev, $fib) = ($fib, $fib + $fibPrev);
}
return $fib;
}
[edit] Recursive
sub fibRec {
my $n = shift;
return $n <= 2 ? 1 : fibRec($n-1) + fibRec($n-2);
}
[edit] Perl 6
Works with: Rakudo version #21 "Seattle"
[edit] Iterative
sub fib (Int $n --> Int) {
$n > 2 or return 1;
my ($prev, $this) = 1, 1;
$prev, $this = $this, $this + $prev for 2 ..^ $n;
return $this;
}
[edit] Recursive
multi fib (Int $n where { $n < 3 }) { 1 }
multi fib (Int $n) { fib($n - 1) + fib($n - 2) }
[edit] Analytic
sub fib (Int $n --> Int) {
constant φ1 = 1 / do constant φ = (1 + sqrt 5)/2;
constant invsqrt5 = 1 / sqrt 5;
floor invsqrt5 * (φ**$n + φ1**$n);
}
[edit] List Generator (built in)
Works with: Rakudo Star
This constructs the fibonacci sequence as a lazy infinite array.
my @fib := (0, 1, *+* ... * );
If you really need a function for it:
my @fib := (0, 1, *+* ... * );
sub fib($n) {
return @fib[$n];
}
[edit] PHP
[edit] Iterative
function fibIter($n) {
if ($n < 2) {
return $n;
}
$fibPrev = 0;
$fib = 1;
foreach (range(1, $n-1) as $i) {
list($fibPrev, $fib) = array($fib, $fib + $fibPrev);
}
return $fib;
}
[edit] Recursive
function fibRec($n) {
return $n < 2 ? $n : fibRec($n-1) + fibRec($n-2);
}
[edit] PicoLisp
[edit] Recursive
(de fibo (N)
(if (> 2 N)
1
(+ (fibo (dec N)) (fibo (- N 2))) ) )
[edit] Recursive with Cache
Using a recursive version doesn't need to be slow, as the following shows:
(de fibo (N)
(cache '*Fibo (format (seed N)) # Use a cache to accelerate
(if (> 2 N)
N
(+ (fibo (dec N)) (fibo (- N 2))) ) ) )
(bench (fibo 1000))
Output:
0.012 sec
-> 43466557686937456435688527675040625802564660517371780402481729089536555417949
05189040387984007925516929592259308032263477520968962323987332247116164299644090
6533187938298969649928516003704476137795166849228875
[edit] PIR
Recursive: Works with: Parrot version tested with 2.4.0
.sub fib
.param int n
.local int nt
.local int ft
if n < 2 goto RETURNN
nt = n - 1
ft = fib( nt )
dec nt
nt = fib(nt)
ft = ft + nt
.return( ft )
RETURNN:
.return( n )
end
.end
.sub main :main
.local int counter
.local int f
counter=0
LOOP:
if counter > 20 goto DONE
f = fib(counter)
print f
print "\n"
inc counter
goto LOOP
DONE:
end
.end
Iterative (stack-based): Works with: Parrot version tested with 2.4.0
.sub fib
.param int n
.local int counter
.local int f
.local pmc fibs
.local int nmo
.local int nmt
fibs = new 'ResizableIntegerArray'
if n == 0 goto RETURN0
if n == 1 goto RETURN1
push fibs, 0
push fibs, 1
counter = 2
FIBLOOP:
if counter > n goto DONE
nmo = pop fibs
nmt = pop fibs
f = nmo + nmt
push fibs, nmt
push fibs, nmo
push fibs, f
inc counter
goto FIBLOOP
RETURN0:
.return( 0 )
end
RETURN1:
.return( 1 )
end
DONE:
f = pop fibs
.return( f )
end
.end
.sub main :main
.local int counter
.local int f
counter=0
LOOP:
if counter > 20 goto DONE
f = fib(counter)
print f
print "\n"
inc counter
goto LOOP
DONE:
end
.end
[edit] Pike
Ported from the Ruby example below ;)
int fibRec(int number){
if(number <= -2){
return pow(-1,(number+1)) * fibRec(abs(number));
} else if(number <= 1){
return abs(number);
} else {
return fibRec(number-1) + fibRec(number-2);
}
}
[edit] PL/I
/* Form the n-th Fibonacci number, n > 1. */
get list (n);
f1 = 0; f2, f3 = 1;
do i = 1 to n-2;
f3 = f1 + f2;
f1 = f2;
f2 = f3;
end;
put skip list (f3);
[edit] PL/SQL
Create or replace Function fnu_fibonnaci(p_iNumber integer)
return integer
is
nuFib integer;
Begin
if p_iNumber is not null then
if p_iNumber=0 then
nuFib:=0;
Elsif p_iNumber=1 then
nuFib:=1;
Else
nuP:=0;
nuQ:=0;
For nuI in 2..p_iNumber loop
nuFib:=nuP+nuQ;
nuP:=nuQ;
nuQ:=nuFib;
End loop;
End if;
End if;
return(nuFib);
End fnu_fibonnaci;
[edit] Pop11
define fib(x);
lvars a , b;
1 -> a;
1 -> b;
repeat x - 1 times
(a + b, b) -> (b, a);
endrepeat;
a;
enddefine;
[edit] PostScript
Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:
%!PS
% We want the 'n'th fibonacci number
/n 13 def
% Prepare output canvas:
/Helvetica findfont 20 scalefont setfont
100 100 moveto
%define the function recursively:
/fib { dup
3 lt
{ pop 1 }
{ dup 1 sub fib exch 2 sub fib add }
ifelse
} def
(Fib\() show n (....) cvs show (\)=) show n fib (.....) cvs show
showpage
[edit] PowerBASIC
Translation of: BASIC
There seems to be a limitation (dare I say, bug?) in PowerBASIC regarding how large numbers are stored. 10E17 and larger get rounded to the nearest 10. For F(n), where ABS(n) > 87, is affected like this:
actual: displayed: F(88) 1100087778366101931 1100087778366101930 F(89) 1779979416004714189 1779979416004714190 F(90) 2880067194370816120 2880067194370816120 F(91) 4660046610375530309 4660046610375530310 F(92) 7540113804746346429 7540113804746346430
FUNCTION fibonacci (n AS LONG) AS QUAD
DIM u AS LONG, a AS LONG, L0 AS LONG, outP AS QUAD
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 FUNCTION
[edit] PowerShell
[edit] Iterative
function fib ($n) {
if ($n -eq 0) { return 0 }
if ($n -eq 1) { return 1 }
$m = 1
if ($n -lt 0) {
if ($n % 2 -eq -1) {
$m = 1
} else {
$m = -1
}
$n = -$n
}
$a = 0
$b = 1
for ($i = 1; $i -lt $n; $i++) {
$c = $a + $b
$a = $b
$b = $c
}
return $m * $b
}
[edit] Recursive
function fib($n) {
switch ($n) {
0 { return 0 }
1 { return 1 }
{ $_ -lt 0 } { return [Math]::Pow(-1, -$n + 1) * (fib (-$n)) }
default { return (fib ($n - 1)) + (fib ($n - 2)) }
}
}
[edit] Prolog
Works with: SWI Prolog
Works with: GNU Prolog
fib(0, 0).
fib(1, 1).
fib(N, X) :- N>1, N1 is N-1, N2 is N-2, fib(N1, X1), fib(N2, X2), X is X1+X2.
[edit] Pure
[edit] Tail Recursive
fib n = loop 0 1 n with
loop a b n = if n==0 then a else loop b (a+b) (n-1);
end;
[edit] PureBasic
[edit] Macro based calculation
Macro Fibonacci (n)
Int((Pow(((1+Sqr(5))/2),n)-Pow(((1-Sqr(5))/2),n))/Sqr(5))
EndMacro
[edit] Recursive
Procedure FibonacciReq(n)
If n<2
ProcedureReturn n
Else
ProcedureReturn FibonacciReq(n-1)+FibonacciReq(n-2)
EndIf
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
[edit] Python
[edit] Iterative
def fibIter(n):
if n < 2:
return n
fibPrev = 1
fib = 1
for num in xrange(2, n):
fibPrev, fib = fib, fib + fibPrev
return fib
[edit] Recursive
def fibRec(n):
if n < 2:
return n
else:
return fibRec(n-1) + fibRec(n-2)
[edit] Generative
def fibGen():
f0, f1 = 0, 1
while True:
yield f0
f0, f1 = f1, f0+f1
[edit] Example use
>>> fg = fibGen()
>>> for x in range(9):
print fg.next()
0
1
1
2
3
5
8
13
21
>>>
[edit] R
recfibo <- function(n) {
if ( n < 2 ) n
else recfibo(n-1) + recfibo(n-2)
}
iterfibo <- function(n) {
if ( n < 2 )
n
else {
f <- c(0, 1)
for (i in 2:n) {
t <- f[2]
f[2] <- sum(f)
f[1] <- t
}
f[2]
}
}
fib <- function(n)
if(n <= 2){if(n>=0) 1 else 0 } else Recall(n-1) + Recall(n-2)
print.table(lapply(0:20, recfibo))
print.table(lapply(0:20, iterfibo))
[edit] REALBasic
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 92nd 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 = 1 to n
sum = noOne + noTwo
noTwo = noOne
noOne = sum
Next
Return noOne
[edit] Ruby
[edit] Iterative
def fibIter(n)
return 0 if n == 0
fibPrev, fib = 1, 1
(n.abs - 2).times { fibPrev, fib = fib, fib + fibPrev }
fib * (n<0 ? (-1)**(n+1) : 1)
end
[edit] Recursive
def fibRec(n)
if n <= -2
(-1)**(n+1) * fibRec(n.abs)
elsif n <= 1
n.abs
else
fibRec(n-1) + fibRec(n-2)
end
end
[edit] Matrix
require 'matrix'
# To understand why this matrix is useful for Fibonacci numbers, remember
# that the definition of Matrix.**2 for any Matrix[[a, b], [c, d]] is
# is [[a*a + b*c, a*b + b*d], [c*a + d*b, c*b + d*d]]. In other words, the
# lower right element is computing F(k - 2) + F(k - 1) every time M is multiplied
# by itself (it is perhaps easier to understand this by computing M**2, 3, etc, and
# watching the result march up the sequence of Fibonacci numbers).
M = Matrix[[0, 1], [1,1]]
# Matrix exponentiation algorithm to compute Fibonacci numbers.
# Let M be Matrix [[0, 1], [1, 1]]. Then, the lower right element of M**k is
# F(k + 1). In other words, the lower right element of M is F(2) which is 1, and the
# lower right element of M**2 is F(3) which is 2, and the lower right element
# of M**3 is F(4) which is 3, etc.
#
# This is a good way to compute F(n) because the Ruby implementation of Matrix.**(n)
# uses O(log n) rather than O(n) matrix multiplications. It works by squaring squares
# ((m**2)**2)... as far as possible
# and then multiplying that by by M**(the remaining number of times). E.g., to compute
# M**19, compute partial = ((M**2)**2) = M**16, and then compute partial*(M**3) = M**19.
# That's only 5 matrix multiplications of M to compute M*19.
def self.fibMatrix(n)
return 0 if n <= 0 # F(0)
return 1 if n == 1 # F(1)
# To get F(n >= 2), compute M**(n - 1) and extract the lower right element.
return CS::lower_right(M**(n - 1))
end
# Matrix utility to return
# the lower, right-hand element of a given matrix.
def self.lower_right matrix
return nil if matrix.row_size == 0
return matrix[matrix.row_size - 1, matrix.column_size - 1]
end
[edit] Generative
require 'generator'
def fibGen
Generator.new do |g|
f0, f1 = 0, 1
loop do
g.yield f0
f0, f1 = f1, f0+f1
end
end
end
Usage:
irb(main):012:0> fg = fibGen
=> #<Generator:0xb7d3ead4 @cont_next=nil, @queue=[0], @cont_endp=nil, @index=0, @block=#<Proc:0xb7d41680@(irb):4>, @cont_yield=#<Continuation:0xb7d3e8a4>>
irb(main):013:0> 9.times { puts fg.next }
0
1
1
2
3
5
8
13
21
=> 9
Works with: Ruby version 1.9
"Fibers are primitives for implementing light weight cooperative concurrency in Ruby. Basically they are a means of creating code blocks that can be paused and resumed, much like threads. The main difference is that they are never preempted and that the scheduling must be done by the programmer and not the VM." [1]
fib = Fiber.new do
a,b = 0,1
loop do
Fiber.yield a
a,b = b,a+b
end
end
9.times {puts fib.resume}
[edit] Sather
The implementations use the arbitrary precision class INTI.
class MAIN is
-- RECURSIVE --
fibo(n :INTI):INTI
pre n >= 0
is
if n < 2.inti then return n; end;
return fibo(n - 2.inti) + fibo(n - 1.inti);
end;
-- ITERATIVE --
fibo_iter(n :INTI):INTI
pre n >= 0
is
n3w :INTI;
if n < 2.inti then return n; end;
last ::= 0.inti; this ::= 1.inti;
loop (n - 1.inti).times!;
n3w := last + this;
last := this;
this := n3w;
end;
return this;
end;
main is
loop i ::= 0.upto!(16);
#OUT + fibo(i.inti) + " ";
#OUT + fibo_iter(i.inti) + "\n";
end;
end;
end;
[edit] Scala
[edit] Recursive
def fib(i:Int):Int = i match{
case 0 => 0
case 1 => 1
case _ => fib(i-1) + fib(i-2)
}
[edit] Lazy sequence
//syntactic sugar for Stream.cons, this is unnecessary but makes the definition prettier
//Stream.cons(head,stream) becomes head::stream
//I think 2.8 will have #::
class PrettyStream[A](str: =>Stream[A]) {
def ::(hd: A) = Stream.cons(hd, str)
}
implicit def streamToPrettyStream[A](str: =>Stream[A]) = new PrettyStream(str)
def fib: Stream[Int] = 0 :: 1 :: fib.zip(fib.tail).map{case (a,b) => a + b}
[edit] Tail recursive
def fib(i:Int):Int = {
def fib2(i:Int, a:Int, b:Int):Int = i match{
case 1 => b
case _ => fib2(i-1, b, a+b)
}
fib2(i,1,0)
}
[edit] Scheme
[edit] Iterative
(define (fib-iter n)
(do ((num 2 (+ num 1))
(fib-prev 1 fib)
(fib 1 (+ fib fib-prev)))
((>= num n) fib)))
[edit] Recursive
(define (fib-rec n)
(if (< n 2)
n
(+ (fib-rec (- n 1))
(fib-rec (- n 2)))))
This version is tail recursive:
(define (fib n)
(letrec ((fib_aux (lambda (n a b)
(if (= n 0)
a
(fib_aux (- n 1) b (+ a b))))))
(fib_aux n 0 1)))
[edit] Dijkstra Algorithm
;;; Fibonacci numbers using Edsger Dijkstra's algorithm
;;; http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
(define (fib n)
(define (fib-aux a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-aux a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else
(fib-aux (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(fib-aux 1 0 0 1 n))
[edit] Seed7
[edit] Recursive
const func integer: fib (in integer: number) is func
result
var integer: result is 1;
begin
if number > 2 then
result := fib(pred(number)) + fib(number - 2);
elsif number = 0 then
result := 0;
end if;
end func;
Original source: [2]
[edit] Iterative
This funtion uses a bigInteger result:
const func bigInteger: fib (in integer: number) is func
result
var bigInteger: result is 1_;
local
var integer: i is 0;
var bigInteger: a is 0_;
var bigInteger: c is 0_;
begin
for i range 1 to pred(number) do
c := a;
a := result;
result +:= c;
end for;
end func;
Original source: [3]
[edit] Slate
n@(Integer traits) fib
[
n <= 0 ifTrue: [^ 0].
n = 1 ifTrue: [^ 1].
(n - 1) fib + (n - 2) fib
].
slate[15]> 10 fib = 55.
True
[edit] Smalltalk
|fibo|
fibo := [ :i |
|ac t|
ac := Array new: 2.
ac at: 1 put: 0 ; at: 2 put: 1.
( i < 2 )
ifTrue: [ ac at: (i+1) ]
ifFalse: [
2 to: i do: [ :l |
t := (ac at: 2).
ac at: 2 put: ( (ac at: 1) + (ac at: 2) ).
ac at: 1 put: t
].
ac at: 2.
]
].
0 to: 10 do: [ :i |
(fibo value: i) displayNl
]
[edit] SNOBOL4
[edit] Recursive
define("fib(a)") :(fib_end)
fib fib = lt(a,2) a :s(return)
fib = fib(a - 1) + fib(a - 2) :(return)
fib_end
while a = trim(input) :f(end)
output = a " " fib(a) :(while)
end
[edit] Tail-recursive
define('trfib(n,a,b)') :(trfib_end)
trfib trfib = eq(n,0) a :s(return)
trfib = trfib(n - 1, a + b, a) :(return)
trfib_end
[edit] Iterative
define('ifib(n)f1,f2') :(ifib_end)
ifib ifib = le(n,2) 1 :s(return)
f1 = 1; f2 = 1
if1 ifib = gt(n,2) f1 + f2 :f(return)
f1 = f2; f2 = ifib; n = n - 1 :(if1)
ifib_end
[edit] Analytic
Works with: Macro Spitbol Works with: CSnobol
Note: Snobol4+ lacks built-in sqrt( ) function.
define('afib(n)s5') :(afib_end)
afib s5 = sqrt(5)
afib = (((1 + s5) / 2) ^ n - ((1 - s5) / 2) ^ n) / s5
afib = convert(afib,'integer') :(return)
afib_end
Test and display all, Fib 1 .. 10
loop i = lt(i,10) i + 1 :f(show)
s1 = s1 fib(i) ' ' ; s2 = s2 trfib(i,0,1) ' '
s3 = s3 ifib(i) ' '; s4 = s4 afib(i) ' ' :(loop)
show output = s1; output = s2; output = s3; output = s4
end
Output:
1 1 2 3 5 8 13 21 34 55 1 1 2 3 5 8 13 21 34 55 1 1 2 3 5 8 13 21 34 55 1 1 2 3 5 8 13 21 34 55
[edit] SNUSP
This is modular SNUSP (which introduces @ and # for threading).
[edit] Iterative
@!\+++++++++# /<<+>+>-\
fib\==>>+<<?!/>!\ ?/\
#<</?\!>/@>\?-<<</@>/@>/>+<-\
\-/ \ !\ !\ !\ ?/#
[edit] Recursive
/========\ />>+<<-\ />+<-\
fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
| #+==/ fib(n-2)|+fib(n-1)|
\=====recursion======/!========/
[edit] Standard ML
[edit] Recursion
This version is tail recursive.
fun fib n =
let
fun fib' (0,a,b) = a
| fib' (n,a,b) = fib' (n-1,a+b,a)
in
fib' (n,0,1)
end
[edit] StreamIt
void->int feedbackloop Fib {
join roundrobin(0,1);
body in->int filter {
work pop 1 push 1 peek 2 { push(peek(0) + peek(1)); pop(); }
};
loop Identity<int>;
split duplicate;
enqueue(0);
enqueue(1);
}
[edit] Tcl
[edit] Simple Version
These simple versions do not handle negative numbers -- they will return N for N < 2
[edit] Iterative
Translation of: Perl
proc fibiter n {
if {$n < 2} {return $n}
set prev 1
set fib 1
for {set i 2} {$i < $n} {incr i} {
lassign [list $fib [incr fib $prev]] prev fib
}
return $fib
}
[edit] Recursive
proc fib {n} {
if {$n < 2} then {expr {$n}} else {expr {[fib [expr {$n-1}]]+[fib [expr {$n-2}]]} }
}
The following Works with: Tcl version 8.5: defining a procedure in the ::tcl::mathfunc namespace allows that proc to be used as a function in expr expressions.
proc tcl::mathfunc::fib {n} {
if { $n < 2 } {
return $n
} else {
return [expr {fib($n-1) + fib($n-2)}]
}
}
# or, more tersely
proc tcl::mathfunc::fib {n} {expr {$n<2 ? $n : fib($n-1) + fib($n-2)}}
E.g.:
expr {fib(7)} ;# ==> 13
namespace path tcl::mathfunc #; or, interp alias {} fib {} tcl::mathfunc::fib
fib 7 ;# ==> 13
[edit] Tail-Recursive
In Tcl 8.6 a tailcall function is available to permit writing tail-recursive functions in Tcl. This makes deeply recursive functions practical. The availability of large integers also means no truncation of larger numbers.
proc fib-tailrec {n} {
proc fib:inner {a b n} {
if {$n < 1} {
return $a
} elseif {$n == 1} {
return $b
} else {
tailcall fib:inner $b [expr {$a + $b}] [expr {$n - 1}]
}
}
return [fib:inner 0 1 $n]
}
% fib-tailrec 100 354224848179261915075
[edit] Handling Negative Numbers
[edit] Iterative
proc fibiter n {
if {$n < 0} {
set n [expr {abs($n)}]
set sign [expr {-1**($n+1)}]
} else {
set sign 1
}
if {$n < 2} {return $n}
set prev 1
set fib 1
for {set i 2} {$i < $n} {incr i} {
lassign [list $fib [incr fib $prev]] prev fib
}
return [expr {$sign * $fib}]
}
fibiter -5 ;# ==> 5
fibiter -6 ;# ==> -8
[edit] Recursive
proc tcl::mathfunc::fib {n} {expr {$n<-1 ? -1**($n+1) * fib(abs($n)) : $n<2 ? $n : fib($n-1) + fib($n-2)}}
expr {fib(-5)} ;# ==> 5
expr {fib(-6)} ;# ==> -8
[edit] For the Mathematically Inclined
This works up to fib(70), after which the limited precision of IEEE double precision floating point arithmetic starts to show.
Works with: Tcl version 8.5
proc fib n {expr {round((.5 + .5*sqrt(5)) ** $n / sqrt(5))}}
[edit] TI-83 BASIC
Unoptimized fibonacci program
:Disp "0" //Dirty, I know, however this does not interfere with the code
:Disp "1"
:Disp "1"
:1→A
:1→B
:0→C
:Goto 1
:Lbl 1
:A+B→C
:Disp C
:B→A
:A→C
:Goto 1
[edit] TI-89 BASIC
Unoptimized recursive implementation.
fib(n)
Func
If n = 0 or n = 1 Then
Return n
ElseIf n ≥ 2 Then
Return fib(n-1) + fib(n-2)
EndIf
EndFunc
[edit] UnixPipes
Uses fib and last as file buffers for computation. could have made fib as a fifo and changed tail -f to cat fib but it is not line buffered.
echo 1 |tee last fib ; tail -f fib | while read x
do
cat last | tee -a fib | xargs -n 1 expr $x + |tee last
done
[edit] UNIX Shell
Works with: bash version 3
#!/bin/bash
a=0
b=1
max=$1
for (( n=1; "$n" <= "$max"; $((n++)) ))
do
a=$(($a + $b))
echo "F($n): $a"
b=$(($a - $b))
done
Recursive:
Works with: bash version 3
fib() {
local n=$1
[ $n -lt 2 ] && echo -n $n || echo -n $(( $( fib $(( n - 1 )) ) + $( fib $(( n - 2 )) ) ))
}
[edit] Ursala
All three methods are shown here, and all have unlimited precision.
#import std
#import nat
iterative_fib = ~&/(0,1); ~&r->ll ^|\predecessor ^/~&r sum
recursive_fib = {0,1}^?<a/~&a sum^|W/~& predecessor^~/~& predecessor
analytical_fib =
%np+ -+
mp..round; ..mp2str; sep`+; ^CNC/~&hh take^\~&htt %np@t,
(mp..div^|\~& mp..sub+ ~~ @rlX mp..pow_ui)^lrlPGrrPX/~& -+
^\~& ^(~&,mp..sub/1.E0)+ mp..div\2.E0+ mp..add/1.E0,
mp..sqrt+ ..grow/5.E0+-+-
The analytical method uses arbitrary precision floating point arithmetic from the mpfr library and then converts the result to a natural number. Sufficient precision for an exact result is always chosen based on the argument. This test program computes the first twenty Fibonacci numbers by all three methods.
#cast %nLL
examples = <.iterative_fib,recursive_fib,analytical_fib>* iota20
output:
< <0,0,0>, <1,1,1>, <1,1,1>, <2,2,2>, <3,3,3>, <5,5,5>, <8,8,8>, <13,13,13>, <21,21,21>, <34,34,34>, <55,55,55>, <89,89,89>, <144,144,144>, <233,233,233>, <377,377,377>, <610,610,610>, <987,987,987>, <1597,1597,1597>, <2584,2584,2584>, <4181,4181,4181>>
[edit] V
Generate n'th fib by using binary recursion
[fib
[small?] []
[pred dup pred]
[+]
binrec].
[edit] VBScript
[edit] Non-recursive, object oriented, generator
Defines a generator class, with a default Get property. Uses Currency for larger-than-Long values. Tests for overflow and switches to Double. Overflow information also available from class.
[edit] Class Definition:
class generator
dim t1
dim t2
dim tn
dim cur_overflow
Private Sub Class_Initialize
cur_overflow = false
t1 = ccur(0)
t2 = ccur(1)
tn = ccur(t1 + t2)
end sub
public default property get generated
on error resume next
generated = ccur(tn)
if err.number <> 0 then
generated = cdbl(tn)
cur_overflow = true
end if
t1 = ccur(t2)
if err.number <> 0 then
t1 = cdbl(t2)
cur_overflow = true
end if
t2 = ccur(tn)
if err.number <> 0 then
t2 = cdbl(tn)
cur_overflow = true
end if
tn = ccur(t1+ t2)
if err.number <> 0 then
tn = cdbl(t1) + cdbl(t2)
cur_overflow = true
end if
on error goto 0
end property
public property get overflow
overflow = cur_overflow
end property
end class
[edit] Invocation:
dim fib
set fib = new generator
dim i
for i = 1 to 100
wscript.stdout.write " " & fib
if fib.overflow then
wscript.echo
exit for
end if
next
[edit] 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
[edit] Vedit macro language
Iterative
Calculate fibonacci(#1). Negative values return 0.
:FIBONACCI:
#11 = 0
#12 = 1
Repeat(#1) {
#10 = #11 + #12
#11 = #12
#12 = #10
}
Return(#11)
[edit] Visual Basic .NET
Platform: .NET
Works with: Visual Basic .NET version 9.0+
Function Fib(ByVal n As Integer) As Decimal
Dim fib0, fib1, sum As Decimal
Dim i As Integer
fib0 = 0
fib1 = 1
For i = 1 To n
sum = fib0 + fib1
fib0 = fib1
fib1 = sum
Next
Fib = fib0
End Function
Recursive
Works with: Visual Basic .NET version 9.0+
Function Seq(ByVal Term As Integer)
If Term < 2 Then Return Term
Return Seq(Term - 1) + Seq(Term - 2)
End Function
End Function
[edit] XQuery
declare function local:fib($n as xs:integer) as xs:integer {
if($n < 2)
then $n
else local:fib($n - 1) + local:fib($n - 2)
};
Categories: Clarified and Needing Review | Programming Tasks | Arithmetic operations | Recursion | Classic CS problems and programs | ActionScript | AppleScript | Ada | ALGOL 68 | AutoHotkey | AWK | BASIC | Batch File | Bc | Befunge | Brainf*** | C | C++ | GMP | C sharp | Cat | Chef | Clojure | Common Lisp | D | E | Erlang | FALSE | Factor | Fancy | Falcon | Forth | Fortran | F Sharp | Go | Groovy | HaXe | Haskell | Hope | HicEst | Icon | Icon Programming Library | Unicon | IDL | J | Java | JavaScript | Joy | Lisaac | Logo | Lua | M4 | Mathematica | MAXScript | Metafont | Modula-3 | MUMPS | NewLISP | Nimrod | Objeck | OCaml | Octave | Oz | Pascal | Perl | Perl 6 | PHP | PicoLisp | PIR | Pike | PL/I | PL/SQL | Pop11 | PostScript | PowerBASIC | PowerShell | Prolog | Pure | PureBasic | Python | R | REALBasic | Ruby | Sather | Scala | Scheme | Seed7 | Slate | Smalltalk | SNOBOL4 | SNUSP | Standard ML | StreamIt | Tcl | TI-83 BASIC | TI-89 BASIC | UnixPipes | UNIX Shell | Ursala | V | VBScript | Vedit macro language | Visual Basic .NET | XQuery
