fib.rb

##  INSPIRED BY: Eigenvectors and eigenvalues | Essence of linear algebra, chapter 10
##               https://www.youtube.com/watch?v=PFDu9oVAE-g&feature=youtu.be&t=16m28s

require 'bigdecimal'

def fib(n, accuracy = 100)
  n = BigDecimal.new(n - 1)
  accuracy = 10 if n < 80
  sqrt5 = BigDecimal.new(5).sqrt(accuracy)  # sqrt(p1) - Returns the square root of the value. If p1 is specified, returns at least that many significant digits.
  # Where all the 'magic' happens:
  ((1/sqrt5)*2**(-1-n)*(-(1-sqrt5)**(1+n)+(1+sqrt5)**(1+n))).round
end


(0..131).each do |n|
  puts "Fib(#{n}) = #{fib(n)}"
end
puts "Fib(1031) = #{fib(1031, 250)}"

fib_1031 = 130849508466328924086396609314991822658318068098198850936734860838436447101528196708357662666934856206891799743896814704094667037241134911338394669074522683565119982450075882603244949183101644660834894801525501042769
puts "Fib(1031) = #{fib_1031}"

fib2.rb

##  INSPIRED BY: Eigenvectors and eigenvalues | Essence of linear algebra, chapter 10
##               https://www.youtube.com/watch?v=PFDu9oVAE-g&feature=youtu.be&t=16m28s

require 'bigdecimal'

class FibonacciSolver
  SQRT5_DEFAULT_ACCURACY = 100

  def initialize
    @sqrt5 = {}
    @sqrt5.default_proc = -> (h, k) { h[k] = BigDecimal.new(5).sqrt(k) } # sqrt(p1) - Returns the square root of the value. If p1 is specified, returns at least that many significant digits.
  end

  def fib(n, accuracy = SQRT5_DEFAULT_ACCURACY)
    n = BigDecimal.new(n - 1)
    accuracy = 10 if n < 80
    sqrt5 = @sqrt5[accuracy]
    # Where all the 'magic' happens:
    ((1/sqrt5)*2**(-1-n)*(-(1-sqrt5)**(1+n)+(1+sqrt5)**(1+n))).round
  end

  def [](n)
    fib(n)
  end

end



###########################################################################################
## BTW:
##  fib(n) = (phi^(n+1) - (1-phi)^(n+1)) / sqrt(5)
##  where phi is the golden ratio
##  source: http://mathforum.org/library/drmath/view/51448.html
##  see also: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

class FibonacciSolver2
  DEFAULT_ACCURACY = 100

  def initialize
    @sqrt5 = {}
    @sqrt5.default_proc = -> (h, k) { h[k] = BigDecimal.new(5).sqrt(k) } # sqrt(p1) - Returns the square root of the value. If p1 is specified, returns at least that many significant digits.
    @phi = {}
    @phi.default_proc = -> (h, k) { h[k] = golden_ratio(k) }
  end

  def golden_ratio(n)
    g = BigDecimal.new(1)
    one = BigDecimal.new(1)
    n.times { g = one + one/g}
    g
  end

  def fib(n, accuracy = DEFAULT_ACCURACY)
    n = BigDecimal.new(n - 1)
    accuracy = 10 if n < 20
    sqrt5 = @sqrt5[accuracy]
    phi = @phi[accuracy]
    # Where all the 'magic' happens:
    ((phi**(n+1) - (1-phi)**(n+1)) / sqrt5).round
  end
  
  def [](n)
    fib(n)
  end
  
end


############################################################################
## Classical Fib Solver

class FibonacciSolver3

  def initialize
    @fib = {}
    @fib.default_proc = -> (h, k) { h[k] = calc_fib(k) }
  end

  def calc_fib(n)
    return 1 if n <= 2
    @fib[n-2] + @fib[n-1]
  end

  def fib(n)
    @fib[n]
  end
  alias_method :[], :fib

end

fib_bench.rb

require_relative 'fib2'
require 'benchmark'

matrix_fib = FibonacciSolver.new
phi_fib = FibonacciSolver2.new
classical_fib = FibonacciSolver3.new

range = (0..80)

Benchmark.bm do |bm|

  bm.report("Classical Fib") do
   range.each {|n| classical_fib[n] }
  end

  bm.report("Matrix Fib") do
    range.each {|n| matrix_fib[n] }
  end
  
  bm.report("Phi Fib") do
    range.each {|n| phi_fib[n] }
  end

end


######################################################/
### OUTPUT ##########################################/
####################################################/

## For range = 50..100
##                  user     system      total        real
## Classical Fib  0.000000   0.000000   0.000000  (  0.000092)
## Matrix Fib     0.250000   0.000000   0.250000  (  0.241825)
## Phi Fib        93.130000  0.000000   93.130000 ( 93.143885)

## For range = 50..100
##                   user     system      total        real
## Classical Fib  0.000000   0.000000   0.000000  (  0.001044)
## Matrix Fib     84.210000  0.000000   84.210000 ( 84.214235)
## Phi Fib                   TOO SLOW

## For range = 10000..10050
##
## Classical Fib  stack level too deep (SystemStackError)
## Matrix Fib                TOO SLOW
## Phi Fib                   TOO SLOW

## For range = 50..10050
##
##                   user     system      total        real
## Classical Fib  0.010000   0.000000   0.010000 (  0.016677)
## Matrix Fib                TOO SLOW
## Phi Fib                   TOO SLOW

## For range = 0..1_000_000
##
## Classical Fib[1]    4762 killed     ruby fib_bench.rb

z_fib.cpp

// g++ --std=c++11 fib.cpp -o fib -l gmp && time ./fib

#include <iostream>
#include <unordered_map>
#include <boost/multiprecision/number.hpp>
#include <boost/multiprecision/gmp.hpp>

#define PRECISION 90000

namespace mp = boost::multiprecision;
typedef unsigned long ulong;
typedef mp::mpz_int prec_int_t;
typedef mp::number<mp::gmp_float<PRECISION>> prec_float_t;
typedef std::unordered_map<ulong, prec_int_t> cache_t;


// Recursive Fib (+ memoization) //
prec_int_t rfib_find_or_calc(ulong n, cache_t* cache);

prec_int_t rfib(ulong n, cache_t* cache) {
  if(n <= 2) return 1;
  prec_int_t result = rfib_find_or_calc(n-2, cache) + rfib_find_or_calc(n-1, cache);
  cache->emplace(n,result);
  return result;
}

prec_int_t rfib_find_or_calc(ulong n, cache_t* cache) {
  cache_t::const_iterator iter = cache->find(n);
  if(iter == cache->end()) return rfib(n, cache);
  else return iter->second;
}

// Iterative Fib //
prec_int_t ifib(ulong n) {
  if(n <= 2) return 1;

  prec_int_t a = 1;
  prec_int_t b = 1;
  prec_int_t c = 0;
  ulong i = 0;

  while(i < n-2) {
    c = a + b;
    a = b;
    b = c;
    i++;
  }

  return c;
}

// Matrix Fib //
prec_float_t mfib(ulong in) {
  prec_float_t n = in-1;
  prec_float_t sqrt5 = sqrt((prec_float_t)5);
  return round((1/sqrt5)*pow(2,-1-n)*(-pow(1-sqrt5,1+n)+pow(1+sqrt5,1+n)));
}


int main() {
    cache_t* cache = new cache_t();


    //for(ulong i=1; i <= 1000000; i+= 10) {
    //  std::cout << "Fib(" << i << ")" << std::endl;
    //  rfib(i, cache);
    //}

    //for(ulong i=1000000; i <= 1000003; i++)
      //std::cout << "Fib(" << i << ") = " << ifib(i) << std::endl;

    //   T* G* M* k*  *
    //ulong n = 2000000;
    //std::cout << "Fib(" << n << ") = " << ifib(n) << std::endl;

    // T* G* M* k*  *
    ulong n = 239500;
    //std::cout << "iFib(" << n << ") = " << ifib(n) << std::endl;
    std::cout << "mFib(" << n << ") = " << mfib(n).str(0, std::ios_base::dec) << std::endl;


    delete cache;
    return 0;
}


// 
// == MATRIX FIB - Fib(239500) ==
// ./fib  87,79s user 0,52s system 99% cpu 1:28,34 total
// ./fib  87,93s user 0,52s system 99% cpu 1:28,49 total
// ./fib  87,82s user 0,51s system 99% cpu 1:28,38 total
// 
// == ITERATIVE FIB - Fib(239500) ==
// ./fib  0,50s user 0,00s system 94% cpu 0,526 total
// ./fib  0,48s user 0,00s system 94% cpu 0,515 total
// ./fib  0,47s user 0,00s system 92% cpu 0,507 total
//

z_fib.go

package main
import (
  "fmt"
  "math/big"
)


func main() {
  for i := 0; i<10 ; i++ {
    fmt.Println(Fib(int64(i)))
  }
}

// INCORRECT fib
func Fib(n int64) *big.Int {
  if n <= 2 { return big.NewInt(1) }

  a, b, c, i := big.NewInt(1), big.NewInt(1), big.NewInt(0), int64(0)
  for i < n-2 {
    c.Add(a,b)
    a = b
    b = c
    i++
  }
  return c
}

z_fib.hs

import Data.List
import Data.Bits


fib :: Int -> Integer
fib n = snd . foldl_ fib_ (1, 0) . dropWhile not $
            [testBit n k | k <- let s = bitSize n in [s-1,s-2..0]]
    where
        fib_ (f, g) p
            | p         = (f*(f+2*g), ss)
            | otherwise = (ss, g*(2*f-g))
            where ss = f*f+g*g
        foldl_ = foldl' -- '


n = 239500
main = putStrLn $ "Fib(" ++ show n ++ ") = " ++ (show $ fib n)


-- Fib(239500)
-- ./fib  0,01s user 0,00s system 31% cpu 0,039 total
-- ./fib  0,01s user 0,00s system 38% cpu 0,041 total
-- ./fib  0,01s user 0,00s system 40% cpu 0,039 total

z_fib.java

import java.math.BigInteger;


public class Fib {
  public static void main(String[] args) {
    //for(int i = 0; i < 10; i++)
      System.out.println( "Fib(" + 2395000 + ") = " + fib(2395000) );
  }

  public static BigInteger fib(long n) {
    if(n <= 2) return BigInteger.ONE;
    
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ONE;
    BigInteger c = BigInteger.ZERO;
    long i = 0;

    while(i < n-2) {
      c = a.add(b);
      a = b;
      b = c;
      i++;
    }
    
    return c;
  }
}

z_fib.nell

# Obliczanie ciągu Fibonacciego
program fib

out "Ile liczb z ciągu Fibonacciego chcesz policzyć ??\n> ";
read n;
outln;

set a = 0;
set b = 1;
set t = 0;

for i in 0..n-1
  set t=a;
  set a=b;
  set b=b+t;
  
  outln 1+i+") " + a;
end

z_fib2.cpp

// source: http://codeforces.com/blog/entry/14516

#include <map>
#include <iostream>
#include <boost/multiprecision/number.hpp>
#include <boost/multiprecision/gmp.hpp>

namespace mp = boost::multiprecision;
typedef mp::mpz_int pint;

std::map<pint, pint> F;

pint fib(pint n) {
  if (F.count(n)) return F[n];
  pint k=n/2;
  if(n%2==0) // n=2*k
    return F[n] = (fib(k)*fib(k) + fib(k-1)*fib(k-1));
	else // n=2*k+1
    return F[n] = (fib(k)*fib(k+1) + fib(k-1)*fib(k));
}

int main() {
  F[0]=F[1]=1;
  std::cout << fib(23950000) << std::endl;
  return 0;
}


// ...169342224240764503343429743913319617691376327751679317949014711656271795896233081546862838763447663597783713254849773990260046181980900079615349661327732333166890299516640330299524448446808340986820369979942578892764466511947978425913874640397405914806048671538949072463906296749501523826623633490001001803697628829582033984925550441267816746493304482155177755554577006042393505317289950581502201334756843257472205063132545373059044768725151609636466221603390786155139857549360393329299125381993168530421038861748702000038960204508197822497311570818872799680000775301589567542531549761475431185092350359606591521099812270786739469443787471178416407346554098938490693341866907675957912130142779004843279440605851460212530681525111032012794601285828387894955220805433603845483860705446010230939984079474152345910816463430626946771149340332112865067787355763480887365857796188938198968620780189141477827792033571384273828517631871586142083824805965218616053017515475223227732512544359158156349027783247992914742449051612098789755577713917177684489269299671625697021581779142051519048986356339088021637501