On 4 March 2014 21:18, Chris Angelico <ros...@gmail.com> wrote: > On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin > <oscar.j.benja...@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 -- https://mail.python.org/mailman/listinfo/python-list