Algoritmus Alpha max plus beta min - Alpha max plus beta min algorithm - Wikipedia

Místo bodů, které v algoritmu dávají stejnou hodnotu, pro různé hodnoty alfa a beta

The Algoritmus alfa max plus beta min je vysokorychlostní aproximace odmocnina součtu dvou čtverců. Druhá odmocnina součtu dvou čtverců, známých také jako Pythagorovo sčítání, je užitečná funkce, protože najde přepona pravoúhlého trojúhelníku s ohledem na dvě délky stran, norma 2-D vektor, nebo velikost ${ displaystyle | z | = { sqrt {a ^ {2} + b ^ {2}}}}$ a komplexní číslo z = A + bdal jsem nemovitý a imaginární části.

Algoritmus se vyhýbá provádění operací s druhou a druhou odmocninou, místo toho používá jednoduché operace, jako je porovnání, násobení a sčítání. Některé volby parametrů α a β algoritmu umožňují redukci operace násobení na jednoduchý posun binárních číslic, který je zvláště vhodný pro implementaci ve vysokorychlostních digitálních obvodech.

Aproximace je vyjádřena jako

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

kde ${ displaystyle mathbf {Max}}$ je maximální absolutní hodnota A a b, a ${ displaystyle mathbf {min}}$ je minimální absolutní hodnota A a b.

Pro nejbližší přiblížení jsou optimální hodnoty pro ${ displaystyle alpha}$ a ${ displaystyle beta}$ jsou ${ displaystyle alpha _ {0} = { frac {2 cos { frac { pi} {8}}} {1+ cos { frac { pi} {8}}}} = 0,960433870103. ..}$ a ${ displaystyle beta _ {0} = { frac {2 sin { frac { pi} {8}}} {1+ cos { frac { pi} {8}}}} = 0,399724734759. ..}$, což dává maximální chybu 3,96%.

${ displaystyle alpha , !}$	${ displaystyle beta , !}$	Největší chyba (%)	Střední chyba (%)
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

Vylepšení

Když ${ displaystyle alpha <1}$, ${ displaystyle | z |}$ bude menší než ${ displaystyle mathbf {Max}}$ (což je geometricky nemožné) poblíž os, kde ${ displaystyle mathbf {min}}$ je blízko 0. To lze napravit nahrazením výsledku za ${ displaystyle mathbf {Max}}$ kdykoli je to větší, v podstatě rozdělte čáru na dva různé segmenty.

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

V závislosti na hardwaru může být toto vylepšení téměř zdarma.

Pomocí tohoto vylepšení se změní, které hodnoty parametrů jsou optimální, protože již nepotřebují blízkou shodu pro celý interval. Nižší ${ displaystyle alpha}$ a vyšší ${ displaystyle beta}$ proto může dále zvýšit přesnost.

Zvyšování přesnosti: Při rozdělení čáry na dvě, jako je tato, by se mohla přesnost ještě zlepšit nahrazením prvního segmentu lepším odhadem než ${ displaystyle mathbf {Max}}$a upravte ${ displaystyle alpha}$ a ${ displaystyle beta}$ podle toho.

${ 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}}$	Největší chyba (%)
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%

Pozor však na nenulovou hodnotu ${ displaystyle beta _ {0}}$ by vyžadovalo alespoň jedno další přidání a nějaké bitové posuny (nebo násobení), pravděpodobně téměř zdvojnásobení nákladů a v závislosti na hardwaru by mohlo v první řadě zmařit účel použití aproximace.

Viz také

• Hypotéka, přesná funkce nebo algoritmus, který je také bezpečný proti přetečení a podtečení

Reference

• Lyons, Richard G.. Porozumění zpracování digitálního signálu, oddíl 13.2. Prentice Hall, 2004 ISBN  0-13-108989-7.
• Griffin, Grante. DSP Trick: Magnitude Estimator.

externí odkazy

• „Rozšíření do tří dimenzí“. Stack Exchange. 14. května 2015.