[count_enable 0]

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

[Гость TSerg]

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

 

***

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

 

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

 

[count_enable 0]

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

[Гость TSerg]

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

Приведите все исходные данные.

 

P.S.

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

Для простых случаев гарантируется решение за N-циклических тактов, где N - число разрядов, но каждый циклический такт включает сдвиги до N-разрядов.

 

[count_enable 0]

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

 

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

 

[Гость TSerg]

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

 

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

 

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

[count_enable 0]

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

[Гость TSerg]

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

 

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

 

 

[amaora 20]

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

 

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

Изменено 25 февраля, 2016 пользователем amaora

[Гость TSerg]

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

 

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

 

P.S.

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

 

Из более-менее интересных вариантов в голову приходит Singular spectrum analysis (SSA или метод "гусеницы")- у них есть целочисленные варианты, которые наверное можно свести к степеням 2.

В этом методе, легко воспроизводятся разностные уравнения с реализацией по типу FIR. Удлиняя реализацию такой условно-линейной системы, скорее всего можно подобрать коэффициенты от степеней 2.

Ну и глобалный МГУА (метод группового учёта аргументов) Ивахненко.

[count_enable 0]

То есть задан набор прямых, с коэффициентами +-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 1]

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

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

[ViKo 1]

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

[Onkel 1]

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

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

[Tanya 4]

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

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

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