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?
Odpowiedzi:
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 .π mi
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.zab 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.π 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.
źródło
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.
źródło
Twój pomysł nie działa, ponieważ liczba reprezentowana w podstawie z mantysą m i wykładnikiem e jest liczbą wymierną b ⋅ m - e , dlatego twoja reprezentacja działa dokładnie dla liczb wymiernych i żadnych innych. Nie możesz reprezentować √b m mi b ⋅ m- e na przykład.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:
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.
źródło
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 :
Cytat z Mathworld - Frakcje ciągłe
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.
źródło
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:
Alfred Tarski (1948), Metoda decyzyjna dla elementarnej algebry i geometrii .
źródło
Możliwe jest dokładne reprezentowanie bardzo dużej klasy liczb zwanych liczbami algebraicznymi , traktując je jako pierwiastki wielomianów.
źródło
źródło
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ą.
źródło
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/3
ponieważ1 divided by 3
poprzez 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.
źródło