Jak C oblicza sin () i inne funkcje matematyczne?

OK dzieciaki, czas na zawodowców.... Jest to jedna z moich największych skarg do niedoświadczonych inżynierów oprogramowania. Przychodzą w obliczaniu funkcji transcendentalnych od zera (używając szeregów Taylora) tak, jakby nikt nigdy wcześniej nie robił tych obliczeń w ich życiu. Nieprawda. Jest to dobrze zdefiniowany problem i został zgłoszony tysiące razy przez bardzo sprytnych inżynierów oprogramowania i sprzętu i ma dobrze zdefiniowane rozwiązanie. Zasadniczo większość funkcji transcendentalnych korzysta z Czebyszewa Wielomiany do ich obliczania. To, jakie wielomiany są używane, zależy od okoliczności. Po pierwsze, Biblią na ten temat jest książka" Computer Approximations " Hart and Cheney. W tej książce możesz zdecydować, czy masz adder sprzętowy, mnożnik, dzielnik itp. i zdecydować, które operacje są najszybsze. na przykład jeśli masz naprawdę szybki dzielnik, najszybszym sposobem obliczenia sinusa może być P1(x) / P2(X), gdzie P1, P2 są wielomianami Czebyszewa. Bez szybkiego dzielnika może być tylko P (x), gdzie P ma znacznie więcej terminów niż P1 lub P2....so byłoby wolniej. Pierwszym krokiem jest określenie sprzętu i jego możliwości. Następnie należy wybrać odpowiednią kombinację wielomianów Czebyszewa(zwykle ma postać cos(ax) = aP (x) dla Cosinus na przykład, gdzie p jest wielomianem Czebyszewa). Następnie decydujesz, jaką dokładność dziesiętną chcesz. np. jeśli chcesz 7 cyfr precyzji, poszukaj tego w odpowiedniej tabeli w książce, o której wspomniałem, i to ci da (dla precyzji = 7.33) liczba N = 4 i liczba wielomianowa 3502. N jest rzędu wielomianu (czyli p4.x^4 + p3.x^3 + p2.x^2 + p1.x + p0), ponieważ N = 4. Następnie wyszukujesz rzeczywistą wartość wartości p4, p3, P2, P1, P0 z tyłu książki pod 3502 (będą one w postaci zmiennoprzecinkowej). Następnie implementujesz swój algorytm w oprogramowaniu w postaci: (((p4.x + p3).x + p2).x + p1).x + p0 ....i tak można obliczyć cosinus do 7 miejsc po przecinku na tym sprzęcie.

Zauważ, że większość sprzętu implementacje operacji transcendentalnych w FPU zwykle obejmują niektóre mikrokody i operacje takie jak to (zależy od sprzętu). Wielomiany Czebyszewa są używane dla większości transcendentalnych, ale nie wszystkich. np. pierwiastek kwadratowy jest szybszy, aby użyć podwójnej iteracji metody Newtona Raphsona, używając najpierw tabeli wyszukiwania. Znowu ta książka "Computer Approximations" ci to powie.

Jeśli planujesz zaimplementować te funkcje, polecam każdemu, aby dostał kopię tej książki. Informatyka naprawdę jest to Biblia dla tego rodzaju algorytmów. Zauważ, że istnieją zestawy alternatywnych środków do obliczania tych wartości, takich jak Kordyliery itp., ale te wydają się być najlepsze dla konkretnych algorytmów, w których potrzebujesz tylko niskiej precyzji. Aby zagwarantować precyzję za każdym razem, wielomiany Czebyszewa są rozwiązaniem. Jak mówiłem, dobrze zdefiniowany problem. Został rozwiązany przez 50 lat teraz.....i tak to się robi.

Teraz, to powiedziawszy, są techniki, dzięki którym Czebyszew wielomiany mogą być użyte do uzyskania wyniku pojedynczej precyzji z wielomianem niskiego stopnia (jak przykład dla cosinusa powyżej). Następnie istnieją inne techniki interpolacji między wartościami w celu zwiększenia dokładności bez konieczności przechodzenia do znacznie większego wielomianu, takie jak "metoda dokładnych tabel Gal". Ta ostatnia technika jest tym, do czego odnosi się post odwołujący się do literatury ACM. Ale ostatecznie Wielomiany Czebyszewa są tym, co jest używane do uzyskania 90% drogi tam.

Enjoy.

Funkcje takie jak sinus i cosinus są zaimplementowane w mikrokodach wewnątrz mikroprocesorów. Na przykład układy Intela mają instrukcje montażu. Kompilator C wygeneruje kod, który wywoła te instrukcje montażu. (Natomiast kompilator Javy Nie Java ocenia funkcje Tryg w oprogramowaniu, a nie w sprzęcie, więc działa znacznie wolniej.)

Układy nie używają szeregów Taylora do obliczania funkcji Tryg, przynajmniej nie do końca. Przede wszystkim używają CORDIC, ale mogą również używać krótkich szeregów Taylora do polerowania wyniku CORDIC lub w szczególnych przypadkach, takich jak obliczanie sinusoidy z dużą dokładnością względną dla bardzo małych kątów. Aby uzyskać więcej wyjaśnień, zobacz tę odpowiedź StackOverflow .

Tak, istnieją również algorytmy programowe do obliczania sin. Zasadniczo obliczanie tego rodzaju rzeczy za pomocą komputera cyfrowego jest zwykle wykonywane za pomocą metod numerycznych , takich jak przybliżenie szeregu Taylora reprezentującego funkcję.

Metody numeryczne mogą przybliżać funkcje do dowolnej dokładności, a ponieważ ilość dokładności, którą masz w liczbie pływającej jest skończona, pasują one do tych zadań całkiem dobrze.

To skomplikowane pytanie. Procesor Intela z rodziny x86 posiada sprzętową implementację funkcji sin(), ale jest częścią FPU x87 i nie jest już używany w trybie 64-bitowym (gdzie zamiast niego używane są rejestry SSE2). W tym trybie używana jest implementacja oprogramowania.

Istnieje kilka takich implementacji. Jeden jest w fdlibm i jest używany w Javie. Z tego co wiem, implementacja glibc zawiera części fdlibm, oraz inne części dodane przez IBM.

Implementacje programowe funkcji transcendentalnych, takich jak sin() zazwyczaj używają przybliżeń wielomianami, często otrzymywanymi z szeregów Taylora.

Użyj szereg Taylora i spróbuj znaleźć związek między terminami serii, aby nie obliczać rzeczy ponownie i ponownie

Oto przykład cosinusa:

double cosinus(double x,double prec)
{
    double t , s ;
    int p;
    p = 0;
    s = 1.0;
    t = 1.0;
    while(fabs(t/s) > prec)
    {
        p++;
        t = (-t * x * x) / ((2 * p - 1) * (2 * p));
        s += t;
    }
    return s;}

Używając tego możemy uzyskać nowy termin sumy używając już używanego (unikamy czynnika i x^2p)

Wyjaśnienie http://img514.imageshack.us/img514/1959/82098830.jpg

Wielomiany Czebyszewa, jak wspomniano w innej odpowiedzi, są wielomianami, w których największa różnica między funkcją a wielomianem jest tak mała, jak to możliwe. To doskonały początek.

W niektórych przypadkach maksymalny błąd nie jest tym, co Cię interesuje, ale maksymalnym błędem względnym. Na przykład dla funkcji sinus, błąd w pobliżu x = 0 powinien być znacznie mniejszy niż dla większych wartości; chcesz mały błąd względny . Więc obliczyłbyś Czebyszewa wielomian dla sin x / x i mnożenie tego wielomianu przez x.

Następnie musisz dowiedzieć się, jak ocenić wielomian. Chcesz go ocenić w taki sposób, że wartości pośrednie są małe, a zatem błędy zaokrąglania są małe. W przeciwnym razie błędy zaokrąglania mogą stać się dużo większe niż błędy w wielomianie. A z funkcjami takimi jak funkcja sinus, jeśli jesteś nieostrożny to może być możliwe, że wynik, który obliczysz dla sin x jest większy niż wynik dla sin y nawet wtedy, gdy x

Na przykład sin x = X - x^3/6 + x^5 / 120-x^7 / 5040... Jeśli obliczysz naiwnie sin x = x * (1-x^2/6 + x^4/120-x^6/5040...), wtedy funkcja w nawiasach maleje i stanie się, że jeśli y jest kolejną większą liczbą DO x, to czasami sin y będzie mniejszy niż sin x. zamiast tego Oblicz sin x = x-x^3 *(1/6-x^2 / 120 + x^4/5040...) tam, gdzie nie może do tego dojść.

Przy obliczaniu wielomianów Czebyszewa zwykle trzeba zaokrąglać współczynniki, aby na przykład podwoić precyzję. Ale o ile wielomian Czebyszewa jest optymalny, to wielomian Czebyszewa ze współczynnikami zaokrąglonymi do podwójnej precyzji nie jest optymalnym wielomianem ze współczynnikami podwójnej precyzji!

Na przykład dla sin (x), gdzie potrzebne są współczynniki dla x, X^3, x^5, x^7 itd. wykonujesz następujące czynności: Oblicz najlepszy przybliżenie sin x z wielomianem (ax + bx^3 + cx^5 + dx^7) z większą niż podwójną precyzją, następnie zaokrąglenie a do podwójnej precyzji, dając A. różnica między a i A byłaby dość duża. Teraz Oblicz najlepsze przybliżenie (sin x-Ax) z wielomianem (b x^3 + cx^5 + dx^7). Otrzymujesz różne współczynniki, ponieważ dostosowują się do różnicy między a i A. Okrągły b do podwójnej precyzji B. Następnie przybliżony (sin x-Ax-Bx^3) z wielomianem CX^5 + dx^7 i tak dalej. Będziesz uzyskaj wielomian, który jest prawie tak dobry jak oryginalny wielomian Czebyszewa, ale znacznie lepszy niż Czebyszew zaokrąglony do podwójnej precyzji.

Następnie należy wziąć pod uwagę błędy zaokrąglania w wyborze wielomianu. Znalazłeś wielomian z minimalnym błędem w wielomianie ignorując błąd zaokrąglania, ale chcesz zoptymalizować wielomian plus błąd zaokrąglania. Gdy masz wielomian Czebyszewa, możesz obliczyć granice dla błędu zaokrąglania. Powiedzmy, że f (x) jest twoją funkcją, P (x) jest wielomianem, A E (x) jest błędem zaokrąglania. Nie chcesz optymalizować / f (x) - P (x) |, chcesz optymalizować | f (x) - P (x) + / - E (x) |. Otrzymasz nieco inny wielomian, który stara się utrzymać błędy wielomianowe w dół, gdzie błąd zaokrąglania jest duży, i rozluźnia błędy wielomianowe trochę, gdzie błąd zaokrąglania jest mały.

Wszystko to sprawi, że błędy zaokrąglania będą miały wartość co najwyżej 0,55 razy niż ostatni bit, gdzie +, -,*, / będą miały wartość co najwyżej 0,50 razy ostatni kawałek.

Dla sin w szczególności, użycie rozszerzenia Taylora dałoby:

Sin (x): = x - x^3/3! + x^5/5! - x^7/7! + ... (1)

Dodawałbyś terminy, dopóki różnica między nimi nie będzie niższa niż akceptowany poziom tolerancji lub tylko dla skończonej liczby kroków (szybciej, ale mniej precyzyjnie). Przykładem może być coś w stylu:

float sin(float x)
{
  float res=0, pow=x, fact=1;
  for(int i=0; i<5; ++i)
  {
    res+=pow/fact;
    pow*=-1*x*x;
    fact*=(2*(i+1))*(2*(i+1)+1);
  }

  return res;
}

Uwaga: (1) działa z powodu aproksymacji sin (x)=x dla małych kątów. Dla większych kątów trzeba obliczyć coraz więcej warunki, aby uzyskać akceptowalne wyniki. Możesz użyć argumentu while I kontynuować dla pewnej dokładności:

double sin (double x){
    int i = 1;
    double cur = x;
    double acc = 1;
    double fact= 1;
    double pow = x;
    while (fabs(acc) > .00000001 &&   i < 100){
        fact *= ((2*i)*(2*i+1));
        pow *= -1 * x*x; 
        acc =  pow / fact;
        cur += acc;
        i++;
    }
    return cur;

}

Rzeczywista implementacja funkcji bibliotecznych zależy od konkretnego kompilatora i / lub dostawcy bibliotek. Czy jest to wykonywane w sprzęcie czy oprogramowaniu, czy jest to rozszerzenie Taylora czy nie itp., będzie się różnić.

Zdaję sobie sprawę, że to absolutnie żadna pomoc.

Odnośnie funkcji trygonometrycznych jak sin(), cos(),tan() po 5 latach nie wspomniano o ważnym aspekcie wysokiej jakości funkcji Tryg: redukcja zakresu .

Wczesne biblioteki używały rozszerzonych precyzyjne lub wykonane programowanie w celu uzyskania wysokiej jakości wyników, ale nadal w ograniczonym zakresie double. Gdy żądano dużej wartości, takiej jak sin(pow(2,30)), wyniki były bez znaczenia lub 0.0 i być może z flagą błędu ustawioną na coś w rodzaju TLOSS całkowita utrata precyzji lub PLOSS częściowa utrata precyzji.

Dobry zakres redukcja dużych wartości do przedziału jak-π do π jest trudnym problemem, który konkuruje z wyzwaniami podstawowej funkcji Tryg, jak sin(), siebie.

Dobrym raportem jest redukcja argumentów dla ogromnych argumentów: dobry do ostatniego bitu (1992). Dobrze obejmuje ten problem: omawia potrzeby i jak było na różnych platformach (SPARC, PC, HP, 30+ inne) i zapewnia algorytm rozwiązania, który daje wyniki Jakości Dla {34]}wszystkich double od -DBL_MAX do DBL_MAX.

Jeśli oryginalne argumenty są w stopniach, ale mogą mieć dużą wartość, użyj fmod() najpierw dla lepszej precyzji. Dobra fmod() Wola wprowadź brak błędu i w ten sposób zapewnij doskonałą redukcję zasięgu.

// sin(degrees2radians(x))
sin(degrees2radians(fmod(x, 360.0))); // -360.0 <= fmod(x,360) <= +360.0

Różne trygenty i remquo() oferują jeszcze większą poprawę. Próbka: sind()

Są one zazwyczaj implementowane w oprogramowaniu i w większości przypadków nie będą używać odpowiednich wywołań sprzętowych (czyli aseembly). Jednak, jak zauważył Jason, są one specyficzne dla implementacji.

Zauważ, że te procedury programowe nie są częścią źródeł kompilatora, ale raczej znajdą się w bibliotekach takich jak clib, czy glibc dla kompilatora GNU. Zobacz http://www.gnu.org/software/libc/manual/html_mono/libc.html#Trig-Functions

Jeśli chcesz większa kontrola, należy dokładnie ocenić, co trzeba dokładnie. Niektóre z typowych metod to interpolacja tabel, wywołanie asemblacji (które często jest powolne) lub inne schematy aproksymacji, takie jak Newton-Raphson dla pierwiastków kwadratowych.

Jeśli chcesz implementacji w oprogramowaniu, a nie w sprzęcie, miejscem do szukania ostatecznej odpowiedzi na to pytanie jest Rozdział 5 Numerical Recipes. Moja kopia jest w pudełku, więc nie mogę podać szczegółów, ale wersja skrócona (jeśli dobrze pamiętam) jest taka, że bierzesz tan(theta/2) jako swoją prymitywną operację i obliczasz Pozostałe stamtąd. Obliczenia wykonywane są z aproksymacją szeregową, ale jest to coś, co zbiega się znacznie szybciej niż Taylor seria.

Przykro mi, że nie mogę pamiętać więcej bez wyciągnięcia ręki na książkę.

Jak Wiele osób zauważyło, jest to zależne od implementacji. Ale o ile rozumiem twoje pytanie, interesowało Cię prawdziwe oprogramowanie implementacja funkcji matematycznych, ale nie udało Ci się go znaleźć. Jeśli tak jest, to tutaj jesteś:

• Pobierz kod źródłowy glibc z http://ftp.gnu.org/gnu/glibc /
• spójrz na plik dosincos.c znajdujący się w rozpakowany katalog główny glibc\sysdeps \ ieee754 \ dbl-64
• Podobnie można znaleźć implementacje reszty biblioteki matematycznej, po prostu poszukaj pliku o odpowiedniej nazwie

Możesz również przyjrzeć się plikom z rozszerzeniem .tbl, ich zawartość to nic innego jak olbrzymie tabele wstępnie obliczonych wartości różnych funkcji w postaci binarnej. Dlatego implementacja jest tak szybka: zamiast obliczać wszystkie współczynniki dowolnej serii, której używają, po prostu wykonują szybkie wyszukiwanie, które jest znacznie szybsze. BTW, używają Krawca szereg do obliczania sinus i cosinus.

Postaram się odpowiedzieć w przypadku sin() w programie C, skompilowanym z kompilatorem C GCC na obecnym procesorze x86 (powiedzmy Intel Core 2 Duo).

W języku C standardowa biblioteka C zawiera wspólne funkcje matematyczne, nie zawarte w samym języku (np. pow, sin i cos odpowiednio dla mocy, sinusa i cosinusa). Których nagłówki zawarte są w math.h .

Teraz w systemie GNU/Linux funkcje bibliotek są dostarczane przez glibc (Biblioteka GNU libc lub GNU C). Ale kompilator GCC chce, żebyś linkował do biblioteki matematycznej (libm.so) użycie znacznika -lm kompilatora do włączenia tych funkcji matematycznych. Nie jestem pewien, dlaczego nie jest częścią standardowej biblioteki C. będą to wersje programowe funkcji zmiennoprzecinkowych, czyli "soft-float".

Pomijając: powód oddzielenia funkcji matematycznych jest historyczny i miał jedynie na celu zmniejszenie rozmiaru programów wykonywalnych w bardzo stare systemy uniksowe, prawdopodobnie przed udostępnieniem bibliotek współdzielonych, o ile mi wiadomo.

Teraz kompilator może zoptymalizować standardową funkcję biblioteki C sin() (dostarczoną przez libm.so), która zostanie zastąpiona wywołaniem natywnej instrukcji do wbudowanej w procesor / FPU funkcji sin (), która istnieje jako instrukcja FPU (FSIN dla x86/x87) na nowszych procesorach, takich jak seria Core 2 (jest to poprawne prawie tak daleko jak i486DX). To zależy od flagi optymalizacji przekazany do kompilatora gcc. JeĹ "li kompilator zostaĹ' poproszony o napisanie kodu, ktĂłry zostaĹ 'uruchomiony na dowolnym procesorze i386 lub nowszym, Nie dokonaĹ' by takiej optymalizacji. Znacznik -mcpu=486 informowałby kompilator, że dokonanie takiej optymalizacji jest bezpieczne.

Teraz, jeśli program wykonałby wersję programową funkcji sin (), zrobiłby to w oparciu o CORDIC (cyfrowy komputer rotacji współrzędnych) lub algorytm BKM , lub bardziej prawdopodobnie tabelę lub szereg mocy obliczenie, które jest obecnie powszechnie stosowane do obliczania takich funkcji transcendentalnych. [Src: http://en.wikipedia.org/wiki/Cordic#Application]

Wszelkie Najnowsze (od 2,9 x ok.) wersja gcc oferuje również wbudowaną wersję sin, __builtin_sin(), która zostanie użyta do zastąpienia standardowego wywołania do wersji biblioteki C, jako optymalizacja.

Jestem pewien, że jest to jasne jak błoto, ale mam nadzieję, że daje więcej informacji, niż się spodziewałeś, i wiele punktów skoków do dowiedz się więcej sam.

Nie ma to jak trafić do źródła i zobaczyć, jak ktoś zrobił to w bibliotece w powszechnym użyciu; przyjrzyjmy się w szczególności jednej implementacji Biblioteki C. Wybrałem uLibC.

Oto funkcja sin:

Http://git.uclibc.org/uClibc/tree/libm/s_sin.c

, który wygląda na to, że obsługuje kilka specjalnych przypadków, a następnie przeprowadza redukcję argumentów, aby zmapować dane wejściowe do zakresu [- pi / 4, pi / 4], (dzieląc argument na dwie części, dużą część i ogonem) przed wywołaniem

Http://git.uclibc.org/uClibc/tree/libm/k_sin.c

Który następnie działa na tych dwóch częściach. Jeśli nie ma ogona, przybliżona odpowiedź jest generowana za pomocą wielomianu stopnia 13. Jeśli jest ogon, otrzymujesz mały dodatek korygujący oparty na zasadzie, że sin(x+y) = sin(x) + sin'(x')y

Gdy taka funkcja jest oceniana, to na pewnym poziomie najprawdopodobniej występuje albo:

• Tabela wartości interpolowanych (dla szybkich, niedokładnych aplikacji - np. grafiki komputerowej)
• Ocena szeregu zbieżnego do pożądanej wartości --- prawdopodobnienie szereg Taylora, bardziej prawdopodobne coś opartego na wymyślnej kwadraturze, takiej jak Clenshaw-Curtis.

Jeśli nie ma wsparcia sprzętowego, kompilator prawdopodobnie używa tego ostatniego metoda, emitująca tylko kod asemblera (bez symboli debugowania), zamiast używać biblioteki c - - - co utrudnia śledzenie rzeczywistego kodu w debuggerze.

Jeśli chcesz przyjrzeć się rzeczywistej implementacji GNU tych funkcji w C, Sprawdź najnowszy trunk glibc. Zobacz bibliotekę GNU C.

Obliczanie Sinus / Cosinus / tangent jest w rzeczywistości bardzo łatwe do wykonania za pomocą kodu przy użyciu szeregów Taylora. Samodzielne pisanie zajmuje jakieś 5 sekund.

Cały proces można podsumować tym równaniem tutaj: http://upload.wikimedia.org/math/5/4/6/546ecab719ce73dfb34a7496c942972b.png

Oto kilka procedur, które napisałem dla C:

double _pow(double a, double b) {
    double c = 1;
    for (int i=0; i<b; i++)
        c *= a;
    return c;
}

double _fact(double x) {
    double ret = 1;
    for (int i=1; i<=x; i++) 
        ret *= i;
    return ret;
}

double _sin(double x) {
    double y = x;
    double s = -1;
    for (int i=3; i<=100; i+=2) {
        y+=s*(_pow(x,i)/_fact(i));
        s *= -1;
    }  
    return y;
}
double _cos(double x) {
    double y = 1;
    double s = -1;
    for (int i=2; i<=100; i+=2) {
        y+=s*(_pow(x,i)/_fact(i));
        s *= -1;
    }  
    return y;
}
double _tan(double x) {
     return (_sin(x)/_cos(x));  
}

Nie używaj serii Taylora. Wielomiany Czebyszewa są zarówno szybsze, jak i dokładniejsze, jak wskazało kilka osób powyżej. Oto implementacja (oryginalnie z ROM-u ZX Spectrum): https://albertveli.wordpress.com/2015/01/10/zx-sine/

If you want sin then asm volatile("fsin" : "=t"(vsin) : "0"(xrads)); if you want cos then asm volatile("fcos" : "=t"(vcos): "0"(xrads)); jeśli chcesz sqrt to asm volatile("fsqrt" : "=t"(vsqrt) : "0"(wartość)); więc po co używać niedokładnego kodu, gdy zrobią to instrukcje maszynowe.