Los niños aprenden las tablas de multiplicar en la escuela. Memorízalos. Buena suerte con los números de tres dígitos. Ahí es donde entran en juego los algoritmos. Apilas los dígitos. Multiplica fila por fila. Durante miles de años pensamos que eso era lo mejor que podíamos hacer. Es lento. Brutalmente lento para big data. Luego, en 1960, un joven de 23 años cambió todo. El misterio de la velocidad de multiplicación sigue abierto.
Por qué es importante
La multiplicación no es sólo una tarea. Opera Internet. Cifrado, IA, procesamiento de audio. Todo ello se apoya en la multiplicación. Multiplicación intensa. Cuando multiplicas números enormes millones de veces por segundo, cada paso cuenta. Una ligera mejora de la eficiencia ahorra miles de millones.
Mire el método de la escuela primaria. Dos dígitos significan cuatro multiplicaciones de un solo dígito. ¿Tres dígitos? Nueve. Se escala cuadráticamente. Duplica la longitud, cuadriplica el trabajo. Duplíquelo nuevamente, el trabajo aumenta dieciséis veces. Los informáticos ignoran los segundos. El hardware se acelera de todos modos. Cuentan los pasos. Lo llamamos notación O grande. La escuela primaria es O (n ^ 2). Cuadrático. Si su número crece en 1.000, el trabajo se dispara en un millón.
La carga de trabajo aumenta con el cuadrado del número de dígitos.
Desde la antigüedad, los magos de las matemáticas asumieron que este límite cuadrático era una ley de la naturaleza. Andrey Kolmogorov, una leyenda soviética, apostó su reputación a ello en una conferencia de 1960. Les dijo a los estudiantes de la Universidad Estatal de Moscú: “Se necesita O(n^2)”. Es una conjetura formal. Un desafío. Espera a que alguien lo pruebe o lo rompa.
Tomó una semana. Anatoly Karatsuba estaba sentado entre el público. Tenía 23 años. Regresó con pruebas de que Kolmogorov estaba equivocado. El profesor quedó atónito. En realidad, Kolmogorov escribió él mismo el artículo para una revista prestigiosa, pero le puso el nombre de Karatsuba. El niño no lo supo hasta que llegaron las reimpresiones por correo.
El truco
Karatsuba se dio cuenta de algo simple pero profundo. Las multiplicaciones son caras. Las adiciones son baratas. ¿Por qué no intercambiarlos?
Tome 12 x 34.
Divídelo.
12 es 10 + 2.
34 es 30 + 4.
Tradicionalmente, haces cuatro multiplicaciones:
1×3
1×4
2×3
2×4
Karatsuba encontró la manera de hacerlo con tres.
Calcula la primera parte: 1×3 = 3.
Calcula la última parte: 2×4 = 8.
Ahora el medio. Normalmente harías (1×4) + (2×3). Dos se multiplica. En su lugar, suma los primeros números: 1+2=3. Suma los últimos números: 3+4=7. Multiplica esas sumas: 3×7=21. Resta las partes que ya conoces. 21 – 3 – 8 = 10.
Auge. Obtuviste el término medio con una multiplicación extra.
¿Vale la pena?
No para números pequeños. Los gastos generales de dividir y sumar le cuestan.
¿Pero para 1.234 x 5.678? Divídelo por la mitad. Recurrida. Divide esas mitades. Hazlo de nuevo. El compuesto de ahorro.
El algoritmo cae a aproximadamente O (n^1,585).
Los números de mil dígitos solían requerir un millón de mults de un solo dígito. Ahora se necesitan menos de 57.000 pasos. Masivo.
Esto no es sólo teoría. Está en Python.
Python usa matemáticas escolares estándar para entradas pequeñas. Lo suficientemente suave.
Una vez que alcanzas aproximadamente 63 dígitos decimales (dependiendo de la base de la máquina), Python activa un interruptor. Karatsuba se hace cargo. No ves que esto suceda. Pero está ahí. Manejando su criptografía.
Algoritmos galácticos
La carrera continuó durante décadas. ¿Podemos ir más rápido?
2019 trajo la última sorpresa. David Harvey y Joris van Der Hoeven publicaron un algoritmo que supera a Karatsuba por mucho.
O(n iniciar sesión n).
Lee eso de nuevo.
Los logaritmos crecen increíblemente lentamente.
n log n es apenas mayor que n.
Básicamente, multiplicar dos números enormes ahora lleva aproximadamente el mismo tiempo que leerlos.
Es asombroso. El techo teórico parece haber sido tocado.
O tal vez no.
Aquí está el truco.
No funciona para los números que nos importan.
El algoritmo de Harvey y Van Der Hoeven sólo se vuelve más rápido que el de Karatsuba cuando los números se vuelven realmente grandes. No es un “número de tarjeta de crédito” grande. Grande galáctico.
En informática tenemos un término para esto: algoritmo galáctico.
Hermosa teoría. Uso práctico cero. Las cifras requeridas son mayores que la mayoría de las transacciones digitales en la historia de la humanidad juntas.
Estamos atrapados en el medio.
Utilizando trucos de los años 60 para la mayor parte de nuestra informática diaria.
Usar trajes del siglo XXI además de matemáticas del siglo XX.
¿Alguna vez usamos O (n log n) en el mundo real?
Quizás cuando procesemos datos se establezca el tamaño de las galaxias.
Hasta entonces esperamos.
Para el siguiente truco.
O mejor hardware para ocultar nuestra pereza.
La respuesta aún podría ser cuadrática.
Podría ser lineal.
No lo sabemos todavía.
