| 12345678910111213141516171819202122232425262728293031323334 |
- #!/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)
|
