Cette déclaration des algorithmes fondamentaux de Knuth est-elle toujours applicable aujourd'hui? [fermé]

10

Dans un sens, 10! (dix factorielle) représente une ligne de démarcation approximative entre les choses qui sont pratiques à calculer et les choses qui ne le sont pas.

Ceci est tiré du livre TAOCP Fundamental Algorithms (1973) de Knuth. Est-ce toujours une déclaration valide ou la puissance de calcul la rend-elle obsolète?

computer-science taocp Bon Ami
la source
Je ne sais pas dans quel sens cela a toujours été vrai - 10! est à peine quelques millions. Trop grand pour une compréhension directe, mais pas particulièrement difficile à calculer, même avec un stylo et du papier.
Hobbs
11
@hobbs, il ne s'agit pas de calculer la valeur de 10 !, il s'agit de faire des calculs sur environ 10! les choses . Autrement dit, si votre méthode nécessite plus d'environ 10! <unités de travail>, il est temps de trouver une nouvelle méthode.
AakashM

Réponses:

21

C'est encore raisonnable.

dix! = 3 628 880. Chaque étape qui suit monte d'au moins un ordre de grandeur.

(fact 10)
3628800

(fact 11)
39916800 -- about 40 million

(fact 12)
479001600 -- almost 500 million

(fact 13.0)
6227020800.0 -- over 6 billion

Très bientôt, vous parlez des chiffres des dépenses du Congrès.

John R. Strohm
la source
15

Le bon professeur est, heureusement, toujours avec nous et le meilleur moyen de trouver une réponse définitive est de lui écrire et de lui demander son avis.

Cela dit, je ne pense pas que le nombre absolu compte autant que la fonction que représentent les factorielles. Que Knuth l'ait ou non réalisé à l'époque, le modèle qu'il a établi avec cette déclaration fonctionne très bien pour regarder en arrière ce qui était pratique à calculer dans les décennies précédentes et avancer dans celles qui ont suivi.

En 1973, notre capacité à générer, stocker, transférer et traiter des données était suffisamment limitée pour en faire 10! un chiffre raisonnable "loin" pour lequel tirer. Je doute que Knuth (ou n'importe qui d'autre, d'ailleurs) aurait pu prédire les améliorations exponentielles de presque tout ce que nous avons apprécié depuis, mais les factorielles correspondent bien aux chiffres réels.

Je l'ai vu de première main: il y a une décennie, j'ai travaillé sur un projet où nous développions des moyens de stocker et de traiter environ 50 millions d'enregistrements tout en réfléchissant à la façon dont nous ferions un ordre de grandeur de plus. Une décennie plus tard, je fais un projet similaire. Mes chiffres cibles ont changé, le tout de manière factorielle:

                      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

Les groupes qui réalisent les deux projets se sont entendus sur des chiffres beaucoup plus ronds que ceux-ci, mais les factoriels ne sont pas très éloignés. Les Google et les Facebook du monde ont les ressources pour faire le genre de choses dont mon projet actuel rêve seulement, mais d'où je suis assis, 13!dans une décennie ou moins, cela ne semble pas si loin.

Je ne pensais pas à de grandes quantités de données en 1992, mais avec le recul, j'aurais probablement examiné tout un facteur de moins.

Blrfl
la source