Working with the set of real numbers
Dave Angel
davea at davea.name
Wed Mar 5 00:20:20 CET 2014
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
More information about the Python-list
mailing list