fibonacci_first_k_digits_in_base_b.sf

#!/usr/bin/ruby

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

# Efficiently compute the first k digits (in base b) of the n-th Fibonacci number, using Binet's formula.

# 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 f(n) {
    n*log((1+sqrt(5))/2) - log(5)/2
}

func nth_fib_first_k_digits(n,k,b=10) {
    int(b**(k-1) * exp(f(n) - log(b)*floor(f(n)/log(b))))
}

for k in (16, 32, 64) {
    printf("First 20 digits of F(2^#{k}) = %s (base 10) = %s (base 7)\n", nth_fib_first_k_digits(2**k, 20), nth_fib_first_k_digits(2**k, 20, 7).base(7))
}

__END__
First 20 digits of F(2^16) = 73199214460290552832 (base 10) = 14145222604233421263 (base 7)
First 20 digits of F(2^32) = 61999319689381859818 (base 10) = 63461236402304653504 (base 7)
First 20 digits of F(2^64) = 11175807536929528424 (base 10) = 11322264102105626133 (base 7)