Czy obliczenie 2 ** x jest szybsze niż exp (x)?

Wybacz naiwność, która będzie oczywista w sposobie zadawania tego pytania, a także w tym, że zadaję to pytanie.

Matematycy zwykle używają ponieważ jest to najprostsza / najładniejsza baza teoretyczna (ze względu na rachunek różniczkowy). Ale komputery wydają się robić wszystko w systemie binarnym, więc czy na komputerze jest to szybsze niż ?$\exp$2**xMath::exp(x)

Ponieważ jest to CS, a nie Stackoverflow, zakładam, że zadajesz pytanie dotyczące analizy numerycznej, a (dla uproszczenia) w szczególności zmiennoprzecinkowy IEEE-754. W takim przypadku odpowiedź na twoje pytanie częściowo zależy od tego, co rozumiesz przez „łatwiej”, a częściowo od szczegółów systemu.

Żaden współczesny procesor, o którym wiem, nie ma wbudowanej instrukcji, która wykonuje dokładnie to, czego można się spodziewać po operacji (którą odtąd nazywamy , jej zwykła nazwa w C) lub 2 x ( ). Oba są realizowane za pomocą funkcji bibliotecznych.$e^x$exp$2^x$exp2

Podobnie jak w przypadku wszystkich metod numerycznych operacji transcendentalnych, należy rozważyć kilka szczególnych przypadków:

exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

Jest jednak jeszcze jedna rzecz, która sprawia, że ​​problem jest nieco mniej skomplikowany: użyteczna domena jest dość mała. Dla binary32, exp(x)niedomiarów jeśli lub więcej, przelewa jeśli x > 88,7 lub więcej. Nietypowo dla transcendentalnych operacji, możemy też ignorować sprawy słabszą od prawidłowej, ponieważ jest nie do odróżnienia od jeśli jest nienormalny. Wszystkie powyższe są również prawdziwe , z tą różnicą, że domena jest nieco inna.$x < -104$$x > 88.7$exp(x)1.0xexp2

Twoja intuicja jest słuszna, ponieważ większość implementacji oblicza . Jednak koszt tego pomnożenia przez jest trywialny w porównaniu z resztą komputerów . Typowa metoda wykorzystuje wstępnie obliczoną tabelę z elementami :$e^x = 2^{x/\ln 2}$$\frac{1}{\ln 2}$exp2$K$

gdzie jest częścią całkowitą , tabela zawiera wartości dla wszystkich w zakresie , a jest pewną wielomianową aproksymacją dox T 2 j / K j [ 0 , K ) $n$$x$$T$$2^{j/K}$$j$$[0,K)$$P$ (kwartalna jest wystarczająca dla binarnego32) w zakresie [ 0 , $2^x$. 2nczęść jest tania, ponieważ jest to po prostu manipulowanie wykładnik. Tto tabela przeglądowa. Pjestwięcprawdopodobnie kosztowną częścią operacji.$[0,\frac{1}{K})$$2^n$$T$$P$

Należy zwrócić uwagę na kompletność, że procesory Intel x86 zawierają instrukcję o nazwie f2xm1, która oblicza dla x w zakresie [ - 1 , 1 ] . Jednak w przypadku nowoczesnego procesora jest to dość droga i niepotokowa instrukcja, dlatego bardzo odradzamy jej używanie. Jak słusznie odnotowano w podręczniku Intel Optimization Reference Manual, sekcja 3.8.5:$2^x-1$$x$$[-1,1]$

Chociaż x87 obsługuje instrukcje transcendentalne, implementacja funkcji transcendentalnej w bibliotece oprogramowania może być szybsza w wielu przypadkach.

Edycja: W komentarzach wskazano, że powinienem wyjaśnić niektóre z nowych terminów stosowanych w IEEE 754-2008. Niektóre języki zmieniły się od 1985 i 1987 r., A większość ludzi jest znacznie bardziej zaznajomiona ze starym żargonem.

Terminy „binary32” i „binary64” to nowe nazwy 32-bitowych i 64-bitowych binarnych liczb zmiennoprzecinkowych, które stary standard nazywał odpowiednio „pojedynczym” i „podwójnym”.

Termin „liczba nienormalna” zastępuje poprzedni termin „liczba normalna” lub „liczba denormalizowana” .

2**x$2^x$<<1 << x

Jeśli 2**xjest funkcja na liczbach całkowitych, to zgadzam się z odpowiedzią Stephena, przesunięcie jest tańsze. Ale zazwyczaj widzę to jako 2^xi, **aby wskazać potęgowanie zmiennoprzecinkowe. W tym przypadku oczekiwałbym podobnej wydajności pomiędzy **i ^ponieważ oba expi pow(podstawowa operacja dla **) są transcendentalnymi operacjami aproksymacji.

Ponieważ 2 ^ x = e ^ (x * ln 2) i e ^ x = 2 ^ (x * log2 (e)), nie spodziewałbyś się dużej różnicy.

Dla x bliskiego zera zwykle używa się wielomianu e ^ x = 1 + x + x ^ 2/2 + x ^ 3/6 ..., ładnie zoptymalizowanego do odcięcia tak szybko, jak to możliwe, przy zachowaniu małego błędu zaokrąglania . Najwyraźniej 2 ^ x jest małym, trochę wolniejszym do obliczenia. „x bliskie 0” to zwykle wartości x, gdzie sqrt (1/2) <= e ^ x <= sqrt (2). Ograniczenie zakresu x zapewnia, że ​​stopień wielomianu nie musi być wybierany zbyt wysoko.

W przypadku większego x zwykle oblicza się 2 ^ x, pozwalając x = x '+ x' ', gdzie x' jest liczbą całkowitą, a -0,5 <= x '' <= 0,5. 2 ^ x 'byłoby następnie obliczone przez skonstruowanie liczby zmiennoprzecinkowej z odpowiednim wzorem bitowym, a 2 ^ x' 'przy użyciu metody e ^ x dla małego x. Tutaj 2 ^ x jest trochę szybszy. Ponadto, jeśli x jest duże (powiedzmy x = 100,3), samo pomnożenie x przez log2 (e) wprowadziłoby nieakceptowalny błąd zaokrąglenia (ponieważ jest o wiele mniej bitów ułamkowych), więc należy bardziej uważać.

I miejmy nadzieję, że dobra funkcja biblioteczna zadba o to, aby za każdym razem x <= y, e ^ x <= e ^ y i 2 ^ x <= 2 ^ y, bez względu na błędy zaokrąglania. Osiągnięcie tego rodzaju rzeczy może być trudne.

Musisz zrozumieć, że matematyka na komputerze jest wykonywana na różne sposoby przez różne oprogramowanie, miejmy nadzieję, że znajdziesz spójne odpowiedzi. Patrząc na większość oprogramowania, myślę, że komputery zachowują się jak dobrze - komputery i obliczą odpowiedź na długi czas nawet dla takich jak 0 ^ 0. Problem polega na tym, że przypadki szczególne obejmują „rozpoznanie”, które nie występuje za darmo w komputerach cyfrowych. Oznacza to, że tylko w tych przypadkach, w których uzyskanie odpowiedzi przyspieszy „najbardziej”, nastąpi optymalizacja. Ale w takich przypadkach nastąpi to wyjątkowo dobrze. Należy również pamiętać, że może być konieczne dokonanie kilku różnych rozpoznań, aby uzyskać właściwą odpowiedź. Nazywa się to poziomami optymalizacji prędkości i stało się to w maksymalnym profesjonalnym stopniu w oparciu o większość oprogramowania zwanego GNU „C”. Jest tak, ponieważ tutaj drobne różnice w czasie działania oprogramowania i oprogramowania i maszyny na maszynie są tam używane jako wartości akceptacji jakości. W innych interpretatorach zwykle tylko wtedy, gdy występuje „flaga zerowa”, ponieważ efekt uboczny poprzednich obliczeń przyspieszy rozpoznanie. takie jak 0 * x => C0.