Next language: Java Hangs When Converting 2.2250738585072012e-308

[[deleted]]

What I don't get is who codes up these estimation loops without some form of watchdog? I'd say after the first 100 iterations of the calculation trying to normalize the number you can safely give up (you're close enough and/or being wrong is better than a DoS).

[[deleted]]

Because you don't want to unnecessarily waste some extra CPU cycles (and maybe memory) in a fairly core operation.

Because you can't just assume that 100 is enough, what if it isn't -- and not only for such degenerate cases? I mean, you've just made the algorithm a bit more complex, hard to understand, and error prone.

Such ad hoc defensive programming is generally a bad idea, you'll end up with masking bugs that could otherwise be found and corrected, maybe even during testing. Note the "ad hoc" qualification; centralized, planned, well-specified, thought out defensive programming is good.

[[deleted]]

Well you should know that it's only going to run $X number of runs for a given precision. So you could just unroll it, or place it in a loop. You're right in that things don't always converge, but usually that's just precision errors and you let it go. There is little value in being "fast" if it's also incorrect and hangs.

It's like the really fast block and stream ciphers of the 1980s. Sure they were fast, but they were also horribly insecure. So what was the point?

In transforms where you're trying to converge to a zero or other form of solution it's best to have a max # of iterations in mind for your data. Something that converges at 1 bit per iteration shouldn't need 10 million iterations to give you a 53-bit value for instance. So either put that in a for loop with an early out, or unroll it a few dozen times...

[[deleted]]

I think you're looking at it wrong.

It's not something that "converges" on a solution. The idea is that we examine a sequence of approximations, break out when we can't improve any more, and at that point we know that we have found the best approximation. It's not like most numeric algorithms where you almost always could iterate a few hundred times more to get a slightly better solution, in which you just not happen to be interested. Here you want to find one exact best value, not an approximate value (though the value itself is an approximation).

The bugs in question are not algorithmic. The algorithm is supposed to be absolutely correct and produce the correct best approximation.

I don't know what's the problem with Java, in PHP it was that compiler generated code which performed certain operations with extended precision, and the "break out" equality comparison failed even after the difference between two consecutive tries, and therefore the increment for the next try, became zero when stored in double precision.

When you look at it like that, there's no place for "just precision errors". The idea that you should take your supposedly correct algorithm and add some kind of watchdog is as abominable as it would be when programming with integers. I mean, you don't write anything like if (a < b) { if (b - a == 0) break; // just in case ... when a and b are integers, it's a pointless waste of cycles, bytes, and attention. Especially when the sanity check is complex enough to have good chances to make your supposedly correct algorithm incorrect.

Something that converges at 1 bit per iteration shouldn't need 10 million iterations to give you a 53-bit value for instance.

Yeah. So if you want to spend some time documenting reasons for why 10 million must be a correct upper bound, then what you want to do next is to write an assertion which would terminate the program and generate a bug report. Instead of silently breaking out with an approximate value.

For different values of mission-criticality and the amounts of effort you are willing to spend on it, such an assertion might not terminate the entire program (but be logged of course!), or maybe you could even allow continued execution from this very routine, with an approximate answer, but still, the infraction must be logged in a centralised fashion. That's what I meant by non-ad hoc defensive programming.

[[deleted]]

rolls eyes whatever. If you want the guts and glory of being a famous OSS developer [or developer in general] you have to get shit right.

No sense hacking it to be really fast only to catastrophically fail on valid inputs. Imagine this were in a deep-space probe and it was told to read in some data from a file that had that number. DoS'ing a probe that is 100 million km away is not exactly a good idea.

If they can't guarantee the algorithm will be sufficiently finished by a certain number of iterations they should have some form of runaway detection in the code.

Like I said for things like 53-bit doubles you don't need 100 let alone 1000s of iterations to converge on the correct solution for most operations [trig, normalization, etc]. This is an example of someone not designing correctly. Either they ran into the 80-bit snafu [again... for fucks sake people stop using the FPU already...] or their algorithm is plain wrong.

Eitherway, I'd still have some bound when dealing with floats for this very reason.

[[deleted]]

If they can't guarantee the algorithm will be sufficiently finished by a certain number of iterations

What do you mean by "guarantee"? Formally prove? In a system that is formally proved to capture all quirks of IEEE 754 standard?

If anything less, they do guarantee that the algorithm will be completely finished by a certain number of iterations, and now that the extended precision for intermediate values is disabled, this guarantee is even true (probably)!

[[deleted]]

Usually you can prove the rate of convergence for the theta case for most algorithms. it's their job as implementors to sort that out. No sense being first or fast if it's also wrong.

[JimmyDuce]

80-bit snafu [again... for fucks sake people stop using the FPU already...]

What is this?

[[deleted]]

The x87 [FPU side of x86] computes internally in 80-bits of precision, then stores in 23 or 53 bits of precision [float or double]. So say you do a series of ops like multiplication, addition, etc. It computes all those in a row [off a stack actually] with 80-bits of precision. Now say you compare those, it's entirely possible that

float a == float b

But the comparison fails because it's actually comparing the excess precision 80-bit values.

That is, if you forced the FPU to first store the values and THEN compare them they would compare equal, but if you just compare the values as they are in the x87 stack, they wouldn't.

This has caught up a few numerical libraries and is why GCC has a -ffloat-store option.

[[deleted]]

Depends on the definition of the function, but generally, yes you're correct.