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

Question

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

Log10 [x ^ k0 + k1], где .21

k0 & k1 являются постоянными.Для практических целей можно принять k0 = 2,12, k1 = 2660. Требуемая точность равна 5 * 10 ^ -4 относительной погрешности.

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

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

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

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

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

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

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

1. Итерационный метод?не думаю, потому что метод Ньютона для log [x] уже является сложным выражением

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

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

Answer 1

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

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

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

Answer 2

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

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

k0 * Log (х).

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

Answer 3

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

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

k0 x, x <0,0031308 </p>

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

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

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