fibonacci_first_and_last_k_digits.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 01 February 2020
# https://github.com/trizen

# Efficient algorithm for computing the first and last k digits of the n-th Fibonacci number.

# This approach uses Binet's formula for computing the first k digits, and modular arithmetic for computing the last k digits.

# See also:
#   https://en.wikipedia.org/wiki/Fibonacci_number
#   https://rosettacode.org/wiki/Fibonacci_matrix-exponentiation

# Based on the following identities (where b is the base):
#   f / exp(log(b)*floor(log(f) / log(b) + 1)) = exp(log(f) - log(b)*floor(log(f) / log(b) + 1))
#                                              = b^(-1 - floor(log(f^(1/log(b))))) * f
#                                              = exp(log(b)*(-1 - floor(log(f) / log(b))) + log(f))

func binet_log_approx(n) {
    const PHI =  (1.25.sqrt + 0.5)
    const IHP = -(1.25.sqrt - 0.5)
    (log(PHI)*n - log(PHI-IHP))
}

func nth_fib_first_k_digits(n,k) {
    var f = binet_log_approx(n)
    floor(10**k * exp(f - log(10)*floor(f/log(10) + 1)))
}

func nth_fib_last_k_digits(n,k) {
    fibmod(n, 10**k)
}

with (20) {|k|
    for n in (16, 32, 64) {
        var first_k = nth_fib_first_k_digits(2**n, k)
        var last_k  = nth_fib_last_k_digits(2**n, k)
        say "F(2^#{n}) = #{first_k} ... #{last_k}"
    }
}

__END__
F(2^16) = 73199214460290552832 ... 97270190955307463227
F(2^32) = 61999319689381859818 ... 39623735538208076347
F(2^64) = 11175807536929528424 ... 17529800348089840187