Michael Hudson mwh at
Thu Jan 24 10:46:48 CET 2002

"Alex Martelli" <aleax at> writes:

> "Bengt Richter" <bokr at> wrote in message
> news:a2oh1f$de8$0 at
>     ...
> > 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 mailing list