fib-sequence 0.1.0

A library for retrieving fibonacci numbers in base 10
Documentation 
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

use super::Number;

pub fn nth(n: u32) -> String {

    if n < 3 {
        return String::from(match n {
            0 => "0",
            1 => "1",
            2 => "1",
            _ => unreachable!(),
        })
    }

    let mut prev = Number::from(1u32);
    let mut curr = Number::from(1u32);

    for (index, should_add) in get_path(n).into_iter().enumerate().rev() {
        if should_add {
            let new_curr = &prev + &curr;
            prev = std::mem::replace(&mut curr, new_curr);
        }
        
        if index > 0 {
            let dummy = &prev + &prev;
            prev = &(&prev * &prev) + &(&curr * &curr);
            curr = &curr * &(&curr + &dummy);
        }

    }

    format!("{}", curr)
}

fn get_path(mut input: u32) -> Vec<bool> {
    let mut vec: Vec<bool> = Vec::with_capacity(32);

    while input > 1 {
        vec.push(input % 2 == 1);
        input >>= 1;
    }

    vec
}

#[cfg(test)]
mod tests {
    #[test]
    fn verify_nth() {
        for (index, value) in crate::Sequence::new().enumerate().take(1000) {
            assert_eq!(value, super::nth(index as u32));
        }
    }
}