Кусково-линейная аппроксимация с заданными множителями., Как аппроксимировать для степеней двойки? Опции

[count_enable]

Классическая КЛА это аппроксимация множеством прямых типа kx+b. Любой математический пакет, включая эксель это умеет. Но для аппаратных реализаций очень выгодно чтобы k был степенью двойки, тогда вместо умножения можно сделать простой сдвиг. Как можно сделать такую КЛА? Пока на ум пришли только нематематические методы типа генетических алгоритмов.

[Guest_TSerg_*]

Нет "кусковой", но есть кусочная.

***
У Вас нет аппаратного умножителя?

Ну и что мешает подобрать множитель близкий к вещественному числу, но с заданным числом 1-ц и 0-лей и, есс-но, с заданной погрешностью аппроксимации?

[count_enable]

У меня есть умножитель, но сдвиг существенно быстрее и проще. Если быть точным, хочу аппроксимировать логистическую функцию. Перед этим нашел в инете КЛА сигмоида tanh и результат по скорости и аппроксимации превосходен. Как-то ведь вычислили коэффициенты для tanh, значит можно и для логистической ведь.

[Guest_TSerg_*]

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

P.S.
Если говорить о принципах ( не только о КЛА ), то есть методы "цифра за цифрой" или CORDIC ( родоначальник - Волдер, затем развиты Смоловым И Байковым ).
Для простых случаев гарантируется решение за N-циклических тактов, где N - число разрядов, но каждый циклический такт включает сдвиги до N-разрядов.

[count_enable]

Исходная задача: аппроксимировать кусочно-линейным способом функцию tanh(x) или другой сигмоид с диапазоном значений -1..1. При этом все коэффициенты k должны быть степенями двойки.

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

[Guest_TSerg_*]

Т.е. задача математическая, а не инженерная.

Инженерные задачи решаются быстрее и "выхлоп" бывает вполне удовлетворителен.

Теорему Ферма тоже решили, в конце-то концов.

[count_enable]

Считайте это любознательностью .

[Guest_TSerg_*]

Считайте это любознательностью .

Раньше такую "любознательность" оплачивало государство, да и сейчас есть такие государства и фонды

[amaora]

То есть задан набор прямых, с коэффициентами +-2^n, задано количество отрезков N. Требуется найти разбиение области определения аппроксимируемой функции на отрезки, так чтобы используя заданные прямые в этих отрезках получить наименьшую невязку прямых с функцией. Так?

Задача скорее всего многоэксремальная, и решается только численно, поисковыми/стохастическими методами оптимизации.

Сообщение отредактировал amaora - Feb 25 2016, 18:15

[Guest_TSerg_*]

Задача скорее всего многоэксремальная, и решается только численно, поисковыми/стохастическими методами оптимизации.

В инженерном случае ( т.е. - конкретном ) так и следует ее решать, т.е. методами оптимизации.

P.S.
Универсальной "формулы" ждать не стоит.

Из более-менее интересных вариантов в голову приходит Singular spectrum analysis (SSA или метод "гусеницы")- у них есть целочисленные варианты, которые наверное можно свести к степеням 2.
В этом методе, легко воспроизводятся разностные уравнения с реализацией по типу FIR. Удлиняя реализацию такой условно-линейной системы, скорее всего можно подобрать коэффициенты от степеней 2.
Ну и глобалный МГУА (метод группового учёта аргументов) Ивахненко.

[count_enable]

То есть задан набор прямых, с коэффициентами +-2^n, задано количество отрезков N. Требуется найти разбиение области определения аппроксимируемой функции на отрезки, так чтобы используя заданные прямые в этих отрезках получить наименьшую невязку прямых с функцией. Так?

Задача скорее всего многоэксремальная, и решается только численно, поисковыми/стохастическими методами оптимизации.

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

Раньше такую "любознательность" оплачивало государство, да и сейчас есть такие государства и фонды sm.gif

Ну вот одно из государств платит мне за любознательность )).

Если что-то придумаю то отпишусь. А пока желающие могут ознакомиться с одним из похожих решений в H. Amin, K. M. Curtis, and B. R. Hayes-Gill, “Piecewise linear approximation applied to nonlinear function of a neural network,” IEE Proceedings - Circuits, Devices and Systems, vol. 144, no. 6, pp. 313–317, Dec. 1997.

[Onkel]

Возможно линейное программирование помогло бы. ...

имхо проще надо быть, ближе к Оккаму. Если k - степень двойки, то значений k очень мало, и нетрудно перебрать все интерполяции kx+b при разных k (0, 1, 2, 4,....2^^n) и выбрать лучшую по невязке. Поскольку число интервалов m тоже ограничено, мы получаем довольно -таки простую задачу - найти n*m невязок и выбрать по результатам m величин k и m величин b. Вроде так ?

[ViKo]

За 2-3 действия можно умножить на 3, 5, 6, 7, 8, 9, 12, 15... без умножения, только сдвигами и суммированием-вычитанием. Раскрываются необъятные горизонты для творчества. А как выбоать лучшее решение, вопрос.

[Onkel]

. без умножения, только сдвигами и суммированием-вычитанием

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

[Tanya]

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

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