Remainder of a division with c++ getting 'Stack Overflow' exception

Question

I'm trying to understand some concepts in C++, and I made this code to get the remainder of a division (like % operator):

double resto(double a, double b) {
    if (a == b) return 0;
    else if (a < b) return a;
    else {
        return resto(a-b, b);
    }
}

When I run it with lowers numbers like (12,3) or (2,3), it runs fine. But if I try to run it with the parameters (2147483647 * 1024, 3) I get:

Stack overflow (parameters: 0x0000000000000001, 0x000000F404403F20)

As I'm new in C++, I'm not sure if it's something with Visual Studio 2017 or it's the compiler, or stack memory, etc.

Caution: `double`s are imprecise, making `if (a == b)` really hard to hit.`2147483647 * 1024` is going to be integer math and overflow if your system uses a 32 bit `int`. — user4581301, Mar 31 '19 at 00:45
So did you do any research on what "stack overflow" means? -- *As im new in c++* -- This actually has nothing to do with C++, as the concept of "stack overflow" appears in many, if not most computer languages. — PaulMcKenzie, Mar 31 '19 at 00:46
2147483647 * 1024 is too large for recursive , you may try to use for loop — howie, Mar 31 '19 at 00:46
Might already help to activate optimisation at some minimum level. Your function should qualify for [tail call optimisation](https://en.wikipedia.org/wiki/Tail_call) – of course, you shouldn't ever rely on!!! If it fails, welcome back at where you are already... — Aconcagua, Mar 31 '19 at 01:00
@KenWhite I disagree: While the referenced question covers a secondary problem (the one of equality check), primary question is why recursion exceeds maximum depths (and this is not related to bad equality check, as at some point, even if that check fails falsely, then `a < b` would apply either immediately or one recursion later). — Aconcagua, Mar 31 '19 at 01:08
@howie The product will overflow – which is undefined behaviour for signed integers. Result even might be negative, in which case `a < b` would appliy immediately. Well, *might*... — Aconcagua, Mar 31 '19 at 01:16
`resto` – while I suppose anybody can guess the meaning in this case, it's preferable to use pure English naming (even in your privete code): It's pretty likely that at some point of time, you'll need to share the code with some non-hispanophone people – and if only here on SO. Using English right from the start helps us better understand your code and/or saves you the necessity to translate... — Aconcagua, Mar 31 '19 at 01:24

user4581301 · Accepted Answer · 2019-03-31T03:09:49.727

resto(2147483647 * 1024, 3);

is going to recurse 2147483647 * 1024 / 3, or about 733 billion, times. Every recursive call is using a small amount of Automatic storage for parameters and book-keeping and the program will likely run out of storage before it reaches even a million iterations.

For this you will have to use a loop or smarter logic (for example subtracting larger multiples of b until using smaller numbers begins to make sense), but fmod is probably going to be faster and more effective.

Other notes:

2147483647 * 1024

is an integer times an integer. This math will take place in ints and overflow if int is 16 or 32 bit on your system. Exactly what happens when you overflow a signed integer is undefined, but typically the number does a 2s compliment wrap-around (to -1024 assuming 32 bit integer). More details on overflowing integers in Is signed integer overflow still undefined behavior in C++?. Use

2147483647.0 * 1024

to force floating point numbers.

Also watch out for Is floating point math broken? Floating point is imprecise and it's often difficult to get to floating point numbers that should be the same to actually be the same. a == b is often false when you expect true. In addition if one number gets too much larger than the other a-b may have no visible effect because b is lost in the noise at the end of a. The difference between the two cannot be represented correctly.

I'd yet mention that signed integer overflow is UB (and perhaps a hint to the consequences, as OP is beginner). — Aconcagua, Mar 31 '19 at 01:20
`but typically` – truth. Apparently, though, in given case it did not for whatever reason, otherwise `a < b` would have caught up immediately. And that's what UB is about... — Aconcagua, Mar 31 '19 at 01:47
Proposition: *[...] you overflow a (signed!) `int` [...]*, to make the difference to unsigned more obvious; maybe even mention the difference? — Aconcagua, Mar 31 '19 at 01:50

Remainder of a division with c++ getting 'Stack Overflow' exception

1 Answers1