Nejlepší odpověď
1. metoda
= UNICHAR (8730) dává symbol odmocniny v aplikaci Microsoft Excel.
Testováno v aplikaci Excel 2016
2. metoda
- Přejít na Vložit kartu a klikněte na Symbol ve skupině Symboly.
- V části Symboly vyberte Matematické operátory z podmnožiny a použijte symbol odmocniny.
Odpověď
Většina moderních procesorů poskytuje operaci druhé odmocniny nativně. Takže s typickým programovacím jazykem na typickém moderním hardwaru je to téměř jistě to, co operace nakonec bude.
Pojďme si tedy promluvit o metodě, kterou používají téměř všechny moderní univerzální CPU.
Reprezentace čísel
První věc, kterou musíme pochopit, je, jak počítač ve skutečnosti představuje druh čísel, o kterých mluvíme. Jsou uloženy v jakémsi vědeckém zápisu.
Nyní je to druh vědeckého zápisu, který znáte, kde je číslo jako -134,5 reprezentováno jako -1,345 \ krát 10 ^ {2}.
Libovolné číslo, které není nula, lze vyjádřit v této podobě, která má koncepčně tři části: znaménko (tj. je číslo kladné nebo záporné), mantisa (číslo mezi 1 a 10, včetně 1, ale bez 10, v tomto případě 1,345), a exponent (síla, na kterou je radix zvýšen, v tomto případě 2; povšimněte si, že exponent může být obecně záporný nebo nulový).
Reprezentace že téměř všechny moderní počítače používají, jsou velmi podobné, kromě toho, že číslo je uloženo pomocí binární reprezentace, nikoli desítkové. Takže ignorování znaménkového bitu a nuly (protože zjištění druhé odmocniny nuly je triviální a druhá odmocnina záporného čísla není skutečné číslo), jsou kladná čísla ve skutečnosti uložena ve tvaru m \ krát 2 ^ {e}, kde m je číslo mezi 1 a 2 (včetně 1, ale bez 2).
Tato reprezentace se označuje jako „plovoucí desetinná čárka“, protože můžete binární bod posunout (analogicky k desetinná čárka, se kterou se můžete seznámit) úpravou exponentu.
Důvodem, proč je toto všechno důležité, je to, že CPU používá reprezentaci k výpočtu druhé odmocniny. Předpokládejme, že exponent je sudý. Pak:
\ sqrt {m \ krát 2 ^ {2 \ epsilon}} = \ sqrt {m} \ krát 2 ^ {\ epsilon}
Podobně, pokud je exponent liché, pak:
\ sqrt {m \ krát 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ krát 2 ^ {\ epsilon}
Nezapomeňte, že m je v rozsahu [1,2). To znamená, že jsme snížili problém výpočtu druhé odmocniny libovolného čísla na jeden z výpočtu druhé odmocniny čísla v tomto rozsahu. Nebo pokud nechceme předpočítat \ sqrt {2}, číslo v rozsahu [1,4). Ať tak či onak, problém jsme dramaticky zjednodušili, protože nyní můžeme použít metody, které se v tomto rozsahu čísel chovají dobře.
Násobení a dělení
Takže teď, když jsme se dostali tak daleko, můžete si myslet (pokud jste se podívali na další odpovědi), že řešením je nyní použít metodu, jako je Newton-Raphsonova iterace, pro výpočet čtverce vykořenit. Chcete-li vypočítat druhou odmocninu n, vyberte počáteční odhad x\_0 a opakujte:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Tato odpověď je chybná . Není to špatné v tom, že vám dá správnou odpověď. Ale je to špatné v tom, že žádný sebeuznávající návrhář CPU (ani žádný spisovatel knihovny, pokud by to museli implementovat do softwaru) by takto neimplementoval druhou odmocninu s plovoucí desetinnou čárkou.
Dělení dvěma je velmi levné operace v binární podobě (což je základ 2, takže je to jen posunutí binárního bodu o jedno místo). Druhé dělení je však velmi nákladná operace a v tomto případě je nutné ji provést několikrát.
Dělení je ve skutečnosti tak nákladné, že moderní CPU používají podobný iterativní algoritmus. (ale ne ve skutečnosti) Newton-Raphsonova iterace k provedení dělení! Je zřejmé, že nechceme to dělat v hardwaru, ve vnitřní smyčce.
Na moderním počítačovém hardwaru je provedení mnohem levnější operace násobení než operace dělení. Důvod proč je trochu složitější vysvětlit; má to co do činění s faktem, že na čip můžeme umístit mnohem více tranzistorů, než jsme byli zvyklí, a násobení je problém, který můžete efektivně přesunout na mnoho tranzistorů. Pokud vás podrobnosti zajímají, vyhledejte stromy Wallace .
V každém případě jde o to, že násobení je poměrně levná operace. Pokud tedy můžeme operaci druhé odmocniny implementovat spíše z hlediska násobení než dělení, bylo by to lepší.
Newton-Raphson, vezměte dvě
Nyní přichází první klíčový přehled: Namísto výpočtu druhé odmocniny spočítejte reciproční druhé odmocniny. To znamená, že místo \ sqrt {n} vypočítat \ frac {1} {\ sqrt {n}}. Ukázalo se, že je to mnohem snazší číslo pro výpočet, a pokud potřebujete druhou odmocninu, vynásobte toto číslo na n a máte hotovo.
Metoda Newton-Raphson pro reciproční druhou odmocninu vypadá takto . Pokud je x\_0 počátečním odhadem na \ frac {1} {\ sqrt {n}}, iterujte:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Opět platí, že dělení dvěma je poměrně levné a vše ostatní je násobení a sčítání / odčítání.
Je to skvělý způsob implementace to v softwaru. Kromě toho stojí za zmínku, že v mnoha praktických situacích (např. Normalizace vektoru pomocí Pythagorovy věty) je reciproční odmocnina ve skutečnosti užitečnější než druhá odmocnina, protože dělení druhou odmocninou je méně efektivní než vynásobení reciproční druhou odmocninou root.
Takto to však obvykle není implementováno v hardwaru.
Goldschmidtův algoritmus
Nyní se můžeme podívat na Goldschmidtův algoritmus, který společně počítá druhou odmocninu a druhou odmocninu.
Vzhledem k b\_0 = n, pokud můžeme najít řadu čísel Y\_i taková, že b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 se blíží 1, pak y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} se přiblíží \ frac {1} {\ sqrt {b\_0}} a x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} se přiblíží \ sqrt {b\_0}.
Řada, kterou používáme, je v podstatě Aktualizační krok Newton-Raphson:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
And pak můžeme sledovat druhou odmocninu:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
A vzájemná odmocnina:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Pokud ale sledujeme x\_i a y\_i, pozorujeme, že b\_i = x\_ {i-1} y\_ {i-1}. Takže vlastně nikdy nemusíme sledovat b\_i:
\ begin {align *} Y\_i & = \ frac {1} {2} \ left (3 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right ) \ end {align *}
A nyní ani nemusíme sledovat Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ left (1 + \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ right) \\ & = x\_ {i-1} + x\_ {i- 1} \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \\ y\_i & = y\_ {i-1} \ left (1 + \ frac {1 } {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ right) \\ & = y\_ {i-1} + y\_ {i-1} \ frac {1} { 2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ end {align *}
Zde je nějaký redundantní výpočet, který můžeme odstranit, což naznačuje následující algoritmus. Vzhledem k tomu, že Y je přibližná hodnota k \ frac {1} {\ sqrt {n}}, nastavte:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Pak iterujte:
\ begin {align *} r\_i & = \ frac {1} {2} \ left (1 – x\_i y\_i \ right) \\ x\_ {i +1} & = x\_i + x\_i r\_i \\ y\_ {i + 1} & = y\_i + y\_i r\_i \ end {align *}
I když je dělení dvěma levné, můžeme se tomu také vyhnout sledováním h\_i = \ frac {1} {2} y\_i místo y\_i. Toto je Goldschmidtův algoritmus.
Předpokládejme, že Y je aproximací \ frac {1} {\ sqrt {n}}. Nastavit:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Pak iterovat:
\ begin {align *} r\_i & = \ frac {1} {2} – x\_i h\_i \\ x\_ {i + 1} & = x\_i + x\_i r\_i \\ h\_ {i + 1} & = h\_i + h\_i r\_i \ end {align *}
Pak x\_i konverguje na \ sqrt {n} a h\_n konverguje na \ frac {1} {2 \ sqrt {n}}.
Implementace v hardwaru
Zatím vše v pořádku. Je to určitě velmi jednoduchý algoritmus. Proč je to ale lepší?
Moderní CPU často mají rychlý obvod, který provádí optimalizovanou operaci multiplikovat , často nazývanou fúzovaný multiplikátor add, nebo zkráceně FMA. Pokud jste dříve vyhledali odkaz na Wallaceovy stromy, mělo by vám být jasné, jak by FMA mohla být téměř stejně efektivní jako operace přímého násobení.
FMA je jedním z nejužitečnějších primitivů, které existují. Pokud potřebujete vyhodnotit polynom, například:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
můžete použít Hornerův pravidlo, což je v podstatě spousta FMA:
\ begin {align *} p\_ {n-1} & = a\_ {n-1} + x a\_n \\ p\_ {n-2} & = a\_ {n-2} + x p\_ {n-1} \\ & \ vdots \\ p\_1 & = a\_1 + x p\_2 \\ p\_0 & = a\_0 + x p\_1 \ end {zarovnat *}
Vnitřní smyčka Goldschmidtova algoritmu jsou tři FMA a nic jiného.To je důvod, proč je to výhoda: k implementaci všeho potřebujete pouze jeden druh obvodu (možná pouze jeden obvod; všimněte si, že druhé dva FMA jsou nezávislé a mohou tak těžit z pipeliningu) plus nějakou řídicí logiku. A je to obvod, který je užitečný v mnoha dalších operacích, takže nebudete plýtvat spoustou hardwaru jen při operaci druhé odmocniny.
Druhým posledním kouskem skládačky je, jak získat dobrou počáteční hodnotu odhad a krátkou odpovědí je, že nejlepší metodou je použít vyhledání tabulky. Dokonce i stůl se skromnou velikostí, protože hledáme pouze odmocniny v tak malém rozsahu, je docela efektivní.
Poslední část skládačky je: Jak zjistíme, kdy skončíme iterace? A odpověď na to je, že známe přesnost čísel, která používáme, a jak dobrý je počáteční odhad. Z toho můžeme předem vypočítat maximální počet požadovaných iterací. Takže vlastně neprovádíme smyčku jako takovou, pouze opakujeme iteraci pevně danou dobu.