|
 |
|
|
|
'Tis a tale sad but true...a bug in the Java implementation of Math.sqrt cost me advancing to round 4.
In the 250, I had the following helper method:
long sqrt(long x) {
...long y = (long)(Math.floor(Math.sqrt(x+0.001)));
...if (y*y == x) return y;
...else return -1;
}
The Math.floor and +0.001 are unnecessary, but they don't contribute to the problem.
Ok, so here's the question: What happens if x is a negative number? It should return -1, right? And so it does -- the bug is much more subtle than that!
Instead what happens is that if you call this enough times on big negative numbers, it messes up FUTURE calls to Math.sqrt on positive numbers! Apparently it corrupts some state inside of Math.sqrt.
Interesting side note. If you call Double.isNaN(Math.sqrt(4)), it will sometimes return true ('cause the square root of 4 is not a number, dontcha know). But, in the process of doing so, it seems to reset the corrupted state inside Math.sqrt. So the solution to make my 250 pass all SysTests is to stick in an extraneous call to Double.isNan, as in the following replacement method:
long sqrt(long x) {
...Double.isNaN(Math.sqrt(4)); // !!!!!!!
...long y = (long)(Math.floor(Math.sqrt(x+0.001)));
...if (y*y == x) return y;
...else return -1;
}
With this change, my 250 passes and I advance to Round 4.
[My thanks to lars2520 for his heroic efforts in helping track down where the bug was that made me fail SysTests!]
|
|
|
|
|
The complete solution, including the Double.isNaN call, is in the practice room. |
|
|
|
|
hm, I could not reproduce this. Calling Double.isNaN(Math.sqrt(4)) in a loop never returns true on my system _nor_ in the practice room. Same holds for the following loop:
for (int i=0; i < 32000; ++i) {
.if ((int)Math.sqrt(i*i+0.001) != i)
..System.out.println("ouch "+i);
}
Never prints out "ouch" in the practice room. I looked at the source Math.sqrt and StrictMath.sqrt but it only calls a native method...
|
|
|
|
|
Right, it only happens when you've been calling Math.sqrt on *negative* numbers. It's easily reproducible in the context of my 250 by adding various if's and println's to my code, like
...if (Double.isNaN(Math.sqrt(4))) System.out.println("ouch");
which will print "ouch" on some (but not all) of the iterations for some of the test cases. But I was unable to come up with a short code snippet that isolates the bug.
|
|
|
|
|
Yes - like any piece of sofware - bugs exist. I personally have been nailed on bugs in BigInteger.isProbablyPrime() and in the Rectangle class. The fun being - it was bugs in the specific version that TC used (and were corrected in the specific version I tested locally with)!
Ah - the joys of implementing in a different environment...
|
|
|
|
|
"Like any piece of software - bugs exist."
Yes, but the quantity of bugs matter. In my experience using Java professionally, Java implementations contain many times more showstopping bugs than C++ implementations. I've lost track of the number of times we've had to work around memory management bugs or library problems. (Sun's JVMs are probably the best of the lot, and they're still far from stable).
It's really sad; Java the language isn't all bad, but it's implementations let it down again and again.
People seem to like Java since it rules out some classes of bugs which C++ programmers can make. But if I make a bug in my C++ program, I can debug and *fix* that bug and ship a stable product. If there's a bug in the JVM, I'm helpless. The latter seems to be the case far too often.
|
|
|
|
|
s/it's/its/
Kind of sad, since I just read "Bob's Quick Guide to the Apostrophe, You Idiots." yesterday.
I plead TCO-induced sleep deprivation. |
|
|
|
|
Yes indeed, same thing happens here. Seems to be a problem with
(long)Math.sqrt(x)
If you use (int)Math.sqrt(x) instead it works, but it's definitely a JVM or compiler problem.
I have been bit by similar things, and usually end up rewriting the problem from scratch when I encounter them.
I'm very sorry to hear about this, vorthys. |
|
|
|
|
This sucks. I don't think vorthys should fail because of a bug in Java, for the following reasons:
1. He had no way of knowing this bug existed, since it is not consistent.
2. The java api does not state that the method behaves in the manner that it does.
3. Coders cannot be expected to know about undocumented problems in TopCoder's specific version of libraries or virtual machines. This in my opinion is unreasonable.
So what is topcoder going to do about it? Probably nothing, I guess we can't really hold TC responsible for Sun's mistake. They also assume that Java behaves the way it is specified. But it seems very unfair that vorthys has to bear the brunt of this error, especially when the result is that he doesn't advance to round 4. It's like having a contest for building a house and giving some people broken hammers by accident. The tools should be the same for everyone. |
|
|
|
|
I believe it is an instance of this bug <http://developer.java.sun.com/developer/bugParade/bugs/4755500.html>. Contrary to that report, I can reproduce this bug in Linux with JRE 1.4.1. The bug is fixed in 1.4.2.
I don't believe the bug has to do with any state in Math.sqrt(), and I don't believe Math.sqrt() even has state.
While Sun's report identifies the bug as "calling Math.round(NaN) can break subsequent calls to Math.round()", it in fact appears to be the case that, more generally, double to long conversions of NaN will break subsequent double to long conversions of normal floating-point values.
As evidence that this is the bug we're seeing, note that vorthys's solution works if you change it as follows:
double z = Math.floor(Math.sqrt(x + 0.001));
if (Double.isNaN(z)) return -1;
long y = (long) z;
So, the workaround is not to convert double NaN values to longs.
It's quite unfortunate that you failed to advance for this reason, vorthys. You have my sympathy.
Pops' post implies that TopCoder has a precedent of going with buggy results of the tools they're using, which is somewhat unfortunate. I can imagine that there are cases where it would be unduly burdensome to figure out that the bug was in the language implementation rather than the submission, but TopCoder could deal with that by placing the burden of proof on the coder to show that there was a bug in the language implementation, within the time period alloted for appeals.
|
|
|
|
|
I agree that vorthys shouldn't fail to advance for this reason, but your first reason is factually incorrect. The bug is deterministically reproducible with JDK 1.4.1_04, which TopCoder documents that they use. Vorthys could have known that the bug existed if he tested with the same JDK as TopCoder locally. |
|
|
|
|
I can't see where vorthys said he tested locally, so I can only assume he tested online.
I also am assuming that vorthys did not see this problem occur on any of the example cases. If he did, well, I'm sorry, but that I think disqualifies him from not knowing. But if he didn't, I don't think it's reasonable to expect him to test for this type of failure.
And the fact that he COULD have known doesn't mean that he SHOULD have known. If I wanted to test all possible ways to play with the Java SDK, yeah, I could probably find some bugs. But is it my responsibility to do that? |
|
|
|
|
That's a really good point: he submitted correct code that passed all example cases, yet failed systests due to an obscure bug in the JVM.
I'd have to say he deserves to be in Semi4, even if that means the field is expanded to 51 for this one case. |
|
|
|
|
I agree with you and radeye. There's no reason he SHOULD have known about the bug, but that doesn't mean he COULDN'T have known about it. I just wanted to observe that it is a deterministic bug. |
|
|
|
|
If this bug is fixed in 1.4.2, it may make sense for the TC to upgrade to the version with no bug, and then re-run the system tests. This would be consistent with the concept of a "level field," because all Java submissions would be scored using the same JVM. If the fix is available, this is probably a fair thing to do. |
|
|
|
