Mark Dickinson <dicki...@gmail.com> added the comment:
> Did you try the floating point implementation? The aim here was to use exactly the same algorithm, but speed it up by working with C integers where possible; that's a fairly simple change. Using floating-point would require more complex changes. Again, the biggest issue with using a floating-point sqrt as an initial value is that we can't assume either IEEE 754 floating-point format, *or* a correctly rounded libm sqrt, even though both those things are highly likely on a typical modern machine. So any use of floating-point would also have to have an accuracy check and a fallback integer-only implementation for the case where the floating-point fails. It's possible to make those changes, but I think we'd end up crossing the threshold to "too complicated" for the implementation of a simple function. It's a bit of a shame, because if we _are_ allowed to assume IEEE 754, and a correctly-rounded sqrt implementation (using round-ties-to-even), then it turns out that one can prove that for any value `n` smaller than 2**106 and `a := int(math.sqrt(float(n)))` (assuming that the `int` and `float` conversions are *also* correctly rounded), we have (a - 1)**2 < n < (a + 1)**2, which is exactly the loop invariant that the current algorithm needs to maintain. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue36957> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
