Reprezentują liczbę rzeczywistą bez utraty precyzji

10

Bieżący zmiennoprzecinkowy (zmiennoprzecinkowy ANSI C, podwójny) pozwala przedstawić przybliżoną liczbę rzeczywistą.
Czy istnieje sposób na przedstawienie liczb rzeczywistych bez błędów ?
Oto pomysł, który miałem, ale nie idealny.

Na przykład 1/3 to 0.33333333 ... (podstawa 10) lub o.01010101 ... (podstawa 2), ale także 0,1 (podstawa 3)
Czy dobrym pomysłem jest wdrożenie tej „struktury”:

base, mantissa, exponent

więc 1/3 może wynosić 3 ^ -1

{[11] = base 3, [1.0] mantissa, [-1] exponent}

Jakieś inne pomysły?

— w tym
źródło

12

W ten sposób będziesz mógł reprezentować liczby wymierne.

— Andrej Bauer,

Jak proponujesz zaimplementować operacje arytmetyczne na liczbach w tej reprezentacji? Używasz logarytmów do zmiany bazy? Byłoby to znacznie droższe niż matematyka zmiennoprzecinkowa IEEE.

— David Zhang

Nie mam pojęcia. Nie jestem inżynierem :) Oczywiście nie mogę tego zaimplementować w sprzęcie. Powolną, nieefektywną implementację można wykonać w C. To byłby tylko eksperyment

— tym

20

Wszystko zależy od tego, co chcesz zrobić.

Na przykład to, co pokazujesz, to świetny sposób reprezentowania liczb wymiernych. Ale nadal nie może idealnie reprezentować czegoś takiego jak lub . $\pi$ $e$

W rzeczywistości wiele języków, takich jak Haskell i Scheme, ma wbudowaną obsługę liczb wymiernych, przechowując je w postaci gdzie są liczbami całkowitymi. $\frac{a}{b}$ $a,b$

Głównym powodem, dla którego nie są one powszechnie stosowane, jest wydajność. Liczby zmiennoprzecinkowe są nieco nieprecyzyjne, ale ich operacje są implementowane sprzętowo. Proponowany system pozwala na większą precyzję, ale wymaga kilku kroków do wdrożenia, w przeciwieństwie do pojedynczej operacji, którą można wykonać sprzętowo.

Wiadomo, że niektóre liczby rzeczywiste są niepoliczalne, takie jak liczby zatrzymania . W przeciwieństwie do nie ma algorytmu wyliczającego jego cyfry, w którym możemy obliczyć tą cyfrę, o ile czekamy wystarczająco długo. $\pi$ $n$

Jeśli chcesz prawdziwej precyzji dla liczb nieracjonalnych lub transcendentalnych, prawdopodobnie będziesz musiał użyć jakiegoś systemu algebry symbolicznej, a następnie uzyskać ostateczną odpowiedź w formie symbolicznej, którą możesz przybliżyć do dowolnej liczby cyfr. Jednak z powodu opisanych powyżej problemów związanych z nierozstrzygalnością to podejście jest z konieczności ograniczone. Nadal jest przydatny w przypadku przybliżania całek lub szeregów nieskończonych.

— jmite
źródło

Czy mogę zadać kolejne pytanie? Gdybyś był inżynierem Intela w latach 80., jak byś „zaprojektował” swój format liczb rzeczywistych?

— tym

3

Nie jestem zbyt wykwalifikowany, aby odpowiedzieć na to pytanie, ponieważ nie jestem inżynierem, jestem badaczem teorii. Nie widzę nic złego w IEEE float i podwójnych standardach, a teraz quad. Nie sądzę, aby było wiele aplikacji zależnych od arytmetyki o wyższej precyzji, a te, które to robią, mogą używać wersji obsługiwanej przez oprogramowanie.

— jmite

Algebra symboliczna nie jest właściwym formalizmem dla prawdziwej arytmetyki. Potrzebujesz reprezentacji, która pozwala na dowolnie duże mantysy.

— Andrej Bauer,

8

@AndrejBauer: arbitralnie duża mantysa nie uratuje cię, jeśli chcesz dokładnego przedstawienia

.

\sqrt{2}

$\sqrt 2$

— user2357112 obsługuje Monikę

@jmite jesteś za bardzo skromny :)

— tym

22

Nie ma możliwości przedstawienia wszystkich liczb rzeczywistych bez błędów, jeśli każda liczba ma mieć skończoną reprezentację. Istnieje niezliczona liczba liczb rzeczywistych, ale tylko niezliczona liczba skończonych ciągów 1 i 0, których możesz użyć do ich przedstawienia.

— David Richerby
źródło

Można ograniczyć wymaganie od reprezentowania każdej liczby rzeczywistej do ograniczenia tylko tych liczb rzeczywistych, które mogą być wyjściem maszyny Turinga. To byłaby tylko policzalna liczba liczb rzeczywistych, ale nadal obejmowałaby każdą liczbę, którą kiedykolwiek chciałbyś reprezentować. Ale nie sądzę, aby można było wykonywać wydajne obliczenia z takimi liczbami.

— kasperd

3

@kasperd Nazywa się je rzeczywistymi obliczalnymi . Niestety, rzeczy takich jak równość nie są obliczalne na podstawie obliczalnych liczb rzeczywistych.

— David Richerby,

Rzeczywiście jest całkiem jasne, że obliczenie równości na takich liczbach jest równoznaczne z rozwiązaniem problemu zatrzymania. Biorąc pod uwagę bazę TM, można zdefiniować liczbę rzeczywistą, która zaczyna się od wielu miejsc po przecinku, które są zerowe, dokładnie tyle, ile czas pracy bazy TM, a następnie jeden. Porównanie tej liczby do zera jest równoznaczne z rozwiązaniem problemu zatrzymania dla oryginalnej TM.

— kasperd

Ta odpowiedź jest fałszywa. Alan Turing w swoim pierwszym artykule na temat maszyn, na których wymyśla maszyny Turinga, mówi o reprezentowaniu rzeczywistości jako nieskończonych ciągów danych. To prowadzi do idei tak zwanej „maszyny Turinga typu II” i istnieje bardzo udana teoria obliczeń liczb rzeczywistych oparta na tej idei. Jest również wdrażany w praktyce, patrz moja odpowiedź.

— Andrej Bauer,

1

Być może robi to technicznie, ale nie ma sensu, że istnieją całkowicie uzasadnione nieskończone reprezentacje liczb rzeczywistych. I to nic dziwnego: połączenie TCP / IP, połączenie Skype lub wideo z kamery to przykłady (potencjalnie) nieskończonej ilości danych. Nie ma a priori ograniczenia co do ilości informacji, które mogą dostarczyć. Istnieje tylko ograniczenie ilości informacji, które można z nich uzyskać w ograniczonym czasie.

— Andrej Bauer,

7

Twój pomysł nie działa, ponieważ liczba reprezentowana w podstawie z mantysą i wykładnikiem jest liczbą wymierną , dlatego twoja reprezentacja działa dokładnie dla liczb wymiernych i żadnych innych. Nie możesz reprezentować $b$ $m$ $e$ $b \cdot m^{-e}$ na przykład. $\sqrt{2}$

Istnieje cała gałąź matematyki obliczeniowej, która zajmuje się dokładną prawdziwą arytmetyką. Zaproponowano wiele struktur danych do reprezentowania dokładnych liczb rzeczywistych: strumienie cyfr, strumienie skurczów afinicznych, sekwencje Cauchy'ego racjonalności, sekwencje Cauchy'ego racji dynastycznych, cięcia Dedekinda, sekwencje przedziałów shkrinkowania itp. Istnieją implementacje dokładnej rzeczywistej arytmetyki na temat tych pomysłów, na przykład:

Implementacja iRRAM Norberta Müllera dokładnych liczb rzeczywistych w C ++
Język Marhsall do dokładnych obliczeń z rzeczywistością Dedekind
Kalkulator do obliczania dokładnych liczb rzeczywistych

Z tych iRRAM jest najbardziej dojrzały i wydajny. Marshall w projekcie eksperymentalnym, a trzeci to projekt studencki, ale także najłatwiej dostępny. Ma bardzo ładne wprowadzenie wyjaśniające problemy dotyczące obliczania liczb rzeczywistych, gorąco polecam, abyś na to spojrzał.

Pozwól mi zrobić uwagę. Ktoś sprzeciwi się temu, że nieskończony obiekt nie może być reprezentowany przez komputer. W pewnym sensie jest to prawda, ale w innym nie jest. Nigdy nie musimy reprezentować całej liczby rzeczywistej, potrzebujemy tylko skończonego przybliżeniana każdym etapie obliczeń. Dlatego potrzebujemy tylko reprezentacji, która może reprezentować rzeczywistość z dowolną dokładnością. Oczywiście, kiedy zabraknie pamięci komputera, zabraknie pamięci komputera - ale jest to ograniczenie komputera, a nie samej reprezentacji. Ta sytuacja nie różni się niczym od wielu innych w programowaniu. Na przykład ludzie używają liczb całkowitych w Pythonie i uważają je za „dowolnie duże”, chociaż oczywiście nie mogą przekroczyć wielkości dostępnej pamięci. Czasami nieskończoność jest przydatnym przybliżeniem bardzo dużej liczby skończonej.

Co więcej, często słyszę twierdzenie, że komputery radzą sobie tylko z obliczalnymi liczbami rzeczywistymi. Pomija to dwa ważne punkty. Po pierwsze, komputery mają dostęp do danych ze świata zewnętrznego, więc musielibyśmy również przyjąć (niemożliwe do zweryfikowania) założenie, że świat zewnętrzny jest również obliczalny. Po drugie, musimy rozróżnić, jakie reale może obliczyć komputer, a jakie reale może reprezentować. Na przykład, jeśli zdecydujemy strumienie cyfr jak reprezentacji liczb rzeczywistych to jest całkowicie możliwe do reprezentowania non-obliczalny rzeczywiście: jeśli ktoś dał nam to wiedzielibyśmy jak go reprezentować. Ale jeśli zdecydujemy się reprezentować liczby rzeczywiste jako fragmenty kodu źródłowego, które obliczają cyfry, to oczywiście nie moglibyśmy reprezentować liczb rzeczywistych, które nie są obliczalne.

W każdym razie najlepiej poradzić sobie z tym tematem.

— Andrej Bauer
źródło

+1, ale sprzeciwiłbym się temu, że nie można przedstawić nieskończonego ciągu przez skończone przybliżenie bez utraty precyzji , jak wymaga tego pytanie. Jasne, możesz uzyskać tyle precyzji, ile chcesz - zbliżając się do racjonalnego - ale nie do końca o to pyta pytanie. Prawdopodobnie jest to problem z pytaniem, a nie z odpowiedzią.

— David Richerby,

2

Chodzi o to, że nie reprezentujemy za pomocą skończonych łańcuchów. Reprezentujemy za pomocą nieskończonych ciągów, ale zawsze potrzebujemy tylko skończonej części takiego nieskończonego ciągu na każdym etapie obliczeń. Innymi słowy: nie ma utraty precyzji, ponieważ struktura danych zawiera całą informację, ale oczywiście nie można uzyskać dostępu do wszystkich informacji ani przetwarzać ich jednocześnie: struktura danych daje tyle precyzji, o ile prosisz . Wąskie gardło nie leży po stronie struktury danych, ale raczej po stronie „konsumenta”, który chce wyciągnąć z niego informacje.

— Andrej Bauer,

@AndrejBauer Ale w niektórych przypadkach musisz uzyskać dostęp lub przetwarzać wszystkie informacje naraz, np. Właśnie to robi obliczenie symboliczne, przechwytując „esencję” lub charakter ilości, a nie jak każdy inny strumień cyfr. Jeśli powiesz symbolicznemu pakietowi obliczeniowemu, aby to zweryfikował

, natychmiast wygenerowałoby true. Jeśli użyłeś metody, którą wydajesz się opisywać, biorąc pierwsze

cyfr pierwiastka kwadratowego z

, dladowolnego

wyciągniesz wniosek, że

{\sqrt{2}}^{2} = 2

$\sqrt{2}^2 = 2$

k

$k$

2

$2$

k

$k$

ponieważ twój wynik będzie (dla dowolnego skończonego

) równy

, zła odpowiedź. Obliczenia są skończone.

{\sqrt{2}}^{2} \neq 2

$\sqrt{2}^2 \ne 2$

k

$k$

1.99...

$1.99...$

— Thomas

2

@Thomas: obliczenia symboliczne nie reprezentują liczb rzeczywistych, ale zwykle pewne podpole liczb rzeczywistych, zwykle generowane przez funkcje elementarne i pierwiastki wielomianów. Podpola te nie są kompletne (zamknięte w ramach limitów sekwencji Cauchy'ego) ani pełne obliczeniowo (zamknięte w obliczalnych granicach sekwencji Cauchy'ego). Reprezentacja nie jest reprezentacją rzeczywistych, chyba że można reprezentować wszystkie rzeczywiste (obliczalne): a obliczenia symboliczne nie spełniają tego warunku.

— Andrej Bauer

1

Te uwagi dotyczące policzalności są nieistotne, ponieważ obliczalne liczby rzeczywiste nie są obliczalne.

— Andrej Bauer

7

Istnieje wiele skutecznych implementacji liczb wymiernych, ale jedna, która była proponowana wiele razy, a nawet całkiem dobrze radzi sobie z niektórymi nieracjonalnymi, to ciąg dalszy .

Cytat z kontynuacji frakcji Darrena C. Collinsa :

Twierdzenie 5-1. - Kontynuacja wyrażenia ułamkowego liczby rzeczywistej jest skończona wtedy i tylko wtedy, gdy liczba rzeczywista jest racjonalna.

Cytat z Mathworld - Frakcje ciągłe

... ciągły ułamek jest okresowy, jeśli jest to pierwiastek kwadratowego wielomianu.

tzn. wszystkie pierwiastki mogą być wyrażone jako okresowe ciągłe ułamki.

Istnieje również Dokładna część kontynuowana dla π, która zaskoczyła mnie, dopóki @AndrejBauer nie zauważył, że tak naprawdę nie jest.

— OldCurmudgeon
źródło

π

$\pi$

π

$\pi$

Kontynuacja reprezentacji ułamków rzeczywistych została zaproponowana jakiś czas temu jako implementacja dokładnej prawdziwej arytmetyki J. Vuillemina. Okazuje się, że nie jest zbyt wydajny, ponieważ liczby stają się dość duże wkrótce i trudno jest zmniejszyć ich rozmiar.

— Andrej Bauer,

Ułamki ciągłe mają pewne problemy obliczeniowe nawet w przypadku reprezentowania liczb wymiernych - podczas gdy można je stosunkowo szybko porównać przy użyciu wariantu porządku leksykograficznego, a podczas gdy manipulowanie pojedynczym ułamkiem ciągłym jest łatwe, zarówno dodawanie (mnożenie), jak i mnożenie na CF są dość skomplikowanymi operacjami wprowadzić w życie.

— Steven Stadnicki

5

W komentarzach znajduje się wiele „rzeczywistych” sugestii (np. Ciągłe ułamki, liniowe przekształcenia ułamkowe itp.). Typowym haczykiem jest to, że chociaż można obliczyć odpowiedzi na formułę, równość jest często nierozstrzygalna.

Jeśli jednak interesują Cię liczby algebraiczne, masz szczęście: teoria prawdziwych zamkniętych pól jest kompletna, o-minimalna i rozstrzygalna. Zostało to udowodnione przez Tarskiego w 1948 roku.

Ale jest haczyk. Nie chcesz używać algorytmu Tarskiego, ponieważ jest on w klasie złożoności NONELEMENTARY, co jest tak niepraktyczne, jak to tylko możliwe. Istnieją nowsze metody, które sprowadzają złożoność do DEXP, co jest najlepszym, co obecnie znamy.

Zauważ, że problem jest trudny NP, ponieważ obejmuje SAT. Jednak nie wiadomo (ani nie uważa się), że jest w NP.

EDYCJA Spróbuję wyjaśnić to trochę bardziej.

Podstawą zrozumienia tego wszystkiego jest problem decyzyjny znany jako Teorie Modulo Satisfiable Modulo, w skrócie SMT. Zasadniczo chcemy rozwiązać SAT dla teorii zbudowanej na logice klasycznej.

Dlatego zaczynamy od klasycznej logiki pierwszego rzędu z testem równości. Jakie symbole funkcji chcemy uwzględnić i jakie są ich aksjomaty, określają, czy teoria jest rozstrzygalna.

Istnieje wiele interesujących teorii wyrażonych w ramach SMT. Na przykład istnieją teorie struktur danych (np. Listy, drzewa binarne itp.), Które służą do udowodnienia poprawności programów, oraz teoria geometrii euklidesowej. Ale dla naszego celu analizujemy teorie różnego rodzaju liczb.

Arytmetyka Presburgera to teoria liczb naturalnych z dodatkiem. Ta teoria jest rozstrzygalna.

Arytmetyka Peano to teoria liczb naturalnych z dodawaniem i mnożeniem. Teoria ta nie podlega dyskusji, o czym słynie Gödel.

Arytmetyka Tarskiego to teoria liczb rzeczywistych ze wszystkimi operacjami w terenie (dodawanie, odejmowanie, mnożenie i dzielenie). Co ciekawe, teoria ta jest rozstrzygalna. Był to wówczas bardzo sprzeczny z intuicją wynik. Możesz założyć, że ponieważ jest to „nadzbiór” liczb naturalnych, jest „trudniejszy”, ale tak nie jest; porównaj na przykład programowanie liniowe ponad racjonalne z programowaniem liniowym ponad liczbami całkowitymi.

Może się nie wydawać oczywiste, że satysfakcja jest wszystkim, czego potrzebujesz, ale tak jest. Na przykład, jeśli chcesz sprawdzić, czy dodatni pierwiastek kwadratowy z 2 jest równy rzeczywistemu pierwiastkowi z kostki z 3, możesz wyrazić to jako problem satysfakcji:

\exists x . x > 0 \land x^{2} - 2 = 0 \land x^{3} - 3 = 0

$\exists x. x>0 \wedge x^2 - 2 = 0 \wedge x^3 - 3 = 0$

$e^x$

$\sin$ $\{ \frac{x}{\pi} | \sin x = 0 \}$ $\sin$

$e^x$ $e^{ix}$

Alfred Tarski (1948), Metoda decyzyjna dla elementarnej algebry i geometrii .

— Pseudonim
źródło

2

Możliwe jest dokładne reprezentowanie bardzo dużej klasy liczb zwanych liczbami algebraicznymi , traktując je jako pierwiastki wielomianów.

$\pi$ $e$

— Więcej osi
źródło

e

$e$

e^{i x}

$e^{ix}$

\sin

$\sin$

\cos

$\cos$

{x \in R | \sin x = 0}

$\{ x \in \mathbb{R} | \sin x = 0 \}$

@Pseudonim To wydaje się bardzo interesujące, ale nie sądzę, że mam matematyczne podstawy, aby to właściwie zrozumieć ... Co rozumiesz przez „wystarczająco blisko liczb całkowitych”?

— Więcej Axes

Zamierzam zmienić swoją odpowiedź, aby wyjaśnić.

— pseudonim

1

$\pi$ $\sqrt2$

— Roślina
źródło

Ta odpowiedź jest fałszywa. Istnieje cała dziedzina dokładnej prawdziwej arytmetyki, która wyjaśnia, jak reprezentować rzeczywistość za pomocą komputerów. Założenie, że rzeczywistość musi być reprezentowana przez skończony ciąg, jest błędne. Możemy również używać ciągów nieskończonych. Już Alan Turing napisał o tym w swoim pierwszym artykule, tym, w którym wynalazł maszyny Turinga!

— Andrej Bauer,

Czy możesz link do artykułu o tym, jak przechowywać i manipulować nieskończonymi ciągami w rzeczywistym komputerze, ponieważ byłaby to odpowiedź na pytanie. Również nie był to jego pierwszy artykuł, pierwsza publikacja to 1936, ten artykuł to 1937.

— lPlant

Masz rację, to papier z 1937 roku. Aby zobaczyć, jak manipulowane są ciągi nieskończone, możesz na przykład spojrzeć na protokół TCP / IP. Nigdy nie mówiłem, że cała rzeczywistość musi być przechowywana na komputerze.

— Andrej Bauer

-1

Nie możesz reprezentować wszystkich liczb rzeczywistych na komputerze, ale możesz reprezentować wiele. Możesz użyć ułamków, które reprezentują więcej liczb niż liczb zmiennoprzecinkowych. Możesz także robić bardziej wyrafinowane rzeczy, takie jak reprezentowanie liczb jako pierwiastek wielomianu z przybliżeniem, które w metodzie Newtona będzie zbieżne z liczbą.

— Alice Ryhl
źródło

To znowu jest fałszywa odpowiedź, wytworzona z niewiedzy. Istnieje cała dziedzina dokładnej prawdziwej arytmetyki, która bada, w jaki sposób reprezentować wszystkie rzeczywistości za pomocą odpowiednich struktur danych.

— Andrej Bauer,

@AndrejBauer Więc sugerujesz, że istnieje struktura danych, która może reprezentować dowolną liczbę rzeczywistą? Każda taka struktura danych musiałaby wykorzystywać niezliczoną nieskończoną liczbę bitów do przedstawienia dowolnej liczby.

— Alice Ryhl,

1

Przeliczalna ilość bitów wystarczy, przede wszystkim, a ponieważ nie trzeba ich wszystkich na raz, ani nie jesteś w stanie przetworzyć je wszystkie na raz, mogą być przechowywane w czasie, jak i przestrzeni.

— Andrej Bauer,

@AndrejBauer Ta odpowiedź jest poprawna i mówi to samo co Twoja, choć z dużo mniejszą ilością informacji. Nie można reprezentować wszystkich liczb rzeczywistych w komputerze. Możesz reprezentować dowolną liczbę rzeczywistą, ale nie wszystkie naraz. Jeśli tak, to zaprzeczam, że możesz reprezentować „wielu”, ponieważ możesz reprezentować tylko skończoną liczbę na dowolnym komputerze i tylko prawie żaden (w sensie matematycznym) na abstrakcyjnym komputerze, który jest równoważny zwykłym modelom obliczeniowym (Turinga) ekwiwalent maszyny).

— Gilles 'SO - przestań być zły'

-1

Możliwe jest dokładne odwzorowanie dowolnej liczby tam, gdzie dane wejściowe są reprezentowalne, poprzez zapisanie ich jako ciąg operacji, więc na przykład przechowujesz, 1/3ponieważ 1 divided by 3poprzez obsługę anulowania operacji możesz uprościć kolejną operację, aby podać dokładną odpowiedź (1/3) * 3. Może to również poradzić sobie z sytuacjami, w których znasz irracjonalne, takie jak πzachowanie go w swoich obliczeniach.

Wymaga to jednak coraz większej ilości pamięci dla każdej liczby i - zakładając, że twój uproszczenie nie jest idealny - prawdopodobnie będzie wymagać coraz większej ilości dla wartości, nad którymi często pracujesz.

— Jack Aidley
źródło

\sqrt{5 + 2 \sqrt{6}} - \sqrt{2} = \sqrt{3}

$\sqrt{5 + 2\sqrt{6}} - \sqrt{2} = \sqrt{3}$

W rzeczy samej. W rzeczywistości prawdopodobnie całkowicie niemożliwe jest zautomatyzowanie całkowicie pomyślnie. Jednak wynik pozostaje precyzyjny, nawet jeśli nie użyłeś najprostszej możliwej reprezentacji.

— Jack Aidley