Fibonacci sequence fun

help
#1

I was playing around with Fibonacci numbers and made the following super-simple snippet:

let fib = successors(Some((0, 1)), |&(a, b)| Some((b, a + b)));

which works beautifully when used simply like this:

    for (n, _) in fib.take(20) {
        println!("{:?}", n);
    }

but I had difficulty turning that variable into a function due to a variety of things (generic types on the Successors struct, unnameability of closure types, etc.):

fn fib() -> ???

so that I can use it like so:

    for (n, _) in fib().take(20) {
        println!("{:?}", n);
    }
1 Like
#2 
fn fib() -> impl Iterator<Item = (u64, u64)> {}
3 Likes
#3

Thanks. I first tried to return a Successors struct directly, but got hung up on the second generic parameter needing to specify the closure type. I then tried impl Iterator, but forgot to specify the Item type and guess I just confused myself after that...

1 Like
#4

Replying to myself. :grinning:

I just wanted to add that even though Rust is sometimes known as a verbose language, it occasionally pleasantly surprises me with conciseness and elegance. I find the above to be both.

1 Like
#5

Even simpler with iterate from the itertools crate:

iterate((0, 1), |&(a, b)| (b, a + b))
4 Likes
#6

One nice thing about iterate is that it's known to be infinite (because there's no way to return None to stop the iteration). That means it'll get a better size_hint than the approaches using successors or similar.

For fun, here's another std-only version, which also has the unbounded size-hint:

fn fib() -> impl Iterator<Item = u64> {
    let mut state = (1, 0);
    std::iter::repeat_with(move || {
         let (a, b) = state;
         state = (b, a + b);
         b
    })
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ca074cfa38ecb081ff88ebf9a4905aa9

(I made that return just 0, 1, 1, 2, 3, 5, … instead of the pairs.)

3 Likes
#7

Even though it isn't usually represented this way, there's something about using the pairs that I really like, because in a very real way that's what the Fibonacci sequence is. Each pair fully determines the next value, meaning no additional state in the iterator and not having to shuffle the values around in a temporary variable.

3 Likes
#8

The linear algebra explanation is that the vector (pair) representation vn = [Fn, Fn+1]T satisfies the simple linear recursive relationship vn+1 = M vn, where M is the coefficient matrix

0 1
1 1

which immediately gives the non-recursive formula vn = Mn v0. Diagonalizing M then results in the usual closed-form formula for the Fibonacci sequence.

#9

I prefer successors in this case (statically sized integers), as the sequence will otherwise overflow.

1 Like
#10

You can save a line of code using destructuring assignments:

fn fib() -> impl Iterator<Item = u64> {
    let (mut a, mut b) = (1, 0);
    std::iter::repeat_with(move || {
         (a, b) = (b, a + b);
         a
    })
}

Rust Playground

3 Likes
#11

Just to participate in the fun here's one of my favorite (cheeky) solution:

const fn fibonacci() -> [u64; 93] { ... }
static FIBS: [u64; 93] = fibonacci();