Fibonacci number benchmark

fibonacci.js

// fibonacci(40) takes 2 seconds in Node.js 0.6.14

// http://en.wikipedia.org/wiki/Fibonacci_number

function fibonacci(n) {
  return n < 2 ? n : fibonacci(n-2) + fibonacci(n-1);
}

fibonacci.php

// fibonacci(40) takes 60 seconds in PHP 5.4.0
// fibonacci(40) takes 21 seconds in PHP 7

function fibonacci($n) {
  return $n < 2 ? $n : fibonacci($n-2) + fibonacci($n-1);
}

fibonacci.py

# fibonacci(40) takes 42 seconds in Python 3.2.2

def fibonacci(n):
	return n if n < 2 else fibonacci(n-1) + fibonacci(n-2)

fibonacci.ruby

# fibonacci(40) takes 18 seconds in Ruby 1.9.3

def fibonacci(n)
  n < 2 ? n : fibonacci(n-1) + fibonacci(n-2)
end

Správny algoritmus v pomalšom jazyku vie byť aj 30x rýchlejší ako hovadina trebárs aj v C.

// fibonacci.c
#include <stdio.h>

int fibonacci(int n) {
    return n < 2 ? n : fibonacci(n-2) + fibonacci(n-1);
}

int main() {
    printf("%d", fibonacci(40));
}

# fibonacci.rb
Q = Math.sqrt(5) / 2

def fibonacci(n)
  (1/(2*Q) * ((0.5 + Q)**n - (0.5 - Q)**n)).to_i
end


puts fibonacci(40)

$ time ./fibonacci
102334155./fibonacci  1.03s user 0.00s system 99% cpu 1.034 total

$ time ruby fibonnaci.rb
102334155
ruby fibonnaci.rb  0.03s user 0.01s system 97% cpu 0.037 total

PS. Je mi jasné, že tu ide skôr o rýchlosť jazyka pri rekurzívnych volaniach, ale ja som to nenazval "Fibonacci number benchmark" :D

Ked uz sa chceme precuravat, zvysil som N na 80 :)

#include <cstdio>

int main() {
  long long a = 0, b = 1;
  for (int i = 2; i <= 80; i++) {
    long long c = a + b; a = b; b = c;
  }
  printf("%lld\n", b);
} 

$ time ./a.out 
23416728348467685

real    0m0.002s
user    0m0.000s
sys     0m0.000s

Tvoje ruby hlavne uz neda spravny vysledok :):

$time ruby fib.rb
23416728348467744

real    0m0.021s
user    0m0.017s
sys     0m0.003s

Fakt O(log N) algoritmus, co umocnuje matice sa mi teraz pisat nechce. Zvlast ked pre male N je uplne nezmyselny, ze ;)

Nakoniec aj umocnovanie matic:

def zero(m,n):                                                                                  
    # Create zero matrix                                                                        
    new_matrix = [[0 for row in range(n)] for col in range(m)]                                  
    return new_matrix                                                                           

def mult(matrix1,matrix2):                                                                      
    # Matrix multiplication                                                                     
    if len(matrix1[0]) != len(matrix2):                                                         
        # Check matrix dimensions                                                               
        print 'Matrices must be m*n and n*p to multiply!'                                       
        print len(matrix1[0])                                                                   
        print len(matrix2)                                                                      
    else:                                                                                       
        # Multiply if correct dimensions                                                        
        new_matrix = zero(len(matrix1),len(matrix2[0]))                                         
        for i in range(len(matrix1)):                                                           
            for j in range(len(matrix2[0])):                                                    
                for k in range(len(matrix2)):                                                   
                    new_matrix[i][j] += matrix1[i][k]*matrix2[k][j]                             
        return new_matrix                                                                       

base = [[1, 1], [1, 0]]                                                                         

n = 100000                                                                                      

res = [[1, 0], [0, 1]]                                                                          

while n > 0:                                                                                    
  if n % 2 == 1:                                                                                
    res = mult(res, base)                                                                       
  base = mult(base, base)                                                                       
  n /= 2                                                                                        

print res[0][1] 

$ time python2.7 mm.py >x

real    0m0.070s
user    0m0.063s
sys     0m0.003s

V porovnani s obycajnym ratanim:

n = 100000

a = 0
b = 1

for i in xrange(2, n+1):
  c = a + b
  a = b
  b = c 

print b 

$ time python2.7 fib.py >y

real    0m0.260s
user    0m0.253s
sys     0m0.003s

Tvoj ruby kod spravi pre 100000 nasledovne:

$ time ruby fib.rb >z
fib.rb:5:in `to_i': Infinity (FloatDomainError)
        from fib.rb:5:in `fibonacci'
        from fib.rb:9:in `<main>'

real    0m0.024s
user    0m0.017s
sys     0m0.007s

@usamec: Ok beriem, ale stale to este neni uplne ono. http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms

O com mi vsak slo naozaj. Microbenchmarky a porovnavanie rychlosti jazykov su podla mna zlo, lebo ten cas co usetris na rychlosti kodu, nehra vo vacsine aplikacii ziadnu vyznamnu rolu. Lepsim algoritmom ziskas mnohonasobne viac.

@jsuchal to zní, jako by jsi chtěl říct, že použitý algoritmus není správný, nebo je snad dokonce hovadina. Nedává snad správné výsledky?

@jsuchal: :)

@dg: Ratat fib. cisla cez rekurziu je mega hovadina (keby si to spravil niekde mimo benchmarku) :). Na druhej strane ako test rychlosti rekurzie je to asi najlepsie co ma napada.

@dg Algoritmus je správny (ten vzorec si vieš vypočítať a overiť na papieri). Problém, ktorý vznikol je realizácia pre čísla s konečnou presnosťou. A áno, nedáva to teda pre vyššie čísla správne výsledky.