The best algorithm that is known is to express the factorial as a product of prime powers. One can quickly determine the primes as well as the right power for each prime using a sieve approach. Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together. This was described by Peter B. Borwein, On the Complexity of Calculating Factorials, Journal of Algorithms 6 376–380, 1985. (PDF) In short, $n!$ can be computed in $O(n(\log n)^3\log \log n)$ time, compared to the $\Omega(n^2 \log n)$ time required when using the definition.
What the textbook perhaps meant was the divide-and-conquer method. One can reduce the $n-1$ multiplications by using the regular pattern of the product.
Let $n?$ denote $1 \cdot 3 \cdot 5 \dotsm (2n-1)$ as a convenient notation.
Rearrange the factors of $(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$ as
$$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$
Now suppose $n = 2^k$ for some integer $k>0$.
(This is a useful assumption to avoid complications in the following discussion, and the idea can be extended to general $n$.)
Then $(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$ and by expanding this recurrence,
$$(2^k)! = \left(2^{2^{k-1}+2^{k-2}+\dots+2^0}\right) \prod_{i=0}^{k-1} (2^i)? = \left(2^{2^k - 1}\right) \prod_{i=1}^{k-1} (2^i)?.$$
Computing $(2^{k-1})?$ and multiplying the partial products at each stage takes $(k-2) + 2^{k-1} - 2$ multiplications. This is an improvement of a factor of nearly $2$ from $2^k-2$ multiplications just using the definition. Some additional operations are required to compute the power of $2$, but in binary arithmetic this can be done cheaply (depending on what precisely is required, it may just require adding a suffix of $2^k-1$ zeroes).
The following Ruby code implements a simplified version of this. This does not avoid recomputing $n?$ even where it could do so:
def oddprod(l,h)
p = 1
ml = (l%2>0) ? l : (l+1)
mh = (h%2>0) ? h : (h-1)
while ml <= mh do
p = p * ml
ml = ml + 2
end
p
end
def fact(k)
f = 1
for i in 1..k-1
f *= oddprod(3, 2 ** (i + 1) - 1)
end
2 ** (2 ** k - 1) * f
end
print fact(15)
Even this first-pass code improves on the trivial
f = 1; (1..32768).map{ |i| f *= i }; print f
by about 20% in my testing.
With a bit of work, this can be improved further, also removing the requirement that $n$ be a power of $2$ (see the extensive discussion).
