Iterative Fibonacci sequence using standard library functions

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(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 
#include 
#include 
#include 
#include 
#include 
#include 

int main()
{
    std::array 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::cout, " "));
    return 0;
}

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 ::digits10 = 19, so fiblim() 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::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.

StackExchange Code Review Q#66424, answer score: 7