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
|
use num_bigint::{BigUint, ToBigUint};
/// Returns (fib(n-1), fib(n), fib(n+1))
fn fib_helper(n: u64) -> [BigUint; 3] {
let [fm1, f0, f1] = if n == 0 {
[
1.to_biguint().unwrap(),
0.to_biguint().unwrap(),
1.to_biguint().unwrap(),
]
} else {
fib_helper2(n / 2)
};
if n % 2 == 1 {
let [mut fm2, fm1, f0] = [fm1, f0, f1];
fm1.clone_into(&mut fm2);
let f1 = fm2 + &f0;
[fm1, f0, f1]
} else {
[fm1, f0, f1]
}
}
/// Returns (fib(2n-1), fib(2n), fib(2n+1))
fn fib_helper2(n: u64) -> [BigUint; 3] {
let [fm1, fp0, fp1] = fib_helper(n);
// f2m1 = fm1^2 + fp0^2
// f2p0 = fp1*fp0 + fp0*fm1 = fp0*(fp1+fm1)
// f2p1 = fp1^2 + fp0^2
let f2p0 = (fp1.clone() + &fm1) * &fp0;
let fp0sqr = fp0.pow(2);
let f2m1 = fm1.pow(2) + &fp0sqr;
let f2p1 = fp1.pow(2) + fp0sqr;
[f2m1, f2p0, f2p1]
}
pub fn fib(n: u64) -> BigUint {
let [_, res, _] = fib_helper(n);
res
}
|
