Подтвердить что ты не робот

Оптимизации для pow() с константным нецелым показателем?

У меня есть горячие точки в моем коде, где я делаю pow(), занимая около 10-20% времени выполнения.

Мой вклад в pow(x,y) очень специфичен, поэтому мне интересно, есть ли способ перевернуть два приближения pow() (по одному для каждого показателя) с более высокой производительностью:

  • У меня есть два константных показателя: 2.4 и 1/2.4.
  • Когда показатель экспоненты равен 2,4, x будет находиться в диапазоне (0.090473935, 1.0].
  • Когда показатель экспоненты равен 1/2,4, x будет находиться в диапазоне (0.0031308, 1.0).
  • Я использую векторы SSE/AVX float. Если особенности платформы можно использовать, прямо на!

Максимальная частота ошибок около 0,01% является идеальной, хотя меня также интересуют алгоритмы полной точности (для float).

Я уже использую быстрое приближение pow() но оно не учитывает эти ограничения. Можно ли сделать лучше?

4b9b3361

ОТВЕТЫ

Ответ 1

В взломанной вене IEEE 754 вот еще одно решение, которое быстрее и менее "волшебно". Он достигает порога ошибки 0,8% примерно за десяток тактовых циклов (для случая p = 2.4, на процессоре Intel Merom).

Числа с плавающей запятой были первоначально изобретены как приближение к логарифмам, поэтому вы можете использовать целочисленное значение в качестве приближения к log2. Это можно сделать несколько возможным путем применения команды convert-from-integer к значению с плавающей запятой, чтобы получить другое значение с плавающей запятой.

Чтобы завершить вычисление pow, вы можете умножить на постоянный коэффициент и преобразовать логарифм обратно с помощью команды convert-to-integer. В SSE соответствующие инструкции cvtdq2ps и cvtps2dq.

Это не совсем так просто. Поле экспоненты в IEEE 754 подписывается с величиной смещения 127, представляющей показатель нуля. Это смещение должно быть удалено перед умножением логарифма и повторным добавлением перед тем, как вы повысите степень риска. Кроме того, корректировка смещения путем вычитания не будет работать на ноль. К счастью, обе регулировки могут быть достигнуты путем умножения на постоянный коэффициент заранее.

x^p
= exp2( p * log2( x ) )
= exp2( p * ( log2( x ) + 127 - 127 ) - 127 + 127 )
= cvtps2dq( p * ( log2( x ) + 127 - 127 - 127 / p ) )
= cvtps2dq( p * ( log2( x ) + 127 - log2( exp2( 127 - 127 / p ) ) )
= cvtps2dq( p * ( log2( x * exp2( 127 / p - 127 ) ) + 127 ) )
= cvtps2dq( p * ( cvtdq2ps( x * exp2( 127 / p - 127 ) ) ) )

exp2( 127 / p - 127 ) является постоянным фактором. Эта функция довольно специализирована: она не будет работать с небольшими дробными показателями, потому что постоянный коэффициент растет экспоненциально с инверсией экспоненты и будет переполняться. Он не будет работать с отрицательными показателями. Большие экспоненты приводят к высокой ошибке, потому что биты мантиссы смешиваются с битами экспоненты путем умножения.

Но это всего лишь 4 быстрых инструкций. Предварительно умножать, конвертировать из "целого" (в логарифм), умножать мощность, преобразовывать в "целое" (от логарифма). Конверсии очень быстрые в этой реализации SSE. Мы также можем сжать дополнительный постоянный коэффициент в первое умножение.

template< unsigned expnum, unsigned expden, unsigned coeffnum, unsigned coeffden >
__m128 fastpow( __m128 arg ) {
        __m128 ret = arg;
//      std::printf( "arg = %,vg\n", ret );
        // Apply a constant pre-correction factor.
        ret = _mm_mul_ps( ret, _mm_set1_ps( exp2( 127. * expden / expnum - 127. )
                * pow( 1. * coeffnum / coeffden, 1. * expden / expnum ) ) );
//      std::printf( "scaled = %,vg\n", ret );
        // Reinterpret arg as integer to obtain logarithm.
        asm ( "cvtdq2ps %1, %0" : "=x" (ret) : "x" (ret) );
//      std::printf( "log = %,vg\n", ret );
        // Multiply logarithm by power.
        ret = _mm_mul_ps( ret, _mm_set1_ps( 1. * expnum / expden ) );
//      std::printf( "powered = %,vg\n", ret );
        // Convert back to "integer" to exponentiate.
        asm ( "cvtps2dq %1, %0" : "=x" (ret) : "x" (ret) );
//      std::printf( "result = %,vg\n", ret );
        return ret;
}

Несколько исследований с показателем = 2.4 показывают, что это последовательно переоценивает примерно на 5%. (Подпрограмма всегда гарантирует переоценку.) Вы можете просто умножить на 0,95, но еще несколько инструкций приведут нас к 4 десятичным цифрам точности, которых должно быть достаточно для графики.

Ключ должен соответствовать переоценке с недооценкой и принимать среднее значение.

  • Вычислить x ^ 0.8: четыре команды, ошибка ~ +3%.
  • Вычислить x ^ -0.4: one rsqrtps. (Это достаточно точно, но приносит в жертву способность работать с нулем.)
  • Вычислить x ^ 0.4: один mulps.
  • Вычислить x ^ -0.2: one rsqrtps.
  • Вычислить x ^ 2: один mulps.
  • Вычислить x ^ 3: один mulps.
  • x ^ 2.4 = x ^ 2 * x ^ 0,4: один mulps. Это завышенная оценка.
  • x ^ 2.4 = x ^ 3 * x ^ -0.4 * x ^ -0.2: two mulps. Это недооценивается.
  • В среднем выше: один addps, один mulps.

Показатель команды: четырнадцать, включая две конверсии с латентностью = 5 и две взаимные оценки квадратного корня с пропускной способностью = 4.

Чтобы правильно принять среднее значение, мы хотим весить оценки по их ожидаемым ошибкам. Недооценка повышает погрешность до 0,6 против 0,4, поэтому мы ожидаем, что она будет равна 1.5x как ошибочная. Взвешивание не добавляет никаких инструкций; это можно сделать в префакторе. Вызов коэффициента a: a ^ 0.5 = 1.5 a ^ -0.75 и a = 1.38316186.

Конечная ошибка составляет около 0,015% или на 2 порядка лучше, чем исходный результат fastpow. Время выполнения составляет около дюжины циклов для цикла занятости с переменными источника и назначения volatile... хотя он перекрывает итерации, в реальном мире также будет отображаться уровень parallelism на уровне инструкций. Учитывая SIMD, это пропускная способность одного скалярного результата за 3 цикла!

int main() {
        __m128 const x0 = _mm_set_ps( 0.01, 1, 5, 1234.567 );
        std::printf( "Input: %,vg\n", x0 );

        // Approx 5% accuracy from one call. Always an overestimate.
        __m128 x1 = fastpow< 24, 10, 1, 1 >( x0 );
        std::printf( "Direct x^2.4: %,vg\n", x1 );

        // Lower exponents provide lower initial error, but too low causes overflow.
        __m128 xf = fastpow< 8, 10, int( 1.38316186 * 1e9 ), int( 1e9 ) >( x0 );
        std::printf( "1.38 x^0.8: %,vg\n", xf );

        // Imprecise 4-cycle sqrt is still far better than fastpow, good enough.
        __m128 xfm4 = _mm_rsqrt_ps( xf );
        __m128 xf4 = _mm_mul_ps( xf, xfm4 );

        // Precisely calculate x^2 and x^3
        __m128 x2 = _mm_mul_ps( x0, x0 );
        __m128 x3 = _mm_mul_ps( x2, x0 );

        // Overestimate of x^2 * x^0.4
        x2 = _mm_mul_ps( x2, xf4 );

        // Get x^-0.2 from x^0.4. Combine with x^-0.4 into x^-0.6 and x^2.4.
        __m128 xfm2 = _mm_rsqrt_ps( xf4 );
        x3 = _mm_mul_ps( x3, xfm4 );
        x3 = _mm_mul_ps( x3, xfm2 );

        std::printf( "x^2 * x^0.4: %,vg\n", x2 );
        std::printf( "x^3 / x^0.6: %,vg\n", x3 );
        x2 = _mm_mul_ps( _mm_add_ps( x2, x3 ), _mm_set1_ps( 1/ 1.960131704207789 ) );
        // Final accuracy about 0.015%, 200x better than x^0.8 calculation.
        std::printf( "average = %,vg\n", x2 );
}

Хорошо... жаль, что я не смог опубликовать это раньше. И расширение его до x ^ 1/2.4 оставлено в виде упражнения; v).

Обновление со статистикой

Я реализовал небольшую тестовую проводку и два случая x (5/ 12) которые соответствуют выше.

#include <cstdio>
#include <xmmintrin.h>
#include <cmath>
#include <cfloat>
#include <algorithm>
using namespace std;

template< unsigned expnum, unsigned expden, unsigned coeffnum, unsigned coeffden >
__m128 fastpow( __m128 arg ) {
    __m128 ret = arg;
//  std::printf( "arg = %,vg\n", ret );
    // Apply a constant pre-correction factor.
    ret = _mm_mul_ps( ret, _mm_set1_ps( exp2( 127. * expden / expnum - 127. )
        * pow( 1. * coeffnum / coeffden, 1. * expden / expnum ) ) );
//  std::printf( "scaled = %,vg\n", ret );
    // Reinterpret arg as integer to obtain logarithm.
    asm ( "cvtdq2ps %1, %0" : "=x" (ret) : "x" (ret) );
//  std::printf( "log = %,vg\n", ret );
    // Multiply logarithm by power.
    ret = _mm_mul_ps( ret, _mm_set1_ps( 1. * expnum / expden ) );
//  std::printf( "powered = %,vg\n", ret );
    // Convert back to "integer" to exponentiate.
    asm ( "cvtps2dq %1, %0" : "=x" (ret) : "x" (ret) );
//  std::printf( "result = %,vg\n", ret );
    return ret;
}

__m128 pow125_4( __m128 arg ) {
    // Lower exponents provide lower initial error, but too low causes overflow.
    __m128 xf = fastpow< 4, 5, int( 1.38316186 * 1e9 ), int( 1e9 ) >( arg );

    // Imprecise 4-cycle sqrt is still far better than fastpow, good enough.
    __m128 xfm4 = _mm_rsqrt_ps( xf );
    __m128 xf4 = _mm_mul_ps( xf, xfm4 );

    // Precisely calculate x^2 and x^3
    __m128 x2 = _mm_mul_ps( arg, arg );
    __m128 x3 = _mm_mul_ps( x2, arg );

    // Overestimate of x^2 * x^0.4
    x2 = _mm_mul_ps( x2, xf4 );

    // Get x^-0.2 from x^0.4, and square it for x^-0.4. Combine into x^-0.6.
    __m128 xfm2 = _mm_rsqrt_ps( xf4 );
    x3 = _mm_mul_ps( x3, xfm4 );
    x3 = _mm_mul_ps( x3, xfm2 );

    return _mm_mul_ps( _mm_add_ps( x2, x3 ), _mm_set1_ps( 1/ 1.960131704207789 * 0.9999 ) );
}

__m128 pow512_2( __m128 arg ) {
    // 5/12 is too small, so compute the sqrt of 10/12 instead.
    __m128 x = fastpow< 5, 6, int( 0.992245 * 1e9 ), int( 1e9 ) >( arg );
    return _mm_mul_ps( _mm_rsqrt_ps( x ), x );
}

__m128 pow512_4( __m128 arg ) {
    // 5/12 is too small, so compute the 4th root of 20/12 instead.
    // 20/12 = 5/3 = 1 + 2/3 = 2 - 1/3. 2/3 is a suitable argument for fastpow.
    // weighting coefficient: a^-1/2 = 2 a; a = 2^-2/3
    __m128 xf = fastpow< 2, 3, int( 0.629960524947437 * 1e9 ), int( 1e9 ) >( arg );
    __m128 xover = _mm_mul_ps( arg, xf );

    __m128 xfm1 = _mm_rsqrt_ps( xf );
    __m128 x2 = _mm_mul_ps( arg, arg );
    __m128 xunder = _mm_mul_ps( x2, xfm1 );

    // sqrt2 * over + 2 * sqrt2 * under
    __m128 xavg = _mm_mul_ps( _mm_set1_ps( 1/( 3 * 0.629960524947437 ) * 0.999852 ),
                                _mm_add_ps( xover, xunder ) );

    xavg = _mm_mul_ps( xavg, _mm_rsqrt_ps( xavg ) );
    xavg = _mm_mul_ps( xavg, _mm_rsqrt_ps( xavg ) );
    return xavg;
}

__m128 mm_succ_ps( __m128 arg ) {
    return (__m128) _mm_add_epi32( (__m128i) arg, _mm_set1_epi32( 4 ) );
}

void test_pow( double p, __m128 (*f)( __m128 ) ) {
    __m128 arg;

    for ( arg = _mm_set1_ps( FLT_MIN / FLT_EPSILON );
            ! isfinite( _mm_cvtss_f32( f( arg ) ) );
            arg = mm_succ_ps( arg ) ) ;

    for ( ; _mm_cvtss_f32( f( arg ) ) == 0;
            arg = mm_succ_ps( arg ) ) ;

    std::printf( "Domain from %g\n", _mm_cvtss_f32( arg ) );

    int n;
    int const bucket_size = 1 << 25;
    do {
        float max_error = 0;
        double total_error = 0, cum_error = 0;
        for ( n = 0; n != bucket_size; ++ n ) {
            float result = _mm_cvtss_f32( f( arg ) );

            if ( ! isfinite( result ) ) break;

            float actual = ::powf( _mm_cvtss_f32( arg ), p );

            float error = ( result - actual ) / actual;
            cum_error += error;
            error = std::abs( error );
            max_error = std::max( max_error, error );
            total_error += error;

            arg = mm_succ_ps( arg );
        }

        std::printf( "error max = %8g\t" "avg = %8g\t" "|avg| = %8g\t" "to %8g\n",
                    max_error, cum_error / n, total_error / n, _mm_cvtss_f32( arg ) );
    } while ( n == bucket_size );
}

int main() {
    std::printf( "4 insn x^12/5:\n" );
    test_pow( 12./5, & fastpow< 12, 5, 1059, 1000 > );
    std::printf( "14 insn x^12/5:\n" );
    test_pow( 12./5, & pow125_4 );
    std::printf( "6 insn x^5/12:\n" );
    test_pow( 5./12, & pow512_2 );
    std::printf( "14 insn x^5/12:\n" );
    test_pow( 5./12, & pow512_4 );
}

Вывод:

4 insn x^12/5:
Domain from 1.36909e-23
error max =      inf    avg =      inf  |avg| =      inf    to 8.97249e-19
error max =  2267.14    avg =  139.175  |avg| =  139.193    to 5.88021e-14
error max = 0.123606    avg = -0.000102963  |avg| = 0.0371122   to 3.85365e-09
error max = 0.123607    avg = -0.000108978  |avg| = 0.0368548   to 0.000252553
error max =  0.12361    avg = 7.28909e-05   |avg| = 0.037507    to  16.5513
error max = 0.123612    avg = -0.000258619  |avg| = 0.0365618   to 1.08471e+06
error max = 0.123611    avg = 8.70966e-05   |avg| = 0.0374369   to 7.10874e+10
error max =  0.12361    avg = -0.000103047  |avg| = 0.0371122   to 4.65878e+15
error max = 0.123609    avg =      nan  |avg| =      nan    to 1.16469e+16
14 insn x^12/5:
Domain from 1.42795e-19
error max =      inf    avg =      nan  |avg| =      nan    to 9.35823e-15
error max = 0.000936462 avg = 2.0202e-05    |avg| = 0.000133764 to 6.13301e-10
error max = 0.000792752 avg = 1.45717e-05   |avg| = 0.000129936 to 4.01933e-05
error max = 0.000791785 avg = 7.0132e-06    |avg| = 0.000129923 to  2.63411
error max = 0.000787589 avg = 1.20745e-05   |avg| = 0.000129347 to   172629
error max = 0.000786553 avg = 1.62351e-05   |avg| = 0.000132397 to 1.13134e+10
error max = 0.000785586 avg = 8.25205e-06   |avg| = 0.00013037  to 6.98147e+12
6 insn x^5/12:
Domain from 9.86076e-32
error max = 0.0284339   avg = 0.000441158   |avg| = 0.00967327  to 6.46235e-27
error max = 0.0284342   avg = -5.79938e-06  |avg| = 0.00897913  to 4.23516e-22
error max = 0.0284341   avg = -0.000140706  |avg| = 0.00897084  to 2.77556e-17
error max = 0.028434    avg = 0.000440504   |avg| = 0.00967325  to 1.81899e-12
error max = 0.0284339   avg = -6.11153e-06  |avg| = 0.00897915  to 1.19209e-07
error max = 0.0284298   avg = -0.000140597  |avg| = 0.00897084  to 0.0078125
error max = 0.0284371   avg = 0.000439748   |avg| = 0.00967319  to      512
error max = 0.028437    avg = -7.74294e-06  |avg| = 0.00897924  to 3.35544e+07
error max = 0.0284369   avg = -0.000142036  |avg| = 0.00897089  to 2.19902e+12
error max = 0.0284368   avg = 0.000439183   |avg| = 0.0096732   to 1.44115e+17
error max = 0.0284367   avg = -7.41244e-06  |avg| = 0.00897923  to 9.44473e+21
error max = 0.0284366   avg = -0.000141706  |avg| = 0.00897088  to 6.1897e+26
error max = 0.485129    avg = -0.0401671    |avg| = 0.048422    to 4.05648e+31
error max = 0.994932    avg = -0.891494 |avg| = 0.891494    to 2.65846e+36
error max = 0.999329    avg =      nan  |avg| =      nan    to       -0
14 insn x^5/12:
Domain from 2.64698e-23
error max =  0.13556    avg = 0.00125936    |avg| = 0.00354677  to 1.73472e-18
error max = 0.000564988 avg = 2.51458e-06   |avg| = 0.000113709 to 1.13687e-13
error max = 0.000565065 avg = -1.49258e-06  |avg| = 0.000112553 to 7.45058e-09
error max = 0.000565143 avg = 1.5293e-06    |avg| = 0.000112864 to 0.000488281
error max = 0.000565298 avg = 2.76457e-06   |avg| = 0.000113713 to       32
error max = 0.000565453 avg = -1.61276e-06  |avg| = 0.000112561 to 2.09715e+06
error max = 0.000565531 avg = 1.42628e-06   |avg| = 0.000112866 to 1.37439e+11
error max = 0.000565686 avg = 2.71505e-06   |avg| = 0.000113715 to 9.0072e+15
error max = 0.000565763 avg = -1.56586e-06  |avg| = 0.000112415 to 1.84467e+19

Я подозреваю, что точность более точного 5/12 ограничена операцией rsqrt.

Ответ 2

Другой ответ, потому что это сильно отличается от моего предыдущего ответа, и это быстро вспыхивает. Относительная погрешность составляет 3e-8. Хотите больше точности? Добавьте еще несколько терминов Чебычева. Лучше держать порядок нечетным, поскольку это приводит к небольшому разрыву между 2 ^ n-эпсилом и 2 ^ n + эпсилон.

#include <stdlib.h>
#include <math.h>

// Returns x^(5/12) for x in [1,2), to within 3e-8 (relative error).
// Want more precision? Add more Chebychev polynomial coefs.
double pow512norm (
   double x)
{
   static const int N = 8;

   // Chebychev polynomial terms.
   // Non-zero terms calculated via
   //   integrate (2/pi)*ChebyshevT[n,u]/sqrt(1-u^2)*((u+3)/2)^(5/12)
   //   from -1 to 1
   // Zeroth term is similar except it uses 1/pi rather than 2/pi.
   static const double Cn[N] = { 
       1.1758200232996901923,
       0.16665763094889061230,
      -0.0083154894939042125035,
       0.00075187976780420279038,
      // Wolfram alpha doesn't want to compute the remaining terms
      // to more precision (it times out).
      -0.0000832402,
       0.0000102292,
      -1.3401e-6,
       1.83334e-7};

   double Tn[N];

   double u = 2.0*x - 3.0;

   Tn[0] = 1.0;
   Tn[1] = u;
   for (int ii = 2; ii < N; ++ii) {
      Tn[ii] = 2*u*Tn[ii-1] - Tn[ii-2];
   }   

   double y = 0.0;
   for (int ii = N-1; ii >= 0; --ii) {
      y += Cn[ii]*Tn[ii];
   }   

   return y;
}


// Returns x^(5/12) to within 3e-8 (relative error).
double pow512 (
   double x)
{
   static const double pow2_512[12] = {
      1.0,
      pow(2.0, 5.0/12.0),
      pow(4.0, 5.0/12.0),
      pow(8.0, 5.0/12.0),
      pow(16.0, 5.0/12.0),
      pow(32.0, 5.0/12.0),
      pow(64.0, 5.0/12.0),
      pow(128.0, 5.0/12.0),
      pow(256.0, 5.0/12.0),
      pow(512.0, 5.0/12.0),
      pow(1024.0, 5.0/12.0),
      pow(2048.0, 5.0/12.0)
   };

   double s;
   int iexp;

   s = frexp (x, &iexp);
   s *= 2.0;
   iexp -= 1;

   div_t qr = div (iexp, 12);
   if (qr.rem < 0) {
      qr.quot -= 1;
      qr.rem += 12;
   }

   return ldexp (pow512norm(s)*pow2_512[qr.rem], 5*qr.quot);
}

Добавление: Что здесь происходит?
По запросу ниже объясняется, как работает вышеуказанный код.

Обзор
Вышеприведенный код определяет две функции: double pow512norm (double x) и double pow512 (double x). Последнее является точкой входа в набор; это функция, которую код пользователя должен вызывать для вычисления x ^ (5/12). Функция pow512norm(x) использует полиномы Чебышева для приближения x ^ (5/12), но только для x в диапазоне [1,2]. (Используйте pow512norm(x) для значений x вне этого диапазона, и результатом будет мусор.)

Функция pow512(x) разбивает входящую x на пару (double s, int n) такую, что x = s * 2^n и такая, что 1≤ s < 2. Дальнейшее разбиение n на (int q, unsigned int r) такое, что n = 12*q + r и r меньше 12, позволяет мне разделить проблему нахождения x ^ (5/12) на части:

  • x^(5/12)=(s^(5/12))*((2^n)^(5/12)) через (uv) ^ a = (u ^ a) (v ^ a) для положительных u, v и вещественных a.
  • s^(5/12) вычисляется через pow512norm(s).
  • (2^n)^(5/12)=(2^(12*q+r))^(5/12) с помощью замены.
  • 2^(12*q+r)=(2^(12*q))*(2^r) через u^(a+b)=(u^a)*(u^b) для положительных u, вещественных a, b.
  • (2^(12*q+r))^(5/12)=(2^(5*q))*((2^r)^(5/12)) с помощью нескольких манипуляций.
  • (2^r)^(5/12) вычисляется по таблице поиска pow2_512.
  • Рассчитайте pow512norm(s)*pow2_512[qr.rem], и мы почти там. Здесь qr.rem - значение r, вычисленное на шаге 3 выше. Все, что необходимо, - это умножить это на 2^(5*q), чтобы получить желаемый результат.
  • Это именно то, что делает функция математической библиотеки ldexp.

Приближение функций
Цель здесь состоит в том, чтобы придумать легко вычислимую аппроксимацию f (x) = x ^ (5/12), которая "достаточно хороша" для рассматриваемой проблемы. Наше приближение должно быть близко к f (x) в некотором смысле. Риторический вопрос: что означает "близко к"? Две конкурирующие интерпретации сводят к минимуму среднеквадратичную ошибку и минимизируют максимальную абсолютную ошибку.

Я буду использовать аналогию с фондовым рынком, чтобы описать разницу между ними. Предположим, вы хотите сохранить для своего возможного выхода на пенсию. Если вам исполнилось двадцать три года, лучше всего инвестировать в акции или фондовые рынки. Это связано с тем, что в течение достаточно длительного промежутка времени фондовый рынок в среднем превосходит любую другую инвестиционную схему. Тем не менее, мы все видели времена, когда вкладывать деньги в акции - это очень плохо. Если вам за пятьдесят или шестидесятые годы (или 40 лет, если вы хотите уйти в отставку), вам нужно инвестировать немного более консервативно. Эти спады могут нанести ущерб вашему пенсионному портфелю.

Возврат к аппроксимации функции: как потребитель в каком-то приближении, вас обычно беспокоит ошибка наихудшего случая, а не производительность "в среднем". Используйте некоторое приближение, созданное для обеспечения максимальной производительности "в среднем" (например, наименьших квадратов), а закон Мерфи требует, чтобы ваша программа потратила много времени, используя аппроксимацию, где производительность намного хуже средней. То, что вы хотите, - это минимаксная аппроксимация, что минимизирует максимальную абсолютную ошибку над некоторым доменом. Хорошая математическая библиотека будет использовать минимаксный подход, а не метод наименьших квадратов, потому что это позволяет авторам математической библиотеки дать некоторую гарантированную производительность своей библиотеки.

В математических библиотеках обычно используется полином или рациональный многочлен для аппроксимации некоторой функции f (x) над некоторой областью a≤x≤b. Предположим, что функция f (x) аналитична по этой области и вы хотите аппроксимировать функцию некоторым полиномом p (x) степени N. Для данной степени N существует некоторый магический единственный многочлен p (x) такой, что p ( x) -f (x) имеет N + 2 экстремумов над [a, b] и такие, что абсолютные значения этих экстремумов N + 2 равны друг другу. Поиск этого магического многочлена p (x) является святым граалем аппроксиматоров функций.

Я не нашел для тебя святого Грааля. Вместо этого я использовал чебышевское приближение. Многочлены Чебышева первого рода являются ортогональным (но не ортонормированным) множеством многочленов с некоторыми очень хорошими чертами, когда речь идет о приближении функции. Чебышевское приближение часто очень близко к этому магическому многочлену р (х). (На самом деле алгоритм обмена Ремеза, который находит этот полиномиальный святой граф, обычно начинается с чебышевского приближения.)

pow512norm (х)
Эта функция использует чебышевское приближение для нахождения некоторого многочлена p * (x), который аппроксимирует x ^ (5/12). Здесь я использую p * (x), чтобы отличить это чебышевское приближение от описанного выше магического многочлена p (x). Чебышевское приближение p * (x) легко найти; нахождение p (x) является медведем. Чебышевское приближение p * (x) равно sum_i Cn [i] * Tn (i, x), где Cn [i] - коэффициенты Чебышева, а Tn (i, x) - полиномы Чебышева, оцененные в точке x.

Я использовал Вольфрам альфа, чтобы найти чебышевские коэффициенты Cn для меня. Например, вычисляет Cn[1]. В первом поле после поля ввода есть нужный ответ, 0.166658 в этом случае. Это не так много цифр, как хотелось бы. Нажмите "Больше цифр" и вуаля, вы получите намного больше цифр. Вольфрам альфа свободен; есть ли предел того, сколько вычислений он сделает. Он попадает в этот предел для членов более высокого порядка. (Если вы покупаете или имеете доступ к математике, вы сможете вычислить эти коэффициенты высокого порядка с высокой степенью точности.)

Многочлены Чебышева Tn (x) вычисляются в массиве Tn. Помимо получения чего-то очень близкого к магическому многочлену p (x), еще одной причиной использования чебышевской аппроксимации является то, что значения этих многочленов Чебышева легко вычисляются: Начните с Tn[0]=1 и Tn[1]=x, а затем итеративно вычислите Tn[i]=2*x*Tn[i-1] - Tn[i-2]. (Я использовал "ii" как индексную переменную, а не "i" в своем коде.Я никогда не использую "i" в качестве имени переменной. Сколько слов на английском языке имеет слово "i" в слове? последовательные 'i's?)

pow512 (х)
pow512 - это функция, которую должен вызывать код пользователя. Я уже описал основы этой функции выше. Еще несколько деталей. Функция математической библиотеки frexp(x) возвращает значение s и экспоненту iexp для ввода x. (Незначительная проблема: я хочу s между 1 и 2 для использования с pow512norm, но frexp возвращает значение от 0,5 до 1.) Функция математической библиотеки div возвращает коэффициент и остаток для целочисленного деления на одну волну foop. Наконец, я использую функцию математической библиотеки ldexp, чтобы собрать три части для окончательного ответа.

Ответ 3

Ян Стивенсон написал этот код, который, по его словам, превосходит pow(). Он описывает идею следующим образом:

Pow в основном реализуется с использованием log: pow(a,b)=x(logx(a)*b). поэтому мы нужен быстрый журнал и быстрый показатель - он не имеет значения, какой x мы используем 2. Фокус в том, что с плавающей запятой номер уже находится в стиле журнала Формат:

a=M*2E

Принимая лог с обеих сторон, получаем:

log2(a)=log2(M)+E

или более просто:

log2(a)~=E

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

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

Ответ 4

Во-первых, использование поплавков в настоящее время не собирается покупать много на большинстве машин. Фактически, удваивается может быть быстрее. Ваша мощность, 1.0/2.4, составляет 5/12 или 1/3 * (1 + 1/4). Несмотря на то что это вызов cbrt (один раз) и sqrt (дважды!), Он по-прежнему в два раза быстрее, чем при использовании pow(). (Оптимизация: -O3, компилятор: i686-apple-darwin10-g++ - 4.2.1).

#include <math.h> // cmath does not provide cbrt; C99 does.
double xpow512 (double x) {
  double cbrtx = cbrt(x);
  return cbrtx*sqrt(sqrt(cbrtx));
}

Ответ 5

Это может не ответить на ваш вопрос.

2.4f и 1/2.4f делают меня очень подозрительным, потому что это именно то, что используется для преобразования между sRGB и линейным цветовым пространством RGB. Поэтому вы, вероятно, пытаетесь оптимизировать это, в частности. Я не знаю, поэтому это может не ответить на ваш вопрос.

Если это так, попробуйте использовать таблицу поиска. Что-то вроде:

__attribute__((aligned(64))
static const unsigned short SRGB_TO_LINEAR[256] = { ... };
__attribute__((aligned(64))
static const unsigned short LINEAR_TO_SRGB[256] = { ... };

void apply_lut(const unsigned short lut[256], unsigned char *src, ...

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

(Причина, по которой sRGB не имеет смысла, поскольку с плавающей точкой следует, что HDR должен быть линейным, а sRGB удобен только для хранения на диске или отображения на экране, но не подходит для манипуляции.)

Ответ 6

Серия Binomial учитывает постоянный показатель, но вы сможете использовать его только в том случае, если вы можете нормализовать весь свой вход в диапазон [1,2). (Заметим, что он вычисляет (1 + x) ^ a). Вам нужно будет сделать некоторый анализ, чтобы решить, сколько терминов вам нужно для желаемой точности.

Ответ 7

Для экспонентов 2.4 вы можете либо составить таблицу поиска для всех ваших значений 2.4, либо функцию lirp или, возможно, более высокого порядка, чтобы заполнить значения in-betweem, если таблица не была достаточно точной (в основном, огромная таблица журналов.)

Или значение значения квадрата * для 2/5s, которое может принимать начальное значение квадрата из первой половины функции, а затем 5-го корня. Для 5-го корня вы могли бы использовать Newton или сделать какой-то другой быстрый аппроксиматор, хотя, честно говоря, как только вы доберетесь до этого момента, вам, вероятно, лучше просто выполнять функции exp и log с соответствующими сокращенными функциями серии.

Ответ 8

Ниже приведена идея, которую вы можете использовать с помощью любого из быстрых методов расчета. Помогает ли это быстрее, зависит от того, как поступают ваши данные. Вы можете использовать тот факт, что, если вы знаете x и pow(x, n), вы можете использовать скорость изменения мощности, чтобы вычислить разумную аппроксимацию pow(x + delta, n) для небольших delta, с одним умножением и добавлением (подробнее или менее). Если последовательные значения, которые вы передаете своим силовым функциям, достаточно близко друг к другу, это приведет к амортизации полной стоимости точного расчета по нескольким вызовам функций. Обратите внимание, что для получения производной вам не требуется вычисление дополнительной мощности. Вы можете расширить это, чтобы использовать вторую производную, чтобы вы могли использовать квадратичную форму, что увеличило бы delta, которое вы могли бы использовать, и все равно получало бы ту же точность.

Ответ 9

Я отвечу на вопрос, который вы действительно хотели спросить, и как быстро выполнить преобразование RGB с RGB и линейным RGB. Чтобы сделать это точно и эффективно, мы можем использовать полиномиальные аппроксимации. Следующие последующие полиномиальные аппроксимации были получены с сольлей и имеют наихудшую относительную погрешность 0,0144%.

inline double poly7(double x, double a, double b, double c, double d,
                              double e, double f, double g, double h) {
    double ab, cd, ef, gh, abcd, efgh, x2, x4;
    x2 = x*x; x4 = x2*x2;
    ab = a*x + b; cd = c*x + d;
    ef = e*x + f; gh = g*x + h;
    abcd = ab*x2 + cd; efgh = ef*x2 + gh;
    return abcd*x4 + efgh;
}

inline double srgb_to_linear(double x) {
    if (x <= 0.04045) return x / 12.92;

    // Polynomial approximation of ((x+0.055)/1.055)^2.4.
    return poly7(x, 0.15237971711927983387,
                   -0.57235993072870072762,
                    0.92097986411523535821,
                   -0.90208229831912012386,
                    0.88348956209696805075,
                    0.48110797889132134175,
                    0.03563925285274562038,
                    0.00084585397227064120);
}

inline double linear_to_srgb(double x) {
    if (x <= 0.0031308) return x * 12.92;

    // Piecewise polynomial approximation (divided by x^3)
    // of 1.055 * x^(1/2.4) - 0.055.
    if (x <= 0.0523) return poly7(x, -6681.49576364495442248881,
                                      1224.97114922729451791383,
                                      -100.23413743425112443219,
                                         6.60361150127077944916,
                                         0.06114808961060447245,
                                        -0.00022244138470139442,
                                         0.00000041231840827815,
                                        -0.00000000035133685895) / (x*x*x);

    return poly7(x, -0.18730034115395793881,
                     0.64677431008037400417,
                    -0.99032868647877825286,
                     1.20939072663263713636,
                     0.33433459165487383613,
                    -0.01345095746411287783,
                     0.00044351684288719036,
                    -0.00000664263587520855) / (x*x*x);
}

И вход sollya, используемый для генерации многочленов:

suppressmessage(174);
f = ((x+0.055)/1.055)^2.4;
p0 = fpminimax(f, 7, [|D...|], [0.04045;1], relative);
p = fpminimax(f/(p0(1)+1e-18), 7, [|D...|], [0.04045;1], relative);
print("relative:", dirtyinfnorm((f-p)/f, [s;1]));
print("absolute:", dirtyinfnorm((f-p), [s;1]));
print(canonical(p));

s = 0.0523;
z = 3;
f = 1.055 * x^(1/2.4) - 0.055;

p = fpminimax(1.055 * (x^(z+1/2.4) - 0.055*x^z/1.055), 7, [|D...|], [0.0031308;s], relative)/x^z;
print("relative:", dirtyinfnorm((f-p)/f, [0.0031308;s]));
print("absolute:", dirtyinfnorm((f-p), [0.0031308;s]));
print(canonical(p));

p = fpminimax(1.055 * (x^(z+1/2.4) - 0.055*x^z/1.055), 7, [|D...|], [s;1], relative)/x^z;
print("relative:", dirtyinfnorm((f-p)/f, [s;1]));
print("absolute:", dirtyinfnorm((f-p), [s;1]));
print(canonical(p));

Ответ 10

Таким образом, традиционно powf(x, p) = x^p решается путем перезаписи x как x=2^(log2(x)), делающего powf(x,p) = 2^(p*log2(x)), что превращает задачу в два приближения exp2() и log2(). Это имеет преимущество в работе с большими мощностями p, однако недостатком является то, что это не оптимальное решение для постоянной мощности p и по заданной входной границе 0 ≤ x ≤ 1.

При мощности p > 1 ответ представляет собой тривиальный минимаксный многочлен над границей 0 ≤ x ≤ 1, что имеет место для p = 12/5 = 2.4, как можно видеть ниже:

float pow12_5(float x){
    float mp;
    // Minimax horner polynomials for x^(5/12), Note: choose the accurarcy required then implement with fma() [Fused Multiply Accumulates]
    // mp = 0x4.a84a38p-12 + x * (-0xd.e5648p-8 + x * (0xa.d82fep-4 + x * 0x6.062668p-4)); // 1.13705697e-3
    mp = 0x1.117542p-12 + x * (-0x5.91e6ap-8 + x * (0x8.0f50ep-4 + x * (0xa.aa231p-4 + x * (-0x2.62787p-4))));  // 2.6079002e-4
    // mp = 0x5.a522ap-16 + x * (-0x2.d997fcp-8 + x * (0x6.8f6d1p-4 + x * (0xf.21285p-4 + x * (-0x7.b5b248p-4 + x * 0x2.32b668p-4))));  // 8.61377e-5
    // mp = 0x2.4f5538p-16 + x * (-0x1.abcdecp-8 + x * (0x5.97464p-4 + x * (0x1.399edap0 + x * (-0x1.0d363ap0 + x * (0xa.a54a3p-4 + x * (-0x2.e8a77cp-4))))));  // 3.524655e-5
    return(mp);
}

Однако, когда p < 1 минимаксная аппроксимация над границей 0 ≤ x ≤ 1 не сходится с нужной точностью. Один вариант [на самом деле] заключается в том, чтобы переписать проблему y=x^p=x^(p+m)/x^m, где m=1,2,3 является положительным целым числом, создавая новое приближение мощности p > 1, но это вводит деление, которое по своей сути медленнее.

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

x = mx* 2^(ex) where 1 ≤ mx < 2
y = x^(5/12) = mx^(5/12) * 2^((5/12)*ex), let ey = floor(5*ex/12), k = (5*ex) % 12
  = mx^(5/12) * 2^(k/12) * 2^(ey)

Минимаксная аппроксимация mx^(5/12) над 1 ≤ mx < 2 теперь сходится намного быстрее, чем раньше, без деления, но требует 12 точек LUT для 2^(k/12). Код ниже:

float powk_12LUT[] = {0x1.0p0, 0x1.0f38fap0, 0x1.1f59acp0,  0x1.306fep0, 0x1.428a3p0, 0x1.55b81p0, 0x1.6a09e6p0, 0x1.7f910ep0, 0x1.965feap0, 0x1.ae89fap0, 0x1.c823ep0, 0x1.e3437ep0};
float pow5_12(float x){
    union{float f; uint32_t u;} v, e2;
    float poff, m, e, ei;
    int xe;

    v.f = x;
    xe = ((v.u >> 23) - 127);

    if(xe < -127) return(0.0f);

    // Calculate remainder k in 2^(k/12) to find LUT
    e = xe * (5.0f/12.0f);
    ei = floorf(e);
    poff = powk_12LUT[(int)(12.0f * (e - ei))];

    e2.u = ((int)ei + 127) << 23;   // Calculate the exponent
    v.u = (v.u & ~(0xFFuL << 23)) | (0x7FuL << 23); // Normalize exponent to zero

    // Approximate mx^(5/12) on [1,2), with appropriate degree minimax
    // m = 0x8.87592p-4 + v.f * (0x8.8f056p-4 + v.f * (-0x1.134044p-4));    // 7.6125e-4
    // m = 0x7.582138p-4 + v.f * (0xb.1666bp-4 + v.f * (-0x2.d21954p-4 + v.f * 0x6.3ea0cp-8));  // 8.4522726e-5
    m = 0x6.9465cp-4 + v.f * (0xd.43015p-4 + v.f * (-0x5.17b2a8p-4 + v.f * (0x1.6cb1f8p-4 + v.f * (-0x2.c5b76p-8))));   // 1.04091259e-5
    // m = 0x6.08242p-4 + v.f * (0xf.352bdp-4 + v.f * (-0x7.d0c1bp-4 + v.f * (0x3.4d153p-4 + v.f * (-0xc.f7a42p-8 + v.f * 0x1.5d840cp-8))));    // 1.367401e-6

    return(m * poff * e2.f);
}