Мне нужно очень быстро рассчитать приближение Стирлинга
Я пишу небольшую библиотеку для статистической выборки, которая должна работать как можно быстрее. В профилировании я обнаружил, что около 40% времени, затрачиваемого на функцию, тратится на вычисления Приближение Стирлинга для логарифма факториала. Я сосредоточил свои усилия по оптимизации на этом кусочке. Вот мой код (который использует MPFR):
const double AL[8] =
{ 0.0, 0.0, 0.6931471806, 1.791759469, 3.178053830, 4.787491743,
6.579251212, 8.525161361 };
void HGD::mpfr_afc(mpfr_t &ret, const mpfr_t &val){
if(mpfr_cmp_ui(val, 7) <= 0){
mpfr_set_d(ret, AL[mpfr_get_ui(val, MPFR_RNDN)], MPFR_RNDN);
}else{
mpfr_set(ret, val, MPFR_RNDN);
mpfr_add_d(ret, ret, 0.5, MPFR_RNDN);
mpfr_log(LV, val, MPFR_RNDN);
mpfr_mul(ret, LV, ret, MPFR_RNDN);
mpfr_sub(ret, ret, val, MPFR_RNDN);
mpfr_add_d(ret, ret, 0.399089934, MPFR_RNDN);
}
}
У меня есть пара разных идей:
- Предварительно вычислите больше, чем первые 8 входов в функцию.
- Оптимизация математики (используйте более грубое приближение для меньшей точности)
- Используйте несколько потоков для параллельного вычисления на разных входах
- Переключитесь на собственную арифметику, когда числа могут вписываться в типы машинных данных
Есть ли другие подходы, которые я мог бы использовать?
Решение
Переключитесь на собственную арифметику, когда числа могут вписываться в типы машинных данных
Это будет моя первая попытка. MPFR, вероятно, будет убийцей производительности.
Мне кажется, вы хотите вычислить логарифм n! который вы уже приближаете с формулой Стерлинга.
Обратите внимание, что n! = Гамма (n + 1). Существуют (казалось бы) высокооптимизированные функции для вычисления как гамма-функции, так и ее логарифма. Например:
- Стандартный C ++ 11 lgamma
- Повысить lgamma
- GNU GSL lngamma
- Томс 291
- http://www.johndcook.com/cpp_gamma.html
Я бы выполнил собственное грубое приближение, только если все вышеперечисленное не соответствует производительности.
Другие решения
Пара мыслей здесь. Во-первых, мне приходит в голову, что использование MPFR для этого может быть излишним. Любая из библиотек с множественной точностью имеет огромные накладные расходы. Не просто накладные расходы, а огромные накладные расходы. Вторая мысль заключается в том, что, возможно, вам не нужно использовать многоточную функцию регистрации. Может быть, вы могли бы уйти со стандартным журналом?
Если вы не можете разместить свои вычисления в плавающей запятой двойной точности, то параллелизация с использованием потоков или других методов, безусловно, поможет. Вы можете попробовать поиграть с оптимизацией компилятора, но я не видел реальных улучшений, пытающихся это сделать.
Последний вариант, который вы можете попробовать, — это вручную распределить пространство памяти, чтобы MPFR имел фиксированные накладные расходы. Я никогда не пробовал, поэтому не знаю, поможет ли это.