Different outputs for Java and CPP

Question

I was solving Nth root of M problem and I solved it with Java and here is the solution:

    public int NthRoot(int n, int m)
    {
        // code here
        int ans = -1;
        if (m == 0)
            return ans;
        if (n == 1 || n == 0)
            return m;
        if (m == 1)
            return 1;
        int low = 1;
        int high = m;
        while (low < high) {
            
            int mid = (low + high) / 2;
            int pow = (int)Math.pow(mid, n);
            if (pow == m) {
                
                ans = mid;
                break;
            }
            if (pow > m) {
                
                high = mid;
            } else {
                
                low = mid + 1;
            }
        }
        
        return ans;
    }

It passed all the test cases. But, when I solved it using C++, some test cases didn't pass. Here is the C++ solution:

    int NthRoot(int n, int m)
    {
        // Code here.
        int ans = -1;
        if (m == 0)
            return ans;
        if (n == 1 || n == 0)
            return m;
        if (m == 1)
            return 1;
        int low = 1;
        int high = m;
        while (low < high) {
            
            int mid = (low + high) / 2;
            int po = (int)pow(mid, n);
            if (po == m) {
                
                ans = (int)mid;
                break;
            }
            if (po > m) {
                
                high = mid;
            } else {
                
                low = mid + 1;
            }
        }
        
        return ans;
    }

One of the test cases it didn't pass is:

6 4096
Java's output is 4 (Expected result)
C++'s output is -1 (Incorrect result)

When I traced it using paper and pen, I got a solution the same as Java's.

But, when I used long long int in the C++ code, it worked fine – but the size of Int/int in both Java and C++ are the same, right? (When I print INT_MAX and Integer.MAX_VALUE in C++ and Java, it outputs the same value.)

Have you tried to *debug* the C++ program to see when and where it goes wrong? Also, without a proper [mcve] (to see how this function is called and with what arguments) it's impossible to say anything certain anyway. — Some programmer dude, Jul 25 '21 at 12:32
By the way, `(int)mid`? If `mid` is a variable of type`int` there's no point in casting it to the same type. — Some programmer dude, Jul 25 '21 at 12:33
"*But the size of Int in both Java and C++ are the same, right?*" - In Java, [`int`s are 32-bit integrals](https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html). In C++, the size of `int` is not determined in the language spec. Depending on different factors, it can be at least `16` or `32` bits. If you want a 32-bit signed integral number, use [`int32_t`](https://en.cppreference.com/w/cpp/types/integer). — Turing85, Jul 25 '21 at 12:34
You could always try `printf("%zu\n", sizeof(int));` to double check that assumption. — Elliott Frisch, Jul 25 '21 at 12:38
@Someprogrammerdude `Line 17: error: incompatible types: possible lossy conversion from double to int int num = Math.pow(5,2);` When I use leetcode, it will throw an error like this since Math.pow returns double. — Marivishnu, Jul 25 '21 at 12:56
"But the size of Int in both Java and C++ are the same, right?". Wrong. — zubergu, Jul 25 '21 at 12:57
@Marivishnu C++ is not Java. This is what happens when you attempt to translate line-by-line from Java to C++, without actually learning C++ proper. Just because the languages look similar, there are vast differences, and you're running into those differences head-on. — PaulMcKenzie, Jul 25 '21 at 12:57
`(int)pow(mid, n);` -- That does not guarantee that you will get the result you're looking for. The `pow` function is a floating point function, and there are instances where [pow() will not give the correct results](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os/25678721#25678721). Do not use floating point functions, variables, etc, if the problem can be solved using integer. — PaulMcKenzie, Jul 25 '21 at 13:02
Have you ever checked what `std::pow(2048, 6)` returns and what the maximum value of your data type (`int`, `long long int`) is, and how c++ handles an overflow compared to java? — t.niese, Jul 25 '21 at 13:08
@PaulMcKenzie https://www.w3schools.com/cpp/cpp_data_types.asp https://www.w3schools.com/java/java_data_types.asp When I checked these 2 pages, they showed that the size of int in both java and CPP are 4 bytes. Is that incorrect? — Marivishnu, Jul 25 '21 at 13:11
@Marivishnu No you are not correct. Again, Java is not C++, and you're falling right into the trap. Java has integer sizes that are fixed, C++ integer sizes depend on the implementation, but must have size guarantees relative to the various integer types (short, int, long, etc.). — PaulMcKenzie, Jul 25 '21 at 13:12
@Someprogrammerdude Yeah that's a mistake. I changed `ans` to `long long int` and I forgot to remove the casting after I changed it to int. — Marivishnu, Jul 25 '21 at 13:17
@Marivishnu w3schools always tend to be a bad source for information. [https://en.cppreference.com/](https://en.cppreference.com/w/cpp/language/types) says that `int` is at least 16bit. So only a size of 2byte is guaranteed. — t.niese, Jul 25 '21 at 13:18
@Marivishnu -- Forget about using `long long int`. If you want to *guarantee* that the integer type you're using is 32-bit or 64-bit, just like Java, use `int32_t` and `int64_t`, not `long long`, `long`, `int`, or some other type where the size is not readily known. — PaulMcKenzie, Jul 25 '21 at 13:19
@PaulMcKenzie `Java has integer sizes that are fixed, C++ integer sizes depend on the implementation` Ok thanks! Got it! — Marivishnu, Jul 25 '21 at 13:21
@t.niese `So only a size of 2byte is guaranteed` Ok! I will refer CPP reference. Thanks for your reply! — Marivishnu, Jul 25 '21 at 13:22
@PaulMcKenzie `Forget about using long long int. If you want to guarantee that the integer type you're using is 32-bit or 64-bit, just like Java, use int32_t and int64_t, not long long, long, int, or some other type where the size is not readily known` Thanks! You really helped a lot! Thanks for your time — Marivishnu, Jul 25 '21 at 13:23
In addition to all the other problems, any C++ ***or Java*** program that uses `pow()` with two integer values, no matter what their size is, is automatically buggy, by default. This is because you'll be surprised to learn that `pow(5,2)` is not really 25. It is whatever `e^(2*log(5))` turns out to be, with rounding errors, et al. This is true for all programmig languages. — Sam Varshavchik, Jul 25 '21 at 13:25

Adrian Mole · Accepted Answer · 2021-07-25T13:23:46.237

As you have probably guessed, the problem is due to the attempt to convert a double value to an int value, when that source is larger than the maximum representable value of an int. More specifically, it relates to the difference between how Java and C++ handle the cast near the start of your while loop: int po = (int)pow(mid, n);.

For your example input (6 4096), the value returned by the pow function on the first run through that loop is 7.3787e+19, which is too big for an int value. In Java, when you attempt to cast a too-big value to an integer, the result is the maximum value representable by the integer type, as specified in this answer (bolding mine):

The value must be too large (a positive value of large magnitude or positive infinity), and the result of the first step is the largest representable value of type int or long.

However, in C++, when the source value exceeds INT_MAX, the behaviour is undefined (according to this C++11 Draft Standard):

7.10 Floating-integral conversions [conv.fpint]

¹ A prvalue of a floating-point type can be converted to a prvalue of an integer type. The conversion truncates; that is, the fractional part is discarded. The behavior is undefined if the truncated value cannot be represented in the destination type.

However, although formally undefined, many/most compilers/platforms will apply 'rollover' when this occurs, resulting in a very large negative value (typically, INT_MIN) for the result. This is what MSVC in Visual Studio does, giving a value of -2147483648, thus causing the else block to run … and keep running until the while loop reaches its terminating condition – at which point ans will never have been assigned any value except the initial -1.

You can fix the problem readily by checking the double returned by the pow call and setting po to INT_MAX, if appropriate, to emulate the Java bevahiour:

    while (low < high) {
        int mid = (low + high) / 2;
        double fpo = pow(mid, n);
        int po = (int)(fpo);
        if (fpo > INT_MAX) po = INT_MAX; // Emulate Java for overflow
        if (po == m) {
            ans = (int)mid;
            break;
        }
        if (po > m) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }

Different outputs for Java and CPP

1 Answers1

7.10 Floating-integral conversions [conv.fpint]