Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!xlned.com!feeder5.xlned.com!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAPTjJmpcM9vLG8pKqDtOBgMDpbo3S2N+7Dv7BAPKbhNTjOTA4g@mail.gmail.com>
References: <8e4c1ab1-e65d-483f-ad9d-6933ae2052c3@googlegroups.com> <CAPTjJmo4qD2B7isr8yAK2t+22KqwaoFrT5b5U66mYe+VgwDkWA@mail.gmail.com> <85r478bv99.fsf_-_@benfinney.id.au> <mailman.6735.1392194885.18130.python-list@python.org> <53153e66$0$24931$e4fe514c@dreader36.news.xs4all.nl> <mailman.7687.1393902132.18130.python-list@python.org> <59dd57ad-39b0-4c71-a58e-b4ae6517b385@googlegroups.com> <mailman.7689.1393904790.18130.python-list@python.org> <53156a42$0$2923$c3e8da3$76491128@news.astraweb.com> <mailman.7696.1393914922.18130.python-list@python.org> <87iortoic0.fsf@elektro.pacujo.net> <CAPTjJmpKASpOEscAjVDC5bpqK1kQt3rLTmCmUp-s4Ov2go6d2g@mail.gmail.com> <CAHVvXxR2TQzoiedi9Dns9RTMr_HVE_A5_tVWPGq_PmQ7zeV9Qw@mail.gmail.com> <CAPTjJmocK7Wpi765JKiNxEtquabm4No9GWomHv-vX7auFkqZ=w@mail.gmail.com> <CAHVvXxTSFnzZbRH2=xRr+yxidmTrUyCYsFPABOQBp3U5_2_-tQ@mail.gmail.com> <CAPTjJmpcM9vLG8pKqDtOBgMDpbo3S2N+7Dv7BAPKbhNTjOTA4g@mail.gmail.com>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Tue, 4 Mar 2014 22:54:01 +0000
Subject: Re: Working with the set of real numbers
To: Chris Angelico <rosuav@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Cc: "python-list@python.org" <python-list@python.org>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.7762.1393973669.18130.python-list@python.org>
Lines: 68
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:67746

On 4 March 2014 22:18, Chris Angelico <rosuav@gmail.com> wrote:
> On Wed, Mar 5, 2014 at 9:02 AM, Oscar Benjamin
> <oscar.j.benjamin@gmail.com> wrote:
>> On 4 March 2014 21:18, Chris Angelico <rosuav@gmail.com> wrote:
>>> On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin
>>> <oscar.j.benjamin@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