Аппроксимируя log10 [x ^ k0 + k1]

Привет. Я пытаюсь аппроксимировать функцию

Log10 [x ^ k0 + k1], где .21 < k0 < 21, 0 < k1 < ~ 2000, а x является целым числом < 2 ^ 14.

k0 и k1 постоянны. Для практических целей можно считать k0 = 2.12, k1 = 2660. Желаемая точность - 5 * 10 -4 -4 относительная ошибка.

Эта функция практически идентична Log [x], за исключением около 0, где она сильно отличается.

Я уже придумал реализацию SIMD, которая на ~ 1.15x быстрее, чем простая таблица поиска, но хотела бы улучшить ее, если это возможно, что очень сложно из-за отсутствия эффективных инструкций.

В моей реализации SIMD используется 16-битная арифметика с фиксированной точкой для оценки полинома 3-й степени (я использую метод наименьших квадратов). Полином использует разные коэффициенты для разных диапазонов ввода. Существует 8 диапазонов и диапазон я охватывает (64) 2 ^ я (64) 2 ^ (i + 1). Рациональным позади этого является производная от Log [x] быстро убывает с x, что означает, что многочлен будет соответствовать ему более точно, так как многочлены являются точным подгоночным для функций, имеющих производную от 0 за пределами определенного порядка.

SIMD-таблицы выглядят очень эффективно с помощью одного _mm_shuffle_epi8(). Я использую SSE float для преобразования int, чтобы получить показатель экспоненты и значение, используемое для приближения фиксированной точки. Я также программировал конвейер, чтобы получить ускорение ~ 1.25x, поэтому дальнейшая оптимизация кода, вероятно, маловероятна.

Я спрашиваю, есть ли более эффективное приближение на более высоком уровне? Например:

Можно ли разложить эту функцию на функции с ограниченным доменом типа log2 ((2 ^ x) * значение) = x + log2 (значение)

следовательно, устраняя необходимость иметь дело с разными диапазонами (поиск таблиц). Основная проблема, я думаю, заключается в добавлении термина k1, который убивает все те хорошие свойства журнала, которые мы знаем и любим, что делает невозможным. Или это?

Итерационный метод? не думаю, потому что метод Ньютона для log [x] уже является сложным выражением
Использование локальных соседних пикселей? - если диапазон 8 входов попадает в тот же диапазон аппроксимации, то я могу искать один коэффициент вместо поиска отдельных коэффициентов для каждого элемента. Таким образом, я могу использовать это как быстрый общий случай и использовать более медленный, общий код, когда это не так. Но для моих данных диапазон должен быть ~ 2000, прежде чем это свойство будет храниться в 70% случаев, что, похоже, не делает этот метод конкурентоспособным.

Пожалуйста, дайте мне некоторое мнение, особенно если вы прикладной математик, даже если вы говорите, что это невозможно. Спасибо.

Ответ 1

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

x ^ k0 + k1 ~ = x ^ k0, позволяя приблизительно оценить функцию как

k0 * Log (х).

Это позаботится обо всех х выше некоторого значения.

Ответ 2

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

Если уже существует быстрая реализация log(x), возможно вычислить P(x) * log(x), где P (x) - многочлен, выбранный чебышевским приближением. (Вместо того, чтобы пытаться выполнить всю функцию как многочлен при приближении, требуется меньше уменьшения диапазона.)

Я здесь любитель, просто погружаюсь в палец, так как ответов уже нет.

Ответ 3

Недавно я прочитал, как модель sRGB сжимает физические значения три стимула в сохраненные значения RGB.

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

k0 x, x < 0.0031308

k1 x ^ 0.417 - k2 в противном случае

Мне сказали, что постоянное добавление в Log [x ^ k0 + k1] должно было сделать начало функции более линейным. Но это может быть легко достигнуто с помощью кусочно-приближенного подхода. Это сделало бы приближение намного более "однородным" - только с двумя диапазонами аппроксимации. Это должно быть дешевле вычислять из-за того, что больше не нужно вычислять индекс диапазона аппроксимации (целочисленный журнал) и выполнять поиск коэффициента SIMD.

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