Оптимизация алгоритма: логарифмирование по расчету или таблице поиска

Если вам действительно нужно

ceil(12 * log2(/* something */))

тогда есть очень простое вычисление O (1), которое будет работать, используя таблицу только из 12 значений.

1. Используйте frexp(), чтобы разделить значение на экспоненту и мантиссу. (Это всего лишь битовая манипуляция, так что это займет всего пару циклов.)

2. Найдите мантиссу в предварительно вычисленном списке степеней 12-го корня из 2,0 (деленного на 2), что вы можете сделать не более чем с четырьмя сравнениями.

3. Результат: 12*(показатель степени - 1) + индекс наименьшего корня >= мантисса.

Отредактировано, чтобы добавить:

На самом деле есть еще лучшее решение, потому что степени 12-го корня из двух распределены достаточно равномерно. Если вы разделите [0,5, 1,0) (диапазон мантиссы, возвращаемый frexp) на 17 равномерно расположенных поддиапазонов, каждый поддиапазон попадет в одно из двух возможных возвращаемых значений. Поэтому, если вы связываете каждый поддиапазон с индексом в векторе корней, вам нужно только сравнить цель (в пределах этого диапазона) с одним корнем.

Мне слишком поздно писать связный английский, поэтому вам придется довольствоваться кодом:

int Ceil12TimesLog2(double x) {
  int exp;
  double mantissa = std::frexp(x, &exp) * 2;
  int idx = indexes[int((mantissa - 1.0) * 17)];
  return 12 * (exp - 1) + (mantissa <= roots[idx] ? idx : idx + 1);
}

// Here are the reference tables.

double roots[12] = {
  0x1.0000000000000p+0,
  0x1.0f38f92d97963p+0,
  0x1.1f59ac3c7d6c0p+0,
  0x1.306fe0a31b715p+0,
  0x1.428a2f98d728bp+0,
  0x1.55b8108f0ec5ep+0,
  0x1.6a09e667f3bccp+0,
  0x1.7f910d768cfb0p+0,
  0x1.965fea53d6e3dp+0,
  0x1.ae89f995ad3adp+0,
  0x1.c823e074ec129p+0,
  0x1.e3437e7101344p+0
};
int indexes[17] = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11 };

Я попробовал это, и это сокращает общее время вычислений примерно с 0,5 секунды (для log2f) до примерно 0,15 секунды, используя цикл в OP. Общий размер справочных таблиц составляет 164 байта.

Написав z для краткости и ясности вместо fk, ваш внутренний цикл вычисляет ceil(12 * log2f((f - 0.5) / z)). Теперь 12 * log2f((f - 0.5) / z) = 12*log2f(f - 0.5) - 12*log2f(z). Предварительно вычислите массив с 999 элементами, что позволит вам вычислить все значения только с 11998 вычислениями логарифмов вместо 10988001 из них:

for (int z=1; z<1000; ++z)
  z12[z] = 12 * log2f(z);

for (int f=1; f<11000; ++f) {
  w = 12 * log2f(f - 0.5);
  for (int z=1; z<1000; ++z) {
    int k = ceil(w - z12[z]);
  }
} 

Я нашел:

• Хотя у вас есть 11Kx1K = 11M комбинаций (f, fk),
• количество различных значений k составляет всего 294 (для его представления вам нужно всего 9 бит).

Так что определенно вы можете построить 2d-массив для хранения отображения и загрузить его в память. Это выглядит как

LOOKUP[f][fk] = v, f in 1..11000, fk in 1..1000 
--------------------
v1,1 v1,2 v1,3 ... v1,1000
v2,1 v2,2 v2,3 ... v2,1000
...    ...    ...  ...
v11000,1 , ...     v11000,1000

Поскольку каждые v составляют два байта, вам нужно всего 11Kx1Kx2B = 22 МБ памяти для загрузки этой таблицы. Это ничего.

Если порядок цикла обратный, то количество повторяющихся значений для k становится намного больше. Тогда в наборе всего 12977 случаев, когда k имеет «единичную серию»; Самая длинная серия 618.

Это предполагает, что обратный подход минимизирует число вызовов log2f — нужно вычислить индекс n, где k(z,f+n) != k(z,f) (и зациклить n экземпляров...)

Во всяком случае, в конечном продукте я сомневаюсь в пользе огромного LUT. Даже подход с использованием таблиц размером 11000 + 1000 кажется мне неоптимальным. Вместо этого я бы предположил, что только с 11000 + 1000 целых чисел существует либо линейное, либо максимальное кусочно-полиномиальное приближение 2-й степени к log2, которое состоит из 8-16 частей.

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