JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Rounding | Reply
I often fail problems, because I fail to round correctly. I want to know what are the safest and easiest methods to do the following:

1. Round a double to the nearest integer
2. Take the ceiling of a double. ie. 1.2 -> 2
3. Round a double to x significant figures. ie. 1.239 rounded to 2 significant figures should be 1.24.

Also can I trust Math.round() to work? Can I trust (int)Math.pow(x,y) to work when both x and y are supposed to be integers?
Re: Rounding (response to post by dimkadimon) | Reply
I haven't seen a situation in TopCoder where 1 or 2 were necessary.
If they were necessary the problem statement should include some tie-breaking text, or disallow inputs where ties could occur.

Otherwise some implementations could return results that differ by 1.0 (or more if the result is used in further calculations) - which is slightly over the usual 1e-9 absolute and relative error.

My guess with pow is that it uses exponentiation of e, and therefore cannot be guaranteed to give the expected result. On the other hand, I would be surprised if there were a combination of values that gave the wrong answer (as long as the number fits in an int). If the type were a 64-bit long, the tables are turned, as a double doesn't have enough precision.

In Java, Math.round(d) just does (int)(d+0.5d)

Edit: I've tried Math.pow() for numbers up to 50000 with no errors.
Re: Rounding (response to post by dimkadimon) | Reply
1. Math.round. I only usually use this in competitions when it's supposed to be really close to the actual number.
2. Math.ceil
3. In Java, you probably just have to do that if you're returning a string. Use java.text.DecimalFormat - new DecimalFormat("0.00").format(1.239). Note that to break real ties (i.e. 1.235), it uses round-even conventions. If you need round-up conventions, you should probably use Math.round(1.235*100)/100.0 or something (I guess that's a reason to use Math.rint?). Well thought-out TC problems usually try to avoid the case where this is a problem.
4. I trust Math.round. If I'm using Math.pow on integer values, I usually round the result, in case the answer is for some reason non-exact. What would be safer is to write your own exponentation algorithm I guess. Of course, as misof pointed out, if the value can be exactly represented in a double, the answer should be accurate (although he didn't say this specifically about exponentation, it probably is still true). Rounding won't solve the problem where an integral value just can't be represented in the floating point system being used (but this is a double->long problem, not a double->int problem, as misof also mentioned).
Re: Rounding (response to post by Kawigi) | Reply
Maybe someone (perhaps Kawigi himself) can show safe ways of doing this in C/C++?

I remember, for example, that sprintf does something that wasn't intuitive; at least, I remember that a lot of people failed a problem recently because sprintf wasn't rounding in an 'expected' way. (This relates to item 3.)
Re: Rounding (response to post by NeverMore) | Reply
I think sprintf uses round-even as well, so the same thing that I said about Java's DecimalFormat should be applied to sprintf and similar C functions. Of course, it's also possible that the rounding convention isn't consistent between platforms or libraries. But most TC problems will disallow inputs which give an answer that is within some amount of being exactly between two possible distict output strings. There are a few, though, that don't, and I think I remember reading in one problem that .5 should always round up for the output. That's a situation to multiply and use round rather than using sprintf or DecimalFormat. If you have a problem that asks specifically for round-even output, then you are probably more likely to make it with DecimalFormat or sprintf (of course, I've only ever seen something like that in ACM, and when I figured out later that that's what DecimalFormat did, I was kicking myself).

I suspect that round, ceil, floor and rint are all similarly safe ways to do different kinds of rounding using cmath.
Re: Rounding (response to post by Kawigi) | Reply
Thank you for all the answers! What else can DecimalFormat do?
Re: Rounding (response to post by tolkienfan) | Reply
How do you explain that (long)Math.pow(3,35) is wrong by 3?
Re: Rounding (response to post by dimkadimon) | Reply
335 requires 56 bits to represent, but a double only has 52 bits of precision.
Re: Rounding (response to post by dimkadimon) | Reply
Your question prompted a response from me, but it turns out the forums have a limit on the size of a response. As a result, I'll post it to a new thread.
Re: Rounding (response to post by dimkadimon) | Reply
I'm flattered that you would ask me, but you should really ask the experts.

In general, you use "." for a decimal point (which means that it gets changed to a "," for Europe and stuff - something to be careful about. This is what makes the KawigiEdit problem timer not work for some people), "," for a 'thousands' seperator, "0" to represent digits that must exist and will use a '0' if there is no significant digit there, and '#' for digits that should be shown if they are significant.
Re: Rounding (response to post by dimkadimon) | Reply
My point was that if the result fits within an int, then the result should be correct when cast to an int; but a long has too much precision to fit in a double.
Edit: typo
Other edit: duh
Re: Rounding (response to post by dimkadimon) | Reply
Actually, the following is found in the specs:
"If both arguments are integers, then the result is exactly equal to the mathematical result of raising the first argument to the power of the second argument if that result can in fact be represented exactly as a double value."

At:
http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Math.html
RSS