Który oblicza się szybciej

Który jest obliczany szybciej, lub lub ? , i są liczbami dodatnimi z .zaloguj a c b $a^b$$\log_a c$ abcb>$\sqrt[b]{c}$$a$$b$$c$$b>1$

Jakiego rodzaju algorytmów użyjesz w porównaniu? Jakie są ich zawiłości?

Na przykład, gdy lub c ≈ a $c \equiv a^b$$c \approx a^b$

To pytanie zostało zainspirowane komentarzami do pytania wymiany stosu matematyki. Jaki jest cel przybliżenia Stirlinga do silni? . Zwłaszcza te komentarze pozostawione przez mjqxxxx , Thomasa Andrewsa i mnie.

Zobacz moją odpowiedź na to pytanie, aby uzyskać informacje na temat niektórych powiązanych problemów.

Ogólnie rzecz biorąc, komputery mogą tylko dodawać, odejmować, mnożyć, dzielić i przesuwać bity. Przez wzgląd na argument, załóżmy, że jesteś nie obliczaniu w szczególnym przypadku, gdy jest potęgą liczby 2 i b jest liczbą naturalną, bo to sprawa sprowadza się do przesunięcia bitowego, a więc jest łatwy.$a^b$$a$$b$

Jeśli jest liczbą naturalną, a chcesz obliczyć do b , można użyć dodatek łańcucha potęgowanie . Każda inna sprawa w twoim pytaniu jest trudna (ogólnie).$b$$a^b$

Niektóre szybkie algorytmy używane do przybliżenia tych funkcji do wysokiej dokładności wymagają czarnej magii. Aby zobaczyć, co mam na myśli przez „czarną magię”, spójrz na ten post na blogu Martina Ankerla i powiązany artykuł, do którego prowadzi link w Neural Computation . Zobacz także algorytm CORDIC .

Podobne rodzaje sztuczek polegających na przerzucaniu bitów wyjaśniono w Hacker's Delight (link znajduje się na stronie towarzyszącej książce).

Inne sposoby obliczania dobrych przybliżeń wykorzystują analizę numeryczną (patrz artykuł Wikipedii na temat teorii aproksymacji ). Jednym złym sposobem na to jest ustalenie odpowiedniego równania różniczkowego i zintegrowanie go za pomocą metody numerycznej, takiej jak metoda Eulera (jak powiedziałem, złe przybliżenie, ale można to zrobić). Lepszym sposobem na to jest użycie przybliżeń serii. Szeregi Taylora zbiegają się o wiele za wolno, więc zamiast tego można zastosować coś w rodzaju aproksymacji Padego lub innego rodzaju aproksymacji szeregów szybko zbieżnych (inne racjonalne aproksymacje, szeregi Czebyszewa itp.).

Algorytm używany do przybliżenia powyższych funkcji będzie zależeć od architektury, wymagań prędkości i wymagań dokładności.

Problem z mówieniem o złożoności polega na tym, że dowolny algorytm oblicza jedynie przybliżenie zmiennoprzecinkowe wspomnianych funkcji, więc czas działania z pewnością będzie zależeć od dokładności, jakiej wymagasz od swojego przybliżenia. Nawet biorąc to pod uwagę, nie sądzę, aby złożoność obliczeniowa była dobrym pierwszym przybliżeniem wydajności; wielkość twoich danych wejściowych będzie mierzona w bitach (tj. liczba bitów potrzebnych do przedstawienia , b i $a$$b$$c$), które będą zależne od precyzji, a nie od wielkości samych danych liczbowych. Ze względów praktycznych dokładność numerycznej reprezentacji liczb nie będzie się bardzo różnić (pojedyncza precyzja, podwójna precyzja, czterokąta precyzja) i zwykle nie decydujesz się na użycie tej precyzji na podstawie jakichkolwiek oszacowań złożoności obliczeniowej funkcji skalarnych . Najbardziej odpowiednią miarą jest czas naścienny i jeśli nie używasz specjalnej architektury (systemy osadzone) lub Twoja aplikacja naprawdę wymaga szybkiego wykładniczego (patrz link do postu na blogu i link do obliczeń neuronowych powyżej), wewnętrzne biblioteki w twoim wybór języka jest prawdopodobnie w porządku.

To dobre pytanie, ponieważ zrozumienie algorytmów numerycznych i wydajności jest ważnym warunkiem bycia skutecznym naukowcem obliczeniowym. Jednocześnie jest to słabe pytanie, ponieważ przedstawione ograniczenia nie kwalifikują go w wystarczającym stopniu, aby dać sensowną odpowiedź.

Wydajność trzech obliczeń będzie silnie zależeć od dokładności wymaganej w wyniku końcowym, a także od minimalnej precyzji wymaganej do przedstawienia argumentów. Kwalifikujesz , b i c jako dodatnie liczby rzeczywiste, ale musimy również wiedzieć, ile cyfr binarnych d n jest wymaganych do ich dokładnego przedstawienia. Aby zrozumieć względy wydajności dla ogólnych liczb rzeczywistych, najpierw musimy zrozumieć, w jaki sposób komputery reprezentują liczby całkowite, a także w jaki sposób przybliżają liczby rzeczywiste za pomocą liczb zmiennoprzecinkowych.$a$$b$$c$$d_n$

Gdy komputery działają na liczbie całkowitej , liczba potrzebnych cyfr binarnych jest oczywiście równa log 2 wielkości liczby całkowitej oraz dodatkowy bit do obsługi znaku:$M$$_2$

log 2 | M | + $d_n=$$_2|M|+1$

Na przykład liczbę -8 można przedstawić za pomocą 4 cyfr binarnych. W celu zapewnienia wydajności i wydajności przestrzennej arytmetyczne jednostki logiczne (ALU), odpowiedzialne za obliczenia liczbowe liczb całkowitych na nowoczesnych jednostkach przetwarzających, są zaprojektowane do obsługi matematyki na liczbach całkowitych do pewnego ustalonego rozmiaru, przy czym najczęściej są to d = 32 id = 64 Nie tylko procesory x86, jak na twoim komputerze, mają ALU, są one podstawowym elementem architektury komputerowej wszechobecnym w dzisiejszym społeczeństwie elektronicznym. Jeśli znasz konsole do gier, możesz pamiętać Nintendo 64, system gier nazwany od wielkości (w bitach), arytmetyczne jednostki logiczne na procesorze konsoli zostały zaprojektowane do obsługi.

Dodawanie, odejmowanie i mnożenie liczb całkowitych w arytmetycznych jednostkach logicznych jest bardzo wydajne i zwykle wymaga nie więcej niż kilku cykli do obliczenia. Podziały są mniej wydajne, a na współczesnych procesorach może wymagać nawet kilkudziesięciu cykli. Wydajność zależy zarówno od architektury jednostki przetwarzającej (i odpowiedniej implementacji arytmetycznej jednostki logicznej), jak i od jej częstotliwości. Zauważ, że 64-bitowy procesor może zwykle wykonywać arytmetykę na operandach bitowych z tą samą prędkością dla x w dowolnym miejscu między 1 a 64.$x$$x$

W obliczeniach ogólnych, a zwłaszcza w obliczeniach naukowych, matematyka na liczbach całkowitych jest niewygodna dla wielu obliczeń i potrzebna jest inna reprezentacja liczb, tak zwana reprezentacja „zmiennoprzecinkowa”. Liczby zmiennoprzecinkowe reprezentują kompromis między sposobem działania współczesnych mikroprocesorów (kartowanie danych w bitowych porcjach) a potrzebami obliczeń poprzez reprezentowanie liczb na procesorze w skróconej notacji naukowej, przy użyciu stałej podstawy b (zwykle b = 2 lub b = 10 ) i reprezentujący liczbę przy użyciu dwóch liczb całkowitych, mantysy (znaczenia w niektórych kręgach) s i wykładnika e . Podana liczba $n$$b$$b=2$$b=10$$s$$e$$x$ jest wówczas w przybliżeniu przedstawiany jako:

$x = s*b^e$

Mówię w przybliżeniu, ponieważ powinno być oczywiste, że nawet proste racjonalności, takie jak nie można przedstawić dokładnie jako liczbę zmiennoprzecinkową dla standardowych zasad. Liczba cyfr przypisanych do znaczenia i określa dokładność liczby, która jest zależna od jej wielkości. WIEEE 754 standardowychOkreśla liczbę reguł jak oczekuje liczb zmiennoprzecinkowych się zachowywać, w tym zakresów mantysy i mantysy (i odpowiadające zasięg i precyzja) dla kilku ważnych wartościachdn, tak że obliczenia numeryczne są powtarzalne w ciągu trochę tolerancji. Jest trochę subtelności w działaniu liczb zmiennoprzecinkowych, których nie mam nadziei uchwycić w tej odpowiedzi, dla dobrego wprowadzenia polecam„Co każdy informatyk powinien wiedzieć o arytmetyce zmiennoprzecinkowej”$\frac{1}{3}$$d_n$.

W ciągu ostatnich 50 lat zainwestowano znaczny wysiłek intelektualny w poprawę zdolności procesora do wydajnego obliczania arytmetycznych operacji zmiennoprzecinkowych. W nowoczesnych procesorach obliczenia te są obsługiwane przez jedną lub więcej jednostek zmiennoprzecinkowych (FPU), bardziej wyrafinowaną wersję arytmetycznej jednostki logicznej przeznaczoną do wykonywania operacji arytmetycznych na liczbach zmiennoprzecinkowych i zwykle zaprojektowaną do obsługi zarówno określonych liczb IEEE 754 32 -bitowe liczby zmiennoprzecinkowe (często nazywane „liczbami zmiennoprzecinkowymi”) i 64-bitowe liczby zmiennoprzecinkowe (często nazywane „liczbami podwójnymi”) skutecznie. Podobnie jak jednostki arytmetyczne, jednostki zmiennoprzecinkowe często obliczają dodawanie, odejmowanie i mnożenie w zaledwie kilku cyklach, podczas gdy dzielenie zwykle wymaga nieco więcej.

W większości przypadków 64-bitowe „podwójne” zmiennoprzecinkowe IEEE 754 są wystarczające do obliczeń numerycznych, więc załóżmy, że , b i c są reprezentowane jako 64-bitowe podwójne, i jesteś zainteresowany wydajnością trzy obliczenia jako operacje skalarne na architekturze Intel Nehalem przy użyciu podzestawu instrukcji zmiennoprzecinkowych x87, tj. nie jesteś zainteresowany obliczaniem tych operacji w pętli for lub w zakresie danych i nie chcesz używać rozszerzeń wektorowych . Informacje o opóźnieniu instrukcji są zbierane z doskonałego zestawu tabel referencyjnych instrukcji Agner Fog dla architektur Intel / AMD.$a$$b$$c$

1. $a^b$
2. zalogować się c$_a c$
3. $c^\frac{1}{b}$

1 Ogólne potęgowanie jest często realizowane z następującą tożsamością:

$a^b = \beta^{a\cdot\text{log}_\beta b}$

Gdzie jest albo 2 albo e (w tym przypadku używam β = 2 ). Zakładając, że chcesz podważyć pewną dokładność wyniku (jednostka x87 wykonuje swoje obliczenia z 80 bitami dokładności, ale nie jest to wystarczające dla niektórych zakresów wartości dla a i b ), obliczenia te można wykonać za pomocą instrukcji sprzętowej FYL2X obliczyć t = a ⋅ log 2 b oraz instrukcję sprzętową F2XM1 (z pewną pomocą skalowania), aby obliczyć 2 t . Zakładając ~ 20 cykli do obsługi skalowania:$\beta$$2$$e$$\beta=2$$a$$b$$t=a\cdot\text{log}_2 b$$2^t$

FYL2X + F2XM1 + ~ 20 = 80 + 51 + ~ 20 = ~ 151 cykli

2 Można to przekształcić na dwa logarytmy i podział przez zmianę tożsamości bazowej i nie trzeba przeskalowywać, aby uzyskać dokładny wynik.

2 * FYL2X + FDIV = 2 * 80 + (7 do 27) = 167 do 187 cykli

[3] Jest to równoważne podziałowi, po którym następuje potęgowanie, więc [1] plus FDIV, ~ 175 cykli.

Zobaczmy, czy mogę sparafrazować pytanie:

$a^b$$\log_a(c)$$a$

Odpowiedź : to naprawdę zależy od tego, czy c ma jakąkolwiek zależność od a, i od tego, jak a porównuje się do b (większa niż, mniejsza niż lub równa).

$c$$b$$a$

Założenie 1 : Załóżmy $c$$\log_a(c) = \ln(c)/\ln(a)$$\log_a(c)$$a^b$$a$$a^b = \omega(\log_a(c))$

Założenie 2 : Załóżmy, że . Następnie,$c=a^b$$\log_a(a^b)=b$$b$$a^b$$log_a(c)$$a^b = \omega(\log_a(c))$

$c$$a^b$$a^b$$c=\Theta(a^b)$

$\log_a(c)$$c^{1/b}$

$a$$b$$c$

$c$$c^{1/b}$$b$$c^{1/b} = o(\log_a(c))$

Założenie 2 : Załóżmy, że $c = a^b$$\log_a(c)= a$$c^{1/b} = a$$\log_a(c) = \Theta(c^{1/b})$

$c$$a^b$$a^b$$c$

$c^{1/b}$$a^b$

$c$$c^{1/b}$$a^b$$c^{1/b}=o(a^b)$

$c=a^b$$c^{1/b}=a$$b>1$$a^b$$c^{1/b}$

$a$$b$$c$