Why does my code output incorrect results? Integer overflow?

Question

Assume that we have 15 numbers from a[0] to a[14] that satisfy:

a[0]=4
a[i]=pow(sqrt(a[i-1])*2-1, 2) for i>=1 and i<=14

I need to print out all the values from a[0] to a[14], each number is on one line, so I write the following code (C++, Code::Blocks):

#include <iostream>
#include <cmath>
using namespace std;
#define maxN 15
int i[maxN]; int n=15;
int main()
{
    i[0]=2;
    cout<<4<<endl;
    for (int k=1; k<n; k++){
        i[k]=i[k-1]*2-1;
        cout<<pow(i[k],2)<<"\t"<<endl;
    }
    return 0;
}

The result is:

4
9
25
81
289
1089
4225
16641
66049
263169
1.05062e+006
4.1984e+006
1.67854e+007
6.71252e+007
2.68468e+008

The last five numbers are not correct (because of integer overflow).

In the "for" loop above, I change the line

cout<<pow(i[k],2)<<"\t"<<endl;

to

cout<<(long) pow(i[k],2)<<"\t"<<endl;

This time, the result is:

After I checked manually, I realized that many numbers are still incorrect: 24; 4224; 66048; 263168; 4198400; 16785408; 67125248; 268468224 (they are all 1 lower than the correct numbers). What should I do to fix this?

*What should I do to fix this?* The `pow` function is a floating point function. Floating point in computers is not like algebra in school, as floating point does not guarantee "exact math". [See this](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) — PaulMcKenzie, Sep 26 '18 at 13:21

YSC · Answer 1 · 2018-09-26T13:23:36.007

1.05062e+006 and 1050625 are the same values, printed differently. pow(i[k],2) returns a floating point type, no integer overflow takes place here, but rather rounding when you convert such a floating point to long.

The format Xe+Y is called scientific notation, its value is X * 10 ^ Y. By default, std::printf and std::ostream::operator<< prints floating points values exceeding a certain bound in their scientific notation. See https://en.cppreference.com/w/cpp/io/manip/fixed for more info.

score 5 · Accepted Answer · answered Sep 26 '18 at 13:32

What should I do to fix this?

change

cout<<pow(i[k],2)<<"\t"<<endl;

to

cout<<i[k]*i[k]<<"\t"<<endl;

pow is a floating point function, which can be imprecise. Note, that in your case there is something strange: if pow uses 64-bit IEEE-754 doubles, it should print accurate numbers for your input. So maybe you use 32-bit float numbers.

Why does my code output incorrect results? Integer overflow?

2 Answers2