Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <bdbf27ac-65bc-43ed-88e1-9c0baca825f2@googlegroups.com>
References: <61d45045-187c-4be7-9da4-21a3124b753f@googlegroups.com> <d15afc73-a4f3-4c10-b66e-41ceceae0fa5@googlegroups.com> <bdbf27ac-65bc-43ed-88e1-9c0baca825f2@googlegroups.com>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Mon, 23 Sep 2013 11:40:52 +0100
Subject: Re: reload and work flow suggestions
To: rusi <rustompmody@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: Python List <python-list@python.org>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.258.1379932881.18130.python-list@python.org>
Lines: 194
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:54627

On 23 September 2013 10:35, rusi <rustompmody@gmail.com> wrote:
>> Then, I launch iPython, which can intellisense launch 3 easily. Then I m=
ake
>> whatever changes I need to 1-3 to make a baby step forward, close iPytho=
n,
>> and repeat.
>
> Hardly looks very ergonomic to me

I'm not quite sure what's meant by intellisense here but using ipython
with a scratch script works very well for me.

Here's how a typical session works for writing a sqrt_floor() function
that works for all positive integers:

In [1]: import math

In [2]: math.sqrt(16)
Out[2]: 4.0

In [3]: math.sqrt(15)
Out[3]: 3.872983346207417

In [4]: int(math.sqrt(15))
Out[4]: 3

In [5]: x =3D 10 ** 20 + 1

In [6]: int(math.sqrt(x ** 2)) =3D=3D x
Out[6]: False

In [7]: edit tmp.py

[At this point vim opens, I do some working on paper and write the
following in vim:

import math

def sqrt_floor(y):
    x =3D int(y)
    while x ** 2 <=3D y < (x+1) ** 2:
        x =3D (x + y // x) // 2
    return x
]

done. Executing edited code...

In [8]: sqrt_floor(100)
Out[8]: 100

In [9]: sqrt_floor(101)
Out[9]: 101

[Okay whoops! that's not what I wanted... Need to invert the condition
in the while loop!]

In [10]: edit tmp.py
 done. Executing edited code...

In [11]: edit tmp.py
 done. Executing edited code...

In [12]: sqrt_floor(101)
Out[12]: 10

In [13]: sqrt_floor(100)
Out[13]: 10

In [14]: x =3D 10 ** 20 + 1

In [15]: sqrt_floor(x ** 2) =3D=3D x
Out[15]: True

[Okay that's better]

In [16]: edit tmp.py

[Now I'll test against a load of integers so the file looks like

import math

def sqrt_floor(y):
    x =3D int(y)
    while not (x ** 2 <=3D y < (x+1) ** 2):
        x =3D (x + y // x) // 2
    return x


for y in range(10 ** 6):
    x =3D sqrt_floor(y)
    assert x ** 2 <=3D y < (x+1) ** 2
]
done. Executing edited code...

[All tests have passed but it took a little while so let's time this functi=
on]

In [17]: timeit sqrt(10 ** 10)
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<snip traceback>
NameError: global name 'sqrt' is not defined

In [18]: from math import sqrt

In [19]: timeit sqrt(10 ** 10)
1000000 loops, best of 3: 393 ns per loop

In [20]: timeit sqrt_floor(10 ** 10)
10000 loops, best of 3: 52.4 us per loop

In [21]: edit tmp.py

[Since sqrt is 100x faster we can use it internally to get an initial guess=
.
Now the file looks like:

import math

def sqrt_floor(y):
    x =3D int(math.sqrt(y))
    while not (x ** 2 <=3D y < (x+1) ** 2):
        x =3D (x + y // x) // 2
    return x


for y in range(10 ** 6):
    x =3D sqrt_floor(y)
    assert x ** 2 <=3D y < (x+1) ** 2
]
done. Executing edited code...

In [22]: timeit sqrt_floor(10 ** 10)
100000 loops, best of 3: 4.58 us per loop

[Great. That's 10x faster than before and probably as good as it gets
for speed but this optimisation has problems...]

In [23]: sqrt_floor(10 ** 1000)
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-23-378bf805089d> in <module>()
----> 1 sqrt_floor(10 ** 1000)

Q:\tmp.py in sqrt_floor(y)
      2
      3 def sqrt_floor(y):
----> 4     x =3D int(math.sqrt(y))
      5     while not (x ** 2 <=3D y < (x+1) ** 2):
      6         x =3D (x + y // x) // 2

OverflowError: long int too large to convert to float

In [24]: edit tmp.py

[Now the file looks like

import math

def sqrt_floor(y):
    try:
        x =3D int(math.sqrt(y))
    except OverflowError:
        x =3D y
    while not (x ** 2 <=3D y < (x+1) ** 2):
        x =3D (x + y // x) // 2
    return x


for y in range(10 ** 6):
    x =3D sqrt_floor(y)
    assert x ** 2 <=3D y < (x+1) ** 2
]

 done. Executing edited code...
[ This reruns the tests in the file; no AssertionError so all good ]

In [25]: sqrt_floor(10 ** 1000)
Out[25]: 100000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000000000000000000=
000000000000000000000000000000000000000000000000000000000000L

In [26]: timeit sqrt(10 ** 10)
1000000 loops, best of 3: 381 ns per loop

And now we're basically done. Recheck the proof, think about how to
handle negative numbers, write a docstring and move on.


Oscar