Computing Fibonacci in Crystal

dynamic_output.md

DYNAMIC

AMD A10-4600M APU with Radeon(tm) HD Graphics × 4)

                    user     system      total        real
fib 1000        0.000000   0.000000   0.000000 (  0.001114)
fib 10000       0.010000   0.000000   0.010000 (  0.016190)
fib 100000      0.640000   0.090000   0.730000 (  0.564936)
fib 500000      14.650000   3.230000   17.880000 (  12.655379)
fib 1000000     56.280000   10.130000   66.410000 (  46.374916)
fib 10000000    5986.610000   324.110000   6310.720000 (  4540.387823)
fib 100000000 ^C

Based on the above numbers, each 10x call takes approximately 100x longer than the previous call, so fib 100_000_000 was cancelled as I estimated it would take ~125 hours to complete and to calculate the billionth (1_000_000_000) would take 520 days.

fast_doubling_memory.md

FAST DOUBLING

• output of /usr/bin/time --verbose for 1 billionth fibonacci number (1_000_000_000)
• Approx 1.7GB memory usage

Command being timed: "./fib 1000000000"
User time (seconds): 210.59
System time (seconds): 1.22
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 3:31.99
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 1805360
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 450758
Voluntary context switches: 396
Involuntary context switches: 22382
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

fast_doubling_output.md

FAST DOUBLING

AMD A10-4600M APU with Radeon(tm) HD Graphics × 4

                              user     system      total        real
FastDoubling 1            0.000000   0.000000   0.000000 (  0.000160)
FastDoubling 10           0.000000   0.000000   0.000000 (  0.000019)
FastDoubling 1000         0.000000   0.000000   0.000000 (  0.000049)
FastDoubling 10000        0.000000   0.000000   0.000000 (  0.000559)
FastDoubling 100000       0.000000   0.000000   0.000000 (  0.002293)
FastDoubling 1000000      0.050000   0.000000   0.050000 (  0.049490)
FastDoubling 10000000     0.790000   0.010000   0.800000 (  0.801583)
FastDoubling 100000000    13.720000   0.070000   13.790000 (  13.834820)
FastDoubling 1000000000   209.510000   1.060000   210.570000 (  210.421864)

Number of digits in nth Fibonacci numbers 1: 1 10: 2 1000: 209 10000: 2090 100000: 20899 1000000: 208988 10000000: 2089877 100000000: 20898764 1000000000: 208987640

fib.cr

require "benchmark"
require "big/big_int"

# http://stackoverflow.com/q/33533830
def dynamic(n : BigInt)
  zero = BigInt.new
  
  return n if n == zero
  
  a = zero
  b = BigInt.new 1
  c = nil
  two = BigInt.new 2

  (two..n).each do
    c = a + b

    a = b
    b = c
  end

  c
end

# https://www.nayuki.io/page/fast-fibonacci-algorithms
module FastDoubling
  ZERO = BigInt.zero
  ONE = BigInt.new 1
  TWO = BigInt.new 2

  def self.calculate(n)
    i = BigInt.new n
    _fib(i).first
  end

  def self._fib(n : BigInt)
    return [ZERO, ONE] if n == ZERO

    a, b = _fib(n / TWO)
    c = a * (b * TWO - a)
    d = a * a + b * b

    if n % TWO == ZERO
      [c, d]
    else
      [d, c + d]
    end
  end
end

nums = [1, 10, 1000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000]
total_digits = Array(Int32).new

Benchmark.bm do |b|  
  nums.each do |i|
    b.report("FastDoubling #{i}") {
      num = FastDoubling.calculate i
      total_digits.push(num.to_s.size)
    }
  end
end

nums.zip(total_digits).each do |pair|
  i, len = pair
  puts "#{i}: #{len}"
end