Why does (int)55 == 54 in C++?

Question

So I'm learning C++. I've got my "C++ Programming Language" and "Effective C++" out and I'm running through Project Euler. Problem 1...dunzo. Problem 2...not so much. I'm working in VS2008 on a Win32 Console App.

Whats the Sum of all even terms of the Fibonacci Sequence under 4 million?

It wasn't working so I cut down to a test case of 100...

Here's what I wrote...

// Problem2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Project Euler Problem 2:\n\n";
    cout << "Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:\n\n";
    cout << "1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n\n";
    cout << "Find the sum of all the even-valued terms in the sequence which do not exceed four million.\n\n";
    cout << "Answer:  " << Solve();
}

double Solve() {
    int FibIndex = 0;
    double result = 0.0;
    double currentFib = GenerateNthFibonacciNumber(FibIndex);
    while (currentFib < 100.0){
     cout << currentFib << " " << (int)currentFib << " " << (int)currentFib % 2 << "\n";
     if ((int)currentFib % 2 == 0){
      result += currentFib;
      cout<<(int)currentFib;
     }
     currentFib = GenerateNthFibonacciNumber(++FibIndex);
    }
    return result;
}

double GenerateNthFibonacciNumber(const int n){
    //This generates the nth Fibonacci Number using Binet's Formula
    const double PHI = (1.0 + sqrt(5.0)) / 2.0;
    return ((pow(PHI,n)-pow(-1.0/PHI,n)) / sqrt(5.0));
}

And here's the output...

Project Euler Problem 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

0 0 0
1 1 1
1 1 1
2 2 0
3 3 1
5 5 1
8 8 0
13 13 1
21 21 1
34 34 0
55 54 0
89 89 1
Answer: 99

So I have three columns of debug code...the number returned from the generate function, (int)generatedNumber, and (int)generatedNumber % 2

So on the 11th term we have

55,54,0

Why does (int)55 = 54?

Thanks

Answer 1

Casting to int truncates the number - same as if you'd called floor(currentFib). So even if currentFib is 54.999999... (a number so close to 55 that it will be rounded up when printed), (int)currentFib will produce 54.

Answer 2

Due to floating point rounding, that 55 row is computing something like 54.99999. Casting double to int truncates the .99999 right off.

On my machine, printing a column displaying (currentFib-(int)currentFib) shows errors on the order of 1.42109e-14. So it's more like 0.999999999999986.

Answer 3

Okay, short answer is that under no condition should (int)55 == 54, so you need to start asking yourself what the associated line of code is really doing.

First question: how strongly does == bind compared to a typecast?

Answer 4

Shog9 has it right, using the type double for a problem like this is not the best way to go if you are going to cast things to ints. If your compiler supports it you should use a long long or some other 64 bit integer type, that will almost certainly hold the result of the sum of all the even terms less than 4 million of the Fibonacci sequence.

If we use the fact that the Fibonacci sequence follows the pattern odd odd even odd odd even... something as follows should do the trick.

...
unsigned int fib[3];
fib[0]=1;
fib[1]=1;
fib[2]=2;

unsigned long long sum=0;

while(fib[2]<4000000)
{
    sum+=fib[2];

    fib[0]=(fib[1]+fib[2]);
    fib[1]=(fib[2]+fib[0]);
    fib[2]=(fib[0]+fib[1]);
}

std::cout<<"The sum is: "<<sum<<". \n";
....

that should do the trick, there might be even faster ways but this one is pretty direct and easy to read.

Looking at it I realize that you could probably get away with a standard unsigned 32 bit integer as the sum number but I will leave it as is just in case.

Additionally your code makes a large number of function calls to the generate nth Fibonacci number function. A decent optimizing compiler will inline these calls but if it doesn't then things will slow down since function calls are more expensive than other techniques.

Answer 5

Hi there,

I agree 100% with shog9's answer - with the algorithm you used to calculate Fibonacci, you have to be really careful with floating point values. I found that the page cubbi.com: fibonacci numbers in c++ seems to show other ways of obtaining them.

I looked around for a good idea on how to make your implementation of GenerateNthFibonacciNumber handle cases where it returns the double 54.999999, but when you cast to an int or a long you get 54.

I came across what appears to be a reasonable solution at C++ Rounding, which I have adapted below in your code.

Also, It's not a huge deal, but you may want to precalculate PHI, then either pass it as a parameter or reference it as a global - now you are recalculating it every time you call the function.

double GenerateNthFibonacciNumber(const int n)
{
        //This generates the nth Fibonacci Number using Binet's Formula   
        const double PHI = (1.0 + sqrt(5.0)) / 2.0;
        double x = ((pow(PHI,n)-pow(-1.0/PHI,n)) / sqrt(5.0));
        // inspired by http://www.codingforums.com/archive/index.php/t-10827.html
        return ((x - floor(x)) >= 0.5) ? ceil(x) : floor(x);
}

Finally, here's how I rewrote your Solve() method so that GenerateNthFibonacciNumber(FibIndex) is only called in one place in the code. I also added the column with the current running total of the even Fibonacci terms to your output:

double Solve() {
    long FibIndex = 0;
    double result = 0.0;
    double oldresult = 0.0;
    int done = 0;
    const double PHI = (1.0 + sqrt(5.0)) / 2.0;

    while (!done)
    {
        double currentFib = GenerateNthFibonacciNumber(++FibIndex);
        if ((int)currentFib % 2 == 0)
     {
      oldresult = result;

      if (currentFib >= 4000000.0)
      {
       done = 1;
      }
      else
      {
       result += currentFib;
      }

     }
     cout << currentFib << " " << (int)currentFib << " " << (int)currentFib % 2 << " " << (int)result << "\n";       
    }
    return result;
}

Answer 6

I know this is not going to help with your real question, but you mentioned you're learning C++. I would recommend keeping as close to ANSI as possible, for learning purposes. I think that's /Za on MSVC (which is what you're probably using), or -ansi -pedantic on GCC.

In particular, you should be using one of these signatures for main until you have a good (platform-specific) reason to do otherwise:

int main(int argc, char *argv[]);
int main(int argc, char **argv); // same as the first
int main();

...instead of any platform-specific version, such as this (Windows-only) example:

#include <windows.h> // defines _TCHAR and _tmain
int _tmain(int argc, _TCHAR* argv[]); // win32 Unicode vs. Multi-Byte

Answer 7

All the above suggestions not to use floating point values for integer mathematics are worth noting!

If you want interger "rounding" for positive floating point values so that values with a fractional component below 0.5 round to the next lowest integer, and values with a fractional component of 0.5 or greater round to the next higher interger, e.g.

0.0 = 0
0.1 = 0
0.5 = 1
0.9 = 1
1.0 = 1
1.1 = 1
...etc...

Add 0.5 to the value you are casting.

double f0 = 0.0;
double f1 = 0.1;
double f2 = 0.5;
double f3 = 0.9;

int i0 = ( int )( f0 + 0.5 );  // i0 = 0
int i1 = ( int )( f1 + 0.5 );  // i1 = 0
int i2 = ( int )( f2 + 0.5 );  // i2 = 1
int i3 = ( int )( f3 + 0.5 );  // i3 = 1

Answer 8

Break the code for generatring, at times float number dont behave the way we think when used in a long expression...break the code and check it.