Message342802
> 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. |
|
Date |
User |
Action |
Args |
2019-05-18 17:07:57 | mark.dickinson | set | recipients:
+ mark.dickinson, serhiy.storchaka |
2019-05-18 17:07:57 | mark.dickinson | set | messageid: <1558199277.63.0.216554094257.issue36957@roundup.psfhosted.org> |
2019-05-18 17:07:57 | mark.dickinson | link | issue36957 messages |
2019-05-18 17:07:57 | mark.dickinson | create | |
|