why 'lambda' and 'reduce'?

[Manuel Garcia]

On Fri, 13 Jun 2003 19:35:11 -0600, Steven Taschuk
<staschuk at telusplanet.net> wrote:

>I think the expression
>    (S((x*y)//F))**2
>is a bit obfuscated.  Modulo rounding error, it's equivalent to
>x*y, nyet?

I made the change, ran the program, had Python compare the digits to
the digits I downloaded, and you are right.

If you use the version with the extra 'lambda' to set x1 and y1, you
will see the reason for my mistake.  In the correct version, I need to
know S((x*y)//F) to keep the iteration happy, so I set x1, and x1*x1
is just another way of saying x*y, and no more expensive to compute.
Before I put in the final 'lambda', I made a thoughtless
cut-and-paste.

I would be lying if I said I understood the iteration more than just
to copy it ;-)

(hmm, if I put an _another_ lambda to store the result of x*y, I might
be able to make it faster...)

This weekend I will be trying to have Python figure out 1,000,000
digits, and I will keep your observation in mind, because I will need
every last bit of speed.

>This is the point which still puzzles me -- I see no obvious
>reason for the rounding error not to propagate.  My experiments
>with the code haven't turned up a case with more than about five
>wrong digits, but I'd expect a proof of stability to be quite
>involved.

Compare it to Newton's method for finding the square root.  (I had to
implement this in my code, to get the square roots for these massive
numbers).  Newton's method is also an iteration, and it is also
quadratic, so the number of correct digits doubles with each step.
You can draw the geometry behind the calculus, and you will see each
step gives the iteration a much better chance to leap closer to the
true value.  With Newton's method, it is not mysterious.  All these
guys have done is find a way of computing Pi that works just as well
as Newton's method finds the square root.  The error never gets a
chance to propagate, in fact a large percentage is sliced off each
step, in fact the percentage grows with each step.

(How is that for hand waving? ;-)

>> What looked like 'geometrical mean' was actually my having to
>> implement a square root function with Newton's method, [...]
>
>Geometric mean is a specific case of square root -- the gm of two
>numbers is the square root of their product.  Note, incidentally,
>that this is the multiplicative equivalent of the arithmetic mean:

I was just trying to figure out what you thought I was 'obfuscating'.
My code consists of Newton's method for the square root, and a copied
quadratic iteration for finding Pi, and nothing else (except a cute
trick with 'reduce' ;-)  Christopher Craig and Tim Peters supplied the
efficient long integer implimentation.

BTW, please except my apology for my being a butthead earlier.

Manuel