El mejor algoritmo actual en un ordenador de hace 30 años es más rápido que el mejor algoritmo de hace 30 años en un ordenador actual

El titular es mi versión personal extrapolada de la siguiente cita:

«Over the past three decades, the progress in algorithms for the simulation of the Ising model has outperformed Moore’s law: running modern algorithms on 30 year old computers would be faster than running 30 year old algorithms on the fastest supercomputers of today!» L.D. Landau.

Extraída del artículo de Vinay Ambegaokar, Matthias Troyer, «Estimating errors reliably in Monte Carlo simulations of the Ehrenfest model,» Am. J. Phys. 78: 150-157, Feb. 2010 [gratis en ArXiv]. Por cierto, ya que estamos, me permito extraer también lo siguiente:

«Stanislav Ulam invented the Monte Carlo method in the 1940s when playing Solitaire while lying sick in bed. He wanted to know the probability of winning in Solitaire but was faced with the problem that with 52! ≈ 1068 different ways of arranging the cards he could never exactly calculate the chance of winning. He realized, however, that by just playing 100 games and counting the number of wins he could already get a pretty good estimate.» R. Eckhardt.



15 Comentarios

  1. Tas seguro de esa afirmacion ?
    Por que hoy en dia lo que es depuracion de codigo es penosa en uso general ,vease juegos y muchas aplicaciones que consumen mas recursos de los que deverian ,se salva que antes se usaban muchos trucos como el famoso del relog del sistema que luego dio efecto al famoso efecto 2000.

    1. No estoy seguro si sabes de lo que estas hablando Fer, es claro que la afirmacion que hace el titulo de esta noticia es un poco «amarillo» (?), pero muchas de las aplicaciones de hoy en dia esta muy depuradas, tu hablas de game engines: justamente los engines mas fuertes tiene meses de trabajo en depuracion para mejorar su rendimiento.
      Igual depurar un algoritmo que ya de por si es poco eficiente no logra gran cosa.

    2. Creo que el articulo es acertado y se refiere a Algoritmos con A mayúscula, no a software en general, que como todo el mundo sabe, los sistemas de calidad de la producción actual dejan mucho que desear.

      Si interesa el tema, mirar los esfuerzos de las compañías como IBM, TOSHIBA y SONY con su plataforma Cell o SGI y su Altix. Arquitecturas que no son otra cosa sino que herramientas para crear nuevas maneras para solucionar problemas (y digo esto y no paradigmas de programación porque lo uno es lo uno y lo otro es lo otro 😉 )

      Buff, me podría enrollar una barbaridad, y eso que yo solo quería decir que deberían es con B

  2. Tu título es demasiado genérico, prefiero la cita de Landau, que es bastante más precisa.

    Además, que los algoritmos mejoren es de esperar (y si no aparecen mejores, nos quedamos con los antiguos, que a la postre serían los mejores), lo que no es tan de esperar es que el software actual sea de tan mala calidad. La ley epónima de Wirth precisamente dice: «el software se ralentiza más deprisa de lo que se acelera el hardware» (http://es.wikipedia.org/wiki/Ley_de_Wirth)

  3. La estética del título es bonita, pero yo creo que en la mayor parte de los casos no es cierta. Hoy en día se tiende a beneficiar a los diseños basados en fuerza bruta para resolver un problema, dado que se cuenta con muchos más recursos. Además, la mayor parte de los algoritmos clásicos para resolver muchas tareas cuentan con más de 20 años en el mejor caso.

  4. Esto no es cierto. Por una parte la arquitectura de los actuales ordenadores se han optimizado para ciertos tipos de algoritmos, mientras que la mayor parte de entornos de programación facilitan el uso de algoritmica bastante mala. La prueba es que los libros de Knuth (http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming ) siguen siendo la mejor referencia para resolver la mayor parte de los problemas.

    Actualmente si un algoritmo no es lo suficiente bueno o eficiente sencillamente se compra un ordenador más potente (o una nube de ellos).

    1. Joaquín, ojalá todo fuera tan fácil. No es tan fácil comprar un ordenador más potente cuando ya estás usando el ordenador más potente. Y no puedes usar una nube de supercomputadores… Por poner un ejemplo, en QCD en redes (lattice QCD) ha costado 30 años de investigación lograr mejorar los algoritmos, que siempre han sido ejecutados en los mayores supercomputadores de cada momento, para lograr un error menor del 1% para la masa del protón (se logró en 2008). ¿Cuándo las simulaciones podrán alcanzar un error similar al error experimental que se obtiene en laboratorio (más de 8 dígitos significativos)? Nadie lo sabe. Se requieren zettaflops (millones de petaflops), pero el ordenador más rápido del mundo (Cray XT5 ‘Jaguar’) no llega a los 3 petaflop por segundo (en teoría, que en la práctica mucho menos). Y no es fácil imaginar una nube de trillones de PC…

      1. No conozco esos algoritmos, pero la mayor parte de ellos están mal paralelizados y se basan en la fuerza bruta. Para «calzar» un algoritmo es necesario que el modelo conceptual con el que se diseña se adapte totalmente a la arquitectura sobre la que se ejecuta (problema de la mayor parte de los cray y similares y la libreria MPI de comunicación) ya que la comunicación de los datos intermedios puede sobrepasar en latencia a los cálculos centralizados. Por eso te comento que la mayor parte de la gente espera a poner un ordenador «mas gordo» por no tener programadores que piensen en paralelo y conozcan bien las arquitecturas. Por experiencia se pueden modificar ciertas implementaciones para que puedan ir entre 2 y 5 ordenes de magnitud más rapidos sobre una misma arquitectura.

        Ahora mismo es cuestión de dinero pues la capacidad de cálculo de un centro de calculo de Amazon o Google sobrepasa ese limite (eso si con un paradigma especial para ciertos algortimos llamado map-reduce) (andan por los TeraFlops).

  5. En el titular se hace una mezcla errónea entre algoritmo e implementación. Creo que se está hablando de comparar implementaciones de algoritmos, no de algoritmos propiamente dichos. Básicamente porque un algoritmo nunca podrá ejecutarse en otra cosa que no sea una máquina de Turing 🙂 y siempre tendrá el mismo orden de complejidad.

    1. Pp, cuidado, no te confundas, para resolver un problema hay muchos algoritmos posibles. Todo dispositivo de cómputo (ordenador, calculadora, móvil, etc.) es equivalente formalmente a una máquina de Turing (según la tesis de Church-Turing). Un algoritmo puede ser implementado de múltiples maneras pero su complejidad computacional no cambia (cada implementación cambia la constante que multiplica el orden de complejidad pero no dicho orden).

      Los algoritmos evolucionan conforme el conocimiento avanza. Por ejemplo, mira la historia de los algoritmos para calcular números primos, no sé si conoces la criba de Eratóstenes y la criba de Aitken, o los algoritmos probabilísticos para determinar si un número es primo o no. Constantemente se están realizando descubrimientos teóricos que permiten mejorar la complejidad computacional de los mejores algoritmos.

      1. Creo que está claro que existen infinitas formas de resolver un problema. Pero para comparar dos algoritmos (A mejor que B) desde el punto de vista de su rapidez, solo es posible hablar de su orden de complejidad en función de la entrada -O(n)-, y esto es independiente del hardware, o sea, de la implementación concreta. Por ejemplo, lo que viene a decir este titular es «La mejor manera de ordenar N números conocida a día de hoy -PEj. Quicksort, Nlog(N)- ejecutada en un ordenador de hace 30 años, es más rápido que el mejor algoritmo para ordenar N números conocido hace 30 años -PEj. burbuja, N cúbico – ejecutándose en un ordenador de hoy. Que no le quepa duda a nadie. Nlog(N) ES siempre es más rápido que N al cubo para el mismo N, independientemente del hardware. Si hablamos de implementación, puede venir un despistado y decir que lo anterior no es cierto, porque para un N suficientemente pequeño, un procesador QuadCore-Leches ordena 100 numeros usando la burbuja más rápido que un 8086 usando Quicksort. Pues eso, entonces solo nos queda sentarnos a esperar que haya ordenadores suficientemente potentes como para que los problemas NP dejen de ser un problema. Fuerza Knuth, aún tenemos esperanza 🙂

        PD, un saludo de un fiel seguidor y felicitaciones por el magnífico blog.

  6. Correcto. Un algoritmo es una forma de resolver un problema. Ni mas, ni menos.

    Un algoritmo no es c++, no es java, no es codigo. Son lo pasos bien definidos y estructurados que dan lugar a la solucion de un problema.

    Creo que se confunden conceptos de implementacion de un algoritmo con el algoritmo propiamente dicho.

    Computabilidad ftw!

  7. Supongo que será generalizando, porque en un ejemplo simple, el algoritmo de sacar el resto de una división no creo que se haya podido acelerar en cientos de veces.

    1. Obviamente, Skab, estoy generalizando y mucho. El algoritmo para sumar dos números es prácticamente imposible de mejorar, como el que tú indicas. Me refiero a problemas en los que el algoritmo óptimo o cuasi-óptimo no es conocido (no hay demostración matemática aún).

      Por supuesto, el titular es una «caricatura» pero como todas las caricaturas siempre tiene algo de verdad. Es bonito ver que mucha gente realiza comentarios, ese es el objetivo del blog, que la gente comente.

Deja un comentario

Por Francisco R. Villatoro
Publicado el ⌚ 14 enero, 2010
Categoría(s): ✓ Historia • Informática • Prensa rosa
Etiqueta(s): ,