On 4 March 2014 23:20, Dave Angel <da...@davea.name> wrote:
>
> 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.
Agreed but there's a big difference between log(N) iterations and N iterations!
> 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
I gues you mean like this:
def sqrt(n):
err = guess = 1
while err > 1e-10:
err = n - guess * guess
guess += err/2
return guess
This requires log2(10)*N iterations to get N digits. So the penalty
for using division would have to be extreme in order for this to
better. Using Decimal to get many digits we can write that as:
def sqrt2(n, prec=1000):
'''Solve x**2 = y'''
eps = D(10) ** -(prec + 5)
err = guess = D(1)
with localcontext() as ctx:
ctx.prec = prec + 10
while abs(err) > eps:
err = n - guess*guess
guess += err/2
return guess
This method works out much slower than Newton with division at 10000
digits: 40s (based on a single trial) vs 80ms (timeit result).
> 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.
If you're working with a fixed small precision then it might be.
> 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.
I'm curious.
Oscar
--
https://mail.python.org/mailman/listinfo/python-list
