Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #80072

Re: Challenge: optimizing isqrt

Show key headers only | View raw

On Sat, Nov 1, 2014 at 12:29 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Q1: What is the largest value of M, such that
>
> all(isqrt(i) == int(math.sqrt(n)) for n in range(M))
>
> returns True?
>
> I have done a brute force test, and in nine hours confirmed that M is at
> least 7627926244. That took nine hours, and I expect that a brute force
> test of every int representable as a float would take *months* of
> processing time.

Here's something that should be faster than pure brute-force:

import math
for i in range(2**34): # 2**34 should take about nine hours
    sqrt = int(math.sqrt(i))
    if sqrt * sqrt > i:
        print("Too high at %d" % i)
        break
    if (sqrt+1) * (sqrt+1) <= i:
        print("Too low at %d" % i)
        break

There are two ways int(math.sqrt(i)) can be wrong: it can return a
number that's too high, or one that's too low. If it's too high,
squaring it (btw, int*int seems to be faster than int**2) will produce
a number higher than the original. If the result was too low, then the
next number up would have been within the correct bounds. There's no
need to actually calculate isqrt here.

I was able to probe up to 2**29 in seven minutes on my computer
(allocating one core, CPython 3.5 from trunk). If it's linear, going
as far as 2**34 should take no more than the nine hours you spent. I
expect time will be a bit worse than linear (working with small
numbers is marginally faster than working with big numbers), but if
it's at least reasonably close, probing as far as 2**53 would take
81555 days. So, uhh, a brute force by your method is going to take a
lot more than months. (And 2**53 isn't technically where ints stop
being representable, but I'd use that as the final cut-off, as it's
where *all* ints stop being representable. In any case, there's a
failure at 2**54-1, so there's no need to go past there.)

Hmm. The speed difference between your brute force and mine isn't all
that much. I'm estimating maybe doing at best twice as much in the
same time. So you're probably already using something similar to the
above, and this isn't adding much to the discussion. :(

ChrisA

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Challenge: optimizing isqrt Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-11-01 12:29 +1100
  Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 13:12 +1100
  Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:02 +0100
    Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:09 +0100
    Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 19:13 +1100
      Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:25 +0100
        Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 19:33 +1100
          Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:38 +0100
            Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 19:45 +1100
  Re: Challenge: optimizing isqrt Akira Li <4kir4.1i@gmail.com> - 2014-11-01 12:12 +0300
  Re: Challenge: optimizing isqrt Serhiy Storchaka <storchaka@gmail.com> - 2014-11-20 20:00 +0200
  Re: Challenge: optimizing isqrt Stephen Tucker <stephen_tucker@sil.org> - 2014-11-21 08:15 +0000
  Re: Challenge: optimizing isqrt Dave Angel <davea@davea.name> - 2014-11-23 10:43 -0500
  Re: Challenge: optimizing isqrt Serhiy Storchaka <storchaka@gmail.com> - 2014-11-25 21:31 +0200
  Re: Challenge: optimizing isqrt Dave Angel <davea@davea.name> - 2014-11-25 19:46 -0500
  Re: Challenge: optimizing isqrt Stephen Tucker <stephen_tucker@sil.org> - 2014-11-26 07:57 +0000
    Re: Challenge: optimizing isqrt Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-11-26 21:25 +1100
  Re: Challenge: optimizing isqrt Serhiy Storchaka <storchaka@gmail.com> - 2014-11-26 18:24 +0200

csiph-web