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
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 various
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 and so the answer
should be th
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 rounded up instead of down. I don't
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 wrote:
That gave me this result almost instantaneously:
45035997615882
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
>>> you're working with a number that's very close to something,
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 square.
>
> Assuming your math.s
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 I'd
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
>> we're working with square roots, "somethin
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 integer square root
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
>> 9007199326062755
> isq
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
int
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
>> 9007199326062755
> isqr
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 point sqrt."""
>>> return int(math.sqrt(n))
> [...]
>
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
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 know that isqrt_float(n) is
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 isqrt_newton(n
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 counts
>> as sufficiently wrong?
>
> Oh, a
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:
>>>
>>> 4503599761588224
>>>
>>> which has been rounded up instead of down. I do
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.
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 be exact but may be a bit slo
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 small
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* that this is the
lowe
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, isqrt_float(n) will raise OverflowErro
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 Method.
25 matches
Mail list logo
