¿Podrán las computadoras multiplicarse 99,999,999,999 veces 999,999,999,999?

Nosotros los humanos podemos hacer cálculos arbitrarios de precisión.

99.999.999.999 * 999.999.999.999 =
(10 ^ 11 – 1) * (10 ^ 12 – 1) =
10 ^ 23 – 10 ^ 11 – 10 ^ 12 + 1 =
10 ^ 11 * (10 ^ 12 – 1 – 10) + 1 =
10 ^ 11 * (1,000,000,000,000 – 11) + 1 =
10 ^ 11 * (999,999,999,989) + 1 =
99,999,999,998,900,000,000,001

Los procesadores no pueden hacer cálculos matemáticos de precisión arbitrarios, por lo que estamos restringidos a una precisión fija, actualmente de 64 bits en la mayoría de los procesadores disponibles comercialmente.

Entonces, esta línea de ejemplo de código C dará la respuesta incorrecta ya que esto se traduce en una multiplicación de 2 miltiplicados de 64 bits que devuelve un valor de 64 bits.

printf (“resultado =% lli \ n”, (__int64) 99999999999 * (__int64) 999999999999);

La siguiente línea de ejemplo de código C le dará una mejor respuesta, pero sigue siendo incorrecta porque, aunque un valor de coma flotante de 64 bits tiene el rango para almacenar este valor, no tiene la precisión para almacenar todos los bits, por lo que la respuesta Todavía está mal.

printf (“resultado =% f \ n”, (doble) 99999999999 * (doble) 999999999999);

Lo siguiente sería correcto, pero la multiplicación en realidad está siendo realizada por un algoritmo de software, utilizando múltiples operaciones de procesador.

printf (“resultado =% lli \ n”, (__int128) 99999999999 * (__int128) 999999999999);

También hay bibliotecas matemáticas de precisión arbitrarias disponibles, o puede escribir la suya propia.

Sin embargo, dado que esto generará múltiples operaciones de procesador, será muy lento y computacionalmente intenso en comparación con las instrucciones de procesador sin procesar, por lo que no espere hacer MFLOPS de matemática de precisión arbitraria.

La mía acaba de hacer:

> $ python -c ‘imprimir 99999999999 * 999999999999’
99999999998900000000001

Las computadoras siempre han podido hacer esto, suponiendo que hay suficiente memoria o almacenamiento para contener tanto los números como la respuesta. Una manera ingenua de multiplicar dos números es usar el mismo método que los humanos aprendemos de niños: comience con los dígitos más bajos y sume la respuesta. En el caso de una computadora, los “dígitos” son realmente fragmentos de varios bytes del número.

Hay formas más sofisticadas, y la forma más eficiente de multiplicar dos números es actualmente usar la transformada rápida de Fourier, que esencialmente convierte la parte de multiplicación en una suma, que es mucho más rápida de calcular (aunque esto solo vale la pena el tiempo extremadamente). números grandes). Vea el artículo de Wikipedia sobre algoritmos de multiplicación, que es bastante completo.

Mi hijo, que está aprendiendo principios matemáticos básicos comunes, pudo resolver esto (tiene 7 años). Él dijo: “Es como multiplicar por 9: lo cambias a 10 y restas el otro número una vez”.

Entonces lo cambió a esto: 1,000,000,000,000 x 99,999,999,999

Luego, “agregó los ceros” al final: 99,999,999,999,000,000,000,000.

Finalmente, resta 99,999,999,999. O, en sus palabras, “100,000,000,000 con el extra 1”. Así que lo alineó todo, “tomó” uno de los 9 donde estaba alineado, y agregó el 1 nuevamente para obtener:

99,999,999,998,900,000,000,001

En cuanto a una computadora, ya es factible más rápido de lo que podemos presionar la tecla Intro para resolverlo. Apuesto a que el viejo Tandy 2000 de mi familia ni siquiera tendría problemas con esto (nuestra primera computadora antigua con DOS solo cuando era solo un niño …)

¿Por qué es esto incluso una pregunta? ¿Querías elevarlo a ese poder? ¿O anidar los poderes en orden descendente? 999,999,999,999 ^ 99,999,999,999… ^ 9? Ahora, esa sería una cuestión de cuándo una computadora puede hacer eso en un tiempo razonable …

Para responder a esta pregunta, decidí abrir Microsoft small basic (un lenguaje de programación para principiantes) y programar esto:

a = 99999999999 * 999999999999
TextWindow.WriteLine (a)

Menos de un segundo después recibí esto:

Entonces, sí, las computadoras pueden multiplicar ecuaciones grandes como esta.

De hecho, si las computadoras pueden calcular 22.4 billones de dígitos de pi, entonces pueden hacer ecuaciones como 99999999999 * 999999999999 en menos de un segundo. Instalé el programa que encontró 12,1 billones de dígitos de pi (según su sitio web, les tomó 87 días, 120 TB de espacio, 60 TB de espacio de respaldo y 1 TB de RAM para terminar el programa) y calculó 100 millones de dígitos de pi en ~ 70 segundos.

¿Qué ecuación tiene que repetir la computadora para encontrar tantos dígitos de pi?

Algoritmo de Chudnovsky – Wikipedia

y

La fórmula de Bellard – Wikipedia.

Si la computadora puede calcular ~ 100 millones de dígitos de pi en 70 segundos, puede multiplicar números grandes como este en una fracción de segundo.

Estoy respondiendo esta pregunta desde la perspectiva de un programador, sin embargo, también está orientada a personas con algunos conocimientos matemáticos básicos.

Sí, es posible realizar cálculos en números gigantes al hacer un uso combinado de la siguiente estrategia para crear un tipo de datos personalizado:

1. Cree una clase (término de programación orientado a objetos) para crear un tipo de datos personalizado que encapsule las disposiciones para trabajar con números gigantescos.
2. Haga uso de la estructura de datos de la matriz donde cada uno de sus índices representa la posición decimal, el 0º índice es el lugar de las unidades y la enésima posición es la (n-1) enésima potencia del lugar de 10. Los operandos deben ingresarse como una cadena que se convertiría en matriz en el constructor
3. Cree funciones en clase que sobrecarguen los operadores aritméticos necesarios que realizarían el cálculo en un número representado como matriz.

El número puede imprimirse en bucle inverso de los elementos de la matriz.

Podría haber descubierto la respuesta a eso solo con la calculadora de Windows. El resultado de la ecuación es 999999999998000000000001 mi mal, hice 12 dígitos en cada número. La respuesta es en realidad 99,999,999,998,900,000,000,001, y para verificar que la computadora no mostrara ningún error de precisión de punto flotante, copié y pegué el resultado y lo dividí por 999,999,999,999, y al igual que debería, resultó en: 99,999,999,999

Trabajar con números como 0.1 puede crear errores de precisión de coma flotante que PUEDEN generar errores en un programa de computadora. Recientemente verifiqué eso en Python.

Creo que fue algo como:
var myvarible = (1.0 + 1.0 + 1.3) / 3;
si myvarible == 1.1 entonces imprima “Algo”;

(Python no tiene “entonces”, pero no puedo hacer sangrías en esta estúpida cosa. También Python no usa “;” pero lo agregué allí para mayor claridad. También myvarible contiene un flotador). De todos modos, “algo” podría nunca se imprima debido a una limitación matemática a 0.1 cuando se convierte de decimal (base 10) a binario (base 2).

La calculadora incluida con Windows 7 puede hacer eso; solo tiene que cambiarlo al modo Científico seleccionando Ver> Científico. En esta imagen también muestra los dos números de entrada porque también elegí Ver> Historial:

¿Querías hacerlo en una hoja de cálculo? Las hojas de cálculo normalmente solo le brindan 15 dígitos significativos de precisión, por lo que la respuesta se redondearía a 99,999,999,998,900,000,000,00 0 . Pero mi complemento de Excel xlPrecision proporciona más de 2 mil millones de dígitos significativos de precisión:

bc -l

aC 1.06.95

Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.

Este es un software gratuito con ABSOLUTAMENTE SIN GARANTÍA.

Para más detalles, escriba “garantía”.

escala = 1000

99999999999 * 999999999999

99999999998900000000001

La aritmética de precisión arbitraria es posible incluso en las CPU más pequeñas. Hay bibliotecas de código abierto para ayudar con el problema, pero realmente no es tan difícil de hacer. Este es realmente un caso en el que puede ser más fácil codificarlo en lenguaje ensamblador que la mayoría de los idiomas de nivel superior, ya que no puede aprovechar de manera muy efectiva los tipos de datos estándar disponibles en los idiomas de alto nivel. En este caso de ejemplo, la aritmética de 64 bits manejaría el problema de forma nativa.

Hay una gran fuente llamada Google, que le muestra las respuestas a preguntas matemáticas:

1e + 23 es el término técnico para “1 seguido de 23 ceros”.

Esto se siente más como una aproximación. Podemos hacerlo mejor.

Tengo una terminal en mi computadora que a veces uso para hacer cálculos rápidos, pero inusuales:

Son 99,999,999,998,900,000,000,001 . La computadora tardó menos de un segundo en calcularlo.

Una vez que alguien “descubrió” la aritmética multibyte (y fue hace mucho tiempo, tuve un problema para encontrar una referencia en 1987, era una idea tan antigua), cualquier número finito podría multiplicarse. (No puede multiplicar algo como Pi y obtener una respuesta exacta; nadie ha calculado Pi hasta el último dígito, si eso es posible).

¿Cuándo podrá hacerlo una computadora que usa 5 bytes para operaciones aritméticas? Nunca. Es como preguntar cuándo podremos escribir 999,999,999,999 en 5 dígitos. ¿Pero multiplicar 2 números de 12 dígitos en una computadora? Incluso si limitamos “computadora” a “dispositivo electrónico”, habría sido en la década de 1940 si alguien hubiera escrito un programa de multiplicación multibyte. (No tenían necesidad de esa precisión: ENIAC fue diseñado para calcular la elevación del cañón para las trayectorias de los proyectiles, y si te quedaban 3 granos de arena, ¿a quién le importa?)

Los números tienen 11 y 12 dígitos cada uno. Multiplicarlos juntos dará como resultado un número de 23 dígitos.

Un número decimal de 11 dígitos necesita 37 bits para representar. Un número de 12 dígitos necesita 39, un número decimal de 23 dígitos requiere 77 bits para representar. Las computadoras modernas pueden procesar 64 bits a la vez.

Por lo tanto, cada operando puede caber en 64 bits, y la multiplicación toma dos operandos de 64 bits y produce una respuesta de 128 bits. 128 bits es más que suficiente para almacenar el resultado.

Entonces, para responder a su pregunta: sí, pueden hacerlo y pueden hacerlo en una sola instrucción (sí, incluso el procesador de su teléfono).

Esos son algunos números bastante pequeños con los que está trabajando.

Probablemente haya notado que el primer número tiene 37 bits y el segundo número tiene 40, por lo que multiplicarlos juntos dará como resultado un número con aproximadamente 77 bits, mayor que el que se puede almacenar en un entero sin signo de 64 bits. Uh-oh, verdad?

Si bien las máquinas de 128 bits pueden volverse populares en el futuro, tal vez incluso dentro de la década, este tipo de cálculo se puede hacer con bastante facilidad simplemente no representando números como enteros de 64 bits. Los lenguajes de programación generalmente están equipados para manejar números como enteros de 64 bits (o incluso de 32 bits o 16 bits u 8 bits) porque generalmente no necesita números más grandes que eso, por lo que no hay necesidad de perder memoria con números de precisión, ¡pero puede simplemente usar una biblioteca para precisión arbitraria o incluso codificar la suya propia! Cuando estaba aprendiendo a programar, escribí tal biblioteca. Representaría números como cadenas, por lo que en lugar de 99,999,999,999 almacenados como un número en la memoria, sería una lista de caracteres, es decir, el carácter ‘9’ repetido 11 veces. Para realizar operaciones aritméticas, lo haría de la manera que aprendimos en la escuela primaria, dígito a dígito. No era una biblioteca muy rápida . ¡Representar números como cadenas es terriblemente ineficiente! Pero hizo el trabajo, y podría multiplicar números tan grandes como quisieras dado el tiempo y el espacio suficientes. Probablemente podría multiplicar números de un millón de dígitos. No lo intenté porque tenía mejores cosas que hacer.

Además, de vuelta en la secundaria, recuerdo haber hecho algo bastante estúpido. ¡Para algo de competencia matemática tuve que encontrar los últimos dígitos de un número como 2000! (¡podría haber sido 2001 !; no recuerdo en qué año sucedió esto) antes de todos los ceros. 2000! = 1 · 1 · 2 · 3 · 4 · 5 ·… · 1999 · 2000 es un número muy grande . Entonces, fui y descargué un programa llamado algo así como BigCalc, ¡y fue capaz de funcionar 2000! aunque tardó unos minutos. ¡Tengo la respuesta correcta! En ese momento no sabía cómo programar, pero hoy lo hubiera hecho de manera muy diferente; ¡no hay razón para calcular realmente 2000! si eres inteligente para hacer un seguimiento de las cosas. Pero el punto es que fue posible.

¿Podrán las computadoras multiplicar 99999999999 veces 999999999999?

[ [correo electrónico protegido] ] $ python -m timeit ‘99999999999L * 999999999999L’
100000000 bucles, lo mejor de 3: 0.0167 usec por bucle

Aparentemente, mi computadora puede hacerlo en aproximadamente 0.017μs, o 0.0000000017 segundos. Dicho de otra manera, en un segundo, podría hacerlo aproximadamente seis millones de veces (utilizando solo un núcleo de CPU).

Esto está utilizando Python, que no es el entorno más eficiente para este tipo de cosas. Usando algo como C y GMP, probablemente sería mucho más rápido.

Er … si. Mi laptop HP Envy básica y corriente con Windows 10 manejó eso con la aplicación de calculadora de acciones. Mi Raspberry Pi 2 con Linux lo manejó con un solo comando. La aplicación de la calculadora de acciones en mi teléfono inteligente lo manejó. Ingresé a una sesión de consola en mi Synology NAS y también multipliqué esto exitosamente allí. Esto está dentro del alcance funcional de todas las computadoras de mi hogar hoy en día.

Ir

repl.it – ​​Python

Este es un compilador de Python en línea (en caso de que no tenga Python en su computadora).

en el área blanca en el tipo izquierdo

imprimir 99999999999 * 999999999999

y luego presione el botón de flecha sobre el área blanca.

El resultado se mostrará en el área negra:

99999999998900000000001

con comas que es

99,999,999,998,900,000,000,001

El hecho de que algunos lenguajes (C, C ++, etc.) estén limitados por defecto a números enteros más pequeños que eso no significa que las computadoras no sean capaces de hacer el cálculo. Puede usar bibliotecas en C, C ++, etc. para agregar la capacidad de manejar enteros más grandes, y otros lenguajes como Python arriba tienen la capacidad por defecto.

Todas las maravillosas herramientas descritas en las otras respuestas, como los lenguajes de programación (Python, etc.), las calculadoras de línea de comandos (bc) y las bibliotecas matemáticas de precisión arbitraria son secretos preciosos cuidadosamente atesorados por ingenieros de software. Los mantenemos en secreto por temor a que si la capacidad que busca estuviera ampliamente disponible, varios países tendrían inmediatamente una deuda nacional ilimitada que resultaría en una cascada mundial de quiebras nacionales.

Permítanme agregar a la respuesta de Senya. Desde 1975, las computadoras basadas en Unix (incluidas las cajas macOS y Linux contemporáneas) han tenido bc a su disposición. Es un software matemático capaz de precisión arbitraria.

Los estudiantes de CS suelen hacer esta pregunta al dar sus primeros pasos en la programación, y se basa principalmente en un concepto erróneo: lo que ves (desbordamiento) no es un límite de las computadoras, sino de los tipos numéricos básicos del lenguaje de programación .

Los lenguajes de programación están diseñados para satisfacer las necesidades de la mayoría de los programas en el campo para los que han sido diseñados esos idiomas.

Y la mayoría de los programas utilizados en el cálculo deben ser rápidos. Y para ser rápido, un programa no necesita tomar demasiadas decisiones. Y para limitar el número de decisiones, necesita ciertas cosas para ser constante.

La mayoría de los lenguajes de programación usan, como tipos básicos numéricos, formatos con un número fijo de bits (para que no tengan que preocuparse por las longitudes y los cambios arbitrarios) que pueden interpretar como una “base posicional 2 enteros” de un “flotante punto y una longitud fija mantisa y exponente ”.

Por lo tanto, si un idioma no ofrece, en sus propios tipos básicos, números con suficientes bits para representar el resultado que desea, no obtendrá ese resultado.

O mejor … no lo obtienes usando solo expresiones básicas entre tipos básicos .

Pero nada le impide escribir programas que combinan más de esos elementos que propagan acarreos y hacen sumas y multiplicaciones entre elementos más complejos y arbitrariamente largos.

Los programas que hacen ese tipo de cosas existen desde hace mucho tiempo: piense, por ejemplo, en el Unix bc: bc Command Manual, es perfectamente capaz de hacer esa multiplicación.