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

редактировать

Быстрое приближение квадратного корня из суммы двух квадратов

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

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

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

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

| z | знак равно α M ax + β M in, {\ displaystyle | z | = \ alpha \, \ mathbf {Max} + \ beta \, \ mathbf {Min},}

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

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

Для наиболее близкого приближения оптимальные значения для $α {\ displaystyle \ alpha}$ $\ alpha$ и $β {\ displaystyle \ beta}$ $\ beta$ равны $α 0 = 2 соз ⁡ π 8 1 + соз ⁡ π 8 = 0,960433870103... {\ displaystyle \ alpha _ {0} = {\ frac {2 \ cos {\ frac {\ pi} {8}}} {1+ \ cos {\ frac {\ pi} {8}}}} = 0,960433870103...}$ ${\ displaystyle \ alpha _ {0} = {\ frac {2 \ cos {\ frac {\ pi} {8}}} {1+ \ cos {\ frac {\ pi} {8}}}} = 0,960433870103...}$ и $β 0 = 2 sin ⁡ π 8 1 + cos ⁡ π 8 = 0,397824734759... {\ displaystyle \ beta _ {0} = {\ frac {2 \ sin {\ frac {\ pi} {8}}} {1+ \ cos {\ frac {\ pi} {8}}}} = 0,397824734759...}$ ${\ 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
$α 0 {\ displaystyle \ alpha _ {0}}$ $\ alpha _ {0}$	$β 0 {\ displaystyle \ beta _ {0}}$ $\ beta _ {0}$	3.96	2.41

Содержание

1 Улучшения
2 См. также
3 Ссылки
4 Внешние ссылки

Улучшения

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

| z | = max (M a x, α M a x + β M i n). {\ displaystyle | z | = \ max (\ mathbf {Max}, \ alpha \, \ mathbf {Max} + \ beta \, \ mathbf {Min}).}

{\ displaystyle | z | = \ max (\ mathbf {Max}, \ alpha \, \ mathbf {Max} + \ beta \, \ mathbf {Мин}).}

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

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

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

| z | знак равно макс (| z 0 |, | z 1 |), {\ displaystyle | z | = \ max {\ big (} | z_ {0} |, | z_ {1} | {\ big)},}

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

| z 0 | знак равно α 0 M ax + β 0 M дюйм, {\ displaystyle | z_ {0} | = \ alpha _ {0} \, \ mathbf {Max} + \ beta _ {0} \, \ mathbf {Min},}

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

| z 1 | = α 1 M a x + β 1 M i n. {\ displaystyle | z_ {1} | = \ alpha _ {1} \, \ mathbf {Max} + \ beta _ {1} \, \ mathbf {Min}.}

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

$α 0 {\ displaystyle \ alpha _ {0}}$ $\ alpha _ {0}$	$β 0 {\ displaystyle \ beta _ {0}}$ $\ beta _ {0}$	$α 1 {\ displaystyle \ alpha _ {1}}$ $\ alpha _ {1}$	$β 1 {\ displaystyle \ beta _ {1}}$ $\ 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%

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

См. Также

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

Ссылки

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

Внешние ссылки

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