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 — PaulMcKenzie
– PaulMcKenzie, Commented Sep 26, 2018 at 13:21

YSC · Accepted Answer · 2018-09-26 13:23:36Z

8

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.

edited Sep 26, 2018 at 13:23

answered Sep 26, 2018 at 13:15

YSC

40.4k11 gold badges103 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

geza · Accepted Answer · 2018-09-26 13:32:12Z

5

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.

answered Sep 26, 2018 at 13:32

geza

30.5k6 gold badges70 silver badges162 bronze badges

Collectives™ on Stack Overflow

Why does my code output incorrect results? Integer overflow?

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related