Working with the set of real numbers

[Oscar Benjamin]

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:
>> 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