why 'lambda' and 'reduce'?
Steven Taschuk
staschuk at telusplanet.net
Sat Jun 14 16:38:31 CEST 2003
Quoth Manuel Garcia:
> On Fri, 13 Jun 2003 19:35:11 -0600, Steven Taschuk
> <staschuk at telusplanet.net> wrote:
[...]
> >This is the point which still puzzles me -- I see no obvious
> >reason for the rounding error not to propagate. [...]
[the AGM converges quadratically]
> [...] so the number of correct digits doubles with each step.
> [...] The error never gets a chance to propagate, [...]
> (How is that for hand waving? ;-)
That's a superb handwave, actually. I am persuaded, in principle.
Assuming the arithmetic of each iteration introduces error which
is less than quadratic in the number of iterations so far... which
is very plausible, without even looking at the code again.
And that the initial state is "correct enough" to get it all
started. (The quadratic convergence might just be asymptotic
behaviour; initially it might have much worse behaviour, and thus
susceptible to the arithmetic error.)
And, of course, that the AGM algorithm converges quadratically.
(Let's leave proving that to the professionals.)
[...]
> I was just trying to figure out what you thought I was 'obfuscating'.
Well, the lambdas do make the code unreadable, as you pointed out.
I'm not sure about the speed advantage you refer to; for example,
the simple-minded rewrite
scale = 10L**5010
def sqrt(n):
guess = n//2L
for _ in range(15):
guess = guess - guess//2L + n*scale//(2L*guess)
return guess
x, y, t, a = scale, scale*scale//sqrt(2L*scale), 2L, scale//2L
for _ in range(13):
x, y = (x+y)//2L, sqrt((x*y)//scale) # arith & geo means!
a = a - t*(x**2 - y**2)//scale
t = 2L*t
s = str(2L*x*x//a)
print s[0] + '.' + s[1:5000]
does not (on my machine, with Python 2.3b1) have noticeably
different run-time. And more obvious optimizations make much
bigger differences anyway; try the above with
def sqrt(n):
guess = n//2L
n = n*scale
for _ in range(15):
guess = guess - guess//2L + n//(2L*guess)
return guess
for example.
[...]
> BTW, please except my apology for my being a butthead earlier.
Ah... well, there's a problem with that, I'm afraid. I've already
dispatched the goons with baseball bats -- they're on the plane, I
can't call them back... sorry.
(Really, no apology needed -- I contributed my share of rudeness,
and I think we've worked out our little spat in email anyway.
Water under the Usenet.)
--
Steven Taschuk staschuk at telusplanet.net
"Its force is immeasurable. Even Computer cannot determine it."
-- _Space: 1999_ episode "Black Sun"
More information about the Python-list
mailing list