Calculate the Fibonacci sequence
From CodeCodex
Source code for calculation of the Fibonacci sequence.
Contents
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 }