Google
 

miércoles, junio 07, 2006

Bug en un algoritmo histórico

Seguro que todos conoceréis los algoritmos llamados binary search y merge-sort (desconozco sus nombres en español), pues recientemente nuestros amigos de Google han encontrado un bug cuando se utiliza sobre matrices mayores de 2^30.

Es un fallo histórico pues es un algoritmo ampliamente usado y que ha pasado despercibido durante más de 20 años. Aunque por suerte no tiene porque afectarnos demasiado ya que solo ocurre en listas de más de mil millones.

3 comentarios:

javi dijo...

A mi no me parece que sea un bug, es símplemente una limitación de las máquinas actuales. Cualquier algortimo en el cual se usen sumas de enteros y se produzcan desbordamientos dejará de funcionar correctamente.

samsaga2 dijo...

Es claramente un bug, en el caso de c++ por ejemplo puede llegar a ocasionar cuelgues de la maquina ya que podria acceder a zonas de memoria de forma aleatoria.

fiero dijo...

A mi tampoco me parece que sea un bug. El hecho de que se pueda llegar a colgar la máquina no es definición de un bug, el programador ya sabía que existía esa limitación al hacer la función en un sistema de 32 bits. Todos tenemos funciones que explotarían con determinador valores de entrada, y que usamosporque estamos seguros que nunca existirán esos valores.

De todas formas el fallo de desbordamiento no es un bug del algoritmo. Es un error en la función de google. Si compilan el mismo programa para una máquina de 64 bits pueden llegar hasta 2^62 elementos ¿no?