fibonacci_number_fast.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 19 June 2018
# https://github.com/trizen

# A very efficient algorithm for computing the nth-Fibonacci number.

func fibonacci_number(n) {

    var (f, g) = (0, 1)
    var (a, b) = (0, 1)

    for k in (0 .. n.ilog2) {
        (f, g) = (f*a + g*b, f*b + g*(a+b)) if n.getbit(k)
        (a, b) = (a*a + b*b, a*b + b*(a+b))
    }

    return f
}

say fibonacci_number(100)       #=> 354224848179261915075
say 15.of(fibonacci_number)     #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]