Jak komputery obliczają wartości grzechu? [Zamknięte]

28

Jak komputer oblicza wartość grzechu? Logicznie, kiedy o tym myślę, jedynym pozornym sposobem jest zapisanie wielu wartości grzechu w pamięci, a gdy wartość grzechu musi zostać „obliczona”, po prostu ściągnie dane z określonego adresu pamięci. (Np. Sin (x) wyciągnij dane z adresu pamięci zawierającego wartość sin (x)) Wydaje się, że to jedyny możliwy sposób, aby to zrobić. Czy jest funkcja, która może być użyta do obliczenia grzechu wartości? Naprawdę próbuję zapytać, jak komputer oblicza grzech na poziomie podstawowym. Czy istnieje sposób na przybliżenie wartości grzechu przy użyciu innej funkcji złożonej z bardziej „podstawowych” operacji, a ALU byłby w stanie wykonać wiele „podstawowych” operacji w celu przybliżenia wartości grzechu, czy może po prostu wyciąga wartości z pamięci?

zack1544
źródło
10
Google „CORDIC”. Google „seria Taylor”. A twoje myśli o pamięci nie są jasne.
Eugene Sh.
8
Metoda „pamięci” jest często stosowaną techniką optymalizacji (nazwa to „tablica przeglądowa”). Ale nie, początkowo komputer go nie ma. Ale jeśli kiedykolwiek zastanawiasz się, jak komputer oblicza <placeholder>, Google „ <placeholder>algorytm obliczeniowy”. W większości przypadków działa lepiej niż w przypadku SE.
Eugene Sh.
5
Oprócz CORDIC i Taylors ', upewnij się, że szukasz również Czebyszewa połączonego z nieliniowymi technikami minimax. Taylor ogranicza średni błąd, podczas gdy Czeczejew ogranicza maksymalny błąd i szybciej się zamyka. Minimax jest potrzebny, ponieważ stałe nie są nieskończenie precyzyjne, podobnie jak operacje. I musisz wykorzystać symetrie, jak szalone!
jonk
3
Czy zdajesz sobie sprawę, że istnieje szereg, którego można używać do obliczania grzechu, podobnie jak w przypadku cos, logów, wykładników, pi, pierwiastków kwadratowych itp.
Andy alias
2
Oczywiście możesz mieć zawartość pamięci komputera „na pierwszym miejscu” - jak myślisz, jak uruchamiają się komputery? Wartości początkowe można podłączyć do obwodu, wbudować w komórki pamięci tylko do odczytu lub warstwy metalizujące IC, wypalić w bezpiecznikach, przechowywać jako ładunek uwięziony, a także odczytywać z dysku, taśmy perforowanej lub przełączników przełączających - dowolną metodą przydatną dla oprogramowania jest w zasadzie użyteczny także w przypadku tabel obliczanych wstępnie, a w rzeczywistości wiele algorytmów wymaga różnych stałych. To, co najlepsze, naprawdę musi zostać określone na podstawie wymagań, technologii, a nawet zasobów, które pozostały po innych potrzebach.
Chris Stratton,

Odpowiedzi:

30

Zazwyczaj funkcje sin (x) o wysokiej rozdzielczości byłyby implementowane za pomocą algorytmu CORDIC (COrdiate Rotation DIgital Computer), co można osiągnąć za pomocą niewielkiej liczby iteracji przy użyciu tylko przesunięć i dodawania / odejmowania oraz małej tabeli odnośników. Oryginalny papier CORDIC Computing Technika Jack Volder jest od 1959 roku działa również ładnie gdy realizowane ze sprzętem w FPGA (i podobny algorytm byłyby realizowane w FPU sprzętu dla tych Micros, które mają FPU).

W przypadku niższej rozdzielczości, na przykład w celu utworzenia zsyntetyzowanej fali sinusoidalnej dla falownika lub silnika VFD (przemiennik częstotliwości), tablica przeglądowa (LUT) z interpolacją lub bez niej działa dobrze. Konieczne jest tylko przechowywanie wartości dla jednej ćwiartki fali sinusoidalnej ze względu na symetrię.

Jak wskazuje @Temlib, algorytmy stosowane we współczesnych FPU wykorzystują redukcję zasięgu, a następnie ocenę za pomocą algorytmu Remeza w celu ograniczenia maksymalnego błędu bezwzględnego. Więcej można znaleźć w tym artykule Intela Formalna weryfikacja funkcji trygonometrycznych zmiennoprzecinkowych .

Spehro Pefhany
źródło
2
CORDIC służy raczej do konwersji sprzętowej funkcji stałej (jego pierwsza historyczna aplikacja). W przypadku komputera z układem FPU aproksymacje wielomianowe są szybsze i bardziej odpowiednie, ponieważ ponownie wykorzystują istniejące operatory arytmetyczne zamiast specjalnej maszyny CORDIC do przenoszenia i dodawania.
TEMLIB
1
@TEMLIB Tak, to ważny punkt, dodam to do odpowiedzi. CORDIC wykorzystano również w pierwszych kalkulatorach naukowych, takich jak HP-35.
Spehro Pefhany
Według mojej wiedzy, CORDIC miał swoją pierwszą implementację sprzętową w kalkulatorze biurkowym HP 9100A. Miał kartę obwodu drukowanego o powierzchni około kwadratu, pokrytą diodami, która służyła jako pamięć ROM przechowująca parametry używane przez algorytmy CORDIC.
Hot Licks,
@HotLicks - nie miałbyś racji, CORDIC został opracowany i używany w komputerze nawigacyjnym podczas lotu prawie dziesięć lat przed HP 9100A.
Chris Stratton
@ChrisStratton - Poprawiłem się.
Hot Licks,
14

Większość komputerowych bibliotek wyzwalaczy opiera się na przybliżeniach wielomianowych , co zapewnia najlepszą równowagę między szybkością a dokładnością. Na przykład kilkanaście operacji mnożenia i dodawania / odejmowania wystarcza do uzyskania pełnej dokładności pojedynczej precyzji dla sinusu i cosinusa.

Dave Tweed
źródło