Мне нужно очень быстро рассчитать приближение Стирлинга

Question

Мне нужно очень быстро рассчитать приближение Стирлинга

Я пишу небольшую библиотеку для статистической выборки, которая должна работать как можно быстрее. В профилировании я обнаружил, что около 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 входов в функцию.
Оптимизация математики (используйте более грубое приближение для меньшей точности)
Используйте несколько потоков для параллельного вычисления на разных входах
Переключитесь на собственную арифметику, когда числа могут вписываться в типы машинных данных

Есть ли другие подходы, которые я мог бы использовать?

4

arbitrary-precision c++mpfr numerical

Решение

Другие решения

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

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

Последний вариант, который вы можете попробовать, — это вручную распределить пространство памяти, чтобы MPFR имел фиксированные накладные расходы. Я никогда не пробовал, поэтому не знаю, поможет ли это.

1

Источник

Accepted Answer

Переключитесь на собственную арифметику, когда числа могут вписываться в типы машинных данных

Это будет моя первая попытка. MPFR, вероятно, будет убийцей производительности.

Мне кажется, вы хотите вычислить логарифм n! который вы уже приближаете с формулой Стерлинга.

Обратите внимание, что n! = Гамма (n + 1). Существуют (казалось бы) высокооптимизированные функции для вычисления как гамма-функции, так и ее логарифма. Например:

Я бы выполнил собственное грубое приближение, только если все вышеперечисленное не соответствует производительности.

2