Calculate the Fibonacci sequence

From CodeCodex

Revision as of 20:45, 2 August 2006 by Jdh30 (Talk | contribs)

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
add eax,ebx
add ebx,eax
add edx,8
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));
   Console.ReadKey();
   }

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

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

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