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
/// Fast non-recursive Fibonacci series and individual calculation with big integers.
/// Won't work with default Windows 11 because of `rug` crate.
///
/// See https://en.wikipedia.org/wiki/Fibonacci_sequence.
/// F0 = 0, F1 = 1, Fn = F(n-1) + F(n-2) for n > 1.
///
/// The `fib_series` closure could equally be implemented as a function here,
/// but closure is arguably easier as you don't have to know or figure out the
/// exact return type (`impl Iterator<Item = Integer>` if you're wondering).
///
/// Using `clap` here is complete overkill, but this is just a demo.
/// On Linux you may need to install the m4 package.
///
/// **Not compatible with Windows MSVC.**
///
/// The `rug` crate runs blindingly fast, but be aware the rug dependency `gmp-mpfr-sys` may
/// take several minutes to compile on first use or a version change.
///
//# Purpose: Demonstrate snippets, closures, `clap` builder and a fast non-recursive fibonacci algorithm using the `successors`.
//# Categories: big_numbers, learning, math, recreational, technique
//# Sample arguments: `-- 100`
use clap::{Arg, Command};
use rug::Integer;
use std::iter::{successors, Successors, Take};
let matches = Command::new("fib_big_clap_rug")
.arg(
Arg::new("number")
.help("The numeric value to process")
.required(true)
.index(1),
)
.get_matches();
// Extract the parsed usize value
let n: usize = matches
.get_one::<String>("number")
.unwrap()
.parse::<usize>()
.unwrap();
// Snippet accepts function or closure. This closure returns only the last value Fn.
fn fib_value_n(n: usize) -> Integer {
successors(Some((Integer::from(0), Integer::from(1))), |(a, b)| Some((b.clone(), (a + b).into())))
.map(|(a, b): (Integer, Integer)| a)
.nth(n)
.unwrap()
}
// Same formula, but we return the whole series from F0 to Fn. Using a closure is
// easier than a function in this case, as we don't have to bother specifying the
// return type `Take<Successors<Integer, _>>` nor do we need braces since the
// closure contains only one statement and the return type is not specified.
// If you want all values in the series, using this version is much more efficient
// than repeatedly calling fn `fib_value_n`. Obvious maybe, but easily overlooked.
let fib_series = |n: usize|
successors(Some((Integer::from(0), Integer::from(1))), |(a, b)| Some((b.clone(), (a + b).into())))
.map(|(a, _b)| a)
.take(n + 1);
// Manually working out the series in debug mode to check our work
#[cfg(debug_assertions)]
let (mut x, mut y) = (Integer::from(0), Integer::from(1));
let mut i = 0;
let mut fib_series_n = Integer::from(0);
for a in fib_series(n) {
#[cfg(debug_assertions)]
{
assert_eq!(x, a);
(x, y) = (y.clone(), x + y);
}
println!("Fibonacci F({i}) is {a}");
if i == n {
fib_series_n = a;
}
i += 1;
}
// Note that because of the different signatures, fib_series only calculates the series 0..=n once,
// while fib_value_n has to calculate o..=i from scratch for each i.
assert_eq!(fib_value_n(i - 1), fib_series_n);