fib_sequence/fibonacci/
get.rs

1use super::Number;
2
3pub fn nth(n: u32) -> String {
4
5    if n < 3 {
6        return String::from(match n {
7            0 => "0",
8            1 => "1",
9            2 => "1",
10            _ => unreachable!(),
11        })
12    }
13
14    let mut prev = Number::from(1u32);
15    let mut curr = Number::from(1u32);
16
17    for (index, should_add) in get_path(n).into_iter().enumerate().rev() {
18        if should_add {
19            let new_curr = &prev + &curr;
20            prev = std::mem::replace(&mut curr, new_curr);
21        }
22        
23        if index > 0 {
24            let dummy = &prev + &prev;
25            prev = &(&prev * &prev) + &(&curr * &curr);
26            curr = &curr * &(&curr + &dummy);
27        }
28
29    }
30
31    format!("{}", curr)
32}
33
34fn get_path(mut input: u32) -> Vec<bool> {
35    let mut vec: Vec<bool> = Vec::with_capacity(32);
36
37    while input > 1 {
38        vec.push(input % 2 == 1);
39        input >>= 1;
40    }
41
42    vec
43}
44
45#[cfg(test)]
46mod tests {
47    #[test]
48    fn verify_nth() {
49        for (index, value) in crate::Sequence::new().enumerate().take(1000) {
50            assert_eq!(value, super::nth(index as u32));
51        }
52    }
53}
fib_sequence/fibonacci/get.rs

fib_sequence/fibonacci/
get.rs
