Czy uzasadnione jest założenie, że dowolna wielkość fizyczna może być reprezentowana przez 64-bitową liczbę całkowitą bez przepełnienia lub niedopełnienia?

Oryginalny algorytm wyszukiwania binarnego w JDK używał 32-bitowych liczb całkowitych i miał błąd przepełnienia, jeśli (low + high) > INT_MAX( http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html ) .

Jeśli przepisujemy ten sam algorytm wyszukiwania binarnego przy użyciu (podpisanych) liczb całkowitych 64-bitowych, czy możemy założyć, że low + highnigdy nie przekroczy INT64_MAX, ponieważ fizycznie niemożliwe jest posiadanie 10 ^ 18 bajtów pamięci?

Czy przy użyciu (podpisanych) 64-bitowych liczb całkowitych do reprezentowania wielkości fizycznych uzasadnione jest założenie, że niedopełnienie i przepełnienie nie mogą się zdarzyć?

Krótka odpowiedź brzmi: nie. Jednak w przypadku niektórych aplikacji twoje założenie może być prawidłowe.

Zakładając, że int, 2 ^ 63, z dodanymi przecinkami dla większej przejrzystości, = 9,223,372,036,854,775,808. Więc to w przybliżeniu 9 * 10 ^ 18. 10 ^ 18 to „Exa”.

Wikipedia mówi: „Szacuje się, że w 2013 r. Internet osiągnął 4 zettabajty. [12]”, czyli 4000 eksabajtów. Dlatego WWW jest około 400 razy większy niż 2 ^ 63 bajty.

Dlatego istnieje co najmniej jedna wielkość fizyczna, która jest znacznie większa niż 64-bitowa liczba całkowita ze znakiem (lub niepodpisana). Zakładając, że twoje jednostki są bajtami . Gdyby twoje jednostki były czymś znacznie większym, jak GigaBytes, byłbyś w porządku, ale twoja precyzja pomiaru byłaby niska.

W innym przykładzie rozważ odległe galaktyki. Galaktyka Andromedy jest w rzeczywistości jedną z bliskich i znajduje się w odległości 2,5 * 10 ^ 6 lat świetlnych. Gdyby twoje jednostki były mile , byłoby to 14,5 * 10 ^ 18, więcej niż 64-bitowa liczba całkowita ze znakiem. Teraz oczywiście zależy to od jednostek używanych do pomiarów, ale niektóre galaktyki są znacznie dalej niż Andromeda. ( Najbardziej znany jest oddalony o 13 * 10 ^ 9 LY ) . W zależności od precyzji, którą chcesz mierzyć, może on przepełnić 64-bitową liczbę całkowitą.

( Dodano ) Tak, mile są kiepską jednostką dla odległości astronomicznej. Bardziej normalną jednostką może być Jednostka Astronomiczna , około 93 milionów mil. Korzystając z tej jednostki miary, najdalej znana galaktyka to około 10 ^ 15 AU (jeśli moja matematyka ma rację), co zmieściłoby się w 64-bitowej int. Jeśli jednak chcesz zmierzyć odległość do Księżyca, do pobliskich satelitów krążących wokół, jednostka ta jest zbyt duża.

Jeszcze jeden przykład z elektroniki: Farad (F), jednostka pojemności . Duży zakres kondensatorów do 5kF. Liczba ta prawdopodobnie wzrośnie z czasem wraz z poprawą samochodów hybrydowych, „inteligentnych sieci” itp. Kiedyś można zmierzyć pojemność tak małą jak 10 ^ -18 F. Tak więc ogólny zakres „rzeczywistej” pojemności, którą możemy zmierzyć dzisiaj, to 5 * 10 ^ 21, większy niż 64-bitowa liczba całkowita.

Nie musisz nawet iść kosmicznie, gdy w grę wchodzą kombinatoryka. W grze w brydża istnieją 2 ^ 95 możliwych ofert, a to z niewielkiej strony złożoności.

Najbardziej odpowiednią fizyczną ilością dla twojego pytania jest RAM komputera .

Windows Server 2012 obsługuje do 4 TB pamięci fizycznej. To 2 ⁴² bajty. Jeśli pojemność pamięci RAM będzie się podwajać co roku, to za 17 lat „Windows Server 2032” będzie obsługiwał 2 ⁶² bajty pamięci fizycznej, a wtedy low + highosiągniesz 2 ⁶³ - 2 i pocałujesz 64-bitową liczbę całkowitą ze znakiem.

Mam nadzieję, że nie zawiodą systemy o znaczeniu krytycznym dla bezpieczeństwa, zakładając, że 64 bity zawsze będą wystarczające.

Dla nieco bardziej ogólnego zastosowania najbardziej odpowiednią wielkością fizyczną jest przestrzeń adresowa pamięci . (Przydatne jest posiadanie znacznie większej przestrzeni adresowej niż pamięć fizyczna, np. Aby umieścić wiele stosów w pamięci, wszystkie z miejscem na powiększenie.) Obecne implementacje x86-64 obsługują 48-bitowe adresy wirtualne, więc mamy tylko 14 lat, zanim te procesory osiągną limit 2 ⁶² bajtów przestrzeni adresowej.

A potem jest rozproszona pamięć współdzielona „gdzie (fizycznie oddzielne) wspomnienia można adresować jako jedną (logicznie współdzieloną) przestrzeń adresową”.

Czy uzasadnione jest założenie, że dowolna wielkość fizyczna może być reprezentowana przez 64-bitową liczbę całkowitą bez przepełnienia lub niedopełnienia?

Nie dokładnie. Istnieje wiele liczb, które są zarówno większe, jak i mniejsze od tego, dlatego mamy liczby zmiennoprzecinkowe. Liczby zmiennoprzecinkowe wymieniają mniejszą precyzję dla lepszego zasięgu.

W tym konkretnym przykładzie, który zacytowałeś, jest bardzo mało prawdopodobne, abyś kiedykolwiek potrzebował większej liczby. 64 bity odpowiadają około 18 kwintillionom elementów. Ale nigdy nie mów nigdy.

Twoje założenie nie obsługuje wielkości fizycznych, które mogą być reprezentowane tylko przez liczby zmiennoprzecinkowe. I nawet jeśli zdecydujesz się skalować wszystkie liczby, powiedzmy przez pomnożenie wszystkich liczb przez 10000 (więc wartości są wciąż liczbami całkowitymi, ale mogą być reprezentowane w dziesiętnych tysięcznych), ten schemat nadal zawodzi dla liczb bardzo bliskich zeru, na przykład masy elektronowej (9.1094 * 10⎻³¹ kg).

To bardzo realna (i bardzo mała) fizyczna ilość , oto kilka innych, z którymi będziesz miał problemy. A jeśli argumentujesz, że nie jest to rzeczywista ilość fizyczna (nawet w kg), rozważ:

10 kg (obviously physical quantity)
1 kg (same)
10⎻² kg (1/100 kg, or about 1/3 ounce) (also quite real)

Widzisz więc, dokąd idę z tym. Ostatni, z którym nie możesz sobie poradzić.

Oczywiście możesz mieć specjalne pole w obrębie liczby, aby przeskalować liczbę całkowitą w górę lub w dół o zmienny mnożnik; Kurde, właśnie wymyśliłeś zmiennoprzecinkowy.

Najpierw odpowiem na pytanie, jakie wartości fizyczne mogą / powinny być reprezentowane przez liczbę całkowitą?

Liczba całkowita jest reprezentacją liczby naturalnej (i różnic między nimi) w systemie komputerowym, więc zastosowanie jej do czegokolwiek innego jest błędne. Zatem przywoływanie odległości lub innych wielkości należących do domeny ciągłej nie jest argumentem. Dla takich ilości istnieją reprezentacje liczb rzeczywistych. I zawsze możesz wybrać arbiralnie dużą jednostkę i dopasować dowolną wartość z określoną precyzją.

Więc jakie są wartości fizyczne, które są liczbami naturalnymi i czy mogą przekroczyć 64-bitową liczbę całkowitą?

Mogę wymyślić dwa. Liczba obiektów fizycznych (takich jak atomy) i poziomy energii, w których może znajdować się układ kwantowy. Są to dwie rzeczy, które są ściśle liczbami całkowitymi. Wiem, że możesz rozdzielić atom, ale nadal wytwarza on liczbę całkowitą i nie możesz go rozdzielić w nieskończoność. Oba mogą z łatwością przekroczyć 64-bitowy zakres liczb całkowitych bez znaku . Liczba atomów jest wyższa, a jeden atom może znajdować się w więcej niż jednym stanie energetycznym.

To, czy informacje są fizyczne, czy nie, jest bardzo dyskusyjne. Powiedziałbym, że nie. Dlatego nie powiedziałbym, że ilość informacji to rzecz fizyczna. Więc nie jest ilość pamięci RAM ani nic takiego. Jeśli pozwolisz na to, łatwo liczba atomów przewyższa tę liczbę, ponieważ potrzebujesz więcej niż jednego atomu do przechowywania jednego bitu w dzisiejszej technologii.

Oprócz odpowiedzi Jerry101 chciałbym zaoferować ten bardzo prosty i praktyczny test poprawności:

Załóżmy, że przydzielasz trochę pamięci mallocw 64-bitowym systemie operacyjnym. Załóżmy, że alokator pamięci zdecyduje się zwrócić ci prawidłowy blok pamięci o żądanym rozmiarze, ale w którym ustawiony jest 63-ty bit.

Innymi słowy, załóżmy, że istnieją pewne środowiska programistyczne, w których 0xFFFFFFFFxxxxxxxxistnieją uzasadnione zakresy pamięci, które mogą zostać zwrócone z wywołania do malloc.

Pytanie brzmi, czy Twój kod nadal będzie działał zgodnie z przeznaczeniem?

Kiedy analogiczna sytuacja występuje w 32-bitowych systemach operacyjnych, niektóre programy nie działały poprawnie, jeśli otrzymały adresy pamięci „w górnej połowie”. Początkowo takie adresy pamięci były uważane za dostępne tylko dla uprzywilejowanego kodu (systemy operacyjne, sterowniki urządzeń i urządzenia peryferyjne), ale ze względu na 32-bitowe załamanie przestrzeni adresowej producenci systemów operacyjnych postanowili udostępnić część tej zarezerwowanej przestrzeni dla aplikacje, które o to proszą.

Na szczęście taka sytuacja jest mało prawdopodobna w przypadku programów 64-bitowych przez jakiś czas, a przynajmniej nie za dziesięć lat.

Kiedy taka sytuacja w końcu się wydarzy, oznacza to, że 128-bitowe adresowalne procesory i systemy operacyjne stałyby się w tym czasie głównym nurtem i że byłyby w stanie zapewnić „64-bitowe środowisko emulacji”, aby umożliwić działanie „starszych aplikacji” przy założeniach podobnych do dzisiejszych 64-bitowych systemów operacyjnych.

Na koniec zauważ, że ta dyskusja koncentruje się tylko na adresach pamięci. Podobny problem z znacznikami czasu należy podjąć z większą ostrożnością, ponieważ niektóre formaty znaczników czasu przydzielają wiele bitów precyzji na mikrosekundy, a zatem pozostawiają mniej bitów do reprezentowania czasu w przyszłości. Zagadnienia te zostały streszczone w artykule w Wikipedii dotyczącym problemu w roku 2038 .

To pytanie należy zadać indywidualnie dla każdego przypadku. Nie powinieneś przyjmować ogólnego założenia, że ​​arytmetyka 64-bitowa nie przepełni się, ponieważ nawet gdy prawidłowe ilości będą w znacznie mniejszym zakresie, złośliwe źródło danych może w końcu dać nieuzasadnione ilości, które mogą się przelać, i lepiej być przygotowani na tę sytuację, niż niespodziewanie ją dotknąć.

W niektórych przypadkach sensowne jest pisanie kodu, który zależy od braku przepełnienia liczb 64-bitowych. Główną klasą znanego mi przykładu są liczniki, w których licznik jest zwiększany za każdym razem, gdy jest używany. Nawet w tempie jednego przyrostu na nanosekundę (niepraktyczne) przepełnienie zajęłoby ponad sto lat.

Zauważ, że chociaż początkowo może wydawać się „zawsze błędne” poleganie na „czasie do awarii” dla poprawności systemu, robimy to cały czas z uwierzytelnianiem / logowaniem. Biorąc pod uwagę wystarczającą ilość czasu (na brutalne wymuszenie), każdy taki system (oparty na hasłach, kluczach prywatnych, tokenach sesji itp.) Jest zepsuty.

Czy MOŻLIWE jest, aby wielkość fizyczna nie pasowała do 64 bitów? Oczywiście. Inni wskazali liczenie atomów na słońcu lub milimetrów do następnej galaktyki. To, czy takie przypadki są istotne dla twojego wniosku, zależy od tego, co to jest. Jeśli liczysz liczbę przedmiotów w dowolnym pojemniku w magazynie, 16 bitów prawdopodobnie wystarczy. Jeśli opracowujesz statystyki dotyczące liczby osób na świecie spełniających różne warunki, musisz być w stanie zarejestrować miliardy, więc będziesz potrzebować więcej niż 32 bity, w tym momencie prawdopodobnie powinieneś mieć 64 (jak mało komputerów mają wbudowaną obsługę 37-bitowych liczb itp.). Jeśli jest to aplikacja chemiczna, która liczy atomy o wartości moli, 64 bity nie będą wystarczające.

Technicznie to, że żaden komputer nie ma dziś 2 ^ 64 bajtów pamięci, niekoniecznie oznacza, że ​​indeks tablicy nigdy nie może być większy niż 2 ^ 64. Istnieje koncepcja zwana „rzadką tablicą”, w której wiele elementów tablicy nie jest nigdzie fizycznie przechowywanych, i zakłada się, że takie niezapisane wartości mają pewną wartość domyślną, np. Zero lub zero. Ale przypuszczam, że jeśli piszesz funkcję do przeszukiwania tablicy lub jakiejś listy, a wielkość pola, którego używasz do przechowywania indeksu w tablicy, jest ponad dwukrotnie większa niż możliwy adres, to sprawdzanie przepełnienia, gdy dodanie dwóch indeksów nie byłoby absolutnie konieczne.

Nieuzasadnione jest założenie, że 64-bitowa liczba całkowita może pomieścić wszystkie liczby. Wiele powodów:

1. Maksymalna i minimalna liczba całkowita 64-bitowa są liczbami skończonymi. Dla każdej liczby skończonej istnieje coraz większa liczba skończona.

2. Obliczenia z liczbami 128-bitowymi i 256-bitowymi są obecnie używane w różnych miejscach. Wiele procesorów ma określone instrukcje, które działają na 128-bitowych liczbach całkowitych.

3. 20 lat temu dysk o pojemności 1 GB został uznany za „duży”. Dzisiaj dysk o pojemności 1 TB jest uważany za mały. 20 lat temu przeciętne komputery stacjonarne miały około 16 MB pamięci RAM. Mój obecny pulpit ma ponad 16 GB pamięci RAM. Przestrzeń dyskowa i pamięć RAM wzrosły wykładniczo w przeszłości i przewiduje się, że w przyszłości będą rosły wykładniczo. Jeśli ktoś nie wymyśli dobrego powodu, dla którego powinien przestać rosnąć, nie ma sensu zakładać, że przestanie rosnąć.