Najlepsza odpowiedź
Pierwsza metoda
= UNICHAR (8730) podaje symbol pierwiastka kwadratowego w programie Microsoft Excel.
Przetestowano w programie Excel 2016
Druga metoda
- Przejdź do Wstaw kartę i kliknij Symbol z grupy Symbole.
- W obszarze Symbole wybierz Operatory matematyczne z podzbioru i użyj symbolu pierwiastka kwadratowego.
Odpowiedź
Większość nowoczesnych procesorów natywnie obsługuje pierwiastek kwadratowy. Tak więc w przypadku typowego języka programowania na typowym nowoczesnym sprzęcie prawie na pewno ostatecznie będzie to operacja.
Porozmawiajmy więc o metodzie używanej przez prawie wszystkie współczesne procesory ogólnego przeznaczenia.
Reprezentacja liczb
Pierwszą rzeczą, którą musimy zrozumieć, jest to, w jaki sposób komputer faktycznie przedstawia rodzaj liczb, o których mówimy. Są one przechowywane w pewnego rodzaju notacji naukowej.
Otóż w rodzaju notacji naukowej, którą być może znasz, gdzie liczba taka jak -134,5 jest reprezentowana jako -1,345 \ times 10 ^ {2}.
Dowolną liczbę, która nie jest zerem, można przedstawić w tej formie, która koncepcyjnie składa się z trzech części: znaku (czyli liczby dodatnia lub ujemna), mantysa (liczba od 1 do 10, w tym 1, ale bez 10, w tym przypadku 1,345) oraz wykładnik (potęga, do której podniesiona jest podstawa, w tym przypadku 2; zauważ, że wykładnik może być ujemny lub ogólnie zerem).
Reprezentacja że prawie wszystkie współczesne komputery są bardzo podobne, z wyjątkiem tego, że liczba jest przechowywana w postaci binarnej, a nie dziesiętnej. Więc ignorując bit znaku i zero (ponieważ znalezienie pierwiastka kwadratowego z zera jest trywialne, a pierwiastek kwadratowy z liczby ujemnej nie jest liczbą rzeczywistą), liczby dodatnie są w rzeczywistości przechowywane w postaci m \ razy 2 ^ {e} gdzie m to liczba od 1 do 2 (w tym 1, ale bez 2).
Ta reprezentacja jest nazywana „zmiennoprzecinkową” ze względu na sposób, w jaki można przesuwać punkt binarny (analogicznie do przecinek dziesiętny, z którym możesz być zaznajomiony), dostosowując wykładnik.
Powodem, dla którego to wszystko jest ważne, jest to, że procesor wykorzystuje reprezentację do obliczania pierwiastków kwadratowych. Załóżmy, że wykładnik jest parzysty. Następnie:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
Podobnie, jeśli wykładnikiem jest nieparzyste, to:
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
Pamiętaj, że m jest w zakresie [1,2). Oznacza to, że ograniczyliśmy problem do obliczenia pierwiastka kwadratowego z dowolnej liczby do obliczenia pierwiastka kwadratowego z liczby z tego zakresu. Lub, jeśli nie chcemy obliczać wstępnie \ sqrt {2}, liczbę z zakresu [1,4). Tak czy inaczej, radykalnie uprościliśmy problem, ponieważ możemy teraz używać metod, które zachowują się dobrze w tym zakresie liczb.
Mnożenie i dzielenie
Teraz, gdy dotarliśmy już tak daleko, możesz pomyśleć (jeśli spojrzałeś na inne odpowiedzi), że rozwiązaniem jest teraz użycie metody takiej jak iteracja Newtona-Raphsona do obliczenia kwadratu korzeń. Aby obliczyć pierwiastek kwadratowy z n, wybierz początkowe przypuszczenie x\_0 i wykonaj iterację:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Ta odpowiedź jest nieprawidłowa . Cóż, nie jest źle, ponieważ da ci poprawną odpowiedź. Ale to źle, że żaden szanujący się projektant procesora (ani żaden autor biblioteki, gdyby musiał wdrożyć go w oprogramowaniu) nie zaimplementowałby w ten sposób zmiennoprzecinkowego pierwiastka kwadratowego.
Dzielenie przez dwa jest bardzo tanim operacja binarna (która, pamiętaj, jest podstawą 2, więc po prostu przesuwa punkt binarny o jedno miejsce). Jednak drugi podział jest bardzo kosztowną operacją iw tym przypadku musisz wykonać operację wiele razy.
Dzielenie jest tak drogie, że w rzeczywistości nowoczesne procesory używają iteracyjnego algorytmu, który jest podobny do (ale nie w rzeczywistości) iteracji Newtona-Raphsona w celu wykonania dzielenia! Najwyraźniej nie chcemy robić tego sprzętowo, w pętli wewnętrznej.
Na nowoczesnym sprzęcie komputerowym jest to znacznie tańsze do wykonania operacja mnożenia niż operacja dzielenia. Powód jest nieco skomplikowany do wyjaśnienia; ma to związek z faktem, że możemy zmieścić znacznie więcej tranzystorów w chipie niż kiedyś, a mnożenie jest problemem, który można efektywnie przenieść na wiele tranzystorów. Wyszukaj drzewa Wallacea , jeśli interesują Cię szczegóły.
W każdym razie chodzi o to, że mnożenie jest stosunkowo tanią operacją. Więc jeśli możemy zaimplementować operację pierwiastka kwadratowego w kategoriach mnożenia zamiast dzielenia, byłoby lepiej.
Newton-Raphson, weź dwa
Teraz pojawia się pierwszy kluczowy wniosek: zamiast obliczać pierwiastek kwadratowy, oblicz odwrotność pierwiastka kwadratowego. Oznacza to, że zamiast \ sqrt {n} oblicz \ frac {1} {\ sqrt {n}}. Okazuje się, że jest to znacznie łatwiejsza do obliczenia liczba, a jeśli potrzebujesz pierwiastka kwadratowego, pomnóż tę liczbę przez n i gotowe.
Metoda Newtona-Raphsona dla odwrotności pierwiastka kwadratowego wygląda następująco . Jeśli x\_0 jest początkowym oszacowaniem \ frac {1} {\ sqrt {n}}, wykonaj iterację:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Ponownie, dzielenie przez dwa jest dość tanie, a wszystko inne to mnożenie i dodawanie / odejmowanie.
To świetny sposób na wdrożenie to w oprogramowaniu. Co więcej, warto zwrócić uwagę, że w wielu praktycznych sytuacjach (np. Normalizacji wektora za pomocą twierdzenia Pitagorasa) odwrotność pierwiastka kwadratowego jest w rzeczywistości bardziej przydatna niż pierwiastek kwadratowy, ponieważ dzielenie przez pierwiastek kwadratowy jest mniej wydajne niż mnożenie przez odwrotność kwadratu root.
Jednak nie jest to sposób, w jaki jest zwykle implementowany w sprzęcie.
Algorytm Goldschmidta
Możemy teraz przyjrzeć się algorytmowi Goldschmidta, który oblicza razem pierwiastek kwadratowy i odwrotność pierwiastka kwadratowego.
Biorąc pod uwagę b\_0 = n, jeśli możemy znaleźć ciąg liczb Y\_i taki, że b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 zbliża się do 1, a następnie y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} zbliży się do \ frac {1} {\ sqrt {b\_0}} i x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} zbliżą się do \ sqrt {b\_0}.
Seria, której używamy, to zasadniczo Krok aktualizacji Newton-Raphson:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
I wtedy możemy śledzić pierwiastek kwadratowy:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
I odwrotność pierwiastka kwadratowego:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Ale jeśli śledzimy x\_i i y\_i, zauważmy, że b\_i = x\_ {i-1} y\_ {i-1}. Więc tak naprawdę nigdy nie musimy śledzić 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 teraz nie musimy też śledzić 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 *}
Jest tu trochę zbędnych obliczeń, które możemy usunąć, sugerując następujące algorytm. Biorąc pod uwagę Y jako przybliżenie \ frac {1} {\ sqrt {n}}, ustaw:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Następnie wykonaj iterację:
\ 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 *}
Chociaż dzielenie przez dwa jest tanie, możemy tego również uniknąć śledząc h\_i = \ frac {1} {2} y\_i zamiast y\_i. To jest algorytm Goldschmidta.
Załóżmy, że Y jest przybliżeniem do \ frac {1} {\ sqrt {n}}. Ustaw:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Następnie iteruj:
\ 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 *}
Następnie x\_i zbiega się do \ sqrt {n}, a h\_n zbiega się do \ frac {1} {2 \ sqrt {n}}.
Wdrażanie tego w sprzęcie
Na razie dobrze. Z pewnością jest to bardzo prosty algorytm. Ale dlaczego jest lepszy?
Nowoczesne procesory często mają szybki obwód, który wykonuje zoptymalizowaną operację mnożenia i akumulacji , często nazywaną fused multiply- add lub w skrócie FMA. Jeśli wcześniej sprawdziłeś odniesienie do drzew Wallacea, powinno być dla ciebie jasne, w jaki sposób FMA może być prawie tak samo wydajne jak zwykła operacja mnożenia.
FMA jest jednym z najbardziej użytecznych prymitywów, jakie można mieć w pobliżu. Jeśli chcesz obliczyć wielomian, na przykład:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
możesz użyć funkcji Hornera reguła, która w zasadzie jest zbiorem 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 {align *}
Wewnętrzna pętla algorytmu Goldschmidta to trzy FMA i nic więcej.Dlatego jest to zaleta: potrzebujesz tylko jednego rodzaju obwodu (prawdopodobnie tylko jednego obwodu; pamiętaj, że dwa drugie FMA są niezależne, więc mogą skorzystać z potokowania) plus trochę logiki sterującej, aby zaimplementować wszystko. Jest to obwód przydatny w wielu innych operacjach, więc nie marnujesz dużo sprzętu tylko na operację pierwiastkową.
Przedostatnim elementem układanki jest to, jak uzyskać dobry inicjał oszacować, a krótka odpowiedź jest taka, że najlepszą metodą jest przeszukiwanie tabeli. Nawet tabela o niewielkich rozmiarach, ponieważ szukamy tylko pierwiastków kwadratowych w tak małym zakresie, jest dość wydajna.
Ostatni element układanki brzmi: skąd wiemy, kiedy skończyliśmy iterowanie? Odpowiedź na to jest taka, że znamy dokładność liczb, których używamy, i jak dobre są początkowe szacunki. Na tej podstawie możemy z góry obliczyć maksymalną liczbę wymaganych iteracji. Więc tak naprawdę nie zapętlamy się jako takie, po prostu wykonujemy iterację określoną liczbę razy.