the positive n-th root of p

Question

The following code prints wrong answer on one of the test cases out of 20. I appreciate if anybody could find the logic error.

#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
using namespace std;

int main() {
    double n, p;
    cin >> n >> p;
    int k = pow(p, 1 / n);
    cout << k;
    return 0;
}

And when your program fails, what is the actual value of `k` and what is it expected to be? — Some programmer dude, Sep 25 '15 at 10:34
@IKavanagh That would be the correct approach had the OP been asked to find the exponent. They're given the (reciprocal of) the exponent and the base, they just have to do the exponentiation. — Asad Saeeduddin, Sep 25 '15 at 10:40
@IKavanagh: I don't see any flaw in the logics (trivial, by the way). Where do you see one ? — , Sep 25 '15 at 10:40
@IKavanagh: The `n`-th root of `p` is equivalent to `pow(p, 1/n)`. — 3442, Sep 25 '15 at 10:41
@FabioTurati: the double type is quite sufficient, and you didn't see the test cases. — , Sep 25 '15 at 10:43
If the problem is that k is occasionally one below the correct answer, then you just need to adjust the conversion from double to int (by adding .5) `pow(p,1/n)+.5` When double can't hold the full precision of p, you still get k very close to the right integer, but it may be low by a tiny fraction. Then in conversion from double to int, low by a tiny fraction turns into low by one. In all cases without such a problem adding .5 before conversion makes no difference. But with such a problem adding .5 fixes it. — JSF, Sep 25 '15 at 10:44
@YvesDaoust The `int` type for k is the problem. If `k` can be up to `10^9`, as given in the question, it can overflow `int` (which I think goes up to 2^16 or something). — Asad Saeeduddin, Sep 25 '15 at 10:46
@YvesDaoust That means I was wrong; looks like the issue was precision, as use2079303's answer explains. — Asad Saeeduddin, Sep 25 '15 at 11:25
@Asad you weren't wrong any more than Yves in regards of the size of `int`. It is implementation defined. 2 byte int is quite rare these days, though. — eerorika, Sep 25 '15 at 11:26
@user2079303: I am indeed old enough to remember programming with 16 bits ints. But many years *before*, the integers were 72 bits on a mainframe. — , Sep 25 '15 at 12:19

eerorika · Accepted Answer · 2015-09-25T11:28:38.217

5

The problem states that p ≤ 10^100. There is no exact double representation for all integers of that magnitude(*). If the closest floating point representation of p is less than the exact p, then the floating point value returned by pow(p, 1 / n); will also be less than the expected k.

When you convert a floating point number, the fractional part is truncated i.e. the number is rounded down. Therefore, if the calcucated floating point value k' is less than the exact k, then k' converted to an integer will be k - 1.

Since you're guaranteed to get a floating point number that is close to the correct integer by a small margin of error, you can solve the problem by rounding to the nearest integer, rather than rounding down. JSF already gave the algorithm for that: Add 0.5 before rounding down.

(*) 64-bit IEEE 754 floating point can represent integers exactly up to 10^17.

Also, there is a potential problem of the size of the result. If the size int on the platform is 2 bytes, then k will overflow. A 4 byte int is sufficient for the given range of k. You can guarantee the necessary size by using int32_t.

edited Sep 25 '15 at 11:28

answered Sep 25 '15 at 11:10

eerorika

232,697
12
197
326

The correct answer. Just two remarks: The wikipedia page you mention says that all integers up to 2^53 have an exact representation (because the number of fractional bits is 52). That would be close to 9e15. No power of 2 matches "exactly 10^17". Do I miss something?-- I also think that even 64 bit `k`s will overflow for some arguments (since according to the OP the exponent p can be 1 so that for n=10^300 k becomes 10^300 which would need almost 1000 digits in a binary int representation). – Peter - Reinstate Monica Sep 25 '15 at 12:28
For those who want to know something more about the limits of storing *exact* integers in a 64-bit `double` I recommend reading [this answer by Steve Jessop](http://stackoverflow.com/a/1848762/3982001) – Fabio says Reinstate Monica Sep 25 '15 at 12:29
That is a nice answer ("DBL_MAX@) :-). – Peter - Reinstate Monica Sep 25 '15 at 12:31

the positive n-th root of p

1 Answers1