Difference between revisions of "Calculate the Fibonacci sequence"

Source code for calculation of the Fibonacci sequence.

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

```#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;
}
```

C++

```#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;
}
```

C#

```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));
}
```

Java

Java console application

```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)));
}
}
}                                                        // by CF
```

OCaml

The simplest implementation as a non-tail-recursive function:

```# let rec fib n = if n<2 then n else fib(n-1) + fib(n-2);;
```

For example:

```# fib 10;;
- : int = 55
```

This function can be made tail recursive by accumulating the two previous Fibonacci numbers:

```# let rec fib ?(r=1) ?(k=0) = function
| 0 -> k
| 1 -> r
| f -> fib ~r:(r+k) ~k:r (f-1);;
val fib : ?r:int -> ?k:int -> int -> int = <fun>
```

Perl

```#!/bin/perl -wl
#
# Prints the sequence of Fibonacci numbers with arbitrary
# precision. If an argument N is given, the program stops
# after generating Fibonacci(N).

use strict;
use bigint;

my \$n = @ARGV ? shift : 1e9999;

exit if \$n < 0;
print "0: 0"; exit if \$n < 1;
print "1: 1"; exit if \$n < 2;

my (\$a, \$b) = (0, 1);
for my \$k (2 .. \$n) {
(\$a, \$b) = (\$b, \$a+\$b);
print "\$k: \$b";
}
```

Python

Print the first 100 fibonnaci numbers, up to '354224848179261915075'. This program considers '0' to be the 0th fibonnaci number, and '1' to be the first.

```#!/usr/bin/env python

a, b = 0, 1
print a
for n in range(100):
print b
a, b = b, a+b
```

Ruby

```#!/usr/bin/env env
a, b = 0, 1
puts "0: #{a}"
1.upto 100 do |n|
puts "#{n}: #{b}"
a, b = b, a+b
end
```

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

MS-DOS

```::print the first 'max' fibonacci numbers
::(only working under windows xp)
@echo off

set index=1
set max=46
set fibold=0
set fib=1

echo.---%max% first FIBONACCI-Numbers---

echo.%fibold%

:WHILE
echo.%fib%
set /A fibnew=fibold + fib
set fibold=%fib%
set fib=%fibnew%
set /A index=index + 1
IF %index% LEQ %max% GOTO WHILE
```