Tim Peters <t...@python.org> added the comment:
Oh yes - I understood the intent of the code. It's as good an approach to living with floating-point slop in this context as I've seen. It's not obviously broken. But neither is it obviously correct, and after a few minutes I didn't see a clear path to rigorously proving it can't break. In FP, if there's one chance in 2**53 that it _can_ break, it will ;-) The suggestions I made change none of that: reducing the number of rounding errors can only help. OTOH, an all-integer version of the algorithm _can_ be "obviously correct", and can embed asserts to verify that it is. It can all be done in a single fixed-size list of 3-lists ([weight, value, alias]), swapping entries as needed to keep the 3 regions of interest ("too small", "on the nose", "too large") each contiguous. Then it's straightforward to prove that you run out of "too small" entries at the same time you run out of "too large" ones. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue41131> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com