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.
Odpowiedzi:
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ę:
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)
Zakres = -pi / 2 do + pi / 2, stopień 7 (4 terminy)
Zakres = -pi / 4 do + pi / 4, stopień 3 (2 terminy)
Zakres = -pi / 4 do + pi / 4, stopień 5 (3 terminy)
Zakres = -pi / 4 do + pi / 4, stopień 7 (4 terminy)
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).