In a sense, 10! (ten factorial) represents an approximate dividing
line between things which are practical to compute and things which
are not.
This is from Knuth’s TAOCP Fundamental Algorithms book (1973).
Is this still a valid statement or has computing power rendered it obsolete ?
2
It is still reasonable.
10! = 3,628,880. Every step after that goes up by AT LEAST an order of magnitude.
(fact 10)
3628800
(fact 11)
39916800 -- about 40 million
(fact 12)
479001600 -- almost 500 million
(fact 13.0)
6227020800.0 -- over 6 billion
Pretty soon, you’re talking about Congressional spending numbers.
The good professor is, fortunately, still with us and the best way to ascertain a definitive answer is to write him and ask his opinion.
That said, I don’t think the absolute number matters as much as the function that factorials represent. Whether or not Knuth realized it at the time, the model he established with that statement works very well for looking backward at what was practical to compute in prior decades and forward through those that followed.
In 1973, our capacity to generate, store, transfer and process data was limited enough to make 10! a reasonable “far edge” figure to shoot for. I doubt Knuth (or anyone else, for that matter) would have been able to predict the exponential improvements in almost everything we’ve enjoyed since then, but factorials have fit the actual numbers nicely.
I’ve seen this firsthand: A decade ago, I worked on a project where we were developing ways to store and process about 50M records while at the same time pondering how we’d do an order of magnitude more. A decade later, I’m doing a similar project. My target figures have shifted, all in a factorial fashion:
2002 2012
Small Test ....... 9! / 362K ... 10! / 3.6M
Large Test ....... 10! / 3.6M ... 11! / 40M
Capacity Goal .... 11! / 40M ... 12! / 479M
Capacity Dream ... 12! / 479M ... 13! / 6.3B
The groups doing both projects bandied about much rounder figures than those, but the factorials aren’t very far off. The Googles and Facebooks of the world have the resources to do the kinds of things my current project only dreams about, but from where I sit, 13! in a decade or less doesn’t seem that far out of reach.
I wasn’t thinking about large quantities of data in 1992, but hindsight says I’d probably have been looking at everything one factorial less.