osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Challenge: find the first value where two functions differ


On Fri, Aug 4, 2017 at 11:44 AM, Steve D'Aprano
<steve+python at pearwood.info> wrote:
> On Sat, 5 Aug 2017 01:47 am, Ian Kelly wrote:
>
>> Here's a much smaller upper bound:
>>
>>>>> n = 2 ** 53
>>>>> s = isqrt_newton(n)
>>>>> n
>> 9007199254740992
>>>>> s
>> 94906265
>>>>> m = (s+1)**2 - 1
>>>>> m
>> 9007199326062755
>>>>> isqrt_newton(m) == isqrt_float(m)
>> False
>
> Oooh, interesting. How did you get that? By luck, or do you have some reason for
> picking (s+1)**2 - 1?

Partly luck. I reasoned that a mismatch would be due to incorrect
rounding, which would most likely happen just before a perfect square.
So I tried the value one less than the first perfect square after 2 **
53 and it happened to work. I also tried the value two less, which did
not.

In any case, Chris's finding beats mine by a factor of two.