Bug storico...

Posted by Lucio Benfante Fri, 16 Jun 2006 05:03:00 GMT

...presente nel JDK, e probabilmente nella maggior parte delle implementazioni di algoritmi con approccio “divide et impera”.

Quanti di noi non hanno mai scritto questa semplice e innocente riga di codice (con low e high di tipo int)?

int mid = (low+high)/2;

Il problema è che la somma dei due interi può risultare in un overflow…gosh…

L’implementazione corretta sarebbe qualcosa di simile a:

int mid = low + ((high-low)/2);

Provate a cercare in qualunque libro di algoritmi e vedrete che anche i grandi sbagliano. Io ho guardato in ‘The Art of Computer Programming’), e anche l’implementazione dell’algoritmo di ricerca binaria di Donald E. Knuth soffre dello stesso bug.

Per quanto riguarda il JDK, il bug si trova (almeno) nel metodo binarySearch della classe java.utils.Arrays. A me non è mai capitato, ma ve l’immaginate la sorpresa (per non dire altro) di vedervi sollevare un ArrayIndexOutOfBoundsException da un metodo di quella classe?

L’annuncio e la discussione del bug li fa lo stesso autore della classe, Josh Bloch, in questo blog.

Posted in Programmazione | Tags binary, bug, overflow, search | 7 comments | no trackbacks