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

12

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ż ?exp2**xMath::exp(x)

izomorfizmy
źródło
7
O jakim numerze mówisz? Liczba całkowita o dowolnym rozmiarze? Zmienny punkt zmiennoprzecinkowy? Zmienna zmiennoprzecinkowa o precyzji arbitralnej?
Gilles „SO- przestań być zły”,
@Gilles To dobra uwaga. Nie zdawałem sobie sprawy, że różnica była ważna.
izomorfizm
3
Widziałem na niektórych kalkulatorach kieszonkowych Casio, że log i moc liczby innej niż e są znacznie wolniejsze niż ln / exp
phuclv
2
Aby zaryzykować bycie bezczelnym, czy próbowałeś mierzyć ich czas i sprawdzić, który jest szybszy? Czy mówisz o prędkości w sensie złożoności ? O(f(n))
jmite
1
Język jest odpowiedzialny za wybór najszybszego sposobu i wykona w nim dobrą robotę. Tylko w przypadku, gdy wymagana jest najwyższa prędkość, a pomiary wykazały, że ma to znaczenie dla wydajności, jeśli martwisz się o tego rodzaju rzeczy
vonbrand

Odpowiedzi:

18

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.exexp2xexp2

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<104x>88.7exp(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 :ex=2x/ln2 K.1ln2exp2K

exp2(x)=2n×T[j]×P(y)

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 ) PnxT2j/Kj[0,K)P (kwartalna jest wystarczająca dla binarnego32) w zakresie [ 0 , 12x. 2nczęść jest tania, ponieważ jest to po prostu manipulowanie wykładnik. Tto tabela przeglądowa. Pjestwięcprawdopodobnie kosztowną częścią operacji.[0,1K)2nTP

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:2x1x[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” .

Pseudonim
źródło
kiedy mówisz „subnormalny” - wyraźnie nie masz na myśli „sub-gaussowskiego”; masz na myśli „gorszy niż [jakiś wzorzec typowości]”?
izomorfizm
2
@ isomorphismes Tutaj „subnormal” odnosi się do sposobu implementacji pływaków. Zobacz liczby normalne na Wikipedii.
Paul Manta,
Nawiasem mówiąc, trochę uprościłem „typową metodę”. Możliwe jest zaimplementowanie exp2 () i exp () z dokładnością ulp za pomocą tylko jednego małego (i dość łatwego do zrozumienia) rozszerzenia przedstawionej tutaj metody, ale wyjaśnienie małego, łatwego do zrozumienia rozszerzenia prawdopodobnie podwoi długość odpowiedź!
pseudonim
6

2**x2x<<1 << x

ogrodnik
źródło
4
Nie aktualne. x może typ zmiennoprzecinkowy
phuclv
1
x
Jeśli xnie jest liczbą całkowitą (powiedzmy 20.75), należy ustawić mantysę 2i wykładnik na zaokrągloną wartość xjako najdokładniejsze oszacowanie (dokładne przedstawienie nie jest możliwe). Co również jest znacznie szybsze niż „pow”.
Damon,
1

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.

Tim
źródło
Co ciekawe, nie wiedziałem, że **jest uważany za synonim wersji zmiennoprzecinkowej (i, głupiutko, zapomniałem, że te dwie rzeczy będą inne).
izomorfizm
1

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.

gnasher729
źródło
0

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.

znak
źródło