Wow, that’s really cool! It’s like writing them in binary, but all rationals terminate!
But it seems like operating on rationals by converting/deconverting to index numbers would be really inefficient, and that article says:
From the perspective of efficiency, the Stern-Brocot tree is probably a bad idea. You may have noticed that the right branch of the tree contains all the whole numbers: this means that the whole part is encoded in unary. Beyond that, we generally have to convert to some fraction in order to do any calculation, which is massively expensive.
Actually, no. A weekly rate of 1 still only allows you to input decimal numbers, right? You can’t type “1 / 7”
in the input field, or can you? If you can, there’s no unit that’s going to save you; the only way is a rational number.
A goal with a weekly rate of 5 where you don’t have to work on the weekends needs 1 / 5 seconds, so maybe you want to store in 35th of a second? Nope, doesn’t make sense to start adding all the possibilities. If you allow rationals, you need to store them as rationals if you want to have them exactly preserved (or accept the consequences of floats).
Fun fact: a lot of tracker music is written with 24 divisions per beat instead of what the more usual 4/4 time signature might suggest (which would maybe be 16 divisions per beat, or 8), to allow both straight and triplet notes.
so it’s possible it’s rounding correctly when calculating whether you’re off the road or not (like in the above experiment), but it’s incorrectly rounding up when calculating pessimistically how much you have to do.
The easiest way to see an example of a floating point error is print(0.1 + 0.2):
As you can see, you don’t need to add many terms before the error creeps in. It is true, however, that so long as you stick to (small) integers you’ll be completely OK. That said, with large enough integers there can be another type of problem:
All in all, floats are just usable as a representation for numbers as we usually think of them: they should only be used in cases where speed is very important and accuracy isn’t.
For Beeminder in particular, there is basically no good reason whatsoever to use floats: Beeminder doesn’t care at all about any of the things floats are good for, and suffers heavily from the weak points that floats have. The one possible reason for Beeminder to use floats (and, I believe, the historical reason why Beeminder does) is that many programming languages (including Ruby) make floats very easy to use, and in fact have dedicated syntax support exclusively for floats. (Such as interpreting decimal literals (like 1.0) as floating point numbers.)
That’s the tradeoff, yes. If you’re doing heavy calculations, or even moderate calculations, you should pick another representation. But if you’re displaying numbers, or comparing numbers, or the like, then it can be very worthwhile. And many real-world use cases for numbers don’t really involve doing non-trivial computation on them, but instead lean rather heavily on the displaying and comparing side of things, for which the Stern-Brocot representation is amazing.
Beeminder is a good example of that: the calculation Beeminder does is on the level of summing perhaps a few hundred or a few thousand data points together to get the total: nothing particularly heavy, even in a representation that is bad at arithmetic.
Not that I’m saying that Beeminder should necessarily implement it this way: best to just use the Ruby standard library Rational class, which uses an (int, int) representation, because it’s right there and easy to use. Sure, there may be better theoretical representations, but it gets the job done and the difference doesn’t matter here too much.
Try it: enter a datapoint on a goal in the format 1/7, and you’ll see that Beeminder absolutely accepts this format. This is an awesome feature in some cases, although because the data is (currently) converted to a float behind the scenes it is a lot less useful then it has the potential to be.
We haven’t forgotten about this! Obviously the Right Fix is a bit involved so what we’ve done in the meantime is … noticed that in @narthur’s case this was caused by an errant “0.666666666666” that snuck in as part of this otherwise integery goal (to be clear, that part was @narthur’s fault, not Beeminder’s!) and just cleaned it up manually so the yellow brick road is defined in terms of integers again, as would normally be the case.
That also means that this bug might be quite rare (let us know when you spot instances of it!) so we’re going to try to detect it automatically but just shirk-n-turk it until we find that that’s untenable.
(Also to clarify for posterity, it’s still true that even with this bug, everything about your actual data is still quasi-impeccably correct to like a billionth of a goal unit. And we’re also impeccably conservative in never underestimating what you have to do for your beemergency when we round something. Just that it’s possible that if Beeminder thinks the bare min is 3.000000000000001 (when really it ought to have been just 3) we may conservatively tell you you have to do 4. Which is plenty bad, I’m just clarifying how bad. Also, we think, mercifully rare.)
(Also-also, huge thanks especially to @zzq for the highly edifying/enlightening thoughts on Rationals vs BigDecimals etc.)