Эффективный метод вычисления логарифмической базы 2 числа от 1 до 2.

Я работаю на платформе с фиксированной запятой (арифметика с плавающей запятой не поддерживается).

Я представляю любое рациональное число q как минимальное значение q * (1 << precision).

Мне нужен эффективный метод для вычисления базы журнала 2 из x, где 1 < x < 2.

Вот что я сделал до сих пор:

uint64_t Log2(uint64_t x, uint8_t precision)
{
    uint64 res = 0;

    uint64 one = (uint64_t)1 << precision;
    uint64 two = (uint64_t)2 << precision;

    for (uint8_t i = precision; i > 0 ; i--)
    {
        x = (x * x) / one; // now 1 < x < 4
        if (x >= two)
        {
            x >>= 1; // now 1 < x < 2
            res += (uint64_t)1 << (i - 1);
        }
    }

    return res;
}

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

Как бы то ни было, используемое precision равно 31, но это может измениться, поэтому мне нужно сохранить его как переменную.

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

Я думал о чем-то вроде "сначала умножь, потом суммируй".

Но это подразумевало бы вычисление x ^ (2 ^ precision), которое очень быстро переполнилось бы.

Спасибо.

ОБНОВЛЕНИЕ:

Раньше я пытался избавиться от ветки, но это только ухудшило ситуацию:

for (uint8_t i = precision; i > 0 ; i--)
{
    x = (x * x) / one; // now 1 < x < 4
    uint64_t n = x / two;
    x >>= n; // now 1 < x < 2
    res += n << (i - 1);
}

return res;

c optimization performance logarithm fixed-point
person goodvibration    schedule 03.08.2017    source источник
comment
Дублировать? stackoverflow.com/ вопросы/4657468/   -  person GManNickG    schedule 04.08.2017
comment
Почему деление на one? Разве x = (x * x) >> precision не эквивалентно?   -  person rodrigo    schedule 04.08.2017
comment
@GManNickG: Не совсем так. Я вижу вещи, похожие на то, что я написал, но нет предложений по оптимизации этого цикла (может быть, это просто невозможно, но я все же хотел бы прочитать некоторые мнения об этом).   -  person goodvibration    schedule 04.08.2017
comment
@родриго: да. Не беспокойтесь о производительности деления и сдвига вправо. На моей базовой платформе они эквивалентны.   -  person goodvibration    schedule 04.08.2017
comment
Если точность равна 32, а x находится между 1 и 2, то представление x с фиксированной точкой имеет 33 бита. Выполнение (x * x) приведет к переполнению 66 битов типа uint64_t.   -  person rodrigo    schedule 04.08.2017
comment
@rodrigo: Извините, вы меня поняли. Фактическая платформа поддерживает uint256_t, но я не хотел упоминать об этом здесь (и начать получать несвязанные вопросы о платформе). Так что не стесняйтесь пересматривать precision=31, и я исправлю это в вопросе. Спасибо.   -  person goodvibration    schedule 04.08.2017
comment
Достаточно ли памяти для справочной таблицы?   -  person deamentiaemundi    schedule 04.08.2017
comment
Что это за платформа? Вы на самом деле синтезируете это для FPGA или что-то в этом роде?   -  person harold    schedule 04.08.2017

Ответы (2)


arrow_upward
1
arrow_downward

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

uint64_t Log2(uint64_t x, uint8_t precision)
{
    uint64_t res = 0;
    uint64_t two = (uint64_t)2 << precision;

    for (uint64_t b = (uint64_t)1 << (precision - 1); b; b >>= 1)
    {
        x = (x * x) >> precision; // now 1 < x < 4
        if (x & two)
        {
            x >>= 1; // now 1 < x < 2
            res |= b;
        }
    }
    return res;
}
person rodrigo    schedule 03.08.2017

arrow_upward
1
arrow_downward

Мое предложение пойдет в противоположном направлении — к использованию постоянной производительности при фиксированном количестве шагов.

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

Разложение Тейлора (с 1715 года) log2(x) обеспечивает прочную основу исчисления плюс (почти) бесконечную точность, априори известную как выполнимую для любой глубины арифметики с фиксированной точкой (будь то для Epiphany / FPGA / ASIC / you держи это в секрете / ... )

Математика преобразует всю проблему в опционально небольшое количество нескольких узловых точек X_tab_i, для которых (столько, сколько требует точность платформы) константы предварительно рассчитан для каждой точки узла. Остальное представляет собой эффективную для платформы сборку суммы продуктов Тейлора, при условии, что результат получается как в постоянном времени, так и с остаточной ошибкой ниже порогового значения, определяемого проектом (целевой компромисс ограничений PSPACE x PTIME здесь очевиден для этапа проектирования, тем не менее процесс всегда является CTIME, CSPACE после развертывания )

Вуаля:

Given X: lookup closest  X_tab_i,
                with    C0_tab_i, C1_tab_i, C2_tab_i, .., Cn_tab_i
//-----------------------------------------------------------------<STATIC/CONST>
//            ![i]
#DEFINE  C0_tab_i  <log2( X_tab_i )>
#DEFINE  C1_tab_i  <    ( X_tab_i )^(-1) * ( +1         / ( 1 * ln(2) )>
#DEFINE  C2_tab_i  <    ( X_tab_i )^(-2) * ( -1         / ( 2 * ln(2) )>
#DEFINE  C3_tab_i  <    ( X_tab_i )^(-3) * ( +1         / ( 3 * ln(2) )>
:::       :                           :                     :
#DEFINE  CN_tab_i  <    ( X_tab_i )^(-N) * ( -1^(N-1) ) / ( N * ln(2) )>

// -----------------------------------------------------------------<PROCESS>-BEG
DIFF  = X - X_tab_i;     CORR  = DIFF;
RES   = C0_tab_i
      + C1_tab_i * CORR; CORR *= DIFF;
RES  += C2_tab_i * CORR; CORR *= DIFF;
...  +=
RES  += Cn_tab_i * CORR; CORR *= DIFF;
// --------------------------------------------------------------<PROCESS>-END:
person user3666197    schedule 04.08.2017