Czy istnieje oprogramowanie, które może automatycznie generować liczbowo dokładne zmiennoprzecinkowe procedury C z formuł symbolicznych?

25

Biorąc pod uwagę rzeczywistą funkcję rzeczywistych zmiennych, czy jest dostępne oprogramowanie, które może automatycznie generować dokładny numerycznie kod do obliczenia funkcji dla wszystkich danych wejściowych na maszynie wyposażonej w arytmetykę IEEE 754?

Na przykład, jeśli rzeczywistą funkcją do oceny były:

$f (a, b, c) = \ frac {-b - \ sqrt {b ^ 2 - 4ac}} {2a}$

Oprogramowanie rozważyłoby katastrofalne anulowanie i możliwe wyszukiwanie tablic wyników dla niektórych zestawów danych wejściowych, aby uniknąć utraty dokładności obliczeniowej.

Alternatywnie, czy istnieje oprogramowanie, które może wygenerować procedurę wyszukiwania opartą wyłącznie na tabeli, aby obliczyć daną funkcję z dużą dokładnością?

software floating-point accuracy

— Daniel Trebbien
źródło

5

Trudny problem w ogóle.

— dmckee

1

Jeśli problem dotyczył konkretnie obliczania (lub faktoryzacji) wielomianów, istnieje kilka bibliotek C (lub C ++).

— moala

2

Warto sprawdzić doskonałą serię artykułów Richarda Harrisa w czasopiśmie ACCU Overload about The Floating Point Blues . I indeksowane je na na Programmers.SX dla ludzi, którzy mogą być zainteresowani.

— Mark Booth

25

Najlepszym rozwiązaniem, jakie znam, jest zaprogramowanie wyrażeń symbolicznych w Mathematica , Maple lub SymPy ; wszystkie linki prowadzą bezpośrednio do dokumentacji generowania kodu. Wszystkie powyższe programy mogą generować kod w C lub Fortran.

Żaden z powyższych programów nie wspomina o dokładności arytmetyki IEEE 754; ogólnie rzecz biorąc, trudno byłoby przewidzieć wszystkie źródła katastrofalnego anulowania, jak zauważa @dmckee. Trudno zastąpić ludzką wiedzę fachową w zakresie analizy numerycznej.

Aby podać konkretny przykład, rozważ obliczenie funkcji trygonometrycznych z dużą precyzją dla dowolnych danych wejściowych w . Jest na to wiele strategii, niektóre nawet zależne od sprzętu, jak widać w artykule Wikipedii Tabele trygonometryczne . Wszystkie algorytmy wymagają pomysłowości i analizy numerycznej, nawet algorytmy zależne od tabel odnośników i serii Taylora lub interpolacji (patrz artykuł Wikipedii Dylemat twórcy tabel ). Aby uzyskać więcej informacji, zobacz powiązane pytanie dotyczące przepełnienia stosu Jak działają funkcje trygonometryczne? $[0, 2\pi]$ .

Oprogramowanie, które generowało kod lub procedury do obliczania dowolnych funkcji z dużą dokładnością, musiałoby nie tylko być świadomym błędów anulowania, ale także przybliżeń szeregowych (Taylor, Padé, Czebyszew, wymierny itp.) Do obliczania funkcji, które nie są zdefiniowane w kategoriach skończona liczba dodatków, odejmowań, mnożenia, podziałów i przesunięć bitów. (Patrz teoria aproksymacji ).

— Geoff Oxberry
źródło

4

„Trudno zastąpić ludzką wiedzę fachową w zakresie analizy numerycznej”. - to samo zasługuje na +1.

— JM

„To trudne” to nie to samo, co „to niemożliwe”. Istnieją „twierdzenia o pełnym zatrudnieniu” dla niektórych zadań (np. Autorów kompilatorów). Czy jest coś takiego dla analityków numerycznych?

— pseudonim

Tak. Twierdzenie Rice'a .

— Geoff Oxberry

14

Jeśli chcesz się dowiedzieć, jak daleko jesteśmy od takiego pakietu oprogramowania, zapoznaj się z notatką roboczą LAPACK z 2001 r. Na temat obliczania rotacji Givens w sposób niezawodny i wydajny . Spodziewałbym się, że większość niespecjalistów (i wielu specjalistów!) W analizie numerycznej będzie zaskoczona tym, ile analizy poświęcono na rozwiązanie tak pozornie prostego problemu:

Dany , znajdź i takie, że $f,g \in \mathbb{C}$ $c \in \mathbb{R}$ $s \in \mathbb{C}$

,

R (do, s) [\begin{matrix} fa \\ sol \end{matrix}] = [\begin{array}{cc} do & s \\ - \bar{s} & do \end{array}] [\begin{matrix} fa \\ sol \end{matrix}] = [\begin{matrix} r \\ 0 \end{matrix}]

$R(c,s) \left[\begin{array}{c} f \\ g \end{array}\right] = \left[\begin{array}{cc} c & s \\ -\bar s & c \end{array}\right] \left[\begin{array}{c} f \\ g \end{array}\right] = \left[\begin{array}{c} r \\ 0 \end{array}\right]$

gdzie jest jednostkowe. Równoważenie niezawodności z wydajnością obliczeniową i bardziej subtelnymi kwestiami, takimi jak ciągłość, jest wysoce nietrywialne i jest mało prawdopodobne, że zostanie zautomatyzowane w dającej się przewidzieć przyszłości. $R(c,s)$

— Jack Poulson
źródło

1

+1 To świetny przykład, dziękuję. Myślę, że gdyby istniało rozwiązanie dla liczb rzeczywistych, to mogłoby być dostosowane do liczb zespolonych.

— Daniel Trebbien

Powinienem chyba wspomnieć, że podstawową trudnością nie jest to, że może być złożona, ale unikanie niepotrzebnego przepełnienia i / lub niedopełnienia. Ma to związek z funkcją hypot: en.wikipedia.org/wiki/Hypot

— Jack Poulson,

11

Generowanie kodu i wstępna kompilacja wyrażeń matematycznych staje się coraz bardziej popularna.

Podczas gdy pakiety symboliczne, takie jak SymPy, Mathematica i Maple, mogą obejmować generowanie kodu, nie jestem pewien, czy którykolwiek z nich myśli też o numeryce.

Istnieje kilka innych projektów, na które można spojrzeć, które dotyczą zarówno symboliki, jak i liczb.

Theano to taki projekt skoncentrowany na operacjach tablicowych. Identyfikują i zastępują niektóre operacje, o których wiadomo, że są liczbowo źle uwarunkowane. Nie jestem pewien, czy dotyczy to twojego konkretnego przypadku, ale warto przyjrzeć się temu.

Spirala może być dla ciebie interesująca. Wstępnie kompilują również abstrakcyjne drzewo składniowe, a także zwracają uwagę na problemy numeryczne. Są bardziej zainteresowani operacjami skalarnymi (jak twój przykład). Są jednak dość wyspecjalizowane w określonej dziedzinie.

Rozwój w tej dziedzinie jest jednak zachęcający. Można być optymistą, że twoje pytanie będzie miało lepszą odpowiedź za kilka lat.

— MRocklin
źródło

2

Zgoda; być może moja odpowiedź okazała się zbyt pesymistyczna, ponieważ istnieje wiele rozwiązań specyficznych dla domeny, ale ogólny problem jest ... trudny.

— Jack Poulson

4

Nie ogólnie, mogę spokojnie powiedzieć, że implementator generatora kodu w SymPy nawet nie próbował = P.

Paolo Bientinesi opracował metodę generowania dowodów stabilności algorytmów algebry liniowej, które są generowane przy użyciu notacji FLAME Roberta van de Geijna.

Zobacz ten papier lub dłuższą roboczą wersję notatki .

— aterrel
źródło

1

Sage pozwala wyrażać formuły w Cython (wariant Pythona, który generuje kod C); jednak w odpowiedzi na bardziej ogólne pytanie: nie. Rozważ Twierdzenie Rice'a .

— mda
źródło