Calculate the Fibonacci sequence

From CodeCodex

(Redirected from Fibonacci sequence)
Related content:

Source code for calculation of the Fibonacci sequence.

Algol 68[edit]

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[edit]

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

Ateji PX[edit]

With Ateji PX(extension of Java) Parallel branches can be created recursively. This is often used in divide-and-conquer algorithms. Here is a simple example computing the Fibonacci series in parallel (this is a naive algorithm for the purpose of exposition):

int fib(int n) {
   if(n <= 1) return 1;
   int fib1, fib2;
   // recursively create parallel branches
   [
      || fib1 = fib(n-1);
      || fib2 = fib(n-2);
   ]
   return fib1 + fib2;
}

BASIC[edit]

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[edit]

#include <stdio.h>

main() {
    int a = 0;
    int b = 1;
    int x = 0;
    while(b < 5000) {
        printf("%d\n", a);
        x = b;
        b = a+b;
        a = x;
    }
    return 0;
}

C++[edit]

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] << endl;
   }
   return 0;
}


2:

#include <iostream>

using namespace std;

unsigned int fibonacci(unsigned int n) {
   if (n == 0) return 0;
   else if (n == 1) return 1;
   else return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
   unsigned int n;
   cin >> n;
   for (int i = 1; i <= n; i++) {
      cout << fibonacci(i) << endl;
   }
   return 0;
}

3:

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

  int result = array[n-1];
  delete [] array;
  return result;
}

C#[edit]

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

This one is alot quicker than the above one

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

Erlang[edit]

fib(N) ->
    fib(N, 0, 1).

fib(0, _, B) -> B;
fib(N, A, B) ->
    io:format("~p~n", [B]),
    fib(N-1, B, A+B).

Go[edit]

func fib(n int) int {
	a, b := 0, 1
	for i := 0; i < n; i++ {
		a, b = b, a+b
	}
	return b
}

Haskell[edit]

-- different versions, from slowest to fastest

-- recursive: O(exp(n))
fib_rec 0 = 0
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 (1,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 = 0
fib_mat 1 = 1
fib_mat n = snd $ fst $ pow n ((1,1),(1,0))

Java[edit]

Java console application

public class Fibonacci{  
	static long sfib (long r, long k, int f)
	{  
		return (f==0) ? k : (f==1) ? r : sfib(r+k,r,f-1);  
	}
	
	public static void main(String Args[])
	{
		int n=90;  
		System.out.println("\nFibonacci Numbers from 0 to "+n+"\n******************************");  

		for (int i=0; i<=n; i++)
		{
			System.out.println(""+i+".\t " + sfib(1,1,i));  
		}
	}
}

A cleaner alternative that uses an ArrayList to cache previous Fibonacci values:

public class Fibonacci {
    static ArrayList<Double> fibList;
    /**
     * A recursive Fibonacci calculation method.<br>
     * <b>Note</b>: 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));
    }
}

Simple code.

public class Fibonacci {
    public static void main(String Args[]) {
        int n = 90;
        long a = 0, b = 1;
        long aux;
        for (int i = 0; i < n; i++) {
            System.out.println(i + ": " + b);
            aux = b;
            b = a + b;
            a = aux;
        }
    }
}

Common Lisp[edit]

This one runs in O(fib(n))

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

Tail recursive version (much faster, O(n)):

;;; 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, O(log(n))):

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

Scheme[edit]

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

Tail recursive version

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

Matlab[edit]

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;

MS-DOS[edit]

::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[edit]

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);;
val fib : int -> int = <fun>

For example:

# fib 10;;
- : int = 55

This function can be made tail recursive by accumulating the two previous Fibonacci numbers (the two accumulators are optional arguments here, with default values):

# 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[edit]

#!/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";
}

PHP[edit]

<?php
$a = 0;
$b = 1;

for ($i = 2; $i < 100; $i++) {
    echo "$b\5";
    list($a, $b) = array($b, $a+$b);
}
?>

PowerShell[edit]

$c=$p=1;$c;$p;while($c -le 100){$c,$p=($c+$p),$c;$c}

Python[edit]

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.

#!/usr/bin/env python

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

I would instead use a generator:

def fib():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a+b

for i, n in zip(range(100), fib()):
    print i, n    

Ruby[edit]

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

Scheme[edit]

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

More effective procedure:

(define (fib-iter n)
  (let fib ((a 0)
            (b 1)
            (n n))
    (if (< n 1)
        a
        (fib b (+ a b) (- n 1)))))

Seed7[edit]

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

Tcl[edit]

proc fib n {expr {$n<2? $n: [fib [incr n -1]] + [fib [incr n -1]]}}

Zsh[edit]

fibonacci() {
	local a c
	local -F1 b
	a=0 ; b=1
	print $a
	repeat 100
	do
		print "${b%.*}"
		c=$a
		a=$b
		((b = c + b))
	done
}