Re: Challenge: find the first value where two functions differ

Chris Angelico writes: > 4503599761588224 I get the same result from searching a wider interval (+/- 50) around each perfect square in the relevant range. -- https://mail.python.org/mailman/listinfo/python-list

Re: Challenge: find the first value where two functions differ

On Sat, 5 Aug 2017 06:17 am, Terry Reedy wrote: [...] > With 53 binary digits, all counts from 0 to 2**53 - 1 are exactly > represented with a exponent of 0, 2**53 = 2**52 * 2, so it is exactly > represented with an exponent of 1. Many other higher counts can be > exactly represented with

Re: Challenge: find the first value where two functions differ

On 8/4/2017 11:44 AM, Chris Angelico wrote: On Sat, Aug 5, 2017 at 12:51 AM, Steve D'Aprano wrote: def isqrt_float(n): """Integer square root using floating point sqrt.""" return int(math.sqrt(n)) The operations in the integer version are well-defined

Re: Challenge: find the first value where two functions differ

On Sat, 5 Aug 2017 02:00 am, Ian Kelly wrote: > On Fri, Aug 4, 2017 at 9:47 AM, Chris Angelico wrote: >> On Sat, Aug 5, 2017 at 1:44 AM, Chris Angelico wrote: >>> That gave me this result almost instantaneously: >>> >>> 4503599761588224 >>> >>> which has been

Re: Challenge: find the first value where two functions differ

On Fri, Aug 4, 2017 at 10:03 AM, Ian Kelly wrote: > On Fri, Aug 4, 2017 at 10:00 AM, Ian Kelly wrote: >> On Fri, Aug 4, 2017 at 9:47 AM, Chris Angelico wrote: >>> On Sat, Aug 5, 2017 at 1:44 AM, Chris Angelico

Re: Challenge: find the first value where two functions differ

On Sat, Aug 5, 2017 at 4:03 AM, Ian Kelly wrote: > On Fri, Aug 4, 2017 at 11:59 AM, Ian Kelly wrote: >> On Fri, Aug 4, 2017 at 11:50 AM, Chris Angelico wrote: >>> My logic was that floating point rounding is easiest to notice when

Re: Challenge: find the first value where two functions differ

On Sat, Aug 5, 2017 at 3:51 AM, Steve D'Aprano wrote: > On Sat, 5 Aug 2017 02:31 am, MRAB wrote: > >> Why would isqrt_float not give the correct answer? Probably because of >> truncation (or rounding up?) of the floating point. I'd expect it to >> fail first near a

Re: Challenge: find the first value where two functions differ

On Sat, 5 Aug 2017 01:44 am, Chris Angelico wrote: > Hmm. Thinking aloud a bit here. We know that isqrt_float(n) is not > technically *exact* for any n that is not a square. I got bogged down in answering that misapprehension, but it may not actually have mattered. You then said: > So what

Re: Challenge: find the first value where two functions differ

On Fri, Aug 4, 2017 at 11:59 AM, Ian Kelly wrote: > On Fri, Aug 4, 2017 at 11:50 AM, Chris Angelico wrote: >> My logic was that floating point rounding is easiest to notice when >> you're working with a number that's very close to something, and since >>

Re: Challenge: find the first value where two functions differ

On Fri, Aug 4, 2017 at 11:50 AM, Chris Angelico wrote: > My logic was that floating point rounding is easiest to notice when > you're working with a number that's very close to something, and since > we're working with square roots, "something" should be a perfect > square. The

Re: Challenge: find the first value where two functions differ

On Fri, Aug 4, 2017 at 11:44 AM, Steve D'Aprano 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

Re: Challenge: find the first value where two functions differ

On Sat, 5 Aug 2017 02:31 am, MRAB wrote: > Why would isqrt_float not give the correct answer? Probably because of > truncation (or rounding up?) of the floating point. I'd expect it to > fail first near a square. Assuming your math.sqrt() is an IEEE-754 correctly-rounded square root, and that

Re: Challenge: find the first value where two functions differ

On Sat, Aug 5, 2017 at 3:44 AM, Steve D'Aprano 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

Re: Challenge: find the first value where two functions differ

On Sat, Aug 5, 2017 at 3:37 AM, Steve D'Aprano wrote: > On Sat, 5 Aug 2017 01:44 am, Chris Angelico wrote: > >> On Sat, Aug 5, 2017 at 12:51 AM, Steve D'Aprano >> wrote: >>> def isqrt_float(n): >>> """Integer square root using floating

Re: Challenge: find the first value where two functions differ

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

Re: Challenge: find the first value where two functions differ

On Sat, 5 Aug 2017 01:44 am, Chris Angelico wrote: > On Sat, Aug 5, 2017 at 12:51 AM, Steve D'Aprano > wrote: >> def isqrt_float(n): >> """Integer square root using floating point sqrt.""" >> return int(math.sqrt(n)) [...] > Hmm. Thinking aloud a bit here. We

Re: Challenge: find the first value where two functions differ

On 2017-08-04 15:51, Steve D'Aprano wrote: This is a challenge for which I don't have a complete answer, only a partial answer. Here are two functions for calculating the integer square root of a non-negative int argument. The first is known to be exact but may be a bit slow: def

Re: Challenge: find the first value where two functions differ

On Fri, Aug 4, 2017 at 9:47 AM, Chris Angelico wrote: > On Sat, Aug 5, 2017 at 1:44 AM, Chris Angelico wrote: >> That gave me this result almost instantaneously: >> >> 4503599761588224 >> >> which has been rounded up instead of down. I don't know if that

Re: Challenge: find the first value where two functions differ

On Fri, Aug 4, 2017 at 10:00 AM, Ian Kelly wrote: > On Fri, Aug 4, 2017 at 9:47 AM, Chris Angelico wrote: >> On Sat, Aug 5, 2017 at 1:44 AM, Chris Angelico wrote: >>> That gave me this result almost instantaneously: >>> >>>

Re: Challenge: find the first value where two functions differ

Well I tried a handomatic binary search and this number seems to differ 33347481357698898183343210233857L whereas this does not 33347481357698898183343210233856L On 04/08/2017 15:51, Steve D'Aprano wrote: This is a challenge for which I don't have a complete answer, only a partial answer.

Re: Challenge: find the first value where two functions differ

On Fri, Aug 4, 2017 at 8:51 AM, Steve D'Aprano wrote: > This is a challenge for which I don't have a complete answer, only a partial > answer. > > Here are two functions for calculating the integer square root of a > non-negative > int argument. The first is known to

Re: Challenge: find the first value where two functions differ

On 04/08/17 15:51, Steve D'Aprano wrote: Another hint: if you run this code: for i in range(53, 1024): n = 2**i if isqrt_newton(n) != isqrt_float(n): print(n) break you can find a much better upper bound for M: 2**53 < M <= 2**105 which is considerable

Re: Challenge: find the first value where two functions differ

On Sat, Aug 5, 2017 at 1:44 AM, Chris Angelico wrote: > That gave me this result almost instantaneously: > > 4503599761588224 > > which has been rounded up instead of down. I don't know if that counts > as sufficiently wrong? Oh, and I forgot to say: I have no actual *proof*

Re: Challenge: find the first value where two functions differ

On Sat, Aug 5, 2017 at 12:51 AM, Steve D'Aprano wrote: > def isqrt_float(n): > """Integer square root using floating point sqrt.""" > return int(math.sqrt(n)) > > > > We know that: > > - for n <= 2**53, isqrt_float(n) is exact; > > - for n >= 2**1024,

Challenge: find the first value where two functions differ

This is a challenge for which I don't have a complete answer, only a partial answer. Here are two functions for calculating the integer square root of a non-negative int argument. The first is known to be exact but may be a bit slow: def isqrt_newton(n): """Integer sqrt using Newton's