Алгоритм альфа макс плюс бета мин - Alpha max plus beta min algorithm - Wikipedia

Не путать с Минимакс или же Альфа – бета обрезка.

Геометрическое место точек, которые дают одинаковое значение в алгоритме для разных значений альфа и бета.

В алгоритм альфа макс плюс бета мин представляет собой высокоскоростное приближение квадратный корень суммы двух квадратов. Квадратный корень из суммы двух квадратов, также известный как Пифагорейское сложение, полезная функция, потому что она находит гипотенуза прямоугольного треугольника с учетом длины двух сторон, норма 2-D вектор, или величина ${\displaystyle |z|={\sqrt {a^{2}+b^{2}}}}$ из комплексное число z = а + бя дал настоящий и воображаемый части.

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

Приближение выражается как

${\displaystyle |z|=\alpha \,\mathbf {Max} +\beta \,\mathbf {Min} ,}$

куда ${\displaystyle \mathbf {Max} }$ - максимальное абсолютное значение а и б, и ${\displaystyle \mathbf {Min} }$ - минимальное абсолютное значение а и б.

Для наиболее близкого приближения оптимальные значения для ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ находятся ${\displaystyle \alpha _{0}={\frac {2\cos {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.960433870103...}$ и ${\displaystyle \beta _{0}={\frac {2\sin {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.397824734759...}$, что дает максимальную ошибку 3,96%.

${\displaystyle \alpha \,\!}$	${\displaystyle \beta \,\!}$	Наибольшая ошибка (%)	Средняя ошибка (%)
1/1	1/2	11.80	8.68
1/1	1/4	11.61	3.20
1/1	3/8	6.80	4.25
7/8	7/16	12.50	4.91
15/16	15/32	6.25	3.08
${\displaystyle \alpha _{0}}$	${\displaystyle \beta _{0}}$	3.96	2.41

Улучшения

Когда ${\displaystyle \alpha <1}$, ${\displaystyle |z|}$ становится меньше, чем ${\displaystyle \mathbf {Max} }$ (что геометрически невозможно) вблизи осей, где ${\displaystyle \mathbf {Min} }$ близка к нулю. Это можно исправить, заменив результат на ${\displaystyle \mathbf {Max} }$ всякий раз, когда это больше, по существу разделяя линию на два разных сегмента.

${\displaystyle |z|=\max(\mathbf {Max} ,\alpha \,\mathbf {Max} +\beta \,\mathbf {Min} ).}$

В зависимости от оборудования это улучшение может быть почти бесплатным.

Использование этого улучшения изменяет оптимальные значения параметров, поскольку им больше не требуется точное соответствие для всего интервала. Более низкий ${\displaystyle \alpha }$ и выше ${\displaystyle \beta }$ таким образом может еще больше повысить точность.

Повышение точности: При таком разделении линии на две можно было бы еще больше повысить точность, заменив первый сегмент более точной оценкой, чем ${\displaystyle \mathbf {Max} }$, и отрегулируйте ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ соответственно.

${\displaystyle |z|=\max {\big (}|z_{0}|,|z_{1}|{\big )},}$

${\displaystyle |z_{0}|=\alpha _{0}\,\mathbf {Max} +\beta _{0}\,\mathbf {Min} ,}$

${\displaystyle |z_{1}|=\alpha _{1}\,\mathbf {Max} +\beta _{1}\,\mathbf {Min} .}$

${\displaystyle \alpha _{0}}$	${\displaystyle \beta _{0}}$	${\displaystyle \alpha _{1}}$	${\displaystyle \beta _{1}}$	Наибольшая ошибка (%)
1	0	7/8	17/32	−2.65%
1	0	29/32	61/128	+2.4%
1	1/8	7/8	33/64	−1.7%
1	5/32	27/32	71/128	1.22%
127/128	3/16	27/32	71/128	−1.13%

Однако помните, что ненулевое значение ${\displaystyle \beta _{0}}$ потребует по крайней мере одного дополнительного сложения и некоторых битовых сдвигов (или умножения), что, вероятно, почти удвоит стоимость и, в зависимости от оборудования, возможно, в первую очередь лишит цели использования приближения.

Смотрите также

• Гипотеза, точная функция или алгоритм, который также защищен от переполнения и потери значимости.

Рекомендации

• Лайонс, Ричард Дж.. Понимание цифровой обработки сигналов, раздел 13.2. Прентис Холл, 2004 ISBN  0-13-108989-7.
• Гриффин, Грант. Уловка DSP: оценщик величины.

внешняя ссылка

• «Расширение до трех измерений». Обмен стеком. 14 мая 2015 года.