¿Esta declaración de los algoritmos fundamentales de Knuth todavía es aplicable hoy? [cerrado]

10

En cierto sentido, 10! (factorial diez) representa una línea divisoria aproximada entre cosas que son prácticas para calcular y cosas que no lo son.

Esto es del libro de algoritmos fundamentales de Knuth TAOCP (1973). ¿Sigue siendo una declaración válida o la potencia informática la ha vuelto obsoleta?

computer-science taocp Bon Ami
fuente
Para mí no está claro en qué sentido fue cierto: ¡10! es solo unos pocos millones. Demasiado grande para la comprensión directa, pero no es particularmente difícil de calcular, incluso con lápiz y papel.
hobbs
11
@hobbs no se trata de calcular el valor de 10 !, se trata de hacer cálculos en aproximadamente 10! cosas . Es decir, si su método requiere más de aproximadamente 10! <unidades de trabajo>, es hora de encontrar un nuevo método.
AakashM

Respuestas:

21

Sigue siendo razonable.

10! = 3,628,880. Cada paso después de eso aumenta AL MENOS un orden de magnitud.

(fact 10)
3628800

(fact 11)
39916800 -- about 40 million

(fact 12)
479001600 -- almost 500 million

(fact 13.0)
6227020800.0 -- over 6 billion

Muy pronto, estás hablando de números de gastos del Congreso.

John R. Strohm
fuente
15

Afortunadamente, el buen profesor todavía está con nosotros y la mejor manera de determinar una respuesta definitiva es escribirle y pedirle su opinión.

Dicho esto, no creo que el número absoluto importe tanto como la función que representan los factoriales. Independientemente de si Knuth se dio cuenta o no en ese momento, el modelo que estableció con esa declaración funciona muy bien para mirar hacia atrás en lo que era práctico calcular en décadas anteriores y avanzar a través de los que siguieron.

¡En 1973, nuestra capacidad para generar, almacenar, transferir y procesar datos era lo suficientemente limitada como para generar 10! una figura razonable de "extremo lejano" para disparar. Dudo que Knuth (o cualquier otra persona) haya podido predecir las mejoras exponenciales en casi todo lo que hemos disfrutado desde entonces, pero los factoriales se han adaptado bien a los números reales.

He visto esto de primera mano: hace una década, trabajé en un proyecto en el que estábamos desarrollando formas de almacenar y procesar alrededor de 50 millones de registros y al mismo tiempo reflexionar sobre cómo haríamos un orden de magnitud más. Una década después, estoy haciendo un proyecto similar. Mis cifras objetivo han cambiado, todo de manera factorial:

                      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

Los grupos que realizan ambos proyectos se dividieron en cifras mucho más redondas que esas, pero los factoriales no están muy lejos. Los Googles y Facebook del mundo tienen los recursos para hacer el tipo de cosas con las que mi proyecto actual solo sueña, pero desde donde me siento, 13!en una década o menos no parece estar tan lejos de mi alcance.

No estaba pensando en grandes cantidades de datos en 1992, pero en retrospectiva dice que probablemente habría estado mirando todo un factorial menos.

Blrfl
fuente