Что вычисляется быстрее,

Что вычисляется быстрее, или или ? , и - положительные вещественные числа с .$a^b$$\log_a c$$\sqrt[b]{c}$$a$$b$$c$$b>1$

Какие алгоритмы вы будете использовать при сравнении? Каковы их сложности?

Например, когда или$c \equiv a^b$$c \approx a^b$

Этот вопрос был вдохновлен комментариями на вопрос об обмене стека математики. Какова цель приближения Стирлинга к факториалу? , Особенно те комментарии, которые оставили mjqxxxx , Томас Эндрюс и я.

Смотрите мой ответ на этот вопрос для некоторых связанных вопросов.

В общем, компьютеры могут только складывать, вычитать, умножать, делить и сдвигать биты. В качестве аргумента давайте предположим, что вы не вычисляете в особом случае, когда a - степень 2, а b - натуральное число, потому что этот случай сводится к сдвигу в битах, и, следовательно, это легко.$a^b$$a$$b$

Если натуральное число, и вы хотите вычислить a b , вы можете использовать возведение в степень сложения . Любой другой случай в вашем вопросе сложен (в общем).$b$$a^b$

Некоторые быстрые алгоритмы, используемые для приближения этих функций к высокой точности, требуют черной магии. Чтобы понять, что я имею в виду под «черной магией», взгляните на этот пост в блоге Мартина Анкерла и связанную с ним статью, на которую он ссылается в разделе « Нейронные вычисления» . Также см. Алгоритм CORDIC .

Подобные виды хитрых трюков объясняются в «Восхищении Хакера» (ссылка на сайт-компаньон для книги).

Другие способы вычисления хороших приближений используют численный анализ (см. Статью в Википедии о теории приближений ). Один плохой способ сделать это - создать соответствующее дифференциальное уравнение и интегрировать его, используя численный метод, такой как метод Эйлера (как я уже сказал, плохое приближение, но вы можете сделать это). Лучший способ сделать это - использовать последовательные приближения. Ряд Тейлора сходится слишком медленно, поэтому вместо него можно использовать что-то вроде аппроксимации Паде или некоторого другого типа приближения быстро сходящихся рядов (другие рациональные приближения, ряды Чебышева и т. Д.).

Алгоритм, который вы используете для аппроксимации вышеуказанных функций, будет зависеть от вашей архитектуры, требований к скорости и требований к точности.

Проблема разговоров о сложностях заключается в том, что любой алгоритм рассчитывает только аппроксимацию с плавающей точкой тех функций, которые вы упомянули, поэтому время выполнения, безусловно, будет зависеть от точности, которую вы требуете от своего приближения. Даже принимая это во внимание, я не думаю, что вычислительная сложность является хорошим первым приближением производительности; размер ваших входов будет измеряться в битах (т. е. количество битов, которое требуется для представления , b и $a$$b$$c$), которые будут зависеть от точности, а не от величин самих числовых входов. Для практических целей точность числового представления чисел не будет сильно различаться (одинарная точность, двойная точность, квадратическая точность), и вы обычно не решаете использовать эту точность на основе каких-либо оценок сложности вычислений скалярных функций , Наиболее актуальным показателем является время по настенным часам, и если вы не используете специальную архитектуру (встроенные системы) или ваше приложение действительно не требует быстрой экспоненты (см. Ссылку на пост в блоге и ссылку на нейронные вычисления выше), встроенные библиотеки в вашем Язык выбора, вероятно, просто отлично.

Это хороший вопрос, потому что понимание численных алгоритмов и производительности является важной предпосылкой для того, чтобы быть эффективным вычислительным ученым. В то же время, это плохой вопрос, потому что установленные ограничения недостаточно квалифицируют его, чтобы дать значимый ответ.

Производительность трех вычислений будет сильно зависеть от точности, необходимой в конечном результате, а также от минимальной точности, необходимой для представления операндов. Вы квалифицируете , b и c как положительные действительные числа, но нам также нужно знать, сколько двоичных цифр d n требуется для их точного представления. Чтобы понять соображения производительности для общих действительных чисел, мы сначала должны понять, как компьютеры представляют целые числа, а также как они аппроксимируют действительные числа, используя числа с плавающей запятой.$a$$b$$c$$d_n$

Когда компьютеры работают с целым числом , тогда необходимое количество двоичных цифр, очевидно, равно log 2 величины целого числа плюс дополнительный бит для обработки знака:$M$$_2$

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

Например, число -8 может быть представлено 4 двоичными цифрами. Для повышения производительности и эффективности использования пространства арифметико-логические единицы (АЛУ), отвечающие за численные вычисления целых чисел на современных процессорах, предназначены для обработки математических вычислений с целыми числами вплоть до некоторого фиксированного размера, наиболее распространенными в наши дни являются d = 32 и d = 64. Не только процессоры x86, как на вашем компьютере, имеют ALU, они являются фундаментальным строительным блоком компьютерной архитектуры, повсеместной в современном электронном обществе. Если вы знакомы с игровыми приставками, вы, возможно, помните Nintendo 64, систему видеоигр, названную по размеру (в битах), для которой были разработаны арифметико-логические устройства на процессоре консоли.

Целочисленные сложения, вычитания и умножения на арифметических логических единицах очень эффективны и обычно требуют не более нескольких циклов для вычисления. Деления менее производительны, и на современных процессорах может потребоваться до нескольких десятков циклов. Производительность зависит как от архитектуры блока обработки (и соответствующей реализации арифметико-логического блока), так и от его частоты. Обратите внимание, что 64-битный процессор обычно может выполнять арифметику с -битными операндами с одинаковой скоростью для x в любом месте от 1 до 64.$x$$x$

В общих вычислениях, и особенно в научных вычислениях, целочисленная математика является громоздкой для многих вычислений, и необходимо другое представление чисел, так называемое представление с плавающей запятой. Числа с плавающей запятой представляют собой компромисс между работой современных микропроцессоров (преобразование данных в битные фрагменты) и потребностями вычислений путем представления чисел на процессоре в усеченной научной нотации с использованием фиксированной базы b (обычно b = 2 или b = 10 ) и представляет число, используя два целых числа, мантиссу (значимую в некоторых кругах) s и показатель степени e . Данное число $n$$b$$b=2$$b=10$$s$$e$$x$ тогда приблизительно представляется как:

$x = s*b^e$

Я говорю примерно, потому что должно быть очевидно, что даже простые рациональные, такие как не может быть представлен точно как число с плавающей точкой для стандартных базисов. Количество цифр, зафиксированных в значении, определяет точность числа, которое относительно его собственной величины. СтандартIEEE 754определяет ряд правил поведения ожидаемых чисел с плавающей запятой, в том числе диапазоны значений и мантиссы (и соответствующий диапазон и точность) для нескольких важных значенийdn, так что численные вычисления могут повторяться в пределах некоторая терпимость. В том, как работают числа с плавающей запятой, есть некоторая тонкость, которую я не могу надеяться охватить в этом ответе. Для хорошего введения я рекомендую«Что должен знать каждый специалист по вычислительной технике об арифметике с плавающей запятой»$\frac{1}{3}$$d_n$,

За последние 50 лет были вложены значительные интеллектуальные усилия в улучшение возможностей процессора для эффективного вычисления арифметических операций с плавающей запятой. На современных процессорах эти вычисления обрабатываются одним или несколькими блоками с плавающей запятой (FPU), более сложной версией арифметического логического блока, предназначенного для выполнения арифметических операций над числами с плавающей запятой и обычно предназначенного для обработки обоих указанных в IEEE 754 32 -битные числа с плавающей запятой (часто называемые «числами с плавающей запятой») и 64-битные числа с плавающей запятой (часто называемые числами с двойными числами) эффективно. Подобно арифметическим логическим единицам, единицы с плавающей запятой часто могут вычислять сложение, вычитание и умножение всего за несколько циклов, в то время как для деления обычно требуется немного больше.

В большинстве случаев для числовых вычислений достаточно 64-разрядных двойных чисел с плавающей точкой IEEE 754, поэтому давайте предположим, что , b и c представлены в виде 64-разрядных двойных чисел , и вас интересует производительность три вычисления в виде скалярных операций в архитектуре Intel Nehalem с использованием подмножества команд с плавающей запятой x87, т. е. вас не интересует вычисление этих операций в цикле for или для диапазона данных, и вы не хотите использовать векторные расширения , Информация о задержке команд собирается из превосходного набора справочных таблиц команд для архитектур Intel / AMD.$a$$b$$c$

1. $a^b$
2. войти в гр$_a c$
3. $c^\frac{1}{b}$

1 Общее возведение в степень часто осуществляется со следующей идентичностью:

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

Где равно 2 или e (в этом случае я использую β = 2 ). Предполагая, что вы готовы отбросить некоторую точность результата (модуль x87 выполняет вычисления с точностью 80 бит, но этого недостаточно для определенных диапазонов значений a и b ), это вычисление можно выполнить с помощью аппаратной инструкции FYL2X. для вычисления t = a ⋅ log 2 b и аппаратной инструкции F2XM1 (с некоторой помощью по масштабированию) для вычисления 2 t . Предполагая ~ 20 циклов для обработки масштабирования:$\beta$$2$$e$$\beta=2$$a$$b$$t=a\cdot\text{log}_2 b$$2^t$

FYL2X + F2XM1 + ~ 20 = 80 + 51 + ~ 20 = ~ 151 циклов

2 Это может быть преобразовано в два логарифма и деление путем изменения базовой идентичности и не требует масштабирования для получения точного результата.

2 * FYL2X + FDIV = 2 * 80 + (от 7 до 27) = от 167 до 187 циклов

[3] Это эквивалентно делению с возведением в степень, поэтому [1] плюс FDIV ~ 175 циклов.

Позвольте мне посмотреть, могу ли я перефразировать вопрос:

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

Ответ : это действительно зависит от того, имеет ли c какую-либо зависимость от a, и как a сравнивается с b (больше, меньше или равно).

$c$$b$$a$

$c$$\log_a(c) = \ln(c)/\ln(a)$$\log_a(c)$$a^b$$a$$a^b = \omega(\log_a(c))$

$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))$

$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$