Dlaczego liczby dziesiętne nie mogą być przedstawione dokładnie w postaci binarnej?

284

Wysłano do SO kilka pytań dotyczących reprezentacji zmiennoprzecinkowej. Na przykład liczba dziesiętna 0,1 nie ma dokładnej reprezentacji binarnej, więc użycie operatora == w celu porównania jej z inną liczbą zmiennoprzecinkową jest niebezpieczne. Rozumiem zasady reprezentacji zmiennoprzecinkowej.

Nie rozumiem, dlaczego, z matematycznego punktu widzenia, liczby po prawej stronie przecinka są już bardziej „specjalne” niż te po lewej?

Na przykład liczba 61.0 ma dokładną reprezentację binarną, ponieważ integralna część dowolnej liczby jest zawsze dokładna. Ale liczba 6.10 nie jest dokładna. Wszystko, co zrobiłem, to przesunięcie dziesiętnego o jedno miejsce i nagle przeszedłem z Exactopia do Inexactville. Matematycznie nie powinno być żadnej istotnej różnicy między tymi dwiema liczbami - to tylko liczby.

Dla kontrastu, jeśli przesunę miejsce po przecinku o jedno miejsce w drugim kierunku, aby uzyskać liczbę 610, nadal będę w stanie Exactopia. Mogę iść w tym kierunku (6100, 610000000, 610000000000000) i nadal są dokładne, dokładne, dokładne. Ale gdy tylko liczba dziesiętna przekroczy pewien próg, liczby nie są już dokładne.

Co się dzieje?

Edycja: aby wyjaśnić, chcę trzymać się z dala od dyskusji na temat standardowych reprezentacji branżowych, takich jak IEEE, i trzymać się tego, co uważam za matematycznie „czysty” sposób. W podstawie 10 wartościami pozycyjnymi są:

... 1000  100   10    1   1/10  1/100 ...

W systemie dwójkowym byłyby to:

... 8    4    2    1    1/2  1/4  1/8 ...

Nie ma także żadnych arbitralnych ograniczeń dotyczących tych liczb. Pozycje zwiększają się w nieskończoność w lewo i w prawo.

Barry Brown
źródło
2
Pomocne może być dokładne zrozumienie, co dzieje się wewnątrz nubmberu zmiennoprzecinkowego: anatomia liczby zmiennoprzecinkowej .
John D. Cook,
57
Binarnie liczba 3 jest reprezentowana jako 2¹ + 2 ° = 2 + 1. Miło i łatwo. Teraz spójrz na 1/3. Jak byś to reprezentował, używając ujemnych mocy 2? Poeksperymentuj trochę, a zobaczysz, że 1/3 równa się sumie nieskończonej sekwencji 2 ^ -2 + 2 ^ -4 + 2 ^ -6 + 2 ^ -8 + ..., tj. nie tak łatwo przedstawić dokładnie w formacie binarnym.
Lars Haugseth,
21
Jon Skeet bardzo dobrze odpowiada na pytanie w twoim ciele. Brakuje tylko jednej rzeczy: zadajesz dwa różne pytania. Tytułowe pytanie brzmi: „dlaczego liczby dziesiętne nie mogą być dokładnie przedstawione w postaci binarnej?” Odpowiedź brzmi: mogą być. Pomiędzy swoim tytułem a ciałem łączysz ideę „binarną” z ideą „reprezentacji zmiennoprzecinkowej”. Zmienny punkt to sposób wyrażania liczb dziesiętnych za pomocą stałej liczby cyfr binarnych kosztem precyzji. Binarny jest tylko inną podstawą do zliczania i może wyrażać dowolną liczbę dziesiętną, biorąc pod uwagę nieskończoną liczbę cyfr.
Chris Blackwell,
3
Istnieje kilka systemów, które mają dokładną reprezentację dziesiętną. Działa prawie tak, jak opisujesz. Typ dziesiętny SQL jest jednym z przykładów. Ma wbudowane języki LISP. Istnieje kilka komercyjnych i otwartych bibliotek do korzystania z dokładnych obliczeń dziesiętnych. Po prostu nie ma wsparcia sprzętowego, a większość języków i sprzętu implementuje standardy IEEE do reprezentowania nieskończonej liczby liczb w 32 lub 64 bitach.
nos
1
To pytanie wydaje się być nie na temat, ponieważ dotyczy matematyki (nawet jeśli dotyczy matematyki związanej z programowaniem) i byłoby lepiej na matematyce
Cole Johnson

Odpowiedzi:

360

Liczby dziesiętne mogą być dokładnie reprezentowane, jeśli masz wystarczająco dużo miejsca - tylko nie zmiennoprzecinkowe liczby binarne . Jeśli używasz zmiennoprzecinkowego typu dziesiętnego (np. System.DecimalW .NET), wówczas można dokładnie przedstawić wiele wartości, których nie można dokładnie przedstawić w binarnym zmiennoprzecinkowym.

Spójrzmy na to z innej strony - w bazie 10, z którą prawdopodobnie będziesz czuć się komfortowo, nie możesz dokładnie wyrazić 1/3. To 0.3333333 ... (cykliczne). Powód, dla którego nie możesz reprezentować 0,1 jako binarnej liczby zmiennoprzecinkowej, jest dokładnie z tego samego powodu. Możesz dokładnie przedstawić 3, 9 i 27 - ale nie 1/3, 1/9 lub 1/27.

Problem polega na tym, że liczba 3 jest liczbą pierwszą, która nie jest dziesięciokrotna. Nie jest to problemem, gdy chcesz pomnożyć liczbę przez 3: zawsze możesz pomnożyć liczbę całkowitą bez żadnych problemów. Ale kiedy dzielisz przez liczbę pierwszą, która nie jest czynnikiem twojej bazy, możesz wpaść w kłopoty (i będzie to zrobić, jeśli starają się podzielić 1 przez tego numeru).

Chociaż 0,1 jest zwykle używany jako najprostszy przykład dokładnej liczby dziesiętnej, której nie można dokładnie przedstawić w binarnym zmiennoprzecinkowym, prawdopodobnie 0,2 jest prostszym przykładem, ponieważ wynosi 1/5 - a 5 jest liczbą pierwszą, która powoduje problemy między dziesiętną a binarną .


Uwaga dodatkowa dotycząca problemu reprezentacji skończonych:

Niektóre zmiennoprzecinkowe typy dziesiętne mają ustalony rozmiar, podobnie jak System.Decimalinne, java.math.BigDecimalsą „dowolnie duże” - ale w pewnym momencie przekroczą limit, czy to pamięć systemowa, czy teoretyczny maksymalny rozmiar tablicy. Jest to jednak zupełnie odrębny punkt od głównej tej odpowiedzi. Nawet jeśli miałbyś naprawdę dużą liczbę bitów do zabawy, nadal nie mógłbyś przedstawić dziesiętnej 0,1 dokładnie w postaci zmiennoprzecinkowej binarnej. Porównaj to z odwrót: podana dowolna liczba cyfr po przecinku, to może dokładnie reprezentować dowolną liczbę, która jest dokładnie to, przedstawianego jako zmiennoprzecinkowych binarnym.

Jon Skeet
źródło
8
To cholernie dobry przykład!
Tom Ritter,
5
... żałuję, że nie mogłem tego dwukrotnie głosować. Pytano mnie o to całkowicie zbyt wiele razy. To prawie tak, jakby ludzie nie mogli myśleć poza bazą 10. hehe
Justin Niessner
38
Tak, na świecie jest 10 rodzajów ludzi - tych, którzy rozumieją binarny i tych, którzy nie rozumieją.
duffymo
83
@JonSkeet: Ctrl + Alt + Delete wyglądałby niewygodnie z dwoma palcami.
Lars Haugseth,
20
@muusbolla: Nie. Liczby reprezentowane przez reprezentację dziesiętną 1i reprezentację dziesiętną 0.9...(nieskończenie powtarzające się 9s po przecinku) są równe. Być może najłatwiejszym sposobem na sprawdzenie tego jest: Niech x = 0.9.... Zauważ, że 10x = 9.9..... Dlatego 9x = 10x - x = 9.9... - 0.9... = 9tak 9x = 9i x = 1. Są inne sposoby, aby to zobaczyć, ale uważam, że jest to najprostsze.
jason
25

Na przykład liczba 61.0 ma dokładną reprezentację binarną, ponieważ integralna część dowolnej liczby jest zawsze dokładna. Ale liczba 6.10 nie jest dokładna. Wszystko, co zrobiłem, to przesunięcie dziesiętnego o jedno miejsce i nagle przeszedłem z Exactopia do Inexactville. Matematycznie nie powinno być żadnej istotnej różnicy między tymi dwiema liczbami - to tylko liczby .

Odsuńmy się na chwilę od szczegółów baz 10 i 2. Zapytajmy - w bazie b , jakie liczby mają reprezentacje kończące, a które nie? Chwila namysłu mówi nam, że liczba xma bkońcową reprezentację wtedy i tylko wtedy, gdy istnieje liczba całkowita ntaka, żex b^n jest liczbą całkowitą.

Na przykład x = 11/500 ma kończącą się reprezentację 10, ponieważ możemy wybrać, n = 3a następnie x b^n = 22liczbę całkowitą. Jednak x = 1/3nie, ponieważ cokolwiekn wybierzemy, nie będziemy w stanie pozbyć się 3.

Ten drugi przykład skłania nas do zastanowienia się nad czynnikami i widzimy, że dla każdego racjonalnego x = p/q (zakładanego w najniższych kategoriach) możemy odpowiedzieć na pytanie, porównując podstawowe czynniki bi q. Jeśli qjakieś czynniki pierwsze nie zostaną uwzględnione w pierwszej kolejności b, nigdy nie będziemy w stanie znaleźć odpowiedniegon aby pozbyć się tych czynników.

Tak więc, na podstawie 10, każdy p/q gdzieq czynniki pierwsze są inne niż 2 lub 5, nie będą miały reprezentacji końcowej.

Wracając teraz do baz 10 i 2, widzimy, że wszelkie racjonalne z kończącą się reprezentacją 10 będą miały postać p/qdokładnie wtedy, gdyq dopiero 2y i 5y w swoim prime Faktoryzacji; i ta sama liczba będzie miała kończącą się reprezentację 2 dokładnie wtedy, gdy qma tylko2 swoje pierwsze rozkładanie na czynniki pierwsze.

Ale jeden z tych przypadków jest podzbiorem drugiego! Kiedy tylko

q ma jedynie 2 swoją pierwszą faktoryzację

oczywiście jest również prawdą

q ma jedynie 2 si 5w swojej pierwotnej faktoryzacji

lub, inaczej mówiąc, ilekroć p/qma końcową reprezentację 2, p/qma końcową reprezentację 10 . Odwrotna jednak ma nie posiadać - gdy qma 5 w swoim prime faktoryzacji, będzie to miało kończącą 10-reprezentacji, ale nie do kończącego 2-reprezentacji. To 0.1przykład wymieniony w innych odpowiedziach.

Mamy więc odpowiedź na twoje pytanie - ponieważ czynniki pierwsze 2 są podzbiorem czynników pierwszych 10, wszystkie liczby kończące 2 są liczbami kończącymi 10, ale nie odwrotnie. Nie chodzi o 61 w porównaniu z 6.1 - to około 10 w porównaniu z 2.

Jako notatkę zamknięcia, jeśli przez niektórych ludzi dziwactwo używane (powiedzmy) podstawy 17, ale nasze komputery używane baza 5, twoja intuicja nigdy nie został uwiedziony przez to - nie byłoby żadne (niezerowe, non-integer) Liczby, które zakończone w obu przypadkach!

AakashM
źródło
Dlaczego więc „alert (0,15 * 0,15)” wyświetla „0,0225”?
Michael Geiser
5
@MichaelGeiser krótka odpowiedź: zaokrąglenie w punkcie wyświetlania. To, co Twoim zdaniem jest, 0.15to tak naprawdę (gdy jest przechowywane jako podwójne IEEE) `0.149999999999999994448884876874`. Zobacz jsfiddle .
AakashM
Niezły przykład kodu punktowego! Chciałbym dać ci na to głos! Muszę grać z kilkoma funkcjami, aby zbadać, gdzie następuje odcięcie zaokrąglenia. Nadal jestem zaskoczony, że tak naprawdę mamy do czynienia z tymi śmieciami; ponieważ ludzie pracują w dziesiątce prawie 100% czasu, a my używamy liczb całkowitych tak często, że można by pomyśleć, że domyślna implementacja matematyki zmiennoprzecinkowej poradziłaby sobie z tym nonsensem.
Michael Geiser
1
@MichaelGeiser obwody do pracy z bazą 2 są mniejsze, szybsze i bardziej energooszczędne niż te do pracy z bazą 10. Dzisiaj możemy być w stanie uzasadnić koszty ogólne, ale w latach 70., kiedy ustalano standardy, było to Wielka rzecz. Próba zrobienia tego bez bezpośredniego wsparcia obwodów procesora jest jeszcze gorsza, spodziewaj się rzędów różnic wielkości prędkości.
Mark Ransom
Ta odpowiedź wyjaśnia lepiej niż sam Jon Skeet!
Goelakash
16

Podstawowym (matematycznym) powodem jest to, że gdy mamy do czynienia z liczbami całkowitymi, są one w nieskończoność nieskończone .

Co oznacza, że ​​chociaż jest ich nieskończona ilość, moglibyśmy „zliczyć” wszystkie elementy w sekwencji, nie pomijając żadnego. Oznacza to, że jeśli chcemy uzyskać pozycję na 610000000000000tej pozycji na liście, możemy to ustalić za pomocą formuły.

Jednak liczby rzeczywiste są niepoliczalnie nieskończone . Nie możesz powiedzieć „daj mi prawdziwą liczbę na stanowisku 610000000000000” i uzyskaj odpowiedź. Powodem jest to, że nawet pomiędzy 0i 1istnieje nieskończona liczba wartości, gdy rozważasz wartości zmiennoprzecinkowe. To samo dotyczy dwóch dowolnych liczb zmiennoprzecinkowych.

Więcej informacji:

http://en.wikipedia.org/wiki/Countable_set

http://en.wikipedia.org/wiki/Uncountable_set

Aktualizacja: przepraszam, chyba źle zinterpretowałem pytanie. Moja odpowiedź dotyczy tego, dlaczego nie możemy przedstawić każdej rzeczywistej wartości, nie zdawałem sobie sprawy, że zmiennoprzecinkowy jest automatycznie klasyfikowany jako racjonalny.

TM.
źródło
6
W rzeczywistości liczby wymierne są w nieskończoność nieskończone. Ale nie każda liczba rzeczywista jest liczbą wymierną. Mogę z pewnością wygenerować ciąg dokładnych liczb dziesiętnych, które w końcu osiągną dowolną liczbę dziesiętną, którą chcesz mi podać. Jeśli musisz poradzić sobie również z liczbami nieracjonalnymi , dostaniesz się do niezliczonych zestawów nieskończonych.
Jon Skeet
To prawda, powinienem powiedzieć „prawdziwy”, a nie „zmiennoprzecinkowy”. Wyjaśni.
TM.
1
W tym momencie logika staje się mniej przydatna, IMO - ponieważ nie tylko nie możemy poradzić sobie ze wszystkimi liczbami rzeczywistymi za pomocą binarnych liczb zmiennoprzecinkowych, ale nie możemy nawet poradzić sobie ze wszystkimi liczbami wymiernymi (np. 0,1). Innymi słowy, nie sądzę, żeby miało to w ogóle związek z policzalnością :)
Jon Skeet
@jonskeet Wiem, że nie zgadzanie się z Jonem Skeetem złamałoby fundamentalne prawo natury, więc oczywiście tego nie zrobię :) Myślę jednak, że dobrze jest myśleć o wewnętrznej reprezentacji liczb jako wskaźnikach zestaw wartości, które chcesz reprezentować zewnętrznie. Przy takim sposobie myślenia możesz zauważyć, że bez względu na to, jak duża jest twoja lista indeksów (nawet gdybyś powiedział, nieskończone szczegóły), nadal nie byłbyś w stanie przedstawić wszystkich liczb rzeczywistych.
TM.
3
@TM: Ale OP nie próbuje reprezentować wszystkich liczb rzeczywistych. Próbuje przedstawić wszystkie dokładne liczby dziesiętne , które są podzbiorem liczb wymiernych , a zatem są nieskończenie liczone. Gdyby używał nieskończonego zestawu bitów jako dziesiętnego typu zmiennoprzecinkowego, nic by się nie stało . Wykorzystuje te bity jako binarny typ zmiennoprzecinkowy, który powoduje problemy z liczbami dziesiętnymi.
Jon Skeet
10

Powtórzyć to, co powiedziałem w moim komentarzu do pana Skeet: my może reprezentować 1/3, 1/9, 1/27, lub jakikolwiek racjonalny w notacji dziesiętnej. Robimy to, dodając dodatkowy symbol. Na przykład wiersz nad cyframi, które powtarzają się w dziesiętnym rozszerzeniu liczby. To, czego potrzebujemy do przedstawienia liczb dziesiętnych jako sekwencji liczb binarnych, to 1) sekwencja liczb binarnych, 2) punkt podstawy i 3) jakiś inny symbol wskazujący powtarzającą się część sekwencji.

Notacja cytatowa Hehnera jest na to sposobem. Używa symbolu cytatu do reprezentowania powtarzającej się części sekwencji. Artykuł: http://www.cs.toronto.edu/~hehner/ratno.pdf oraz wpis w Wikipedii: http://en.wikipedia.org/wiki/Quote_notation .

Nic nie mówi o tym, że nie możemy dodać symbolu do naszego systemu reprezentacji, więc możemy reprezentować liczby dziesiętne dokładnie za pomocą binarnej notacji cudzysłowów i odwrotnie.

ntownsend
źródło
Ten system notacji działa, jeśli wiemy, gdzie zaczyna się i kończy cykl. Ludzie są całkiem dobrzy w wykrywaniu cykli. Ale generalnie komputery nie są. Aby móc efektywnie korzystać z symbolu powtórzeń, komputer musiałby być w stanie dowiedzieć się, gdzie są cykle po wykonaniu obliczeń. Na przykład dla liczby 1/3 cykl rozpoczyna się od razu. Ale dla liczby 1/97 cykl nie pokazuje się, dopóki nie wypracujesz odpowiedzi na co najmniej 96 cyfr. (Właściwie potrzebujesz 96 * 2 + 1 = 193 cyfr, aby się upewnić.)
Barry Brown
4
W rzeczywistości komputer nie jest wcale trudny do wykrycia cyklu. Jeśli czytasz artykuł Hehnera, opisuje on, jak wykrywać cykle dla różnych operacji arytmetycznych. Na przykład w algorytmie podziału, który wykorzystuje powtarzane odejmowanie, wiesz, gdzie zaczyna się cykl, gdy zobaczysz różnicę, którą widziałeś wcześniej.
ntownsend
3
Pytanie dotyczyło również dokładnego przedstawienia liczb. Czasami dokładna reprezentacja oznacza wiele bitów. Piękno notowania cytatów polega na tym, że Hehner pokazuje, że średnio o 31% oszczędności w zakresie reprezentacji w porównaniu do standardowej 32-bitowej reprezentacji o stałej długości.
ntownsend
6

BCD - binarnie dziesiętny - reprezentacje są dokładne. Nie zajmują dużo miejsca, ale jest to kompromis, który musisz wykonać w celu uzyskania dokładności w tym przypadku.

Alan
źródło
1
BCD nie są mniej lub bardziej dokładne niż jakakolwiek inna baza. Przykład: jak dokładnie reprezentujesz 1/3 w BCD? Nie możesz
Jörg W Mittag
12
BCD jest dokładnym odwzorowaniem DECIMAL, a więc „um” części jego nazwy. Nie ma też dokładnej reprezentacji dziesiętnej 1/3.
Alan
4

Jest to ten sam powód, dla którego nie możesz reprezentować 1/3 dokładnie w bazie 10, musisz powiedzieć 0.33333 (3). W systemie binarnym jest to ten sam typ problemu, ale występuje tylko dla innego zestawu liczb.

James
źródło
4

(Uwaga: dołączę „b”, aby wskazać tutaj liczby binarne. Wszystkie pozostałe liczby są podawane dziesiętnie)

Jednym ze sposobów myślenia o różnych rzeczach jest zapis naukowy. Przyzwyczailiśmy się widzieć liczby wyrażone w notacji naukowej, np. 6.022141 * 10 ^ 23. Liczby zmiennoprzecinkowe są przechowywane wewnętrznie w podobnym formacie - mantysa i wykładnik, ale przy użyciu potęg dwóch zamiast dziesięciu.

Twoje 61.0 może zostać przepisane jako 1.90625 * 2 ^ 5 lub 1.11101b * 2 ^ 101b z mantysą i wykładnikami potęgi. Aby pomnożyć to przez dziesięć i (przesunąć przecinek dziesiętny), możemy:

(1,90625 * 2 ^ 5) * (1,25 * 2 ^ 3) = (2,3828125 * 2 ^ 8) = (1,19140625 * 2 ^ 9)

lub z mantysą i wykładnikami w formacie binarnym:

(1,11101b * 2 ^ 101b) * (1,01b * 2 ^ 11b) = (10,0110001b * 2 ^ 1000b) = (1,00110001b * 2 ^ 1001b)

Zwróć uwagę na to, co zrobiliśmy, aby pomnożyć liczby. Pomnożymy mantysy i dodamy wykładniki. Następnie, ponieważ mantysa zakończyła się na więcej niż dwa, znormalizowaliśmy wynik, podnosząc wykładnik potęgi. To tak, jakbyśmy korygowali wykładnik po wykonaniu operacji na liczbach w dziesiętnej notacji naukowej. W każdym przypadku wartości, z którymi pracowaliśmy, miały skończoną reprezentację w formacie binarnym, a zatem wartości generowane przez podstawowe operacje mnożenia i dodawania również generowały wartości o skończonej reprezentacji.

Zastanówmy się teraz, jak podzielimy 61 przez 10. Zaczniemy od podzielenia mantysy, 1.90625 i 1.25. W ułamku dziesiętnym daje to 1,525 ładną krótką liczbę. Ale co to jest, jeśli przekonwertujemy go na binarny? Zrobimy to w zwykły sposób - odejmując największą możliwą potęgę dwóch, gdy tylko jest to możliwe, podobnie jak przekształcanie liczb całkowitych dziesiętnych na binarne, ale użyjemy ujemnych potęg dwóch:

1,525 - 1 * 2 ^ 0 -> 1
0,525 - 1 * 2 ^ -1 -> 1
0,025 - 0 * 2 ^ -2 -> 0
0,025 - 0 * 2 ^ -3 -> 0
0,025 - 0 * 2 ^ -4 -> 0
0,025 - 0 * 2 ^ -5 -> 0
0,025 - 1 * 2 ^ -6 -> 1
0,009375 - 1 * 2 ^ -7 -> 1
0,0015625 - 0 * 2 ^ -8 -> 0
0,0015625 - 0 * 2 ^ -9 -> 0
0,0015625 - 1 * 2 ^ -10 -> 1
0,0005859375 - 1 * 2 ^ -11 -> 1
0,00009765625 ...

O o. Teraz mamy kłopoty. Okazuje się, że 1,90625 / 1,25 = 1,525, jest ułamkiem powtarzalnym wyrażonym binarnie: 1.11101b / 1.01b = 1.10000110011 ... b Nasze maszyny mają tylko tyle bitów, aby utrzymać tę mantysę, więc zaokrągli ułamek i zakładamy zera powyżej pewnego punktu. Błąd, który widzisz, dzieląc 61 przez 10, jest różnicą między:

1.100001100110011001100110011001100110011 ... b * 2 ^ 10b
i, powiedzmy:
1.100001100110011001100110b * 2 ^ 10b

To zaokrąglenie mantysy prowadzi do utraty precyzji, którą kojarzymy z wartościami zmiennoprzecinkowymi. Nawet jeśli mantysę można wyrazić dokładnie (np. Po prostu dodając dwie liczby), nadal możemy uzyskać utratę liczbową, jeśli mantysa potrzebuje zbyt wielu cyfr, aby zmieścić się po normalizowaniu wykładnika.

W rzeczywistości robimy takie rzeczy przez cały czas, gdy zaokrąglamy liczby dziesiętne do rozsądnego rozmiaru i po prostu podajemy kilka pierwszych cyfr. Ponieważ wynik wyrażamy w postaci dziesiętnej, wydaje się to naturalne. Ale jeśli zaokrąglimy liczbę dziesiętną, a następnie przekonwertujemy ją na inną podstawę, wyglądałby tak samo brzydko, jak liczby dziesiętne, które otrzymujemy z powodu zaokrąglania zmiennoprzecinkowego.

Boojum
źródło
4

To dobre pytanie.

Całe twoje pytanie dotyczy „w jaki sposób reprezentujemy liczbę?”

WSZYSTKIE liczby mogą być reprezentowane w postaci dziesiętnej lub binarnej (uzupełnienie 2). Wszyscy !!

ALE niektóre (większość z nich) wymagają nieskończonej liczby elementów („0” lub „1” dla pozycji binarnej lub „0”, „1” do „9” dla reprezentacji dziesiętnej).

Jak 1/3 w postaci dziesiętnej (1/3 = 0,33333333 ... <- z nieskończoną liczbą „3”)

Jak 0,1 w systemie binarnym (0,1 = 0,00011001100110011 .... <- z nieskończoną liczbą „0011”)

Wszystko jest w tej koncepcji. Ponieważ twój komputer może brać pod uwagę tylko skończony zestaw cyfr (dziesiętny lub binarny), tylko niektóre liczby mogą być dokładnie reprezentowane na twoim komputerze ...

I jak powiedział Jon, 3 jest liczbą pierwszą, która nie jest 10-krotna, więc 1/3 nie może być reprezentowana skończoną liczbą liczbę elementów w podstawie 10.

Nawet z arytmetyką z dowolną precyzją system pozycji numeracji w podstawie 2 nie jest w stanie w pełni opisać 6.1, chociaż może reprezentować 61.

W wersji 6.1 musimy użyć innej reprezentacji (jak reprezentacja dziesiętna lub IEEE 854, która zezwala na bazę 2 lub bazę 10 na reprezentację wartości zmiennoprzecinkowych)

ThibThib
źródło
Możesz reprezentować 1/3 jako samą frakcję. Nie potrzebujesz nieskończonej ilości bitów, aby to przedstawić. Po prostu reprezentujesz go jako ułamek 1/3, zamiast wyniku biorąc 1 i dzieląc go przez 3. Kilka systemów działa w ten sposób. Potrzebny jest wtedy sposób użycia standardowego / * + i podobnych operatorów do pracy z reprezentacją ułamków, ale to całkiem proste - możesz wykonywać te operacje za pomocą pióra i papieru, uczenie komputera, jak to robić, nie jest niczym wielkim .
nos
Mówiłem o „reprezentacji binarnej (uzupełnienie 2)”. Ponieważ, oczywiście, użycie innej reprezentacji może pomóc ci reprezentować pewną liczbę ze skończoną liczbą elementów (i będziesz potrzebować nieskończoną liczbę elementów dla niektórych innych)
ThibThib
3

Jeśli zrobisz wystarczająco dużą liczbę z liczbą zmiennoprzecinkową (ponieważ może to robić wykładniki), to skończysz z niedokładnością przed kropką dziesiętną. Nie sądzę więc, aby twoje pytanie było całkowicie uzasadnione, ponieważ przesłanka jest błędna; nie jest tak, że przesunięcie o 10 zawsze spowoduje większą precyzję, ponieważ w pewnym momencie liczba zmiennoprzecinkowa będzie musiała użyć wykładników wykładniczych do reprezentowania dużej liczby i również straci pewną precyzję w ten sposób.

Dan Lew
źródło
3

Dziwi mnie, że nikt tego jeszcze nie powiedział: używaj ciągłych frakcji . Każda liczba wymierna może być w ten sposób skończona reprezentowana binarnie.

Kilka przykładów:

1/3 (0,3333 ...)

0; 3

5/9 (0,5555 ...)

0; 1, 1, 4

10/43 (0.232558139534883720930 ...)

0; 4, 3, 3

9093/18478 (0,49209871198181621387596060179673 ...)

0; 2, 31, 7, 8, 5

Stąd istnieje wiele znanych sposobów przechowywania sekwencji liczb całkowitych w pamięci.

Oprócz przechowywania liczby z idealną dokładnością, ciągłe ułamki mają również inne zalety, takie jak najlepsze racjonalne przybliżenie. Jeśli zdecydujesz się wcześniej zakończyć sekwencję liczb w ciągłym ułamku, pozostałe cyfry (po połączeniu w ułamek) dadzą najlepszą możliwą ułamek. W ten sposób można znaleźć przybliżenia liczby pi:

Ciągła frakcja Pi:

3; 7, 15, 1, 292 ...

Kończąc sekwencję na 1, daje to ułamek:

355/113

co jest doskonałym racjonalnym przybliżeniem.

Nacięcie
źródło
Ale jak przedstawiłbyś to w formacie binarnym? Na przykład 15 wymaga przedstawienia 4 bitów, ale 292 wymaga 9. Skąd sprzęt (a nawet oprogramowanie) wie, gdzie są granice bitów między nimi? Jest to kompromis między wydajnością a dokładnością.
żarliwy
2

W równaniu

2^x = y ;  
x = log(y) / log(2)

Dlatego zastanawiałem się, czy moglibyśmy mieć logarytmiczny system bazowy dla binarnych, takich jak,

 2^1, 2^0, 2^(log(1/2) / log(2)), 2^(log(1/4) / log(2)), 2^(log(1/8) / log(2)),2^(log(1/16) / log(2)) ........

To może rozwiązać problem, więc jeśli chcesz napisać coś takiego jak 32.41 w wersji binarnej, byłoby to możliwe

2^5 + 2^(log(0.4) / log(2)) + 2^(log(0.01) / log(2))

Lub

2^5 + 2^(log(0.41) / log(2))
rachit_verma
źródło
1

Problem polega na tym, że tak naprawdę nie wiesz, czy liczba faktycznie wynosi dokładnie 61,0. Rozważ to:


float a = 60;
float b = 0.1;
float c = a + b * 10;

Jaka jest wartość c? Nie jest to dokładnie 61, ponieważ b nie jest tak naprawdę .1, ponieważ .1 nie ma dokładnej reprezentacji binarnej.

Dima
źródło
1

Istnieje próg, ponieważ znaczenie cyfry zmieniło się z liczby całkowitej na liczbę całkowitą. Aby przedstawić 61, masz 6 * 10 ^ 1 + 1 * 10 ^ 0; 10 ^ 1 i 10 ^ 0 są liczbami całkowitymi. 6.1 to 6 * 10 ^ 0 + 1 * 10 ^ -1, ale 10 ^ -1 to 1/10, co zdecydowanie nie jest liczbą całkowitą. Tak trafiasz do Inexactville.

Mark Ransom
źródło
1

Paralelę można utworzyć z ułamków i liczb całkowitych. Niektóre ułamki, np. 1/7, nie mogą być reprezentowane w postaci dziesiętnej bez partii i partii dziesiętnych. Ponieważ zmiennoprzecinkowy jest oparty na binarnych przypadkach, specjalne przypadki zmieniają się, ale pojawiają się te same problemy z dokładnością.

poseł.
źródło
0

Istnieje nieskończona liczba liczb wymiernych i skończona liczba bitów, za pomocą których można je reprezentować. Zobacz http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems .

zpasternack
źródło
Ale nawet przy nieskończonej liczbie bitów, jeśli użyjesz zmiennoprzecinkowego punktu binarnego , nadal nie będziesz w stanie dokładnie przedstawić 0,1, tak jak nie możesz reprezentować 1/3 dokładnie dziesiętnie, nawet przy nieskończonej liczbie bitów.
Jon Skeet
3
@Jon To nieprawda: przy nieskończonej liczbie miejsc po przecinku mogę na przykład wyrazić dokładnie jedną trzecią . Problemem w świecie rzeczywistym jest to, że fizycznie niemożliwe jest posiadanie „nieskończonej liczby” miejsc po przecinku lub bitów.
ChrisW,
0

Liczba 61.0 rzeczywiście ma dokładną operację zmiennoprzecinkową - ale nie jest to prawdą dla wszystkich liczb całkowitych. Jeśli napisałeś pętlę, która dodała jedną do liczby zmiennoprzecinkowej podwójnej precyzji i 64-bitowej liczby całkowitej, w końcu osiągnąłbyś punkt, w którym 64-bitowa liczba całkowita doskonale reprezentuje liczbę, ale liczba zmiennoprzecinkowa nie… ponieważ nie ma wystarczającej ilości znaczących bitów.

O wiele łatwiej jest dotrzeć do punktu przybliżenia po prawej stronie przecinka dziesiętnego. Gdybyś zaczął zapisywać wszystkie liczby w binarnym zmiennoprzecinkowym, miałoby to większy sens.

Innym sposobem myślenia o tym jest to, że gdy zauważysz, że 61,0 jest doskonale reprezentowalne w podstawie 10, a przesunięcie punktu dziesiętnego wokoło tego nie zmieni, to wykonujesz mnożenie przez potęgi dziesięciu (10 ^ 1, 10 ^ -1 ). W zmiennoprzecinkowym pomnożenie przez potęgę dwóch nie wpływa na dokładność liczby. Spróbuj wziąć 61,0 i wielokrotnie dzieląc go przez trzy, aby zilustrować, jak idealnie precyzyjna liczba może utracić swoją dokładną reprezentację.

John Calsbeek
źródło
0

znasz liczby całkowite, prawda? każdy bit reprezentuje 2 ^ n


2 ^ 4 = 16
2 ^ 3 = 8
2 ^ 2 = 4
2 ^ 1 = 2
2 ^ 0 = 1

cóż, to samo dla zmiennoprzecinkowego (z pewnymi różnicami), ale bity reprezentują 2 ^ -n 2 ^ -1 = 1/2 = 0,5
2 ^ -2 = 1 / (2 * 2) = 0,25
2 ^ -3 = 0,125
2 ^ -4 = 0,0625

Reprezentacja binarna zmiennoprzecinkowa:

znak Ułamek wykładniczy (myślę, że niewidoczny 1 jest dołączony do ułamka)
B11 B10 B9 B8 B7 B6 B5 B4 B3 B2 B1 B0

yan bellavance
źródło
0

Wyżej wymieniona odpowiedź o wysokiej punktacji przybiła ją.

Najpierw miksowałeś bazę 2 i bazę 10 w swoim pytaniu, a następnie, gdy umieścisz liczbę po prawej stronie, która nie jest podzielna na bazę, masz problemy. Jak 1/3 w systemie dziesiętnym, ponieważ 3 nie wchodzi w potęgę 10 lub 1/5 w systemie binarnym, co nie przechodzi w potęgę 2.

Kolejny komentarz NIGDY nie jest równy liczbom zmiennoprzecinkowym kropka. Nawet jeśli jest to dokładna reprezentacja, istnieją pewne liczby w niektórych systemach zmiennoprzecinkowych, które mogą być dokładnie reprezentowane na więcej niż jeden sposób (IEEE jest w tym złym, jest to okropna specyfikacja zmiennoprzecinkowa na początek, więc spodziewaj się bólów głowy). Nic innego tutaj 1/3 nie jest RÓWNE dla liczby na kalkulatorze 0,333 3333, bez względu na to, ile jest 3 po prawej stronie przecinka dziesiętnego. Jest lub może być wystarczająco blisko, ale nie jest równy. więc można oczekiwać, że coś w rodzaju 2 * 1/3 nie będzie równe 2/3 w zależności od zaokrąglenia. Nigdy nie używaj równego z zmiennoprzecinkowym.

old_timer
źródło
0

Jak dyskutowaliśmy, w arytmetyce zmiennoprzecinkowej dziesiętne 0,1 nie może być idealnie reprezentowane w postaci binarnej.

Reprezentacje zmiennoprzecinkowe i liczby całkowite zapewniają siatki lub siatki dla reprezentowanych liczb. Po dokonaniu arytmetyki wyniki spadają z siatki i muszą być ponownie umieszczone na siatce zaokrąglając. Przykładem jest 1/10 na siatce binarnej.

Jeśli użyjemy binarnej reprezentacji dziesiętnej, jak sugerował jeden dżentelmen, czy bylibyśmy w stanie utrzymać liczby na siatce?

Joe
źródło
1
Oczywiście liczby dziesiętne. Ale to tylko z definicji. Nie możesz reprezentować 1/3 dziesiętnie, podobnie jak nie możesz reprezentować 0.1 w systemie binarnym. Każdy schemat kwantyzacji kończy się niepowodzeniem dla nieskończenie dużego zestawu liczb.
Kylotan