Самая быстрая замена pow() через модифицированный exp. путем возведения в квадрат, когда низшие силы уже рассчитаны

Question

EDIT:

Цель:
Сформировать вездесущий метод получения пользовательской функции питания, который превосходит встроенный pow(double, uint) за счет многократного использования предварительно рассчитаны/кэшированные полномочия от расчетов мощности по общим переменным.

Что уже было сделано:
Я уже получена такая функция, что это примерно 40% быстрее, чем встроенный, однако это является перебором вручную производной функции - Я хочу, чтобы метод автогенерирование такого функционального блока мощности для произвольной мощности uint.

---

KNOWNS

Для получения оптимального обычая pow(double, uint) вам нужны knowns. По этому вопросу известны (уточнить):

1. Мощность будет целым числом.
2. Максимальное значение мощности может быть известно (N_MAX).
3. Предварительно рассчитанные мощности, которые могут быть (повторно) использованы, известны во время компиляции (например, в моем примере r2, r4 и r6).
4. Квадрат r2 можно считать всегда рассчитанным независимо от других предварительно рассчитанных мощностей.

---

РЕШЕНИЕ ТРЕБОВАНИЯ

Оптимальное решение требует отдельной программы для записи таблицы или препроцессора логику в case поиска для генерации такой таблицы является приемлемым, однако, не-оптимальные решения с использованием ручной сгенерированные (т. е. полученные с помощью перебора) таблицы поиска, использующие полномочия, не будут приняты (поскольку у меня это уже есть, и покажите, что в моем примере ... идея состоит в том, чтобы уйти от этого).

---

ВОЗМОЖНОЕ РЕШЕНИЕ ROUTE

Как предложение, вы знаете N_MAX и набор полномочий, которые предварительно вычислены B (B={2,4,6} для моего примера). Вы можете произвести либо в отдельной программе, либо в препроцессоре таблицу всех квадратов Sq(Bi, x) < = N_MAX . You can use this to form a basis set A , which you then search somehow to determine the least number of terms that can be summed to produce an arbitrary exponent of n >> 1 , where n < = N_MAX` (сдвиг обусловлен тем, что мы позаботимся о нечетном случае путем проверки LSB и умножения на sqrt (r2)).

---

ТЕОРЕТИЧЕСКИЕ ПРЕДПОСЫЛКИ

Я считаю, что формально ниже метод представляет собой модифицированный вариант exponentations путем возведения в квадрат:

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

.... который использует тот факт, что некоторые мощности нижнего порядка уже по необходимости предварительно вычисляются, поэтому он сдвигает оптимальный набор умножений от экспоненты ванили по квадрату (что я предполагаю pow(double, int)).

Однако существует значительная экономия за счет использования запасных промежуточных продуктов с малой мощностью вместо простого exp. по квадратам на r2.

---

ТЕОРЕТИЧЕСКИЕ ИСПОЛНЕНИЯ

Например, для одного набора объектов n=14 .... в этом сценарии эксп. полномочия дает

double r4 = Sq(r2), r14=Sq(r4)*r4*r2; //4 op. 

... который принимает -FP умножений ..... но используя r2 и r6 мы имеем

double r14=Sq(r6)*r2; //2 op. 

.... -FP умножений. ... другими словами, перейдя от «немой» экспоненции квадратами к моему модифицированному exp. по квадратам, использующим общую предварительную подготовку экспонентов, я сократил стоимость вычислений на 50% с точки зрения умножения ... по крайней мере, до тех пор, пока не будут рассмотрены затраты на память.

РЕАЛЬНОГО ИСПОЛНЕНИЯ

С моим текущим методом (составитель с gcc -O3) я получаю 35,1 сек., чтобы запустить 1 миллион циклов моей программы, в сравнении с (без изменений) 56,6 с с использованием встроенного int pow(double, int) .... так почти теоретическое ускорение.

На этом этапе вы можете почесывать голову тем, как 50% вырезания в одной команде могут доставить ускорение на 40%. Но в основном эта строка кода называется 1000+ раз за цикл и на сегодняшний день является самой оцененной/самой дорогой линией кода во всей программе. Следовательно, программа кажется очень чувствительной к небольшой оптимизации/улучшению этого фрагмента.

---

ОРИГИНАЛ POST и пример кода

Мне нужно заменить функцию pow(double, int) как я уже вычислил 6-й член мощности и имеют 2-й, 4-й промежуточные мощности сохранены, все из которых могут быть использованы для уменьшить умножения во втором вызове pow, который использует ту же самую базу double.

В частности, в моем коде на языке C++ у меня есть критический фрагмент кода для вычисления кода, в котором я возвращаю обратную величину расстояния между точками 3D до 6-й мощности и n-й мощности. например .:

double distSq = CalcDist(p1,p2), r2 = a/distSq, r6 = r2 * r2 * r2; 
results += m*(pow(sqrt(r2), n) - r6); 

Где m и a являются константы, связанные с подогнанным уравнением и n является произвольной силой.

Немного более эффективной формой является:

double distSq = CalcDist(p1,p2), r2 = a/distSq, r6 = r2 * r2 * r2; 
results += m*(pow(r2, n)*(n&0x1?sqrt(r2):1.0) - r6); 

Тем не менее, это также не является оптимальным. То, что я обнаружил, значительно быстрее, - это иметь пользовательскую функцию pow, которая использует кратные r2, r4 и r6, которые я должен рассчитать уже в любом случае для второго термина.

.: например

double distSq = CalcDist(p1,p2), r2 = a/distSq, r4 = r2 * r2, r6 = r4 * r2; 
results += m*(POW(r2, r4, r6 n) - r6); 

Внутри функции:

double POW(double r2, double r4, double r6, uint n) 
{ 
    double results = (n&0x1 : sqrt(r2) : 1.0); 
    n >>= 1; 
    switch (n) 
    { 
    case 1: 
    .... 
    case 12: 
     Sq(Sq(r6)); 

    } 
    return result; 
} 

Хорошая вещь в том, что моя функция появляется быстро в предварительном тестировании. Плохая новость заключается в том, что она не очень вездесущая и очень длинная, поскольку мне нужны case заявления для int полномочий от 8 до 50 или около того (потенциально даже выше в будущем). Далее в каждом конкретный случай я должен был изучить и попробовать различные комбинации, чтобы найти с помощью грубой силы вывода, какая комбинация r2, r4 и r6 дал наималейшим умножениям

Кто-нибудь есть более повсеместное решение для замены pow(double, int), который использует предварительно вычисленное полномочие базу, чтобы сократить количество необходимых умножений и/или иметь повсеместную теорию о том, как вы можете определить идеальную комбинацию для получения наименьших умножений для произвольного n и некоторого набора предварительно рассчитанных множителей?

Answer 1

Вот несколько DP-подобный алгоритм, который даст вам минимальное количество умножений для заданного n и доступных мощностей x^i, а также оптимальные стратегии с помощью обратного отслеживания. Каждому возможному экспоненту n присвойте пару (minimum number of multiplications to get here, type of multiplication that gets you there), где для второго номера просто напишите i или специальный символ S для возведения в квадрат.

Очевидно, вы начинаете с 1 -> (0, /).

Учитывая n -> (m_n, Action_m), установить n+i -> в (m_n + 1, i), если m_n + 1 меньше, чем возможно, ранее вычисленным минимальное количество ходов до n+i. Аналогично, установите 2n -> (m_n + 1, S), если это лучше, чем возможное предыдущее решение.

Этот алгоритм дает оптимальные стратегии примерно в O(n_max * #available powers). Я не утверждаю, что сам алгоритм оптимально эффективен, хотя, конечно, нет смысла использовать это «на лету». Это полезно, только если у вас есть разумный n_max (100, в вашем случае, конечно, хорошо) и эффективный способ хранения стратегий.

Две мысли рассмотреть следующие вопросы:

(1) Пока это не протестированный, я не уверен, что это приведет к значительному улучшению производительности по сравнению со стандартным ехром путем возведения в квадрате (в значительной степени зависит от имеющихся полномочий, конечно) ,

(2) Численное поведение ошибок таких стратегий (а также exp по квадрату) полностью отличается от pow(double, double).