Jak działają funkcje trygonometryczne?

Tak więc w liceum matematycznym i prawdopodobnie na studiach uczy się nas, jak używać funkcji trygonometrycznych, co robią i jakiego rodzaju problemy rozwiązują. Ale zawsze były mi przedstawiane jako czarna skrzynka. Jeśli potrzebujesz jakiejś wartości sinus lub cosinus, naciskasz przycisk sin lub cos na kalkulatorze i gotowe. Co jest w porządku.

Zastanawiam się, jak zwykle implementuje się funkcje trygonometryczne.

Najpierw musisz dokonać jakiejś redukcji zasięgu. Funkcje trygonometryczne są okresowe, więc musisz zredukować argumenty do standardowego interwału. Na początek możesz zmniejszyć kąty w zakresie od 0 do 360 stopni. Ale używając kilku tożsamości, zdajesz sobie sprawę, że możesz sobie poradzić za mniej. Jeśli obliczysz sinusy i cosinusy dla kątów od 0 do 45 stopni, możesz rozpocząć obliczanie wszystkich funkcji trygonometrycznych dla wszystkich kątów.

Po zredukowaniu argumentów większość chipów używa algorytmu CORDIC do obliczania sinusów i cosinusów. Możesz usłyszeć, jak ludzie mówią, że komputery używają serii Taylora. Brzmi rozsądnie, ale to nieprawda. Algorytmy CORDIC znacznie lepiej nadają się do wydajnej implementacji sprzętu . ( Biblioteki oprogramowania mogą korzystać z serii Taylora, powiedzmy na sprzęcie, który nie obsługuje funkcji trygonometrycznych). Może wystąpić dodatkowe przetwarzanie, przy użyciu algorytmu CORDIC w celu uzyskania całkiem dobrych odpowiedzi, a następnie zrobienie czegoś innego, aby poprawić dokładność.

Istnieje kilka ulepszeń powyższego. Na przykład dla bardzo małych kątów theta (w radianach), sin (theta) = theta z całą dostępną precyzją, więc bardziej wydajne jest po prostu zwrócenie theta niż użycie innego algorytmu. Tak więc w praktyce istnieje wiele logiki specjalnego przypadku, aby wycisnąć całą możliwą wydajność i dokładność. Żetony z mniejszymi rynkami mogą nie wymagać tak dużego wysiłku optymalizacyjnego.

edycja: Jack Ganssle ma przyzwoitą dyskusję w swojej książce o systemach wbudowanych „The Firmware Handbook” .

FYI: Jeśli masz ograniczenia dokładności i wydajności, szereg Taylora nie powinien być używany do przybliżania funkcji do celów numerycznych. (Zachowaj je dla swoich kursów Calculus.) Wykorzystują analityczność funkcji w jednym punkcie , np. Fakt, że wszystkie jej pochodne istnieją w tym punkcie. Niekoniecznie zbiegają się one w przedziale zainteresowania. Często wykonują kiepską robotę, rozkładając dokładność aproksymacji funkcji, aby być „idealnym” tuż przy punkcie oceny; błąd zwykle powiększa się, gdy się od niego oddalasz. A jeśli masz funkcję z dowolną nieciągłą pochodną (np. Falami kwadratowymi, trójkątnymi i ich całkami), szereg Taylora da ci złą odpowiedź.

Najlepszym „łatwym” rozwiązaniem, gdy używa się wielomianu maksymalnego stopnia N do aproksymacji danej funkcji f (x) w przedziale x0 <x <x1, jest przybliżenie Czebyszewa ; dobrą dyskusję znajdziesz w Przepisach numerycznych. Zwróć uwagę, że Tj (x) i Tk (x) w artykule Wolframa, do którego dołączyłem, użyłem cos i odwrotnego cosinusa, są to wielomiany i w praktyce do uzyskania współczynników używasz wzoru powtarzania. Ponownie zobacz Receptury numeryczne.

edycja: Wikipedia ma całkiem przyzwoity artykuł na temat teorii przybliżenia . Jedno ze źródeł, które cytują (Hart, „Computer Approximations”) jest wyczerpane (a używane kopie są zwykle drogie), ale zawiera wiele szczegółów na temat takich rzeczy. (Jack Ganssle wspomina o tym w 39 numerze swojego biuletynu The Embedded Muse ).

edycja 2: Oto kilka namacalnych wskaźników błędów (patrz poniżej) dla Taylor kontra Chebyshev dla sin (x). Kilka ważnych punktów, na które należy zwrócić uwagę:

1. że maksymalny błąd przybliżenia szeregu Taylora w danym zakresie jest znacznie większy niż maksymalny błąd przybliżenia Czebyszewa tego samego stopnia. (W przypadku mniej więcej tego samego błędu możesz uciec z jednym terminem mniej z Czebyszewem, co oznacza szybszą wydajność)
2. Zmniejszenie zasięgu to ogromna wygrana. Dzieje się tak, ponieważ udział wielomianów wyższego rzędu zmniejsza się, gdy przedział aproksymacji jest mniejszy.
3. Jeśli nie możesz uciec z redukcją zasięgu, twoje współczynniki muszą być przechowywane z większą precyzją.

Nie zrozumcie mnie źle: szereg Taylora będzie działał poprawnie dla sinus / cosinus (z rozsądną precyzją dla zakresu -pi / 2 do + pi / 2; technicznie, przy wystarczającej liczbie terminów, można osiągnąć dowolną pożądaną precyzję dla wszystkich rzeczywistych wejść, ale spróbuj obliczyć cos (100) za pomocą szeregu Taylora i nie możesz tego zrobić, chyba że używasz arytmetyki o dowolnej precyzji). Gdybym utknął na bezludnej wyspie z nienaukowym kalkulatorem i musiałbym obliczyć sinus i cosinus, prawdopodobnie użyłbym szeregu Taylora, ponieważ współczynniki są łatwe do zapamiętania. Jednak rzeczywiste zastosowania do pisania własnych funkcji sin () lub cos () są na tyle rzadkie, że najlepiej byłoby użyć wydajnej implementacji w celu osiągnięcia pożądanej dokładności - czego nie jest w przypadku serii Taylora .

Zakres = -pi / 2 do + pi / 2, stopień 5 (3 terminy)

• Taylor max błąd około 4.5e-3, F (x) = XX ³ /6 + x ⁵ /120
• Czebyszewa: maksymalny błąd około 7e-5, f (x) = 0,9996949x-0,1656700x ³ + 0,0075134x ⁵

Zakres = -pi / 2 do + pi / 2, stopień 7 (4 terminy)

• Taylor max błąd około 1,5-e-4, F (x) = XX ³ /6 + x ⁵ /120 x ⁷ /5040
• Czebyszewa: maksymalny błąd około 6e-7, f (x) = 0,99999660x-0,16664824x ³ + 0,00830629x ⁵ -0,00018363x ⁷

Zakres = -pi / 4 do + pi / 4, stopień 3 (2 terminy)

• Taylor max błąd około 2.5E-3, F (x) = XX ³ /6
• Czebyszewa: maksymalny błąd około 1,5e-4, f (x) = 0,999x-0,1603x ³

Zakres = -pi / 4 do + pi / 4, stopień 5 (3 terminy)

• Taylor max błąd około 3.5E-5, F (x) = XX ³ /6 + x ⁵
• Czebyszewa: maksymalny błąd około 6e-7, f (x) = 0,999995x-0,1666016x ³ + 0,0081215x ⁵

Zakres = -pi / 4 do + pi / 4, stopień 7 (4 terminy)

• Taylor max błąd około 3e-7, F (x) = XX ³ /6 + x ⁵ /120 x ⁷ /5040
• Czebyszewa: maksymalny błąd około 1,2e-9, f (x) = 0,999999986x-0,166666367x ³ + 0,008331584x ⁵ -0,000194621x ⁷

Wydaje mi się, że są obliczane przy użyciu serii Taylora lub CORDIC . Niektóre aplikacje, które intensywnie wykorzystują funkcje trygonometryczne (gry, grafika), konstruują tabele trygonometrii podczas uruchamiania, aby mogły po prostu wyszukiwać wartości, zamiast ponownie je obliczać.

Przeczytaj artykuł w Wikipedii o funkcjach trygonometrycznych. Dobrym miejscem do nauki o ich implementacji w kodzie są Receptury Numeryczne .

Nie jestem zbyt wielkim matematykiem, ale rozumiem, skąd „pochodzą” grzechy, cos i tan jest takie, że są one w pewnym sensie obserwowane podczas pracy z trójkątami prostokątnymi. Jeśli wykonasz pomiary długości boków grupy różnych trójkątów prostokątnych i wykreślisz punkty na wykresie, możesz uzyskać z tego sin, cos i tan. Jak zauważa Harper Shelby, funkcje są po prostu zdefiniowane jako właściwości trójkątów prostokątnych.

Bardziej wyrafinowane zrozumienie można osiągnąć poprzez zrozumienie, w jaki sposób te proporcje odnoszą się do geometrii koła, co prowadzi do radianów i całej tej dobroci. To wszystko znajduje się we wpisie w Wikipedii.

Najczęściej w komputerach reprezentacja szeregów potęg jest używana do obliczania sinusów i cosinusów, a te są używane do innych funkcji trygonometrycznych. Rozwinięcie tych szeregów do około 8 członów powoduje obliczenie potrzebnych wartości z dokładnością bliską epsilon maszyny (najmniejsza niezerowa liczba zmiennoprzecinkowa, jaką można przechowywać).

Metoda CORDIC jest szybsza, ponieważ jest implementowana na sprzęcie, ale jest używana głównie w systemach wbudowanych, a nie w standardowych komputerach.

Chciałbym rozszerzyć odpowiedź udzieloną przez @Jason S. Używając metody podziału domeny podobnej do tej opisanej przez @Jason S i używając przybliżeń szeregów Maclaurina, średnie (2-3) X przyspieszenie przez tan (), sin () , cos (), atan (), asin () i acos () wbudowane w kompilator gcc z optymalizacją -O3. Najlepsze funkcje aproksymujące z serii Maclaurina opisane poniżej zapewniają podwójną precyzję.

W przypadku funkcji tan (), sin () i cos () oraz dla uproszczenia nakładającą się domenę 0 do 2pi + pi / 80 podzielono na 81 równych przedziałów z „punktami kotwiczenia” przy pi / 80, 3pi / 80, ..., 161pi / 80. Następnie oceniono i zapisano tan (), sin () i cos () z tych 81 punktów kontrolnych. Przy pomocy tożsamości trygonometrycznych opracowano jedną funkcję szeregu Maclaurina dla każdej funkcji trygonometrycznej. Dowolny kąt pomiędzy ± nieskończonością może zostać przesłany do funkcji aproksymujących trygonometrię, ponieważ funkcje najpierw przekształcają kąt wejściowy do domeny od 0 do 2pi. Ten narzut na tłumaczenie jest uwzględniony w narzutie aproksymacji.

Podobne metody opracowano dla funkcji atan (), asin () i acos (), w których nakładająca się domena od -1,0 do 1,1 została podzielona na 21 równych przedziałów z punktami zakotwiczenia na poziomie -19/20, -17/20, .. ., 19/20, 21/20. Następnie przechowywano tylko atan () z tych 21 punktów kontrolnych. Ponownie, przy pomocy odwrotnych tożsamości trygonometrycznych, opracowano pojedynczą funkcję szeregu Maclaurina dla funkcji atan (). Wyniki funkcji atan () zostały następnie użyte do przybliżenia asin () i acos ().

Ponieważ wszystkie funkcje aproksymujące wyzwalanie odwrotne są oparte na funkcji aproksymującej atan (), każda wartość wejściowa argumentu podwójnej precyzji jest dozwolona. Jednak argument wejściowy do funkcji aproksymujących asin () i acos () jest obcinany do domeny ± 1, ponieważ każda wartość poza nim jest bez znaczenia.

Aby przetestować funkcje aproksymujące, trzeba było ocenić miliard losowych ocen funkcji (to znaczy optymalizujący kompilator -O3 nie mógł ominąć oceniania czegoś, ponieważ jakiś obliczony wynik nie zostałby użyty). Aby usunąć błąd związany z szacowaniem miliarda liczby losowe i przetwarzanie wyników, koszt uruchomienia bez oceny funkcji wyzwalania lub odwrotnego wyzwalania został wykonany jako pierwszy. To odchylenie było następnie odejmowane od każdego testu, aby uzyskać bardziej reprezentatywne przybliżenie rzeczywistego czasu oceny funkcji.

Tabela 2. Czas spędzony w sekundach na wykonywaniu wskazanej funkcji lub funkcji miliard razy. Szacunki uzyskuje się przez odjęcie czasu oszacowania miliarda liczb losowych przedstawionych w pierwszym wierszu tabeli 1 od pozostałych wierszy tabeli 1.

Czas spędzony w tan (): 18.0515 18.2545

Czas spędzony w TAN3 (): 5,93853 6,02349

Czas spędzony w TAN4 (): 6,72216 6,99134

Czas spędzony w grzechu () i cos (): 19,4052 19,4311

Czas spędzony w SINCOS3 (): 7.85564 7.92844

Czas spędzony w SINCOS4 (): 9,36672 9,57946

Czas spędzony w atanie (): 15,7160 15,6599

Czas spędzony w ATAN1 (): 6,47800 6,55230

Czas spędzony w ATAN2 (): 7,26730 7,24885

Czas spędzony w ATAN3 (): 8,15299 8,21284

Czas spędzony w asin () i acos (): 36,8833 36,9496

Czas spędzony w ASINCOS1 (): 10,1655 9,78479

Czas spędzony w ASINCOS2 (): 10,6236 10,6000

Czas spędzony w ASINCOS3 (): 12,8430 12,0707

(Ze względu na oszczędność miejsca, tabela 1 nie jest pokazana). Tabela 2 przedstawia wyniki dwóch oddzielnych serii miliardów ocen każdej funkcji aproksymacyjnej. Pierwsza kolumna to pierwsza seria, a druga kolumna to druga seria. Liczby „1”, „2”, „3” lub „4” w nazwach funkcji wskazują liczbę terminów użytych w funkcji szeregu Maclaurina do oceny określonego przybliżenia trygonometrycznego lub odwrotnego trygonometrii. SINCOS # () oznacza, że ​​zarówno sin, jak i cos zostały obliczone w tym samym czasie. Podobnie ASINCOS # () oznacza, że ​​zarówno asin, jak i acos zostały ocenione w tym samym czasie. Równoczesna ocena obu wielkości wymaga niewielkich dodatkowych kosztów.

Wyniki pokazują, że zwiększenie liczby terminów nieznacznie wydłuża czas realizacji, zgodnie z oczekiwaniami. Nawet najmniejsza liczba terminów dawała wszędzie dokładność około 12-14 cyfr z wyjątkiem przybliżenia tan () w pobliżu miejsca, w którym jego wartość zbliża się do ± nieskończoności. Można by się spodziewać, że nawet funkcja tan () będzie miała tam problemy.

Podobne wyniki uzyskano na wysokiej klasy laptopie MacBook Pro w systemie Unix oraz na wysokiej klasy komputerze stacjonarnym z systemem Linux.

Jeśli prosisz o bardziej fizyczne wyjaśnienie sin, cos i tan, zastanów się, jak odnoszą się one do trójkątów prostokątnych. Rzeczywistą wartość liczbową cos (lambda) można znaleźć, tworząc trójkąt prostokątny, w którym jeden z kątów jest lambda, i dzieląc długość boku trójkąta przylegającego do lambda przez długość przeciwprostokątnej. Podobnie w przypadku grzechu użyj przeciwnej strony podzielonej przez przeciwprostokątną. W przypadku stycznej użyj przeciwnej strony podzielonej przez sąsiedni bok. Klasycznym memonicem do zapamiętania jest SOHCAHTOA (wymawiane socatoa).