![Java User Group [Padova]](/images/theme/header.jpg)
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.
Beh dai, basta che l’array su cui fai la ricerca binaria abbia meno di 2^30 elementi :)
Citando Knuth: “Beware of bugs in the above code; I have only proved it correct, not tried it.” :)
non è l’algoritmo sbagliato è il linguaggio, se la promozione tra tipi fosse implicita ( o se avessero usato BigInteger dall’inizio) il problema non sarebbe esistito.
IIRC knuth parla dell’algoritmo in astratto (i.e. parlando di limiti considera +/- infinito ma nell’aritmetica degli interi sulle cpu che conosco questi non esistono) quindi forse non si è sbagliato.. d’altronde preferisco pensare che l’abbia fatto :)
no.. espresso male: è l’interazione tra algoritmo e linguaggio, poveracci gli int no hanno niente di male in se :)
In realtà, leggendolo più attentamente, l’implementazione dell’algoritmo di Knuth è corretta, ma non per il motivo espresso da riffraff.
riffraff, hai ragione se ci limitiamo alla descrizione dell’algoritmo, con l’ipotesi che le operazioni espresse in essa, diciamo così, “in astratto” vengano poi implementate in modo che ne mantangano esattamente la semantica.
Ma Knuth ne dà anche un’implementazione in MIX, usando il registro A per trovare l’indice intermedio:
Tale registro ha la dimensione di una “word”, cioè 5 byte (da 6 bit) più il segno. Quindi va in overflow se si cerca di memorizzarvici un valore più grande di 1073741823.
L’algoritmo però è corretto perchè ciò che viene sommato è il contenuto dei due registri I1 e I2, che sono da 2 byte più il segno, quindi la loro somma non potrà mai mandare in overflow il registro A.
its a creative article.i teaches in a good way..thanks for sharing.. Regards..
I completely resolved my question when I read this post, thanks to the author for the very detailed description. I wrote my review on the https://cvwritingservicesuk.com/uk-careersbooster-review/, you can go in and read. Thank you very much for your attention in your time.