Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed4.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: <CAPTjJmocK7Wpi765JKiNxEtquabm4No9GWomHv-vX7auFkqZ=w@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>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Tue, 4 Mar 2014 22:02:15 +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.7754.1393970560.18130.python-list@python.org>
Lines: 60
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:67737

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:
>> I don't quite follow your reasoning here. By "cut-and-try" do you mean
>> bisection? If so it gives the first N decimal digits in N*log2(10)
>> iterations. However each iteration requires a multiply and when the
>> number of digits N becomes large the multiplication is worse than
>> linear. So the result is something like N**2 log(N)log(log(N)),
>
> By "cut and try" I'm talking about the really REALLY simple algorithm
> for calculating square roots. It's basically brute force.
>
> 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's generally going to take roughly O(n*n) time to generate n digits,
> give or take.

It does not take O(n*n) time. This is Newton iteration and for
well-behaved problems such as this it generates more than n digits
after n iterations. I modified my code to show the error (x**2 - y) at
each iteration:

$ python3.3 root.py
2
0.2
0.007
0.000006
5E-12
3E-24
8E-49
8E-98
8E-196
9E-392
1E-783

The number of correct digits doubles at each iteration so after n
iterations you have 2**n digits (I misstated this as n**2 before).
This means that it takes log(N) iterations to get N digits. See here
for more:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method

See also the section below that:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation

> That's the baseline against which anything else can be
> compared. There are plenty of better ways to calculate them.

Such as?


Oscar