/
fibonacci_k-th_order_efficient_algorithm.sf
79 lines (65 loc) · 2.69 KB
/
fibonacci_k-th_order_efficient_algorithm.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#!/usr/bin/ruby
# Daniel "Trizen" Șuteu
# Date: 24 January 2019
# https://github.com/trizen
# Generalized efficient formula for computing the k-th order Fibonacci numbers, using exponentation by squaring.
# OEIS sequences:
# https://oeis.org/A000045 (2-nd order: Fibonacci numbers)
# https://oeis.org/A000073 (3-rd order: Tribonacci numbers)
# https://oeis.org/A000078 (4-th order: Tetranacci numbers)
# https://oeis.org/A001591 (5-th order: Pentanacci numbers)
# See also:
# https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers
# https://en.wikipedia.org/wiki/Exponentiation_by_squaring
# Example of Fibonacci matrices for k=2..4:
#
# A_2 = Matrix(
# [0, 1],
# [1, 1]
# )
#
# A_3 = Matrix(
# [0, 1, 0],
# [0, 0, 1],
# [1, 1, 1]
# )
#
# A_4 = Matrix(
# [0, 1, 0, 0],
# [0, 0, 1, 0],
# [0, 0, 0, 1],
# [1, 1, 1, 1]
# )
# Let R = (A_k)^n.
# The n-th k-th order Fibonacci number is the last term in the first row of R.
func fibonacci_matrix(k) is cached {
Matrix.build(k,k, {|i,j|
((i == k-1) || (i == j-1)) ? 1 : 0
})
}
func modular_fibonacci_kth_order(n, k, m) {
var A = fibonacci_matrix(k)
(A.powmod(n, m))[0][-1]
}
func fibonacci_kth_order(n, k=2) {
var A = fibonacci_matrix(k)
(A**n)[0][-1]
}
for k in (2..6) {
say ("Fibonacci of k=#{k} order: ", (15+k).of { fibonacci_kth_order(_, k) })
}
say ''
for k in (2..6) {
say ("Last n digits of 10^n #{k}-order Fibonacci numbers: ", 10.of { modular_fibonacci_kth_order(10**_, k, 10**_) })
}
__END__
Fibonacci of k=2 order: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
Fibonacci of k=3 order: [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768]
Fibonacci of k=4 order: [0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671]
Fibonacci of k=5 order: [0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624]
Fibonacci of k=6 order: [0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109]
Last n digits of 10^n 2-order Fibonacci numbers: [0, 5, 75, 875, 6875, 46875, 546875, 546875, 60546875, 560546875]
Last n digits of 10^n 3-order Fibonacci numbers: [0, 1, 58, 384, 1984, 62976, 865536, 2429440, 86712832, 941792256]
Last n digits of 10^n 4-order Fibonacci numbers: [0, 6, 96, 160, 1792, 92544, 348928, 6868608, 41256704, 824732160]
Last n digits of 10^n 5-order Fibonacci numbers: [0, 1, 33, 385, 1025, 69921, 360833, 4117505, 34469121, 304605953]
Last n digits of 10^n 6-order Fibonacci numbers: [0, 6, 4, 925, 3376, 93151, 642996, 3541264, 38339728, 425978989]