Anagram

[Michael Hudson]

"Alex Martelli" <aleax at aleax.it> writes:

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

http://www.swox.com/gmp/manual/Factorial-Algorithm.html

says

  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
  on.

Cheers,
M.

-- 
  Haha! You had a *really* weak argument! <wink>
                                      -- Moshe Zadka, comp.lang.python