Fibonacci Series Exercise

Question

This is an exercise from the text "Programming: Principles and Practice Using C++" by B.S. : Exercise 11 of chapter 5.

The following is asked:

" Write a program that writes out the first so many values ​​of the Fibonacci series, that >is, the series that starts with 1 1 2 3 5 8 13 21 34. The next number of the series is the >sum of the two previous ones. Find the largest Fibonacci number that fits in an int. "

Let's start by saying that chapter 5 covers the topic of error handling, including using the try throw a catch statement to handle exceptions. So it is assumed that the exercise will involve this topic in some way.

At this level of the text macros or similar things have not yet been covered. The use of INT_MAX or similar things is assumed that they have not yet been explained.

To find the series I used a helper variable called temp. Honestly, I didn't succeed in the goal without using one.

To handle the exception I thought of intercepting the overflow on the integer (in fact I used an unsigned one) checking that the result of the sum of the last two values ​​(Fibonacci series) was not less than the last value itself (overflow situation).

#include <iostream>
#include <string>
#include <stdexcept>
#include <exception>
int main()
{
 
 unsigned int previus{ 0 };
 unsigned int actual{ 1 };
 unsigned int temp{ 0 };
 try
 {
 while (true)
 {
 previus = temp;
 std::cout << actual << ' ';
 temp = actual;
 if (actual + previus < actual)
 throw std::runtime_error("Unsigned integer limit exceeded\n");
 actual = actual + previus;
 }
 }
 catch (const std::exception& e)
 {
 std::cerr << "\n\nruntime error: " << e.what();
 }
}

What do you think?

• user555045: The exercise asked for "largest Fibonacci number that fits in an int" but you solved it for unsigned int, is that OK?
• RedM3tal: @ user555045 True, initially I had in fact used a signed integer; the if check was to intercept the value as soon as it became negative (actual < 0). I wanted to force it by using an unsigned integer just to see how to handle it.
• JonathanZ: It's a small point, but I'm guessing your native language is something like French, where "actuelle" would be a good name for the current value. If you want to write in English, rename that variable to "current". In English, "actual" means "real, genuine, authentic".

Answer 1

Specifications for overflowing unsigned integer types differ from signed integers. Switching to unsigned types may provide some insight, yet not a certain approach to solve the int problem.

Failed to meet goal

Goal: " ...Find the largest Fibonacci number that fits in an int."

Instead code stops with the largest Fibonacci number that fits in an unsigned.

Overflow with unsigned is well defined: it wraps. (MOD (UINT_MAX + 1).

If if (actual + previus < actual) instead used int types, then overflow of actual + previus is undefined behavior (UB) and not a reliant test.

Use of INT_MAX or the like is the best approach even if OP implies it is not allowed.

if (actual > INT_MAX - previus) {
 // Too big.
}

There exists some esoteric tricks or assumptions (e.g. UINT_MAX/2 --> INT_MAX) one can use to code without using the int limits, yet those are more of an advanced topic than using INT_MAX (std::numeric_limits<int>::max()).
See also Programmatically determining max value of a signed integer type

Unfortunately this sounds like the lesson is encouraging using an after int overflow detection approach - that is not good...

Minor: Consider correct spelling

previus --> previous

• RedM3tal: exactly the text level at this point is very basic...also interesting are the ideas with (MOD (UINT_MAX + 1).
• Peter Cordes: @RedM3tal: If the text hasn't introduced INT_MAX or macros at all, then a reasonable thing for a beginner to do is just invent their own: assuming they know they're using an implementation where int is 32-bit, they can just use unsigned and compare x > 0x7FFFFFFF. Fibonacci grows by less than double every iteration, so there will always be an unsigned Fib(n) > INT_MAX which fits in unsigned, assuming it and int have the same number of value bits.
• chux: @PeterCordes Isn't more common for unsigned to have 1 more value bit than int?
• Peter Cordes: Or if you just print the results, you could manually look for one that didn't grow; symptoms overflow of UB tend to be simpler if you avoid compares that let the compiler optimize based on no-UB assumptions. (But of course that choice required that I knew about signed-overflow UB. I agree it sounds like they might be encouraging writing bad code that will only work if you compile with GCC -fwrapv to define the behaviour of signed overflow as 2's complement wrap-around)
• Peter Cordes: @chux: Oh, does C++ terminology of value bits vs. padding bits in an object-representation not include the sign bit as a value bit?

Answer 2

The code you wrote is kind of expected from a beginner. It does work correctly, but it's a bit more lines of code than necessary, and there is also a much simpler way than using exceptions to break out of the loop. Here is the "pro" version:

#include <iostream>
#include <utility>
int main() {
 unsigned int previous{0}, actual{1};
 while (actual + previous >= actual) {
 actual = std::exchange(previous, actual + previous);
 std::cout << actual << ' ';
 }
 std::cout << '\n';
}

These are the improvements over your code:

• Instead of an infinite while-loop, we can just do the test for integer overflow in the condition of the while. That avoids needing to throw and catch an exception.
• The function std::exchange() is used to rotate actual, previous and actual + previous (in that order) without needing a temporary variable.
• I declared previous and actual in a single statement, so that if you want to change the type of these variables, you only need to do it in one place.

As a result, the code is much simpler and shorter, although of course you do need to know about std::exchange() to understand it.

• RedM3tal: thanks for the reply. Interesting use of this exchange() method. To be studied in depth and to be taken into consideration every time you have the need to preserve the old value. Very useful
• Peter Cordes: @RedM3tal: Yeah, I like it. The other way to remove a bunch of variable assignment from Fibonacci is to unroll by two, into x += y; y += x;. But that makes it quite non-simple if you want to stop after an odd n. The unrolled version in Assembly Language (x86): How to create a loop to calculate Fibonacci sequence using x86 assembly manages to keep the loop prologue compact, doing a first odd iteration for odd n so an even number remains, but it's certainly not simple.
• RedM3tal: @Peter Cordes: Surely there are methods that are better suited to the purpose. I have a really minimal experience but generally I mature the idea maybe thinking about it for a certain time and then I try to carry it forward, I abandon it if it really doesn't work and it becomes too complicated. In any case it is very useful to see the different methodologies in tackling things and from these gain experience which is then the purpose for which I publish them here.