Working with the set of real numbers

[Oscar Benjamin]

On 4 March 2014 22:18, Chris Angelico <rosuav at gmail.com> wrote:
> On Wed, Mar 5, 2014 at 9:02 AM, Oscar Benjamin
> <oscar.j.benjamin at gmail.com> wrote:
>> On 4 March 2014 21:18, Chris Angelico <rosuav at gmail.com> wrote:
>>> On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin
>>> <oscar.j.benjamin at gmail.com> wrote:
>>>
>>> epsilon = 0.0001
>>> def sqrt(n):
>>>     guess1, guess2 = 1, n
>>>     while abs(guess1-guess2) > epsilon:
>>>         guess1 = n/guess2
>>>         guess2 = (guess1 + guess2)/2
>>>    return guess1
>>
>> That's the exact same algorithm I showed! How on earth would you call
>> that brute force?
>
> It uses a lot of division. There are various refinements that can be
> done that replace some of that division with multiplication, but I'd
> have to go do some research to figure it out.

There's a description of such a method here:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots

I don't know whether that would work out faster (when using decimal -
for float it would probably be slower).

> Let's compare two
> versions. In the first, you set the precision (I'm talking in terms of
> REXX's "NUMERIC DIGITS" statement

I have no idea what that is.

>- anything beyond this many digits
> will be rounded (and represented exponentially, if necessary); I'm not
> sure if decimal.Decimal precision works this way) such that you get 10
> digits.

With the decimal module if you set the precision to 5 digits then it
basically represents the number in "standard form" with 5 digits .e.g:
1.2345 x 10**21.

> Each iteration requires division by a 10-digit number, which
> is an operation that takes a certain amount of time; and it's going to
> take some number of iterations to get to the final answer.
>
> Second version, you set the precision so you get 20 digits.

If we're talking about 10-20 digits then the decimal module is
overkill: just use float. The speed up from hardware arithmetic will
massively out-weigh any other performance considerations. My version
was intended to produce large numbers of digits which is when the
big-O comes in:

$ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 10)'
10000 loops, best of 3: 22.4 usec per loop
$ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 100)'
10000 loops, best of 3: 59.1 usec per loop
$ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 1000)'
1000 loops, best of 3: 1.15 msec per loop
$ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 10000)'
10 loops, best of 3: 85.9 msec per loop
$ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 100000)'
10 loops, best of 3: 1.59 sec per loop


Oscar