Calculate the Fibonacci sequence

 Related content:

Source code for calculation of the Fibonacci sequence.

Algol 68

This version asks the user to input an integer i, and prints out the first i numbers in the Fibonacci sequence.

PROC print fibo = (INT n) VOID :
# prints out the Fibonacci sequence up to n. #
BEGIN
INT a := 0, b := 1;
FOR i TO n DO
print((whole(i, 0), " => ", whole(b, 0), new line));
INT c = a   b;
a := b;
b := c
OD
END;

INT i;
print("Compute Fibonacci sequence up to? ");
print fibo(i)

80386 Assembly

MASM:

.data
fibonacci DWORD 100 dup (0)
.code
mov edx,offset fibonacci
mov eax,1
mov ebx,1
mov ecx,49
@@:
mov DWORD PTR [edx],eax
mov DWORD PTR [edx 4],ebx
sub ecx,1
jnz @B

BASIC

fib0=0

fib1=1

FOR cnt= 1 TO n

fib2=fib1 fib0

PRINT fib2

fib0=fib1

fib1=fib2

NEXT cnt

/* fib2 is the sum of the two preceeding terms.*/

C

<HIGHLIGHTSYNTAX language="c">

1. include <stdio.h>

int main() {

int i, x;
int a = 0;
int b = 1;
printf("%i\n%i\n", a, b);
for(i = 2; i < 100; i  )
{
x = a;
a = b;
b = x   b;
printf("%i\n", b);
}
return 0;

} </HIGHLIGHTSYNTAX>

C

1: <HIGHLIGHTSYNTAX language="cpp">

#include <iostream>

using namespace std; int main() {

int number[30] = {1, 1, 0};
int total;
for(int i = 2; i < 30; i  )
{
number[i] = number[i - 1]   number[i - 2];
cout << number[i];
}
return 0;

} </HIGHLIGHTSYNTAX>

2: <HIGHLIGHTSYNTAX language="cpp">

1. include <iostream.h>
void fibonacci(n)

{

if(n==0) return 0;
else
if(n==1) return 1;
else return fibonacci(n-1) fibonacci(n-2);

}

void main() {

unsigned int n;
cin>>n;
for(int i=1;i<=n;i  )
cout<<fibonacci(i);

} </HIGHLIGHTSYNTAX>

Db

<HIGHLIGHTSYNTAX language="csharp"> static int Fibonacci (int x)

{
Console.WriteLine ("x = {0}", x);
if (x <= 1)
{ return 1; }
return Fibonacci (x-1)   Fibonacci (x-2);
}

static void Main( )

{
Console.WriteLine ("Fibonacci no. = {0}", Fibonacci (5));
}

</HIGHLIGHTSYNTAX> This one is alot quicker than the above one <HIGHLIGHTSYNTAX language="csharp"> int a = 0; int b = 1; int c = 0; int n = 46; //to the N'th fibonacci No.

Console.WriteLine("Which Fibonacci Number do you want?");

if (n != 1) {

for (int i = 1; i <= n; i  )
{
c = a   b;
a = b;
b = c;
}
Console.WriteLine("the {0}th Fibonacci number is {1}", n, a);

} else {

Console.WriteLine("the {0}st Fibonacci number is 1", n);

<HIGHLIGHTSYNTAX language="haskell"> -- different versions, from slowest to fastest

-- recursive: O(exp(n)) fib_rec 0 = 1 fib_rec 1 = 1 fib_rec n = fib_rec (n-1) fib_rec (n-2)

-- dynamic programming 1, imperative style: O(n) fib_dyn1 0 = 0 fib_dyn1 1 = 1 fib_dyn1 n = select \$ until done step (0,0,1)

where done (k,_,_)   = n == k

step (k,x,y) = (k 1,y,x y) select (_,_,y) = y

-- dynamic programming 2: O(n) -- fibs is the infinite sequence of fibonacci numbers fibs = 0 : 1 : zipWith ( ) fibs (tail fibs) fib_dyn2 n = fibs !! n

-- matrix multiplication: O(log n) -- uses the identity: (F_{n 1},F_{n})^T=M^n * (1,0)^T where M=((1,1),(1,0)) pow 0 _ = ((1,0),(0,1)) pow 1 m = m pow n m = let (q,r) = divMod n 2 y = pow q m z = prod y y in if r == 0 then z else prod z m

prod ((a,b),(c,d)) ((a',b'),(c',d'))

= ( ( a*a'   b*c', a*b'   b*d' )
, ( c*a'   d*c', c*b'   d*d' )
)

fib_mat 0 = 1 fib_mat 1 = 1 fib_mat n = fst \$ fst \$ pow n ((1,1),(1,0)) </HIGHLIGHTSYNTAX>

Java

Java console application <HIGHLIGHTSYNTAX language="java122"> public class Fibonacci{

static double sfib (double r, double k, double f){
return(f==0)?k : (f==1)?r : sfib(r k,r,f-1);
}

public static void main(String Args[]){
int n=100;          // es kann selbst bestimmt werden bis zu welcher Zahl die Fibs
ausgegeben werden sollen
System.out.println("Fibonacci Zahlen von 0 bis " n "\n******************************");
for (int i=0; i<=n; i  ){
System.out.println("" i ".\t Fib Zahl=\t" (sfib(1,0,i)));
}
}

} </HIGHLIGHTSYNTAX> A cleaner alternative that uses an ArrayList to cache previous Fibonacci values: <HIGHLIGHTSYNTAX language="java122"> public class Fibonacci {

static ArrayList<Double> fibList;
/**
* A recursive Fibonacci calculation method.
* Note: This method considers that the * Fibonacci Sequence starts at 0. To alter the * method to start at 1 use the following code * in place of the fib() method: * double f; if(n <= 2) { f = 1.0; if(fibList.size() <= 2) fibList.add(f); return f; } f = (n < fibList.size()) ? fibList.get(n - 2) fibList.get(n - 1) : fib(n - 2) fib(n - 1); if(n >= fibList.size()) fibList.add(f); return f; * @param n the number to which the Fibonacci sequence * should be calculated. * @return the Fibonacci value at n. */ public static double fib(int n) { double f; if(n <= 1) { f = 1.0; if(fibList.size() <= 1) fibList.add(f); return f; } f = (n < fibList.size()) ? fibList.get(n - 2) fibList.get(n - 1) : fib(n - 2) fib(n - 1); if(n >= fibList.size()) fibList.add(f); return f; } public static void main(String[] args) { fibList = new ArrayList<Double>(); int n = 50; System.out.println("The first " n " Fibonacci numbers:"); for(int i = 0; i < n; i ) System.out.println(fib(i)); }

} </HIGHLIGHTSYNTAX>

Common Lisp

* (defun fib(n) (if (< n 2) n (  (fib (- n 1)) (fib (- n 2)))))
FIB
* (fib 10)
55

Tail recursive version (much faster):

;;; Remember that Tail-recursion optimization isn't enabled by
;;; default in most CL compilers/interpreters.
(defun fib-optimized (n)
(labels
((fib2 (num l m)
(if (< num n)
(fib2 (1  num) (  l m) l)
l)))
(fib2 0 0 1)))

A different algorithm, based on US' NIST's Dictionary Of Algorithms description of Bill Gosper