Difference between revisions of "Calculate the Fibonacci sequence"

From CodeCodex

m
Line 24: Line 24:
 
</pre>
 
</pre>
  
==Assembly==
+
==80386+ Assembly==
 
MASM:
 
MASM:
 
<pre>
 
<pre>
Line 69: Line 69:
 
==C==
 
==C==
  
<pre>
+
<HIGHLIGHTSYNTAX language="c">
 
#include <stdio.h>
 
#include <stdio.h>
  
Line 89: Line 89:
 
   return 0;
 
   return 0;
 
}
 
}
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==C++==
 
==C++==
<pre>
+
<HIGHLIGHTSYNTAX language="cpp">
 
#include <iostream>
 
#include <iostream>
 
using namespace std;
 
using namespace std;
Line 106: Line 106:
 
   return 0;
 
   return 0;
 
}
 
}
</pre>
+
</HIGHLIGHTSYNTAX>
  
==C#==
+
==Db==
<pre>
+
<HIGHLIGHTSYNTAX language="csharp">
 
static int Fibonacci (int x)
 
static int Fibonacci (int x)
 
   {
 
   {
Line 123: Line 123:
 
   Console.ReadKey();
 
   Console.ReadKey();
 
   }
 
   }
</pre>
+
</HIGHLIGHTSYNTAX>
 
This one is alot quicker than the above one
 
This one is alot quicker than the above one
<pre>
+
<HIGHLIGHTSYNTAX language="csharp">
 
int a = 0;
 
int a = 0;
 
int b = 1;
 
int b = 1;
Line 150: Line 150:
 
}
 
}
 
Console.ReadKey();
 
Console.ReadKey();
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==Haskell==
 
==Haskell==
<pre>
+
<HIGHLIGHTSYNTAX language="haskell">
 
-- different versions, from slowest to fastest
 
-- different versions, from slowest to fastest
  
Line 191: Line 191:
 
fib_mat 1 = 1
 
fib_mat 1 = 1
 
fib_mat n = fst $ fst $ pow n ((1,1),(1,0))
 
fib_mat n = fst $ fst $ pow n ((1,1),(1,0))
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==Java==
 
==Java==
 
Java console application
 
Java console application
<pre>
+
<HIGHLIGHTSYNTAX language="java122">
 
public class Fibonacci{
 
public class Fibonacci{
 
     static double sfib (double r, double k, double f){
 
     static double sfib (double r, double k, double f){
Line 210: Line 210:
 
     }
 
     }
 
}
 
}
</pre>
+
</HIGHLIGHTSYNTAX>
 
A cleaner alternative that uses an ArrayList to cache previous Fibonacci values:
 
A cleaner alternative that uses an ArrayList to cache previous Fibonacci values:
<pre>
+
<HIGHLIGHTSYNTAX language="java122">
 
public class Fibonacci {
 
public class Fibonacci {
 
     static ArrayList<Double> fibList;
 
     static ArrayList<Double> fibList;
Line 261: Line 261:
 
     }
 
     }
 
}
 
}
</pre>
+
</HIGHLIGHTSYNTAX>
  
==Lisp==
+
==Common Lisp==
 
<pre>
 
<pre>
 
* (defun fib(n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
 
* (defun fib(n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
Line 269: Line 269:
 
* (fib 10)
 
* (fib 10)
 
55
 
55
 +
</pre>
 +
 +
Tail recursive version (much faster):
 +
<pre>
 +
;;; 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)))
 +
</pre>
 +
 +
A different algorithm, based on US' NIST's Dictionary Of Algorithms description of Bill Gosper & Gene Salamin method, at [http://www.nist.gov/dads/HTML/fibonacciNumber.html] (***Much much much*** faster):
 +
<pre>
 +
;;; Helper functions:
 +
(defun pairwise-multiply (pair1 pair2)
 +
    (let ((ac (* (first pair1) (first pair2)))
 +
            (ad (* (first pair1) (second pair2)))
 +
            (bc (* (second pair1) (first pair2)))
 +
            (bd (* (second pair1) (second pair2))))
 +
        (list (+ ac ad bc) (+ ac bd))))
 +
 +
;;; If you're going for values well above n=1000000 (and maybe some more),
 +
;;; you might want to consider making this function tail-recursive, or make
 +
;;; the iterative version.
 +
(defun pairwise-pow (pair n)
 +
    ;; It's an error having n < 1, you may want to change this to check for
 +
    ;; that condition.
 +
    (cond
 +
        ((= n 1) pair)
 +
        ((evenp n) (let ((result (pairwise-pow pair (truncate (/ n 2)))))
 +
                        (pairwise-multiply result result)))
 +
        (t (let ((result (pairwise-pow pair (truncate (/ n 2)))))
 +
                (pairwise-multiply pair (pairwise-multiply result result))))))
 +
 +
(defun fibonacci (n)
 +
    (if (zerop n) 0
 +
        (first (pairwise-pow '(1 0) n))))
 +
 +
;; Try this one, don't worry, it won't take you a millisecond.
 +
(fibonacci 10000)
 
</pre>
 
</pre>
  
 
==Matlab==
 
==Matlab==
<pre>
+
<HIGHLIGHTSYNTAX language="matlab5">
 
function f = binet(a,b,n)
 
function f = binet(a,b,n)
 
% vectorized version of fibonacci fibonacci O(1) using Binet formula
 
% vectorized version of fibonacci fibonacci O(1) using Binet formula
Line 283: Line 327:
 
f = c(1)*phi.^n+c(2)*phi1.^n;
 
f = c(1)*phi.^n+c(2)*phi1.^n;
 
if (~rem(a,1) && ~rem(b,1)),  f = round(f); end;
 
if (~rem(a,1) && ~rem(b,1)),  f = round(f); end;
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==MS-DOS==
 
==MS-DOS==
Line 311: Line 355:
 
==OCaml==
 
==OCaml==
 
The simplest implementation as a non-tail-recursive function:
 
The simplest implementation as a non-tail-recursive function:
<pre>
+
<HIGHLIGHTSYNTAX language="ocaml">
 
# let rec fib n = if n<2 then n else fib(n-1) + fib(n-2);;
 
# let rec fib n = if n<2 then n else fib(n-1) + fib(n-2);;
 
val fib : int -> int = <fun>
 
val fib : int -> int = <fun>
</pre>
+
</HIGHLIGHTSYNTAX>
 
For example:
 
For example:
<pre>
+
<HIGHLIGHTSYNTAX language="ocaml">
 
# fib 10;;
 
# fib 10;;
 
- : int = 55
 
- : int = 55
</pre>
+
</HIGHLIGHTSYNTAX>
 
This function can be made tail recursive by accumulating the two previous Fibonacci numbers (the two accumulators are optional arguments here, with default values):
 
This function can be made tail recursive by accumulating the two previous Fibonacci numbers (the two accumulators are optional arguments here, with default values):
<pre>
+
<HIGHLIGHTSYNTAX language="ocaml">
 
# let rec fib ?(r=1) ?(k=0) = function
 
# let rec fib ?(r=1) ?(k=0) = function
 
     | 0 -> k
 
     | 0 -> k
Line 327: Line 371:
 
     | f -> fib ~r:(r+k) ~k:r (f-1);;
 
     | f -> fib ~r:(r+k) ~k:r (f-1);;
 
val fib : ?r:int -> ?k:int -> int -> int = <fun>
 
val fib : ?r:int -> ?k:int -> int -> int = <fun>
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==Perl==
 
==Perl==
<pre>
+
<HIGHLIGHTSYNTAX language="perl">
 
#!/bin/perl -wl
 
#!/bin/perl -wl
 
#
 
#
Line 351: Line 395:
 
     print "$k: $b";
 
     print "$k: $b";
 
}
 
}
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==PHP==
 
==PHP==
Line 370: Line 414:
 
==Python==
 
==Python==
 
Print the first 100 fibonnaci numbers, up to '354,224,848,179,261,915,075'. This program considers '0' to be the 0th fibonnaci number, and '1' to be the first.
 
Print the first 100 fibonnaci numbers, up to '354,224,848,179,261,915,075'. This program considers '0' to be the 0th fibonnaci number, and '1' to be the first.
<pre>
+
<HIGHLIGHTSYNTAX language="python">
 
#!/usr/bin/env python
 
#!/usr/bin/env python
  
Line 378: Line 422:
 
     print b
 
     print b
 
     a, b = b, a+b
 
     a, b = b, a+b
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==Ruby==
 
==Ruby==
Line 392: Line 436:
  
 
==Scheme==
 
==Scheme==
<pre>
+
<HIGHLIGHTSYNTAX language="scheme">
 
(define (fib n)
 
(define (fib n)
 
   (if (< n 2)
 
   (if (< n 2)
 
   n
 
   n
 
   (+ (fib (- n 1)) (fib (- n 2)))))
 
   (+ (fib (- n 1)) (fib (- n 2)))))
</pre>
+
</HIGHLIGHTSYNTAX>
  
 
==Seed7==
 
==Seed7==
Line 439: Line 483:
 
[[Category:Objective Caml]]
 
[[Category:Objective Caml]]
 
[[Category:PHP]]
 
[[Category:PHP]]
 +
[[Category:Common Lisp]]

Revision as of 03:22, 30 May 2007

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? ");
read((i, new line));
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
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

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

<HIGHLIGHTSYNTAX language="cpp">

  1. 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>

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));
  Console.ReadKey();
  }

</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?");

n = Convert.ToInt16(Console.ReadLine());

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

} Console.ReadKey(); </HIGHLIGHTSYNTAX>

Haskell

<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 & Gene Salamin method, at [1] (***Much much much*** faster):

;;; Helper functions:
(defun pairwise-multiply (pair1 pair2)
    (let ((ac (* (first pair1) (first pair2)))
            (ad (* (first pair1) (second pair2)))
            (bc (* (second pair1) (first pair2)))
            (bd (* (second pair1) (second pair2))))
         (list (+ ac ad bc) (+ ac bd))))

;;; If you're going for values well above n=1000000 (and maybe some more),
;;; you might want to consider making this function tail-recursive, or make
;;; the iterative version.
(defun pairwise-pow (pair n)
    ;; It's an error having n < 1, you may want to change this to check for
    ;; that condition.
    (cond
        ((= n 1) pair)
        ((evenp n) (let ((result (pairwise-pow pair (truncate (/ n 2)))))
                        (pairwise-multiply result result)))
        (t (let ((result (pairwise-pow pair (truncate (/ n 2)))))
                (pairwise-multiply pair (pairwise-multiply result result))))))

(defun fibonacci (n)
    (if (zerop n) 0
        (first (pairwise-pow '(1 0) n))))

;; Try this one, don't worry, it won't take you a millisecond.
(fibonacci 10000)

Matlab

<HIGHLIGHTSYNTAX language="matlab5"> function f = binet(a,b,n) % vectorized version of fibonacci fibonacci O(1) using Binet formula % a and b are real seeds % n is the integer vector of the indices to be computed % if the seeds are integer the result is rounded to insure integer result

phi = (1+sqrt(5))/2; phi1 = -1/phi; n = n-1; c = [ 1 1; phi phi1]\[a;b]; f = c(1)*phi.^n+c(2)*phi1.^n; if (~rem(a,1) && ~rem(b,1)), f = round(f); end; </HIGHLIGHTSYNTAX>

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

OCaml

The simplest implementation as a non-tail-recursive function: <HIGHLIGHTSYNTAX language="ocaml">

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

val fib : int -> int = <fun> </HIGHLIGHTSYNTAX> For example: <HIGHLIGHTSYNTAX language="ocaml">

  1. fib 10;;

- : int = 55 </HIGHLIGHTSYNTAX> This function can be made tail recursive by accumulating the two previous Fibonacci numbers (the two accumulators are optional arguments here, with default values): <HIGHLIGHTSYNTAX language="ocaml">

  1. 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> </HIGHLIGHTSYNTAX>

Perl

<HIGHLIGHTSYNTAX language="perl">

  1. !/bin/perl -wl
  2. Prints the sequence of Fibonacci numbers with arbitrary
  3. precision. If an argument N is given, the program stops
  4. 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";

} </HIGHLIGHTSYNTAX>

PHP

<?php
$a=0;
$b=1;
echo "$a\n$b\n";
for($i=2;$i<100;$i++){
    $temp=$a;
    $a=$b;
    $b=$temp+$b;
    echo "$b\n";
}
?>

Python

Print the first 100 fibonnaci numbers, up to '354,224,848,179,261,915,075'. This program considers '0' to be the 0th fibonnaci number, and '1' to be the first. <HIGHLIGHTSYNTAX language="python">

  1. !/usr/bin/env python

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

    print b
    a, b = b, a+b

</HIGHLIGHTSYNTAX>

Ruby

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

Scheme

<HIGHLIGHTSYNTAX language="scheme"> (define (fib n)

 (if (< n 2)
 n
 (+ (fib (- n 1)) (fib (- n 2)))))

</HIGHLIGHTSYNTAX>

Seed7

$ include "seed7_05.s7i";
  include "bigint.s7i";

const proc: main is func
  local
    var integer: i is 0;
    var bigInteger: a is 0_;
    var bigInteger: b is 1_;
    var bigInteger: c is 0_;
  begin
    writeln(a);
    for i range 1 to 100 do
      writeln(b);
      c := a;
      a := b;
      b +:= c;
    end for;
  end func;