fastest algorithm for factorials?
Lawrence Detweiler
Robert D. Silverman
:- - -
:
:What's the fastest algorithm for computing n factorial?
(2) I assume you mean fastest KNOWN algorithm. There are no omega results
for this problem.
(3) Nothing faster than multiplying the first n integers is known.
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"
R. Kym Horsell
>In article <19...@ccncsu.ColoState.EDU> ld23...@longs.LANCE.ColoState.Edu (Lawrence Detweiler) writes:
>:- - -
>:
>:What's the fastest algorithm for computing n factorial?
>
I may be putting my foot in my mouth again, but what about
n! = (n-r)! r! C(n,r)
If n is a power of 2 we have a nice recurrance; the C(n,r) can be
decomposed into additions (Pascal's triangle style) and we have O(log n)
multiplies and O(log^2 n) additions.
-kym
Tim Peters
>In article <1991Nov8.1...@linus.mitre.org> b...@faron.mitre.org (Robert D. Silverman) writes:
>>In article <19...@ccncsu.ColoState.EDU> ld23...@longs.LANCE.ColoState.Edu (Lawrence Detweiler) writes:
>>:- - -
>>:
>>:What's the fastest algorithm for computing n factorial?
>>
>>(3) Nothing faster than multiplying the first n integers is known.
>
>
> n! = (n-r)! r! C(n,r)
See also Knuth, Vol 2, 2nd ed, section 4.5.4, exercise 38a, for a way
that takes O(log n) operations (although each operation involves very
large integers ...).
the-name-of-this-group-is-"comp.theory"-not-"comp.practical"-right?-
ly y'rs - tim
Tim Peters Kendall Square Research Corp
t...@ksr.com, ksr!t...@uunet.uu.net
Christer Ericson
>In <1991Nov8.1...@linus.mitre.org> b...@faron.mitre.org (Robert D. Silverman) writes:
>>In article <19...@ccncsu.ColoState.EDU> ld23...@longs.LANCE.ColoState.Edu (Lawrence Detweiler) writes:
>>:
>>:What's the fastest algorithm for computing n factorial?
>>
>> [stuff deleted]
>>(3) Nothing faster than multiplying the first n integers is known.
>Hrrrmmm (clearing my throat), I must say that you seem pretty sure about
>something that isn't true! See my article <christer.689612149@berghem> for
>an algorithm that uses n/2 multiplications, n/4 additions, and n/4
>subtractions compared to the naive algorithm which uses n (well n-1 to be
>exact) multiplications. I'd claim that it (my algorithm), even though it
>uses the same number of operations, is faster on just about any architecture
>since multiplication is a more expensive operation than both addition and
>subtraction.
I don't know what compelled me to say this. Obviously, as anyone can see
from inspecting the code (appended below for clarity), my algorithm uses
n/2 multiplications and n additions/subtractions (as it stands it uses n/2
additions and n/2 subtractions, but it could easily be changed into using
n additions only) whereas the naive algorithm uses n multiplications and
n additions (or subtractions.) Thus, my algorithm uses the same number of
adds/subs but only half as many multiplications as the naive algorithm,
which clearly makes it faster.
I believe I got it right this time :-)
--- cut here ---
fac(n)
int n;
{
int x, y;
x = (n & 1) ? n-- : 1;
y = n;
while (n) {
x *= y;
y += (n -= 2);
}
return x;
}
naivefac(n)
int n;
{
int x = 1;
while (n > 1)
x *= n--;
return x;
}
--- cut here too ---
| Christer Ericson Internet: chri...@cs.umu.se |
| Department of Computer Science, University of Umea, S-90187 UMEA, Sweden |
Dan Gordon
>In article <19...@ccncsu.ColoState.EDU> ld23...@longs.LANCE.ColoState.Edu (Lawrence Detweiler) writes:
>:- - -
>:
>:What's the fastest algorithm for computing n factorial?
>
I believe I recall an article that came out a few years ago with a faster
algorithm. The idea was to figure out the power of each prime less than
n dividing n factorial, calculate each prime to that power, and then
multiply the results together. This reduces the time (measured in
bit operations) by a factor of log n or log log n, I don't remember which.
Unfortunately, I couldn't find the article. Can anyone provide the
reference?
Dan Gordon
University of Georgia, Department of Computer Science
d...@pollux.cs.uga.edu
Eric Smith
How big is n? If you're talking about the factorials of the first few
hundred integers, you could just keep the results in a table and do a
1-microsecond table lookup each time you need the factorial of a
number. This assumes you want a floating point result, and not the
exact digits (or bits). If you want the exact digits, you have to spend
a lot of time copying digits around, because those big numbers are long.
But why would anyone want to calculate a bunch of factorials in a hurry
anyway? That is the interesting question here. I know of lots of
applications where you want some ratios of factorials, but those can
be computed much faster without computing the actual factorials involved.
Dan Gordon
>>:
>>:What's the fastest algorithm for computing n factorial?
>>
>>(3) Nothing faster than multiplying the first n integers is known.
>
>
>I believe I recall an article that came out a few years ago with a faster
>algorithm.
>Unfortunately, I couldn't find the article. Can anyone provide the
>reference?
>
Jeff Shallit found the reference:
Peter Borwein, On the Complexity of Calculating Factorials,
Journal of Algorithms, Volume 6 (1985), pp. 376-380.
The gist is that you can calculate n factorial in time
O(log log n M(n log n)), where M(n) is the time to multiply two
n-bit numbers. With fast multiplication, this works out to
O(n (log n log log n)^2), compared to O(n^2 log n) for the
naive method.
Dan Gordon
Department of Computer Science, University of Georgia
d...@pollux.cs.uga.edu
Hans Boehm
>In article <19...@ccncsu.ColoState.EDU> ld23...@longs.LANCE.ColoState.Edu (Lawrence Detweiler) writes:
>:- - -
>:
>:What's the fastest algorithm for computing n factorial?
...
>
>(3) Nothing faster than multiplying the first n integers is known.
I missed the original posting. At the risk of stating the obvious or
redundant:
The order in which you multiply the first n integers matters. The
odd-even divide-and-conquer algorithm
n! = f(n,1)
f(n,m) = 1 if n is 0
n if m >= n
f(n,2m) * f(n-m,2m)
is much better than the standard text book algorithm, both as a
theoretical and as a practical matter. As a practical issue, it
makes much better use of the machines multiplication hardware, since
both operands are likely to use one or more machine words.
Since the multiplications involved are balanced, you can use faster
multiplication algorithms. For Omega(n**(1+eps)) multiplication,
the computation time is dominated by the final multiplication.
Hans-J. Boehm
(bo...@parc.xerox.com)
Huckleberry Muffin
>>
>> Nothing faster than multiplying the first n integers is known.
>
>
>I believe I recall an article that came out a few years ago with a faster
>algorithm. The idea was to figure out the power of each prime less than
>n dividing n factorial, calculate each prime to that power, and then
>multiply the results together. This reduces the time (measured in
>bit operations) by a factor of log n or log log n, I don't remember which.
Are you given the primes less than n or do you have to
figure them out? (The former would not be unrealistic but this is
comp.theory) It looks to me like this would make a big difference
in the speed of the algorithm.
cloyd
--
Cloyd Goodrum III " I've never held an ocean
UNCC Computer Science Department In the palm of my hand "
Charlotte, N.C. -- Nick Drake
unccvax!goo...@mcnc.org
Jeffrey Shallit
>In article <1991Nov10.2...@athena.cs.uga.edu> d...@pollux.cs.uga.edu (Dan Gordon) writes:
>>In article <1991Nov8.1...@linus.mitre.org> b...@faron.mitre.org (Robert D. Silverman) writes:
>>
>>I believe I recall an article that came out a few years ago with a faster
>>algorithm. The idea was to figure out the power of each prime less than
>>n dividing n factorial, calculate each prime to that power, and then
>>multiply the results together. This reduces the time (measured in
>>bit operations) by a factor of log n or log log n, I don't remember which.
>
> Are you given the primes less than n or do you have to
>figure them out? (The former would not be unrealistic but this is
>comp.theory) It looks to me like this would make a big difference
>in the speed of the algorithm.
>
>Cloyd Goodrum III " I've never held an ocean
>UNCC Computer Science Department In the palm of my hand "
>Charlotte, N.C. -- Nick Drake
>unccvax!goo...@mcnc.org
As always, the answer depends on one's model of computation. If the "unit cost"
model of computation, in which each arithmetic operation, no matter how large
the operands, requires unit time, then Mr. Goodrum is correct. In this case,
the "divide-and-conquer" algorithm suggested previously (and first discussed
by Adi Shamir in a paper on how to factor in "polynomial time" in this model)
is quite fast.
However, most will agree that for computations on integers, where the *exact
result*, and not just an approximation, is desired, the unit-cost model is
not really applicable. For example, just to *write down* n! will take
Omega(n log n) bits, using Stirling's formula. Hence we really should do
our computations in a model where the cost that is charged depends on the
operation and the size of the operand. This model is sometimes called
"naive bit complexity"; it charges, for example, mn to multiply an m bit
number by an n bit number. (Yes, I know there are faster methods.)
In this model, the time to determine the primes <= n first (say by the sieve
of Eratosthenes) is dominated by the time to multiply the appropriate
prime powers together. Thus, contrary to Mr. Goodrum, whether or
not the primes are provided makes no difference in the asymptotic
speed of the algorithm.
Jeffrey Shallit
University of Waterloo