On 4 March 2014 22:18, Chris Angelico <ros...@gmail.com> wrote: > On Wed, Mar 5, 2014 at 9:02 AM, Oscar Benjamin > <oscar.j.benja...@gmail.com> wrote: >> 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: >>> >>> 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 uses a lot of division. There are various refinements that can be > done that replace some of that division with multiplication, but I'd > have to go do some research to figure it out.
There's a description of such a method here: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots I don't know whether that would work out faster (when using decimal - for float it would probably be slower). > Let's compare two > versions. In the first, you set the precision (I'm talking in terms of > REXX's "NUMERIC DIGITS" statement I have no idea what that is. >- anything beyond this many digits > will be rounded (and represented exponentially, if necessary); I'm not > sure if decimal.Decimal precision works this way) such that you get 10 > digits. With the decimal module if you set the precision to 5 digits then it basically represents the number in "standard form" with 5 digits .e.g: 1.2345 x 10**21. > Each iteration requires division by a 10-digit number, which > is an operation that takes a certain amount of time; and it's going to > take some number of iterations to get to the final answer. > > Second version, you set the precision so you get 20 digits. If we're talking about 10-20 digits then the decimal module is overkill: just use float. The speed up from hardware arithmetic will massively out-weigh any other performance considerations. My version was intended to produce large numbers of digits which is when the big-O comes in: $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 10)' 10000 loops, best of 3: 22.4 usec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 100)' 10000 loops, best of 3: 59.1 usec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 1000)' 1000 loops, best of 3: 1.15 msec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 10000)' 10 loops, best of 3: 85.9 msec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 100000)' 10 loops, best of 3: 1.59 sec per loop Oscar -- https://mail.python.org/mailman/listinfo/python-list