Алгоритм альфа-макс плюс бета-мин

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

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

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

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

${\ Displaystyle | Z | = \ альфа \, \ mathbf {Max} + \ beta \, \ mathbf {Min},}$

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

Для наиболее близкого приближения оптимальными значениями и являются и , что дает максимальную ошибку 3,96%.${\ 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...}$

${\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	16.07	12,50	4,91
15/16	15/32	6,25	3,08
${\displaystyle \alpha _{0}}$	${\displaystyle \beta _{0}}$	3,96	2.41

Улучшения [ править ]

Когда , становится меньше (что геометрически невозможно) рядом с осями, где близко 0. Это можно исправить, заменив результат на всякий раз, когда он больше, по существу разделив линию на два разных сегмента.${\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	0	0,898204193266868	0,485968200201465	± 2,12%
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}}$

См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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