search

jlouis / glicko2

Glicko 2 computations in Go
Other
6 stars 1 forks source link

Strange Behaviour on golang >1.7 #2

Open 0x4139 opened 7 years ago

0x4139 commented 7 years ago

Running the same code with the same input several times gives a different result each time. Doesn't really make sense why.

jlouis commented 7 years ago

This is a peculiar bug, because there is no source of randomness in the code which could make execution become non-deterministic. However, there is lots of floating point computations and the result is likely to skew a bit for numbers that are close but different from an FP perspective: you will likely have to regard numbers to be equal if they are within some window of each other.

So in particular:

There may be a bug, but it would help tremendously in tracking it down.

The other part of the glicko2 algorithm which tend to be ridden with numerical stability issues is the root-finder needed to compute the volatility value (sigma). The code here uses Ridder's method, which should be numerically stable. The official paper used to do a Newton-Raphson, but it was replaced with a bisection method (as NR is numerically instable given floating point computations). Ridder's method is an improvement: it is often faster than bisection, and is also numerically stable.

However, given the same input, these functions ought to return the same output. There is no non-determinism in there. Of course, being floating point, a newer Go compiler might choose to reorder floating point arithmetic which can give different results. And I would also expect the results to be off if you ran the computation on an ARM compared to an x86-64.

0x4139 commented 7 years ago

I'm sorry i didn't replied earlier, I was really curious in why such strange behavior would appear, so from what i investigated it's related on how GO compiler reorders floating points in a map. Sorry for the misleading title at the beginning.

jlouis commented 7 years ago

Reorders floating points in a map? The map order is undefined on traversal and has always been since day one, but I'm not sure I understand how you store FP values in the map?

The numbers you are seeing.. are they very close to each other, or are they far off? I don't think the algorithm has been built up with the idea of numerical stability, but it shouldn't wander off with numbers that are completely off.