Fibonacci in Python and Ruby

fib.py

import timeit
from typing import Tuple

def naive_fib(n: int) -> int:
    if n <= 1: # n == 0 or n == 1
        return n
    else:
        return naive_fib(n - 1) + naive_fib(n - 2)

print(naive_fib(20))

def linear_fib(n: int) -> int:
    a = 0
    b = 1
    for _ in range(n):
        # a, b = b, a + b
        c = a + b
        a = b
        b = c
    return a

print(linear_fib(20))
print(linear_fib(10000))

# see https://blog.miz-ar.info/2019/01/fast-fibonacci/
def fast_doubling(n: int) -> Tuple[int, int]:
    if n <= 1: # n == 0 or n == 1
        return n, 1
    else:
        a, b = fast_doubling(n // 2)
        if n % 2 == 0:
            return a * (b + b - a), a * a + b * b
        else:
            return a * a + b * b, b * (a + a + b)

def fast_fib(n: int) -> int:
    return fast_doubling(n)[0]

print(fast_fib(10000))

print("naive_fib@20*100", timeit.timeit(lambda: naive_fib(20), number=100))
print("linear_fib@20*100", timeit.timeit(lambda: linear_fib(20), number=100))
print("linear_fib@10000*10000", timeit.timeit(lambda: linear_fib(10000), number=10000))
print("fast_fib@10000*10000", timeit.timeit(lambda: fast_fib(10000), number=10000))

fib.rb

require 'benchmark'

def naive_fib(n)
  if n <= 1
    n
  else
    naive_fib(n - 1) + naive_fib(n - 2)
  end
end

puts(naive_fib(20))

def linear_fib(n)
  a = 0
  b = 1
  n.times do
    # a, b = b, a + b
    c = a + b
    a = b
    b = c
  end
  a
end

puts(linear_fib(20))
puts(linear_fib(10000))

Benchmark.bmbm do |x|
  x.report("naive_fib@20*100") { 100.times do naive_fib(20) end }
  x.report("linear_fib@20*100") { 100.times do linear_fib(20) end }
end

# see https://blog.miz-ar.info/2019/01/fast-fibonacci/
def fast_doubling(n)
  if n <= 1
    return n, 1
  else
    a, b = fast_doubling(n/2)
    if n % 2 == 0
      return a * (b + b - a), a * a + b * b
    else
      return a * a + b * b, b * (a + a + b)
    end
  end
end

def fast_fib(n)
  fast_doubling(n)[0]
end

puts(fast_fib(10000))

Benchmark.bmbm do |x|
  x.report("linear_fib@10000*10000") { 10000.times do linear_fib(10000) end }
  x.report("fast_fib@10000*10000") { 10000.times do fast_fib(10000) end }
end