Essa afirmação dos algoritmos fundamentais de Knuth ainda é aplicável hoje? [fechadas]

10

Em certo sentido, 10! (dez fatorial) representa uma linha divisória aproximada entre coisas práticas para calcular e coisas que não são.

Isto é do livro de Algoritmos Fundamentais TAOCP de Knuth (1973). Essa declaração ainda é válida ou o poder de computação a tornou obsoleta?

computer-science taocp Bon Ami
fonte
Não está claro para mim em que sentido isso foi verdade - 10! são apenas alguns milhões. Grande demais para compreensão direta, mas não particularmente difícil de calcular, mesmo com caneta e papel.
hobbs
11
@ Hobbs não está falando sobre calcular o valor de 10 !, está falando sobre fazer cálculos em cerca de 10! coisas . Ou seja, se o seu método exigir mais do que 10! <unidades de trabalho>, é hora de encontrar um novo método.
AakashM

Respostas:

21

Ainda é razoável.

10! = 3.628.880. Cada passo depois disso aumenta pelo menos uma ordem de magnitude.

(fact 10)
3628800

(fact 11)
39916800 -- about 40 million

(fact 12)
479001600 -- almost 500 million

(fact 13.0)
6227020800.0 -- over 6 billion

Em breve, você estará falando sobre os números de gastos do Congresso.

John R. Strohm
fonte
15

Felizmente, o bom professor ainda está conosco e a melhor maneira de determinar uma resposta definitiva é escrevê-lo e pedir sua opinião.

Dito isto, não acho que o número absoluto seja tão importante quanto a função que os fatoriais representam. Quer Knuth tenha percebido ou não na época, o modelo que ele estabeleceu com essa afirmação funciona muito bem para olhar para trás, para o que era prático para calcular nas décadas anteriores e para os seguintes.

Em 1973, nossa capacidade de gerar, armazenar, transferir e processar dados era limitada o suficiente para produzir 10! uma figura "de ponta" razoável para se atirar. Duvido que Knuth (ou qualquer outra pessoa, nesse sentido) tivesse sido capaz de prever as melhorias exponenciais em quase tudo o que desfrutamos desde então, mas os fatoriais se ajustaram bem aos números reais.

Eu já vi isso em primeira mão: há uma década, trabalhei em um projeto em que estávamos desenvolvendo maneiras de armazenar e processar cerca de 50 milhões de registros e, ao mesmo tempo, ponderando como faríamos uma ordem de magnitude mais. Uma década depois, estou fazendo um projeto semelhante. Minhas figuras-alvo mudaram, tudo de maneira fatorial:

                      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

Os grupos que fazem os dois projetos fizeram bandas com números muito redondos do que aqueles, mas os fatoriais não estão muito distantes. Os Googles e os Facebooks do mundo têm os recursos para fazer o tipo de coisa que meu projeto atual apenas sonha, mas de onde estou, 13!em uma década ou menos, não parece tão fora de alcance.

Eu não estava pensando em grandes quantidades de dados em 1992, mas, em retrospectiva, diz que provavelmente estaria analisando tudo menos um fatorial.

Blrfl
fonte