Los ni\u00f1os aprenden las tablas de multiplicar en la escuela. Memor\u00edzalos. Buena suerte con los n\u00fameros de tres d\u00edgitos. Ah\u00ed es donde entran en juego los algoritmos. Apilas los d\u00edgitos. Multiplica fila por fila. Durante miles de a\u00f1os pensamos que eso era lo mejor que pod\u00edamos hacer. Es lento. Brutalmente lento para big data. Luego, en 1960, un joven de 23 a\u00f1os cambi\u00f3 todo. El misterio de la velocidad de multiplicaci\u00f3n sigue abierto. <\/p>\n
La multiplicaci\u00f3n no es s\u00f3lo una tarea. Opera Internet. Cifrado, IA, procesamiento de audio. Todo ello se apoya en la multiplicaci\u00f3n. Multiplicaci\u00f3n intensa. Cuando multiplicas n\u00fameros enormes millones de veces por segundo, cada paso cuenta. Una ligera mejora de la eficiencia ahorra miles de millones. <\/p>\n
Mire el m\u00e9todo de la escuela primaria. Dos d\u00edgitos significan cuatro multiplicaciones de un solo d\u00edgito. \u00bfTres d\u00edgitos? Nueve. Se escala cuadr\u00e1ticamente. Duplica la longitud, cuadriplica el trabajo. Dupl\u00edquelo nuevamente, el trabajo aumenta diecis\u00e9is veces. Los inform\u00e1ticos ignoran los segundos. El hardware se acelera de todos modos. Cuentan los pasos. Lo llamamos notaci\u00f3n O grande. La escuela primaria es O (n ^ 2). Cuadr\u00e1tico. Si su n\u00famero crece en 1.000, el trabajo se dispara en un mill\u00f3n. <\/p>\n
\nLa carga de trabajo aumenta con el cuadrado del n\u00famero de d\u00edgitos. <\/p>\n<\/blockquote>\n
Desde la antig\u00fcedad, los magos de las matem\u00e1ticas asumieron que este l\u00edmite cuadr\u00e1tico era una ley de la naturaleza. Andrey Kolmogorov, una leyenda sovi\u00e9tica, apost\u00f3 su reputaci\u00f3n a ello en una conferencia de 1960. Les dijo a los estudiantes de la Universidad Estatal de Mosc\u00fa: “Se necesita O(n^2)”. Es una conjetura formal. Un desaf\u00edo. Espera a que alguien lo pruebe o lo rompa. <\/p>\n
Tom\u00f3 una semana. Anatoly Karatsuba estaba sentado entre el p\u00fablico. Ten\u00eda 23 a\u00f1os. Regres\u00f3 con pruebas de que Kolmogorov estaba equivocado. El profesor qued\u00f3 at\u00f3nito. En realidad, Kolmogorov escribi\u00f3 \u00e9l mismo el art\u00edculo para una revista prestigiosa, pero le puso el nombre de Karatsuba. El ni\u00f1o no lo supo hasta que llegaron las reimpresiones por correo. <\/p>\n
El truco<\/h3>\n
Karatsuba se dio cuenta de algo simple pero profundo. Las multiplicaciones son caras. Las adiciones son baratas. \u00bfPor qu\u00e9 no intercambiarlos? <\/p>\n
Tome 12 x 34.
\nDiv\u00eddelo.
\n12 es 10 + 2.
\n34 es 30 + 4. <\/p>\nTradicionalmente, haces cuatro multiplicaciones:
\n1×3
\n1×4
\n2×3
\n2×4 <\/p>\nKaratsuba encontr\u00f3 la manera de hacerlo con tres.
\nCalcula la primera parte: 1×3 = 3.
\nCalcula la \u00faltima parte: 2×4 = 8. <\/p>\nAhora el medio. Normalmente har\u00edas (1×4) + (2×3). Dos se multiplica. En su lugar, suma los primeros n\u00fameros: 1+2=3. Suma los \u00faltimos n\u00fameros: 3+4=7. Multiplica esas sumas: 3×7=21. Resta las partes que ya conoces. 21 – 3 – 8 = 10.
\nAuge. Obtuviste el t\u00e9rmino medio con una multiplicaci\u00f3n extra. <\/p>\n\u00bfVale la pena?
\nNo para n\u00fameros peque\u00f1os. Los gastos generales de dividir y sumar le cuestan.
\n\u00bfPero para 1.234 x 5.678? Div\u00eddelo por la mitad. Recurrida. Divide esas mitades. Hazlo de nuevo. El compuesto de ahorro.
\nEl algoritmo cae a aproximadamente O (n^1,585).
\nLos n\u00fameros de mil d\u00edgitos sol\u00edan requerir un mill\u00f3n de mults de un solo d\u00edgito. Ahora se necesitan menos de 57.000 pasos. Masivo. <\/p>\nEsto no es s\u00f3lo teor\u00eda. Est\u00e1 en Python.
\nPython usa matem\u00e1ticas escolares est\u00e1ndar para entradas peque\u00f1as. Lo suficientemente suave.
\nUna vez que alcanzas aproximadamente 63 d\u00edgitos decimales (dependiendo de la base de la m\u00e1quina), Python activa un interruptor. Karatsuba se hace cargo. No ves que esto suceda. Pero est\u00e1 ah\u00ed. Manejando su criptograf\u00eda. <\/p>\nAlgoritmos gal\u00e1cticos<\/h3>\n
La carrera continu\u00f3 durante d\u00e9cadas. \u00bfPodemos ir m\u00e1s r\u00e1pido?
\n2019 trajo la \u00faltima sorpresa. David Harvey y Joris van Der Hoeven publicaron un algoritmo que supera a Karatsuba por mucho.
\nO(n iniciar sesi\u00f3n n). <\/p>\nLee eso de nuevo.
\nLos logaritmos crecen incre\u00edblemente lentamente.
\nn log n es apenas mayor que n.
\nB\u00e1sicamente, multiplicar dos n\u00fameros enormes ahora lleva aproximadamente el mismo tiempo que leerlos. <\/p>\nEs asombroso. El techo te\u00f3rico parece haber sido tocado.
\nO tal vez no.
\nAqu\u00ed est\u00e1 el truco.
\nNo funciona para los n\u00fameros que nos importan. <\/p>\nEl algoritmo de Harvey y Van Der Hoeven s\u00f3lo se vuelve m\u00e1s r\u00e1pido que el de Karatsuba cuando los n\u00fameros se vuelven realmente<\/em> grandes. No es un “n\u00famero de tarjeta de cr\u00e9dito” grande. Grande gal\u00e1ctico.
\nEn inform\u00e1tica tenemos un t\u00e9rmino para esto: algoritmo gal\u00e1ctico.
\nHermosa teor\u00eda. Uso pr\u00e1ctico cero. Las cifras requeridas son mayores que la mayor\u00eda de las transacciones digitales en la historia de la humanidad juntas. <\/p>\nEstamos atrapados en el medio.
\nUtilizando trucos de los a\u00f1os 60 para la mayor parte de nuestra inform\u00e1tica diaria.
\nUsar trajes del siglo XXI adem\u00e1s de matem\u00e1ticas del siglo XX. <\/p>\n\u00bfAlguna vez usamos O (n log n) en el mundo real?
\nQuiz\u00e1s cuando procesemos datos se establezca el tama\u00f1o de las galaxias.
\nHasta entonces esperamos.
\nPara el siguiente truco.
\nO mejor hardware para ocultar nuestra pereza. <\/p>\nLa respuesta a\u00fan podr\u00eda ser cuadr\u00e1tica.
\nPodr\u00eda ser lineal.
\nNo lo sabemos todav\u00eda.<\/p>\n","protected":false},"excerpt":{"rendered":"Los ni\u00f1os aprenden las tablas de multiplicar en la escuela. Memor\u00edzalos. Buena suerte con los n\u00fameros de tres d\u00edgitos. Ah\u00ed es donde entran en juego los algoritmos. Apilas los d\u00edgitos. Multiplica fila por fila. Durante miles de a\u00f1os pensamos que eso era lo mejor que pod\u00edamos hacer. Es lento. Brutalmente lento para big data. Luego, […]<\/p>\n","protected":false},"author":1,"featured_media":7909,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"tdm_status":"","tdm_grid_status":""},"categories":[1],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/es\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}