Fibonacci sequence
From CodeCodex
| Image:Lightbulb.png Related content: |
| <DPL>
category=Math shownamespace=false </DPL> |
Source code for calculation of the Fibonacci sequence.
Contents |
[edit] 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)
[edit] 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
[edit] 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.*/
[edit] C
#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;
}
[edit] C++
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;
}
[edit] 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();
}
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();
[edit] 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))
[edit] 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)));
}
}
}
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));
}
}
[edit] Common Lisp
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)
[edit] Matlab
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;
[edit] 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
[edit] 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);; 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>
[edit] 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";
}
[edit] PHP
<?php
$a = 0;
$b = 1;
for ($i = 2; $i < 100; $i++) {
echo "$b\n";
list($a, $b) = array($b, $a+$b);
}
?>
[edit] PowerShell
$c=$p=1;$c;$p;while($c -le 100){$c,$p=($c+$p),$c;$c}
[edit] 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.
#!/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
[edit] Ruby
#!/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
[edit] Scheme
(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)))))
[edit] 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;
[edit] Zsh
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
}
