A falta de ser revisado y confirmado por otros expertos, se ha publicado en la Web hace pocos días: “Integer multiplication in time O(n log n)”, por David Harvey y Joris Van Der Hoeven. Esto supondría un avance importante en relación con una conjetura realizada en 1971 por Schonhage y Strassen. Por supuesto, el interés [...]

. El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(nlog 3)  ( ≈ O(n1,59) )  aparece publicado en el artículo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de [...]

. Punteros a cosas (curiosidades) mencionadas hoy en clase: algoritmo de coste lineal para el cálculo del k-ésimo elemento de un vector (y por tanto para el cálculo de la mediana) orígenes del algoritmo de Karatsuba premio Turing de este año su algoritmo (ojo, hay una errata en esa página; cuando en un párrafo de [...]

. Ha surgido hoy en clase, es el método gráfico de multiplicar, conocido también como método maya o Tzeltal.