reload and work flow suggestions

[Oscar Benjamin]

On 23 September 2013 10:35, rusi <rustompmody at gmail.com> wrote:
>> Then, I launch iPython, which can intellisense launch 3 easily. Then I make
>> whatever changes I need to 1-3 to make a baby step forward, close iPython,
>> 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 = 10 ** 20 + 1

In [6]: int(math.sqrt(x ** 2)) == 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 = int(y)
    while x ** 2 <= y < (x+1) ** 2:
        x = (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 = 10 ** 20 + 1

In [15]: sqrt_floor(x ** 2) == 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 = int(y)
    while not (x ** 2 <= y < (x+1) ** 2):
        x = (x + y // x) // 2
    return x


for y in range(10 ** 6):
    x = sqrt_floor(y)
    assert x ** 2 <= y < (x+1) ** 2
]
done. Executing edited code...

[All tests have passed but it took a little while so let's time this function]

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 = int(math.sqrt(y))
    while not (x ** 2 <= y < (x+1) ** 2):
        x = (x + y // x) // 2
    return x


for y in range(10 ** 6):
    x = sqrt_floor(y)
    assert x ** 2 <= 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 = int(math.sqrt(y))
      5     while not (x ** 2 <= y < (x+1) ** 2):
      6         x = (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 = int(math.sqrt(y))
    except OverflowError:
        x = y
    while not (x ** 2 <= y < (x+1) ** 2):
        x = (x + y // x) // 2
    return x


for y in range(10 ** 6):
    x = sqrt_floor(y)
    assert x ** 2 <= 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]: 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L

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