mwh at python.net
Thu Jan 24 10:46:48 CET 2002
"Alex Martelli" <aleax at aleax.it> writes:
> "Bengt Richter" <bokr at oz.net> wrote in message
> news:a2oh1f$de8$0 at 184.108.40.206...
> > Well, that's looking for the fastest way to do the same algorithm (unless
> > gmpy.fac() does something different) ...
> It calls GMP's factorial, and I haven't examined it but I believed the
> latter just did N multiplications (each a rather fast one). Skip's
> measurements suggest there may be something better going on inside
> GMP's factorial, but I don't have GMP's sources right here and now
> to double-check...
Factorials n! are calculated by a simple product from 1 to n, but
arranged into certain sub-products.
First as many factors as fit in a limb are accumulated, then two of
those multiplied to give a 2-limb product. When two 2-limb products
are ready they're multiplied to a 4-limb product, and when two
4-limbs are ready they're multiplied to an 8-limb product, etc. A
stack of outstanding products is built up, with two of the same size
multiplied together when ready.
Arranging for multiplications to have operands the same (or nearly
the same) size means the Karatsuba and higher multiplication
algorithms can be used. And even on sizes below the Karatsuba
threshold an NxN multiply will give a basecase multiply more to work
Haha! You had a *really* weak argument! <wink>
-- Moshe Zadka, comp.lang.python
More information about the Python-list