Dla jakiej wartości i wykonuje pętlę while (i == i + 1) {} na zawsze?

120

Przeszedłem przez tę układankę z zaawansowanego kursu programowania na egzaminie uniwersyteckim w Wielkiej Brytanii .

Rozważmy następującą pętlę, w której i jest jak dotąd niezadeklarowany:

while (i == i + 1) {}

Znajdź definicję i, która poprzedza tę pętlę, taką, że pętla while trwa wiecznie.

Następne pytanie, które zadawało to samo pytanie dla tego fragmentu kodu:

while (i != i) {}

było dla mnie oczywiste. Oczywiście w tej innej sytuacji tak jest, NaNale naprawdę utknąłem w poprzedniej. Czy ma to związek z przepełnieniem? Co spowodowałoby, że taka pętla zapętla się na zawsze w Javie?

java loops types jake mckenzie
źródło
3
Jakieś możliwości zastąpienia .equals()metody? Ponieważ i jest niezadeklarowany, możemy użyć dowolnej klasy tego, co chcemy.
Geno Chen
7
@Raedwald studiowanie „nieprofesjonalnego” kodu czyni cię bardziej „profesjonalnym”, więc ... W każdym razie, to dobre pytanie
Andrew Tobilko
12
Ciekawostka: w C # działa to również dla typów liczbowych dopuszczających wartość null, których wartości są null, ponieważ null == nulljest prawdziwe i null + 1jest null.
Eric Lippert
4
@EricDuminil: Sytuacja jest znacznie gorsza niż sobie wyobrażasz. W wielu językach arytmetyka zmiennoprzecinkowa musi być wykonywana z co najmniej 64 bitami precyzji określonymi przez double, co oznacza, że ​​można to zrobić z większą precyzją na życzenie kompilatora, i tak się dzieje w praktyce . Mogę wskazać na kilkanaście pytań na tej stronie od programistów C #, którzy zastanawiają się, dlaczego 0.2 + 0.1 == 0.3zmienia jego wartość w zależności od ustawień kompilatora, fazy księżyca i tak dalej.
Eric Lippert
5
@EricDuminil: Winę za ten bałagan spoczywa na Intelu, który dał nam zestaw chipów, który wykonuje bardziej precyzyjną i szybszą arytmetykę zmiennoprzecinkową, jeśli liczby można zarejestrować, co oznacza, że ​​wyniki obliczeń zmiennoprzecinkowych mogą zmieniać ich wartości w zależności od o tym, jak dobrze działa dziś program planujący rejestr w optymalizatorze. Twoje wybory jako projektanta języka są wtedy pomiędzy powtarzalnymi obliczeniami a szybkimi, precyzyjnymi obliczeniami , a społeczność, która dba o matematykę zmiennoprzecinkową, wybierze to drugie.
Eric Lippert

Odpowiedzi:

142

Po pierwsze, ponieważ while (i == i + 1) {}pętla nie zmienia wartości i, uczynienie tej pętli nieskończoną jest równoznaczne z wybraniem wartości, iktóra spełnia i == i + 1.

Takich wartości jest wiele:

Zacznijmy od „egzotycznych”:

double i = Double.POSITIVE_INFINITY;

lub

double i =  Double.NEGATIVE_INFINITY;

Przyczyna spełnienia tych wartości i == i + 1została podana w
JLS 15.18.2. Operatory addytywne (+ i -) dla typów liczbowych :

Suma nieskończoności i skończonej wartości jest równa nieskończonemu operandowi.

Nie jest to zaskakujące, ponieważ dodanie skończonej wartości do nieskończonej wartości powinno dać nieskończoną wartość.

To powiedziawszy, większość wartości itego spełnienia i == i + 1to po prostu duże double(lub float) wartości:

Na przykład:

double i = Double.MAX_VALUE;

lub

double i = 1000000000000000000.0;

lub

float i = 1000000000000000000.0f;

doubleI floattypy mają ograniczoną dokładność, więc jeśli wziąć tyle duża doublelub floatwartość, dodając 1do niego spowoduje taką samą wartość.

Eran
źródło
10
Lub (double)(1L<<53)- lubfloat i = (float)(1<<24)
dave_thompson_085
3
@Ruslan: Każdy matematyk by się z tym nie zgodził. Liczby zmiennoprzecinkowe nie mają większego sensu. Nie są asocjacyjne, nierefleksyjne (NaN! = NaN), a nawet nie są zastępowalne (-0 == 0, ale 1/0! = 1 / -0). Dlatego większość mechanizmów algebry nie ma zastosowania.
Kevin
2
@Kevin, podczas gdy liczby zmiennoprzecinkowe nie mogą w ogóle mieć zbyt dużego sensu w ogóle, zachowanie nieskończoności (co jest opisane w tym zdaniu) zostało zaprojektowane tak, aby miało sens.
Ruslan
4
@Kevin Aby być uczciwym wobec floatów, jeśli masz do czynienia z nieskończonościami lub niezdefiniowanymi wartościami, nie możesz również przyjąć właściwości, które wypisałeś w algebrze.
Voo
2
@Kevin: IMHO, matematyka zmiennoprzecinkowa mogłaby mieć o wiele więcej sensu, gdyby zastąpiła pojęcia „dodatnich i ujemnych zera” dodatnich, ujemnych i bez znaku „nieskończenie małych” razem z jednym „prawdziwym zerem” i sprawiła, że NaN równy sobie. Prawdziwe zero mogłoby zachowywać się jak tożsamość addytywna we wszystkich przypadkach, a operacje polegające na dzieleniu przez nieskończenie małe straciłyby skłonność do zakładania, że ​​nieskończenie małe są dodatnie.
supercat
64

Te łamigłówki zostały szczegółowo opisane w książce „Java Puzzlers: Traps, Pitfalls and Corner Cases” autorstwa Joshua Blocha i Neala Gaftera.

double i = Double.POSITIVE_INFINITY;
while (i == i + 1) {}

lub:

double i = 1.0e40;
while (i == i + 1) {}

oba spowodują nieskończoną pętlę, ponieważ dodanie 1do wartości zmiennoprzecinkowej, która jest wystarczająco duża, nie zmieni tej wartości, ponieważ nie „wypełnia luki” do jej następcy 1 .

Uwaga dotycząca drugiej zagadki (dla przyszłych czytelników):

double i = Double.NaN;
while (i != i) {}

również skutkuje nieskończoną pętlą, ponieważ NaN nie jest równe żadnej wartości zmiennoprzecinkowej, w tym sobie 2 .

1 - Java Puzzlers: Traps, Pitfalls i Corner Cases (rozdział 4 - Loopy Puzzlers).

2 - JLS §15.21.1

Oleksandr Pyrohov
źródło
1

double i = Double.POSITIVE_INFINITY;

Farcas George
źródło
0

Tylko pomysł: a co z wartościami logicznymi?

bool i = TRUE;

Czy to nie jest przypadek, w którym i + 1 == i?

Dominique
źródło
zależy od języka. Wiele języków automatycznie wymusza wartości logiczne na ints w połączeniu z int. Inni robią to, co sugerujesz - zmuszając int do wartości logicznej.
Carl Witthoft
8
To pytanie dotyczy języka Java, a Twoja sugestia nie przechodzi kompilacji w języku Java (który nie ma +operatora przyjmującego operandy a booleani an intjako).
Eran
@Eran: na tym polega cała idea przeciążania operatorów. Możesz sprawić, że wartości logiczne Java będą zachowywać się jak elementy C ++.
Dominique
4
Tyle że Java nie obsługuje przeciążania operatorów, więc nie możesz.
CupawnTae,