C++, Integer Overflow?

Question

I made a program to find the factors of a number:

#include <iostream> #include <cmath> using namespace::std; int main() { long int n = 6008514751432; int i = 1; while (i <= n/2) { if (n % i == 0) cout << i << " "; i++; } }

I am using xCode BTW It works fine with smaller numbers, like 2000 lets say, or even 200000. But, when I get up to 6008514751432, which is the number I need to know, it doesn't work, it just says the program is running and displays nothing! What is going on?

Update: When I run the program and wait about 2 minutes, it says:

Warning: the current language does not match this frame. Current language: auto; currently c++ (gdb)

What compiler are you using? On Visual C++, long ints and ints occupy the same amount of memory, so they have the same integer range. — In silico
– In silico, Commented Mar 7, 2012 at 4:10
"it just says the program is running and displays nothing!" Sadly, it tells you the truth. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Mar 7, 2012 at 4:12

Etienne de Martel · Accepted Answer · 2012-03-07 04:10:43Z

long int is likely 4 byte wide on your implementation, which means it can only store values up to 2^31 - 1, or 2147483647.

You might try switching to long long, which is typically larger (8 bytes on most platforms):

long long n = 6008514751432LL; long long i = 1LL; while (i <= n/2) {     if (n % i == 0)         cout << i << " ";     i++; }

If that's still not sufficient, you will need to look for some infinite precision number library, such as GMP.

Keith · Accepted Answer · 2012-03-07 04:10:41Z

Depending on your platform, you find that 6008514751432 is too large for the type long int. You need to make sure you are using a type that holds a 64-bit integer type.

Also, if you are just trying to find the factors of a number, there is no need to look higher than sqrt(n) as factors greater than that have a corresponding co-factor less than that. Make sure to out the sqrt outside the loop itself.

On a system where long int is larger than int, note that you'll find that at some point i wraps to 0

@user1247509: long long is a 64-bit signed integer type you can use on compilers that support it. I recommend that you use long long if you can.

Konrad Rudolph · Accepted Answer · 2013-02-09 12:38:32Z

If it's running it's probably not integer overflow in this specific case.

6008514751432 / 2 as a 32-bit int comes out negative (-144495672) So the while loop would terminate immediately.

Integer overflow begets undefined behaviour so anything could happen, but most systems behave predictably

Also if it was overflow your compiler should have warned you, or even refused to compile it.

Half of 6008514751432 is still quite a large number and it will take significant time to count that high, and do all those "%" operations. Meanwhile the first few factors (1,2,4,8,1307,2614 etc) have been sent to COUT but not yet flushed so those results are sitting in the buffer, where you can't see them.

If you change your program to put each number on a new line that may give some results sooner, you'll still be waiting days to weeks for the final result though.

I suggest you look for a faster factoring algorithm.

Spoiler: FWIW 6008514751432 has prime factors

2 2 2 1307 574647547

J.N. · Accepted Answer · 2012-03-07 04:15:17Z

You are assuming that long int is bigger than it is. You should try the following:

print n after you have assigned it
print sizeof(int), sizeof(long long)
use int64_t and the like. int, long and others are not the best choice when the actual size matters.
Add a read from stdin in your loop do try and debug step by step if problems persist

Collectives™ on Stack Overflow

C++, Integer Overflow?

4 Answers 4

Comments

4 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

4 Comments

Comments

Comments

Related