¿Pueden las computadoras calcular grandes factoriales más rápido si están representando internamente los números usando una base grande (por ejemplo, 1000)?

La mayoría de las computadoras están diseñadas para usar binario. Si la máquina física subyacente usa binario, entonces usar una base más alta en su programa solo agrega pasos adicionales que la computadora debe realizar para traducir números de un lado a otro, ralentizándolo.

Ahora, es teóricamente posible diseñar computadoras que no se basen en las matemáticas binarias como base de hardware. Sin embargo, actualmente tenemos aproximadamente medio siglo de experiencia en el diseño de los que sí lo hacen, y muy poco en el diseño de los que no. Por lo tanto, sabemos cómo optimizar los sistemas binarios mucho mejor que los sistemas que usan otras bases. Y, por supuesto, en el momento en que alguien pasa la optimización del hardware para un nuevo tipo de computadora usando, por ejemplo, la base 1000, mucha más gente trabajará actualmente para mejorar el hardware de la computadora binaria.

Entonces, si bien es teóricamente posible, como cuestión práctica, no.

Lea sobre aritmética de precisión arbitraria (también conocida como bigint-s o bignum-s).

No reinvente su propia biblioteca bignum. Utilice uno existente, por ejemplo, GMPlib.

Los algoritmos bignum son muy inteligentes. Algunas de las operaciones elementales están inspiradas en la computación en base 2 ** 32 (o 2 ** 64 en la mayoría de las máquinas de 64 bits). Pero es mucho más complejo (y aprovecha las instrucciones especializadas de la máquina, como agregar con carry).

No estoy seguro de cómo funcionaría eso, ya que probablemente no sería capaz de representar todos los números.

Creo que es más una cuestión de hacer que nuestros algoritmos sean más inteligentes.
Por ejemplo, digamos que debes sumar 2 números juntos.

1000 + 2000 = 3000

Puede dejar que la computadora calcule los 2 números juntos y obtener la respuesta 3000. Otra forma de resolver el mismo problema podría ser buscar la respuesta en una base de datos donde la respuesta ya está calculada.

Ambos métodos nos darían la respuesta 3000, pero uno de ellos podría ser más rápido. Esto es básicamente lo que hacen los programadores. Por ejemplo, el primer código que escribí en mi trabajo actual tardó 30 minutos en ejecutarse. Lo reescribí y me llevó 1 minuto ejecutarlo. Lo reescribí nuevamente y tardé 1 segundo en ejecutarse.

Base 1000 en realidad sería aritmética de varios bytes, pero aún binaria. (A menos que pueda pensar en cómo crear puertas de 1,000 estados. Tri-state es el más alto que hemos obtenido, y el tercer estado no es realmente un “estado”).

Los factoriales (hasta donde yo sé) son operaciones incrementales. Termina una operación y luego usa su resultado para calcular la siguiente operación. Una computadora base 1000 puede ser más rápida si todos los números que usa en su operación son menores de 1000, por lo tanto, no requiere la representación o conversión de números y proporciona una media de cálculo más directa en lugar de 0 y 1 repetitivos para los que debe encontrar un significado. Pero una computadora base 1000 probablemente tendrá otro diseño de procesamiento de información. He oído hablar de una computadora de base 3 construida por rusos.

Sí, pero solo por un factor constante pequeño (en comparación con las implementaciones de enteros grandes que almacenan cada binario / cada dígito decimal por separado). El cambio de base no cambia la complejidad temporal asintótica de cualquier cálculo con enteros grandes.

Aquí hay algunos detalles más, principalmente destinados a aquellos que no están seguros de cuál es la pregunta en sí.

El punto principal cuando realiza su propia implementación de aritmética de enteros grandes es que los números que está procesando no encajan en sus tipos de datos antiguos simples. Para almacenar un número entero grande, debe tomarlo y dividirlo en trozos de tamaño constante. La pregunta que se hace aquí es si el tamaño de estos fragmentos influye en la velocidad de la implementación y cómo lo hace.

Internamente, casi todas las computadoras usan binario, por lo que parece que el binario es una opción natural para nuestra representación interna de enteros grandes, ¿verdad? Bueno no exactamente.

Las operaciones de nivel más bajo son en realidad operaciones en enteros del tamaño de una palabra de máquina, hoy en día generalmente de 32 bits y 64 bits. Una buena implementación de software de enteros grandes podría, por ejemplo, almacenar los bits del entero grande en bloques de 32 (es decir, en enteros sin signo de 32 bits) y luego usar enteros de 64 bits para los cálculos internos para asegurarse de que no t desbordamiento.

Para todos los efectos, la mejor descripción de la implementación anterior es que representa internamente el número en la base 2 ^ 32. Dicha implementación será más rápida que una implementación que tenga una matriz simple de bits del número y acceda a esos bits de uno en uno.

Del mismo modo, hay implementaciones de enteros grandes que desean usar la base 10 internamente, de modo que no tengan que perder tiempo en conversiones de base cada vez que generen los números. Esta es a menudo una opción de diseño válida. Pero también en esta configuración podemos acelerar la implementación eligiendo una base más grande: por ejemplo, una base de uso común es [matemática] 10 ^ 9 [/ matemática], porque 9 dígitos decimales aún encajarán convenientemente en un entero de 32 bits variable.