How does a goal with a rate of 1 have +2 due?

[zedmango]

@zzq

But for many cases, the best way to represent fractional numbers is neither floats, nor decimals, nor even rationals stored as an (int, int) pair. Rather, it is rationals stored in the form of indexes into the Stern–Brocot tree . (The pg_rational extension I linked above actually uses this representation internally.) This post gives a good explanation of the subject

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.

[eugeniobruno]

@zedmango

The only catch is that 7 might be important, since there are 7 days in a week. A goal with a weekly rate of 1 needs 1/7 unit each day.

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.

[narthur]

Weirdly enough, after doing my 1 workout today, Beeminder is perfectly satisfied, even though at the beginning of the day it said 2 were required. But now it says that 2 are due tomorrow.

[eugeniobruno]

Hah, interesting. I’m going to quote myself here:

@eugeniobruno

I tried summing exact ones for a while:

>>> for i in range(10000000):
...   if k != float(i):
...     print(k, float(i))
...   k += float(1)

and the sum are exact, at least up to 10 million summed ones. Maybe if you sum stuff like 0.2 + 0.9 + 0.3 + 0.5 + 0.15 + 0.35, eventually you get the rounding error.

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.

[zedmango]

Ohhh that makes a lot more sense. So it’s just the way the rounding up is being done.

[eugeniobruno]

I want to stress that I’m speculating that’s what’s going on. Again, I’m no computer science number wizard.

[zedmango]

It seems very likely though.

[zzq]

@eugeniobruno

Wait, before sounding the alarm - my knowledge of floating point/numerical representations of numbers in computer science is very, very shallow. I tried summing exact ones for a while:

>>> for i in range(10000000):
...   if k != float(i):
...     print(k, float(i))
...   k += float(1)

and the sum are exact, at least up to 10 million summed ones. Maybe if you sum stuff like 0.2 + 0.9 + 0.3 + 0.5 + 0.15 + 0.35, eventually you get the rounding error.

Maybe we should ask @zzq, it seems like they know what they’re talking about (I had no idea about the existence of the Stern-Brocot tree…)

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.)

@zedmango

But it seems like operating on rationals by converting/deconverting to index numbers would be really inefficient

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.

@eugeniobruno

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.

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.

[eugeniobruno]

@zzq

For Beeminder in particular, there is basically no good reason whatsoever to use floats

@zzq

.

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

I feel really good about thinking the same way as the computer science number wizard. Floats are wrong for beeminder, and rationals would be the right representation.

[dreev]

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.)

[zedmango]

@dreev

noticed that in @narthur’s case this was caused by an errant “0.666666666666” that snuck in as part of this otherwise integery goal

Clearly it needs to be exorcised like this was!