Napisałem kodu jednocześnie temu, która polegała obliczyć bez korzystania z funkcji biblioteki. Wczoraj sprawdzałem stary kod i starałem się, aby był jak najszybciej (i poprawiony). Oto moja dotychczasowa próba:
const double ee = exp(1);
double series_ln_taylor(double n){ /* n = e^a * b, where a is an non-negative integer */
double lgVal = 0, term, now;
int i, flag = 1;
if ( n <= 0 ) return 1e-300;
if ( n * ee < 1 )
n = 1.0 / n, flag = -1; /* for extremely small n, use e^-x = 1/n */
for ( term = 1; term < n ; term *= ee, lgVal++ );
n /= term;
/* log(1 - x) = -x - x**2/2 - x**3/3... */
n = 1 - n;
now = term = n;
for ( i = 1 ; ; ){
lgVal -= now;
term *= n;
now = term / ++i;
if ( now < 1e-17 ) break;
}
if ( flag == -1 ) lgVal = -lgVal;
return lgVal;
}
Tutaj staram się znaleźć tak, e właśnie nad n, a następnie dodać wartość logarytmu z n , który jest mniejszy niż 1. W tym momencie, dla ekspansji TayloralOg(1-x)może być stosowany bez obawy.
Ostatnio zainteresowałem się analizą numeryczną i dlatego nie mogę przestać zadawać pytania, o ile szybciej ten segment kodu można uruchomić w praktyce, a jednocześnie jest wystarczająco poprawny? Czy muszę przejść na inne metody, na przykład używając ciągłego ułamka, takiego jak ten ?
funkcję dostarczaną przez C standardowej biblioteki jest prawie 5.1 razy szybciej niż w tym wykonaniu.
AKTUALIZACJA 1 : Korzystając z hiperbolicznej serii arctan wspomnianej w Wikipedii , obliczenia wydają się prawie 2,2 razy wolniejsze niż standardowa funkcja dziennika biblioteki C. Chociaż nie sprawdziłem dokładnie wydajności, a w przypadku większych liczb moja obecna implementacja wydaje się NAPRAWDĘ powolna. Chcę sprawdzić zarówno moją implementację pod kątem związanego z błędem, jak i średniego czasu dla szerokiego zakresu liczb, jeśli mogę. Oto mój drugi wysiłek.
double series_ln_arctanh(double n){ /* n = e^a * b, where a is an non-negative integer */
double lgVal = 0, term, now, sm;
int i, flag = 1;
if ( n <= 0 ) return 1e-300;
if ( n * ee < 1 ) n = 1.0 / n, flag = -1; /* for extremely small n, use e^-x = 1/n */
for ( term = 1; term < n ; term *= ee, lgVal++ );
n /= term;
/* log(x) = 2 arctanh((x-1)/(x+1)) */
n = (1 - n)/(n + 1);
now = term = n;
n *= n;
sm = 0;
for ( i = 3 ; ; i += 2 ){
sm += now;
term *= n;
now = term / i;
if ( now < 1e-17 ) break;
}
lgVal -= 2*sm;
if ( flag == -1 ) lgVal = -lgVal;
return lgVal;
}
Każda sugestia lub krytyka jest mile widziana.
double series_ln_better(double n){ /* n = e^a * b, where a is an non-negative integer */
double lgVal = 0, term, now, sm;
int i, flag = 1;
if ( n == 0 ) return -1./0.; /* -inf */
if ( n < 0 ) return 0./0.; /* NaN*/
if ( n < 1 ) n = 1.0 / n, flag = -1; /* for extremely small n, use e^-x = 1/n */
/* the cutoff iteration is 650, as over e**650, term multiplication would
overflow. For larger numbers, the loop dominates the arctanh approximation
loop (with having 13-15 iterations on average for tested numbers so far */
for ( term = 1; term < n && lgVal < 650 ; term *= ee, lgVal++ );
if ( lgVal == 650 ){
n /= term;
for ( term = 1 ; term < n ; term *= ee, lgVal++ );
}
n /= term;
/* log(x) = 2 arctanh((x-1)/(x+1)) */
n = (1 - n)/(n + 1);
now = term = n;
n *= n;
sm = 0;
/* limiting the iteration for worst case scenario, maximum 24 iteration */
for ( i = 3 ; i < 50 ; i += 2 ){
sm += now;
term *= n;
now = term / i;
if ( now < 1e-17 ) break;
}
lgVal -= 2*sm;
if ( flag == -1 ) lgVal = -lgVal;
return lgVal;
}
źródło
frexpOdpowiedź Kirilla dotyczyła już wielu istotnych kwestii. Chciałbym rozwinąć niektóre z nich w oparciu o praktyczne doświadczenia w projektowaniu bibliotek matematycznych. Uwaga z góry: projektanci bibliotek matematycznych zwykle używają każdej opublikowanej optymalizacji algorytmicznej, a także wielu optymalizacji specyficznych dla maszyny, z których nie wszystkie zostaną opublikowane. Kod często będzie pisany w języku asemblera, zamiast używać skompilowanego kodu. Jest zatem mało prawdopodobne, aby prosta i skompilowana implementacja osiągnęła ponad 75% wydajności istniejącej wysokiej jakości implementacji biblioteki matematycznej, przy założeniu identycznych zestawów funkcji (dokładność, obsługa przypadków specjalnych, raportowanie błędów, obsługa trybu zaokrąglania).
Dokładność jest zazwyczaj oceniana przez porównanie z referencją o wyższej precyzji (innej firmy). Funkcje pojedynczej argumentacji o pojedynczej precyzji można łatwo przetestować wyczerpująco, inne funkcje wymagają testowania za pomocą (ukierunkowanych) losowych wektorów testowych. Oczywiście nie można obliczyć nieskończenie dokładnych wyników odniesienia, ale badania dylematu twórcy tabeli sugerują, że dla wielu prostych funkcji wystarczy obliczyć odniesienie z dokładnością około trzykrotnie większą niż precyzja docelowa. Zobacz na przykład:
Vincent Lefèvre, Jean-Michel Muller, „Najgorsze przypadki prawidłowego zaokrąglania funkcji elementarnych w podwójnej precyzji”. W postępowaniu 15 Sympozjum IEEE na temat arytmetyki komputerowej , 2001,111-118). (preprint online)
Pod względem wydajności należy odróżnić optymalizację pod kątem opóźnień (ważne, gdy patrzy się na czas wykonywania operacji zależnych) od optymalizacji pod kątem przepustowości (istotnej przy rozważaniu czasu wykonania niezależnych operacji). W ciągu ostatnich dwudziestu lat rozpowszechnianie sprzętowych technik paralelizacji, takich jak równoległość na poziomie instrukcji (np. Procesory superskalarne, procesory poza kolejnością), równoległość na poziomie danych (np. Instrukcje SIMD) i równoległość na poziomie wątku (np. Hiperwątkowość, procesory wielordzeniowe) doprowadziły do położenia nacisku na przepustowość obliczeniową jako bardziej odpowiednią metrykę.
Połączona operacja wielokrotnego dodawania ( FMA ), po raz pierwszy wprowadzona przez IBM 25 lat temu, a teraz dostępna we wszystkich głównych architekturach procesorów, jest kluczowym elementem składowym nowoczesnych implementacji bibliotek matematycznych. Zapewnia redukcję błędów zaokrąglania, daje ograniczoną ochronę przed odejmowaniem anulowania i znacznie upraszcza arytmetykę podwójnego podwójnego .
C99log()C99fma()źródło