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
