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

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 ¹ .

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 ² .

^{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,