Working with the set of real numbers

[Dave Angel]

 Oscar Benjamin <oscar.j.benjamin at gmail.com> Wrote in message:
> On 4 March 2014 21:18, Chris Angelico <rosuav at gmail.com> wrote:
>
> 
> 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?
> 

One problem with complexity claims is that it's easy to miss some
 contributing time eaters. I haven't done any measuring on modern
 machines nor in python, but I'd assume that multiplies take
 *much* longer for large integers, and that divides are much
 worse. So counting iterations isn't the whole story.
 

On the assumption that division by 2 is very fast,  and that a
 general multiply isn't too bad, you could improve on Newton by
 observing that the slope is 2.

   err = n - guess * guess
    guess += err/2

Some 37 years ago I microcoded  a math package which included
 square root.  All the math was decimal, and there was no hardware
 multiply or divide. The algorithm I came up with generated the
 answer one digit at a time, with no subsequent rounding needed.
 And it took just a little less time than two divides. For that
 architecture,  Newton's method would've been too
 slow.

Incidentally, the algorithm did no divides, not even by 2. No
 multiplies either.  Just repeated subtraction,  sorta like divide
 was done.

If anyone is curious,  I'll be glad to describe the algorithm; 
 I've never seen it published, before or since.  I got my
 inspiration from a method used in mechanical,  non-motorized, 
 adding machines.  My father had shown me that approach in the
 50's. 



-- 
DaveA