Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 ?

share|improve this question

closed as primarily opinion-based by MichaelT, Bart van Ingen Schenau, gnat, Dynamic, Robert Harvey Mar 3 at 5:14

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

    
It's not clear to me in what sense it was ever true — 10! is a mere few million. Too large for direct comprehension, but not particularly hard to compute with, even with pen and paper. –  hobbs Jan 9 '13 at 8:27
10  
@hobbs it's not talking about computing the value of 10!, it's talking about doing computations on about 10! things. That is, if your method requires more than about 10! <units of work>, it's time to find a new method. –  AakashM Jan 9 '13 at 9:48
add comment

2 Answers 2

up vote 19 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.