Iterative Fibonacci sequence using standard library functions

Question

We're all aware of Fibonacci sequence calculators but they look like C-style code. I want to avoid that and take advantage of the standard library. This code is very short, so I'm focusing on readability and correctness.

• Barring comments, will people be able to understand the code just by looking at it?

• As you're probably aware, this doesn't scale well due to stack limits. Using a dynamic memory approach, i.e. auto arr = std::make_unique<type[]>(size);, this allocates A LOT of memory. Comparatively, an iterative approach doesn't need any memory allocation at all, as it doesn't store the previous results, only the last one. As a result, my approach is automatically slower. For example, this answer ran in under a second, while mine ran in 7 seconds for a size of 1000000 (and allocated 8,000,000 bytes).

  What's a way to make this faster AND to cut down on the memory usage?

• I've compared the output to the oeis list and it seems correct. Would this break for bigger numbers? What should I replace std::uint64_t with? While I need std::uint64_t to store the bigger numbers, it obviously doubles the amount of memory allocated.

#include <algorithm> #include <array> #include <functional> #include <iostream> #include <iterator> #include <numeric> #include <cstdint> int main() { std::array<std::uint64_t, 10000> arr; arr.fill(0); arr[1] = 1; arr[2] = 1; std::transform(arr.begin(), arr.end() - 2, arr.begin() + 1, arr.begin() + 2, std::plus<>()); std::copy(arr.begin(), arr.end(), std::ostream_iterator<std::uint64_t>(std::cout, " ")); return 0; } 

Answer 1

I think it's clear enough, but would benefit from some changes.

Minimize initialization

There really isn't any need to call fill for this, and really only the first two array items need to be initialized:

arr[0] = 0; arr[1] = 1; 

Check numeric limits

The code does not actually work beyond around the 94th term in the sequence due to mathematical overflow. I used this code to verify that:

std::uint64_t last = 0; unsigned i = 0; for (const auto &n : arr) { if (n < last) { std::cout << "broke at term " << i << " because " << n << " < " << last << '\n'; exit(1); } ++i; last = n; } 

On my machine, this produces the following output:

broke at term 94 because 1293530146158671551 < 12200160415121876738

Prevent numeric overflow

Better than checking for overflow after it happens is to prevent the problem from occurring in the first place. Here's a way to do that, but first we have to do some mathematics.

First, there is a closed form way to calculate the Fibonacci numbers:

$$ F(n) = \left\lfloor{\frac{\varphi^n}{\sqrt{5}} + \frac{1}{2}}\right\rfloor $$

where \$\varphi\$ is the golden ratio:

$$ \varphi = \frac{1+\sqrt{5}}{2} $$

For large numbers, we can approximate \$F(n)\$:

$$ F(n) \approx \frac{\varphi^n}{\sqrt{5}} $$

If we want to know how many decimal digits are in \$F(n)\$, we can take \$\log_{10}(F(n))\$. So to be pedantic, we can create a new function \$D_F(n)\$ which estimates the number of decimal digits in Fibonacci term \$n\$:

$$ D_F(n) = \log_{10}\left(\frac{\varphi^n}{\sqrt{5}}\right) $$

In this case, we want it the other way around. That is, rather that starting with \$n\$ and calculating the number of digits \$d\$, we want to start with \$d\$ and find the largest term \$n\$ that uses no more than \$d\$ digits. This just requires a little algebra to create a function \$N_F(d)\$ that gives the largest term number that requires no more than \$d\$ digits to store:

$$ N_F(d) = \frac{\log_{10}\left(\sqrt{5}\right) + d}{\log_{10}(\varphi)} $$

Now we can actually use the result in code by inserting a few lines above main into your program like so:

constexpr int fibterm(unsigned digits) { return (digits + log10(sqrt(5))) / log10((1+sqrt(5))/2); } template <typename T> constexpr int fiblim() { return fibterm(std::numeric_limits<T>::digits10)+1; } 

Now your array can be completely safe:

std::array<std::uint64_t, fiblim<std::uint64_t>()> arr; 

On my machine std::numeric_limits<std::uint64_t>::digits10 = 19, so fiblim<std::uint64_t>() evaluates to 93 and we can verify that indeed, \$F(92)\$ is 19 digits long and the next term, \$F(93)\$ is 20 digits.

Remember that std::numeric_limits<T>::digits10 tells us the maximum number of digits that can always be stored in a T reliably, so std::uint64_t can hold any 19-digit number. It might be able to store some larger numbers, (as indeed it can correctly calculate \$F(93)\$ in this case) but it's not guaranteed.

Also note the +1 at the end of fibterm. This is due to the fact that we're calculating storage space required, rather than the term number. So even if we only wanted \$F(0)\$, it requires 1 storage slot.

Consider possible enhancements

Because the numeric range of std::uint64 is limited, as we saw above, if you wish to calculate more terms, you will need to use some other type. One could imagine using one of the many multi-precision numeric libraries out there, or, if the intent is to simply print them, you may want to calculate them in place as arrays of decimal digits. This latter approach would mean that the computationally costly step of converting from binary to decimal could be completely eliminated, greatly speeding the execution of the program.

Be strict about language conformance

The code currently uses std::plus<>() as the last argument to std::transform but that is actually not C++11. It's new in C++14 and it's a good and handy feature, properly used here, but it's not strictly C++11.

Omit return 0

Your compiler will automatically generate return 0 at the end of main so there's really no need to manually insert it.