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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/// Very fast recursive calculation of an individual Fibonacci number
/// using the matrix squaring technique.
/// This example is by courtesy of Gemini AI. For F100,000 this is the
/// fastest individual calculation, 3-4 times faster than the doubling
/// method, and about 10 times faster than the classic iteration. For
/// F1,000,000 to F10,000,000 it's overtaken by the doubling method.
/// These are not formal benchmarks and your mileage may vary. Besides,
/// these are only demo scripts and come with no guarantees.
///
/// Aside from the imports, this script is interchangeable with `demo/fib_matrix_ibig.rs`
/// and performance on my setup was very similar. However, `dashu` is
/// not confined to integers but also supports floating point and rational
/// numbers.
///
/// See https://en.wikipedia.org/wiki/Fibonacci_sequence.
/// F0 = 0, F1 = 1, Fn = F(n-1) + F(n-2) for n > 1.
///
//# Purpose: Demo a very fast precise computation for large individual Fibonacci numbers.
//# Categories: big_numbers, learning, math, recreational, technique
//# Sample arguments: `-- 100`
use dashu::ubig;
use dashu::integer::UBig;
use std::env;
use std::time::Instant;
fn fibonacci_matrix(n: u128) -> UBig {
if n <= 1 {
return UBig::from(n);
}
let mut a = [[ubig!(1), ubig!(1)], [ubig!(1), ubig!(0)]];
let mut result = [[ubig!(1), ubig!(0)], [ubig!(0), ubig!(1)]];
// Efficient exponentiation using repeated squaring
let mut power = n - 1;
while power > 0 {
if power & 1 == 1 {
result = multiply_matrices(result.clone(), a.clone());
}
power >>= 1;
a = multiply_matrices(a.clone(), a.clone());
}
return result[0][0].clone();
}
fn multiply_matrices(a: [[UBig; 2]; 2], b: [[UBig; 2]; 2]) -> [[UBig; 2]; 2] {
let mut result: [[UBig; 2]; 2] = [[ubig!(0), ubig!(0)], [ubig!(0), ubig!(0)]];
for i in 0..2 {
for j in 0..2 {
for k in 0..2 {
result[i][j] += a[i][k].clone() * b[k][j].clone();
}
}
}
return result;
}
let args: Vec<String> = env::args().collect();
if args.len() != 2 {
eprintln!("Usage: {} <n>, where 0 <= n", args[0]);
std::process::exit(1);
}
let msg = "Please provide a positive integer";
let n: u128 = args[1].parse().expect(msg);
let n_disp = n
.to_string()
.as_bytes()
.rchunks(3)
.rev()
.map(std::str::from_utf8)
.collect::<Result<Vec<&str>, _>>()
.unwrap()
.join(",");
let start = Instant::now();
let fib_n = fibonacci_matrix(n);
let dur = start.elapsed();
println!("Done! in {}.{}s", dur.as_secs(), dur.subsec_millis());
let fib_n_str = fib_n.to_string();
let l = fib_n_str.len();
if l <= 100 {
println!("F({n_disp}) len = {l}, value = {fib_n_str}");
} else {
println!(
"F({n_disp}) len = {l}, value = {} ... {}",
&fib_n_str[0..20],
fib_n % (ubig!(10).pow(20))
);
}