On Mon, Sep 07, 2015 at 06:20:02PM -0400, Raul Miller wrote:
> On Mon, Sep 7, 2015 at 6:03 PM, Ted Unangst <[email protected]> wrote:
> > Michael Warmuth-Uhl wrote:
> >> On 2015-09-07, Otto Moerbeek wrote:
> >> It seems to fix the issues on amd64, but I'm not sure if the accuracy of
> >> long double and sqrtl is guaranteed to be enough in general.
> >
> > using floating point seems suspect. i think what's needed is an integer sqrt
> > function.
>
> Floating point works fine for integers as long as your integers fit
> within the mantissa component of the floating point representation.
>
> Assuming the usual IEEE-754 implementation:
>
> For double, this means integers cannot exceed 2^53 (9007199254740992)
> without losing least significant bits (2^53-1 can be represented, 2^53
> can be represented but has lost the least significant bit so typically
> that means it's assumed to be zero - which is fine, but that means
> that 1+2^53 cannot be represented).
>
> For long double, this means integers cannot exceed 2^113
> (10384593717069655257060992658440192) without losing least significant
> bits.
>
> That said, you can implement integer square root using binary search.
My bet would be Newton iteration, which should converge faster than
binary search. ping(8) has an implementation of integer sqrt.
BTW, long double won't fix the problem on al platforms since it is not
guaranteed to be longer than double.
-Otto
