Методе за израчунавање квадратног корена

У нумеричкој анализи, огранку математике, постоји неколико 'алгоритама квадратног корена' или 'методе израчунавања главног квадратног корена'. За квадратни корен негативног или комплексног броја, погледајте испод. Проналажење ${\displaystyle {\sqrt {S}}}$ је исто као и решавање једначине ${\displaystyle f(x)=x^{2}-S=0\,\!}$. Стога, сваки општи алгоритам проналажења корена се може користити. Њутнове методе, на пример, смањују се у овом случају такозваним Вавилонском методом.

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-S}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right)}$

Уопштено, ове методе дају приближне резултате. Да бисте добили већу прецизност за кореновање, већа прецизност за квадрат је потребна као и већи број корака који се мора израчунати.

Груба процена

Многи алгоритми квадратних корена захтевају иницијалну вредност . Ако је почетна вредност далеко од стварног квадратног корена, алгоритам ће бити успорен. Стога је корисно имати грубу процену, што може бити врло нетачно, али лако за израчунати. Уз ${\displaystyle S}$ изражен у научној нотацији ${\displaystyle a\times 10^{2n}}$ где ${\displaystyle 1\leq a<100}$ n је цео број, квадратни корен ${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 10^{n}}$ може се проценити као

${\displaystyle {\sqrt {S}}\approx {\begin{cases}2\cdot 10^{n}&{\text{ако је }}a<10,\\6\cdot 10^{n}&{\text{ако је }}a\geq 10.\end{cases}}}$

Фактори два и шест користе се јер се тако приближимо геометријској средини s од најниже и највише могуће вредности са одређеним бројем цифара: ${\displaystyle {\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\approx 2\,}$ and ${\displaystyle {\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\approx 6\,}$.

За ${\displaystyle S=125348=12.5348\times 10^{4}}$, процена је ${\displaystyle {\sqrt {S}}\approx 6\cdot 10^{2}=600}$.

Када се ради у бинарном бројевом систему (као што рачунари раде интерно), изражавајући ${\displaystyle S}$ као ${\displaystyle a\times 2^{2n}}$ где ${\displaystyle 0.1_{2}\leq a<10_{2}}$, квадратни корен ${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 2^{n}}$ може се представити као ${\displaystyle {\sqrt {S}}\approx 2^{n}}$, будући да је геометријска средина од најнижих и највиших вредности ${\displaystyle {\sqrt {{\sqrt {0.1_{2}}}\cdot {\sqrt {10_{2}}}}}={\sqrt[{4}]{1}}=1}$. За ${\displaystyle S=125348=1\;1110\;1001\;1010\;0100_{2}=1.1110\;1001\;1010\;0100_{2}\times 2^{16}\,}$ бинарна апроксимација даје ${\displaystyle {\sqrt {S}}\approx 2^{8}=1\;0000\;0000_{2}=256\,.}$ Ове приближне вредности су корисне за проналажење бољег почетка за итеративне алгоритме, што доводи до бржег приближавања-одређивања.

Вавилонски метод

Графикон коришћење вавилонске методе за приближавање квадратног корена 100 (10) помоћу почетне вредности x₀ = 50, x₀ = 1, и x₀ = −5. Имајте на уму да коришћење негативне почетне вредности даје негативан корен.

Први алгоритам за приближавање √S је познат као 'Вавилонска метода' , назван по Вавилонцимa. Нема директних доказа који показује како су Вавилонци израчунавали квадратни корен, иако постоји доста претпоставки. Херонов метод, назван по грчком математичару првог века Херону из Александрије који је дао први експлицитан опис овог метода^[1] Може се извести из (али претходи 16 века пре) Њутновог метода. Основна идеја је да ако је x прецењен за квадратни корен не-негативног реалног броја S онда S/x ће бити потцењен и тако се разумно може очекивати просек ова два броја да се обезбеди боља апроксимација (иако је формално доказ о тој тврдњи зависи од неједнакости аритметичких и геометријских средствава који показује овај просек да је увек прецењен од квадратног корена, као што је наведено у чланку о квадратном корену, што омогућава конвергенције). Тачније, ако је x наша почетна претпоставка за √S и e је грешка у нашој процени таква да S = (x+ e)², онда можемо да проширимо биномно и решити га за

${\displaystyle e={\frac {S-x^{2}}{2x+e}}\approx {\frac {S-x^{2}}{2x}},}$ када је ${\displaystyle e\ll x}$.

Дакле, можемо надокнадити грешке и ажурирати нашу стару процену као

${\displaystyle x:=x+e={\frac {S+x^{2}}{2x}}={\frac {x+{\frac {S}{x}}}{2}}}$

Пошто израчуната грешка није тачна, то постаје наша следећа најбоља претпоставка. Процес ажурирања је поновљен док се жељена тачност не добије. Ово је квадратни конвергенцијални алгоритам, што значи да се број исправних цифара приближавањем отприлике удвостручује са сваким понављањем. Онда наставља као:

1. Почиње са произвољном позитивном почетном вредношћу x₀ (што је ближе стварном квадратном корену S , то боље).
2. Нека x_{n + 1} буде просек од x_n и S/x_n (Користећи аритметичку средину као да је приближна геометријска средња вредност).
3. Поновити корак 2 све док се не постигне жељена тачност

Претходни кораци се могу такође представити и као:

${\displaystyle x_{0}\approx {\sqrt {S}},}$

${\displaystyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),}$

${\displaystyle {\sqrt {S}}=\lim _{n\to \infty }x_{n}.}$

Пример

За израчунавање √S, где је S = 125348, до 6 значајних фигура, користите метод грубе процене изнад да добијете резултат

${\displaystyle x_{0}=6\cdot 10^{2}=600.000\,}$

${\displaystyle x_{1}={\frac {1}{2}}\left(x_{0}+{\frac {S}{x_{0}}}\right)={\frac {1}{2}}\left(600.000+{\frac {125348}{600.000}}\right)=404.457}$

${\displaystyle x_{2}={\frac {1}{2}}\left(x_{1}+{\frac {S}{x_{1}}}\right)={\frac {1}{2}}\left(404.457+{\frac {125348}{404.457}}\right)=357.187}$

${\displaystyle x_{3}={\frac {1}{2}}\left(x_{2}+{\frac {S}{x_{2}}}\right)={\frac {1}{2}}\left(357.187+{\frac {125348}{357.187}}\right)=354.059}$

${\displaystyle x_{4}={\frac {1}{2}}\left(x_{3}+{\frac {S}{x_{3}}}\right)={\frac {1}{2}}\left(354.059+{\frac {125348}{354.059}}\right)=354.045}$

${\displaystyle x_{5}={\frac {1}{2}}\left(x_{4}+{\frac {S}{x_{4}}}\right)={\frac {1}{2}}\left(354.045+{\frac {125348}{354.045}}\right)=354.045\,.}$

Стога, √125348 ≈ 354.045.

Конвергенција

Нека релативна грешка у x_n буде дефинисана са

${\displaystyle \varepsilon _{n}={\frac {x_{n}}{\sqrt {S}}}-1}$

тада је

${\displaystyle x_{n}={\sqrt {S}}\cdot (1+\varepsilon _{n}).}$

Онда се може показати

${\displaystyle \varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n})}}}$

тако да важи

${\displaystyle 0\leq \varepsilon _{n+2}\leq \min \left\{{\frac {\varepsilon _{n+1}^{2}}{2}},{\frac {\varepsilon _{n+1}}{2}}\right\}}$

и самим тим приближавање је осигурано под условом да су и x₀ и S су истовремено позитивни.

Најгори случај за приближавање

Ако користите грубу процену са Вавилонском методом, онда су најмање тачни случајеви у растућем редоследу:

${\displaystyle {\begin{aligned}S&=1;&x_{0}&=2;&x_{1}&=1.250;&\varepsilon _{1}&=0.250.\\S&=10;&x_{0}&=2;&x_{1}&=3.500;&\varepsilon _{1}&<0.107.\\S&=10;&x_{0}&=6;&x_{1}&=3.833;&\varepsilon _{1}&<0.213.\\S&=100;&x_{0}&=6;&x_{1}&=11.333;&\varepsilon _{1}&<0.134.\end{aligned}}}$

Према томе у сваком случају,

${\displaystyle \varepsilon _{1}\leq 2^{-2}.\,}$

${\displaystyle \varepsilon _{2}<2^{-5}<10^{-1}.\,}$

${\displaystyle \varepsilon _{3}<2^{-11}<10^{-3}.\,}$

${\displaystyle \varepsilon _{4}<2^{-23}<10^{-6}.\,}$

${\displaystyle \varepsilon _{5}<2^{-47}<10^{-14}.\,}$

${\displaystyle \varepsilon _{6}<2^{-95}<10^{-28}.\,}$

${\displaystyle \varepsilon _{7}<2^{-191}<10^{-57}.\,}$

${\displaystyle \varepsilon _{8}<2^{-383}<10^{-115}.\,}$

Заокруживање грешке ће успорити приближавање. Препоручује се да се задржи барем једна додатна цифра иза жељене тачности x_n тако да се резултату минимизира грешка заокруживања.

Цифра по цифру рачунање

Ово је метод да пронађете сваку цифру од квадратног корена у низу. То је спорије него Вавилонска метода (ако имате калкулатор који може поделити у једној операцији), али има неколико предности:

• Може бити лакше за ручне калкулације .
• Свака цифра корена која је пронађена је тачна, односно, не мора касније да буде промењена
• Ако квадратни корен има експанзију да престане, алгоритам завршава после последње цифре када је пронађена. Према томе, може се користити за проверу исправности, цео број је квадратни број.
• Алгоритам ради за било који бројевни систем, и наравно, начин на који поступа зависи од изабраног система.

Основни принцип

Претпоставимо да смо у стању да пронађемо квадратни корен броја N изражавајући га као збир ' n позитивних бројева таквих да

${\displaystyle N=(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}.}$

По неколико пута применом основног идентитета

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2},}$

термин десна страна може се проширити као

${\displaystyle {\begin{aligned}&(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}\\=&\,a_{1}^{2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\dotsb +a_{n-1}^{2}+2\left(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\\=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_{3}+\dotsb +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end{aligned}}}$

Овај израз нам омогућава да пронађемо квадратни корен од узастопно погађане вредности ${\displaystyle a_{i}}$s. Претпоставимо да су бројеви ${\displaystyle a_{1},\ldots ,a_{m-1}}$ већ били изабрани, онда н-тог броја на десној страни од сумирања даје ${\displaystyle Y_{m}=[2P_{m-1}+a_{m}]a_{m},}$, где ${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}}$ је приближна вредност квадратни корен који је до тада пронађен. Сада сваки нови погодак ${\displaystyle a_{m}}$ треба да задовољи рекурзију

${\displaystyle X_{m}=X_{m-1}-Y_{m},}$

тако да ${\displaystyle X_{m}\geq 0}$ за све ${\displaystyle 1\leq m\leq n,}$ са почетком ${\displaystyle X_{0}=N.}$ када ${\displaystyle X_{n}=0,}$ исти квадратни корен је пронађен; ако није, онда сумирањем ${\displaystyle a_{i}}$s даје одговарајуће приближавање квадратног корена, са ${\displaystyle X_{n}}$ као приближавање грешке.

На пример, у децималном систему бројева имамо

${\displaystyle N=(a_{1}\cdot 10^{n-1}+a_{2}\cdot 10^{n-2}+\cdots +a_{n-1}\cdot 10+a_{n})^{2},}$

где ${\displaystyle 10^{n-i}}$ су носиоци и коефицијенти ${\displaystyle a_{i}\in \{0,1,2,\ldots ,9\}}$. У сваком н-тој фази квадратног рачунања корена, приближан корен је пронађен, ${\displaystyle P_{m-1}}$ и сума ${\displaystyle Y_{m}}$ је дата

${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{n-i}=10^{n-m+1}\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1},}$

${\displaystyle Y_{m}=[2P_{m-1}+a_{m}\cdot 10^{n-m}]a_{m}\cdot 10^{n-m}=[20\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1}+a_{m}]a_{m}\cdot 10^{2(n-m)}.}$

Место вредности ${\displaystyle Y_{m}}$ је чак и моћ од „10“, ми само треба да радимо са паром најзначајнијих цифара у преосталом периоду ${\displaystyle X_{m-1}}$ у свакој н-тој фази.

Очигледно је да се сличан метод користи за израчунавање квадратног корена у другим бројевим системима осим за децимални систем бројева. На пример, проналажење цифре-по-цифру квадратни корен у бинарном систему бројева је врло ефикасан, јер је вредност ${\displaystyle a_{i}}$ тражена од мањег скупа бинарних цифара {0,1}. То чини рачунање брже јер у свакој фази вредност ${\displaystyle Y_{m}}$ је или ${\displaystyle Y_{m}=0}$ за ${\displaystyle a_{m}=0}$ или ${\displaystyle Y_{m}=2P_{m-1}+1}$ за ${\displaystyle a_{m}=1}$. Чињеница да имамо само две могуће опције за ${\displaystyle a_{m}}$ и чини процес одлучивања вредности ${\displaystyle a_{m}}$ у н-тој фази рачуна лакше. То је зато што само треба да проверите да ли ${\displaystyle Y_{m}\leq X_{m-1}}$ за ${\displaystyle a_{m}=1.}$ Ако је овај услов задовољен, онда узимамо ${\displaystyle a_{m}=1}$; ако не онда ${\displaystyle a_{m}=0.}$

Децимални (база 10)

Напиши оригинални број у децималном облику. Корен ће бити написан на линији изнад. Сада раздвајање цифара у парове, почевши од децималног зареза и иде и лево и десно. Децимална тачка корена ће бити изнад децималног зареза. Једна цифра корена ће се појавити изнад сваког пара цифара тог корена.

Почевши са левим паром цифара, урадите следећу процедуру за сваки пар:

1. Почевши са леве стране, спусти најзначајнији (скроз лево) пар цифара који није искоришћен (ако су се искористиле све цифре, пишите "00") и упишите их на десној страни остатка из претходног корака (за први корак, неће бити остатка). Другим речима, помножите остатак са 100 и додајте две цифре. То ће бити 'тренутна вредност' c '.
2. Нађите p, y и x, као следеће:
   • Нека p буде део корена који је пронађен, игноришући било децимални зарез. (За први корак, p = 0).
   • Одредите највећу цифру x такву да ${\displaystyle x(20p+x)\leq c}$. Користићемо нову променљиву y = x(20p + x).
     • Пажња: 20p + x је просто дупло p, са цифром x која се појављује десно).
     • Пажња: Можете пронаћи x погађањем шта је c/(20•p) и шта ради у пробном рачунању y, онда подешавањем x навише или наниже према потреби.
   • Ставите цифру ${\displaystyle x}$ као наредну цифру корена, нпр., изнад две цифре корена које сте спустили доле. Тако да ће p бити „старије“ p пута 10 плус x.
3. Одузимање y од c да се добије нови остатак.
4. Ако је остатак нула и нема више цифара за спуштање, онда је алгоритам завршен. У супротном вратите се на први корак за друго понављање.

Примери

Наћи квадратни корен од 152.2756.

          1  2. 3  4 
       /
     \/  01 52.27 56

         01                   1*1 <= 1 < 2*2                 x = 1
         01                     y = x*x = 1*1 = 1
         00 52                22*2 <= 52 < 23*3              x = 2
         00 44                  y = (20+x)*x = 22*2 = 44
            08 27             243*3 <= 827 < 244*4           x = 3
            07 29               y = (240+x)*x = 243*3 = 729
               98 56          2464*4 <= 9856 < 2465*5        x = 4
               98 56            y = (2460+x)*x = 2464*4 = 9856
               00 00          Алгоритам је завршен: Решење је 12.34

Наћи квадратни корен од 2.

          1. 4  1  4  2
       /
     \/  02.00 00 00 00

         02                  1*1 <= 2 < 2*2                 x = 1
         01                    y = x*x = 1*1 = 1
         01 00               24*4 <= 100 < 25*5             x = 4
         00 96                 y = (20+x)*x = 24*4 = 96
            04 00            281*1 <= 400 < 282*2           x = 1
            02 81              y = (280+x)*x = 281*1 = 281
            01 19 00         2824*4 <= 11900 < 2825*5       x = 4
            01 12 96           y = (2820+x)*x = 2824*4 = 11296
               06 04 00      28282*2 <= 60400 < 28283*3     x = 2
                             Жељена прецизност је постигнута:
                             Квадратни корен броја 2 је отприлике 1.4142

Бинарни бројевни систем (база 2)

Својствено цифра-по-цифру алгоритму је претрага и тест тих корака: пронаћи цифру, ${\displaystyle \,e}$, када се десно дода од текућег решења ${\displaystyle \,r}$, тако ${\displaystyle \,(r+e)\cdot (r+e)\leq x}$, где ${\displaystyle \,x}$ је вредност за коју се тражи корен. Проширење: ${\displaystyle \,r\cdot r+2re+e\cdot e\leq x}$. Тренутна вредност ${\displaystyle \,r\cdot r}$—или, обично, остатак може да се постепено-ажурира ефикасно када се ради у бинарном, као вредност ${\displaystyle \,e}$ ће имати један комплет бита („моћ двојке“) и операције које су потребне за рачунање ${\displaystyle \,2\cdot r\cdot e}$ и ${\displaystyle \,e\cdot e}$ може бити замењен са бржим операцијама.

Пример

Овде смо добили квадратни корен од 81, који када се претвара у бинарни даје 1010001. Бројеви у левој колони дају могућност да између тог броја и нуле се користи за одузимање у тој фази рачунања. Коначни одговор је 1001, која је у децималном број 9.

             1 0 0 1
            ---------
           √ 1010001

      1      1
             1
            ---------
      101     01  
               0
             --------
      1001     100
                 0
             --------
      10001    10001
               10001
              -------
                   0

short isqrt(short num) {
    short res = 0;
    short bit = 1 << 14; // Други највиши бит је постављен: 1 << 30 за 32 бита
 
    // "бит" почиње са највећом "снагом" четири <= аргумент.
    while (bit > num)
        bit >>= 2;
        
    while (bit != 0) {
        if (num >= res + bit) {
            num -= res + bit;
            res = (res >> 1) + bit;
        }
        else
            res >>= 1;
        bit >>= 2;
    }
    return res;
}

Експоненцијални идентитет

Калкулатор обично спроводи добре навике да израчуна експоненцијалну функцију и природни логаритам, а затим израчунава квадратни корен S, користећи идентитет пронађеног помоћу својства од логаритама (${\displaystyle \ln x^{n}=n\ln x}$) и експонената (${\displaystyle e^{\ln x}=x}$):

${\displaystyle {\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.}$

Именилац одговара n^том корену. У случају изнад именилац је 2, па једначина наводи да се квадратни корен може наћи.

Бакхсхали апроксимација

Овај метод за проналажење приближног квадратног корена је описан у древном индијском математичком рукопису под називом „Бакхсхали рукопис“. То је еквивалентно са два понављања из вавилонског метода почиње са N. Оригинална презентација гласи: Да бисте израчунали ${\displaystyle {\sqrt {S}}}$, пустите N² да буде најближа савршеном квадрату да S. Затим, израчунати:

${\displaystyle d=S-N^{2}\,\!}$

${\displaystyle P={\frac {d}{2N}}}$

${\displaystyle A=N+P\,\!}$

${\displaystyle {\sqrt {S}}\approx A-{\frac {P^{2}}{2A}}}$

Ово се такође може записати и овако:

${\displaystyle {\sqrt {S}}\approx N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}+4Nd}}={\frac {8N^{4}+8N^{2}d+d^{2}}{8N^{3}+4Nd}}={\frac {N^{4}+6N^{2}S+S^{2}}{4N^{3}+4NS}}={\frac {N^{2}(N^{2}+6S)+S^{2}}{4N(N^{2}+S)}}}$

Пример

Пронађите ${\displaystyle {\sqrt {9.2345}}}$

${\displaystyle N=3\,\!}$

${\displaystyle d=9.2345-3^{2}=0.2345\,\!}$

${\displaystyle P={\frac {0.2345}{2\times 3}}=0.0391}$

${\displaystyle A=3+0.0391=3.0391\,\!}$

${\displaystyle {\sqrt {9.2345}}\approx 3.0391-{\frac {0.0391^{2}}{2\times 3.0391}}\approx 3.0388}$

Ведска метода за проналажење квадратног корена

Ведска дуплекс метод из књиге „Ведска Математика“ је варијанта цифра по цифру методе за израчунавање квадратног корена. 'Дуплекс' је квадрат централне цифре плус дупло унакрсног производа цифара на подједнакој удаљености од центра. Дуплекс се рачуна од цифара количника (квадратних корена цифара), рачунајући до сада, али након почетних цифара. Дуплекс се одузима од дивиденди цифара пре другог одузимање за производ количника цифара временима делилац цифара. За савршене корене дуплекс и дивиденда ће добити мањи и доћи до нуле после неколико корака. За не-савршене квадрате декадну вредност квадратног корена може се израчунати до прецизности коју желимо. Међутим, како се децимална места размножавају, прилагођавање дуплекса постаје већи и дужи за израчунавање.

Основни принцип

Настављамо са цифром-по-цифру рачуном, под претпоставком да желимо да изразимо број N као квадрат збира n позитивних бројева као

${\displaystyle N=(a_{0}+a_{1}+\ldots +a_{n-1})^{2}}$

${\displaystyle =a_{0}^{2}+2a_{0}\sum _{i=1}^{n-1}a_{i}+a_{1}^{2}+2a_{1}\sum _{i=2}^{n-1}a_{i}+\cdots +a_{n-1}^{2}.}$

Одредити делиоца као ${\displaystyle q=2a_{0}}$ и дуплекс за низ од m бројева тако да

${\displaystyle d_{m}={\begin{cases}a_{\lceil m/2\rceil }^{2}+\sum _{i=1}^{\lfloor m/2\rfloor }2a_{i}a_{m-i+1}&{\mbox{for}}\;m\;{\mbox{odd}}\\\sum _{i=1}^{m/2}2a_{i}a_{m-i+1}&{\mbox{for}}\;m\;{\mbox{even}}.\\\end{cases}}}$

Дакле, можемо поново изразити идентитет у смислу делиоца и дуплекса као

${\displaystyle N-a_{0}^{2}=\sum _{i=1}^{n-1}(qa_{i}+d_{i}).}$

Сада рачунање можете да наставите од рекурзивно претпостављањем вредности ${\displaystyle a_{m}}$, тако да

${\displaystyle X_{m}=X_{m-1}-qa_{m}-d_{m},}$

тако да ${\displaystyle X_{m}\geq 0}$ за све ${\displaystyle 1\leq m\leq n-1}$, са почетком ${\displaystyle X_{0}=N-a_{0}^{2}.}$ Када ${\displaystyle X_{m}=0}$ алгоритам заврши и сумира ${\displaystyle a_{i}}$s даје квадратни корен. Ова метода је више личи на „дуге поделе“ где ${\displaystyle X_{m-1}}$ је дивиденда и ${\displaystyle X_{m}}$ је остатак За случај децималних бројева, ако

${\displaystyle N=(a_{0}\cdot 10^{n-1}+a_{1}\cdot 10^{n-2}+\cdots +a_{n-2}\cdot 10+a_{n-1})^{2}}$

где ${\displaystyle a_{i}\in \{0,1,2,\ldots ,9\}}$, онда је почетак ${\displaystyle X_{0}=N-a_{0}^{2}\cdot 10^{2(n-1)}}$ и делилац ће бити ${\displaystyle q=2a_{0}\cdot 10^{n-1}}$. такође производ у било ком m-тој фази биће ${\displaystyle qa_{m}\cdot 10^{n-m-1}=2a_{0}a_{m}\cdot 10^{2n-m-2}}$ и дуплекс ће бити ${\displaystyle d_{m}={\tilde {d}}_{m}\cdot 10^{2n-m-3}}$, где ${\displaystyle {\tilde {d}}_{m}}$ дуплекси од низа ${\displaystyle a_{1},a_{2},\ldots ,a_{m}}$. У свакој m-тој фази, видећемо да је вредност дуплекса ${\displaystyle {\tilde {d}}_{m}}$ за један мањи од производа ${\displaystyle 2a_{0}a_{m}}$. Тако, у реалним прорачунима уобичајено је да се одузети дуплекс вредности m-тог низа (m+1)-те фазе. Такође, за разлику од претходне цифра-по-цифру квадратног корена рачуна, где је у сваком m-тој фази, рачун се вршио тако што се најзначајнији пар цифара у преосталом периоду ${\displaystyle X_{m-1}}$, метода дуплекс користи само јединствени најзначајнији цифра ${\displaystyle X_{m-1}}$. Другим речима, да израчунамо дуплекс једног броја, дупло производ сваки пар са истим растојањем цифара плус квадрат центра цифре (цифара десно од десне колоне).

Број => Рачунање = Дуплекс
3 ==> 32 = 9
14 ==>2(1•4) = 8 
574 ==> 2(5•4) + 72 = 89
1,421 ==> 2(1•1) + 2(4•2) = 2 + 16 = 18 
10,523 ==> 2(1•3) + 2(0•2) + 52 = 6+0+25 = 31 
406,739 ==> 2(4•9)+ 2(0•3)+ 2(6•7) = 72+0+84  = 156

Пример

Замислите савршен квадрат 2809 = 53 < sup > 2 </ sup >. Користите метод дуплекса да пронађе квадратни корен 2.809.

• Спусти број у групе од по две цифре .
• Дефинисати 'Делилац' , а 'Дивиденде' и 'Количник' да пронађу 'корен' .
• С обзиром 2809. Размотримо прву групу, 28.
  • Најближи савршени квадрат испод те групе.
  • Корен тог савршеног корена је прва цифра нашег 'корена' .
  • Од 28> 25 и 25 = 5 ² , узети 5 као прву цифру у квадратном корену.
  • За делиоца се двоструко ову прву цифру (2 • 5), што је 10.
• Следеће, подесите поделу оквира са колоном.
  • 28: 0 9 је 'дивиденд' и 5: представља 'количник' . ( Напомена: количник треба увек да буде један двоцифрени број, и то би требало да буде таква да је дивиденда у наредној фази је не-негативна. )
  • Ставите две тачке на десној страни 28 и 5 и задржите двотачке постројили вертикално.
• Израчунајте 'остатак' . 28: 25 минус: 3 :. је
  • Остатак на левој страни следеће цифре да добијете нову дивиденду.
  • Ево, додајте 3 до следећег дивиденди цифра 0, што чини нови дивиденду 30. делиоца 10 иде на 30 само 3 пута.
• Поновите операцију.
  • Нулта остатак прилогу 9. Девет је следећи дивиденда.
  • Ово обезбеђује цифре са десне стране колоне, тако да умањи дуплекс, 3 ² = 9.
  • Одузимањем ове дуплекс од дивиденди 9, нула остатак резултатима.
  • Десет у нуле је нула. Следећи корен цифра је нула. Следећи дуплекс 2 (3 • 0) = 0.
  • Дивиденда је нула. Ово је квадратни корен, 53.

Метод две променљиве

Овај метод је примењив за проналажење квадратног корена ${\displaystyle 0<S<3\,\!}$ и конвергира најбоље за ${\displaystyle S\approx 1}$. Ово, међутим, има реална ограничења за компјутерску калкулацију, као основом 2 покретним зарезом и фиксне репрезентација тачке, то је тривијално да се умножавају ${\displaystyle S\,\!}$ целим бројем „моћи“ 4, и стога ${\displaystyle {\sqrt {S}}}$ од стране одговарајућег броја „моћи“ 2, променом експонента или пребацивањем. Дакле, ${\displaystyle S\,\!}$ > може бити премештена у распону ${\displaystyle {\frac {1}{2}}\leq S<2}$. Осим тога, следећи метод не користи опште подјеле, већ само додацима, одузимања, множења и поделама дужинама од два, који су опет тривијални да се спроведу. Непогодност ове методе је да нумеричке грешке се акумулирају, за разлику од једне варијабилне итеративне методе попут вавилонског један.

Почетни корак ове методе је

${\displaystyle a_{0}=S\,\!}$

${\displaystyle c_{0}=S-1\,\!}$

док је итеративни корак

${\displaystyle a_{n+1}=a_{n}-a_{n}c_{n}/2\,\!}$

${\displaystyle c_{n+1}=c_{n}^{2}(c_{n}-3)/4\,\!}$

Онда, ${\displaystyle a_{n}\rightarrow {\sqrt {S}}}$ (while ${\displaystyle c_{n}\rightarrow 0}$). Имајте на уму да приближавање ${\displaystyle c_{n}\,\!}$, а самим тим и ${\displaystyle a_{n}\,\!}$, је квадратна. Доказ ове методе је прилично лаган. Прво, преписати итеративну дефиницију ${\displaystyle c_{n}\,\!}$ као

${\displaystyle 1+c_{n+1}=(1+c_{n})(1-c_{n}/2)^{2}\,\!}$.

Онда је једноставно доказати индукцијом да

${\displaystyle S(1+c_{n})=a_{n}^{2}}$

а самим тим и приближавање ${\displaystyle a_{n}\,\!}$ до жељеног резултата ${\displaystyle {\sqrt {S}}}$ је обезбеђена од стране конвергенције ${\displaystyle c_{n}\,\!}$ to 0, што заузврат следи из ${\displaystyle -1<c_{0}<2\,\!}$. Ова метода је развијена око 1950. године

Итеративне методе за реципрочне квадратне корене

Итеративне методе за проналажење реципрочног квадратног корена S који је ${\displaystyle 1/{\sqrt {S}}}$. Након што је пронађен, наћи ${\displaystyle {\sqrt {S}}}$ једноставним множењем: ${\displaystyle {\sqrt {S}}=S\cdot (1/{\sqrt {S}})}$. Ове итерација укључују само множење, а не поделе. Оне су због тога брже од Вавилонског начина-методе. Међутим, они нису стабилни. Ако почетна вредност није близу узајамном квадратном корену, итерација ће да се разилазе далеко од тога, пре него да се спајају. Стога може бити корисно да се изврши итерација Вавилонском методом на грубој процени пре него што почнете да примењујете ову методу.

• Примена Њутнове методе једначини ${\displaystyle (1/x^{2})-S=0}$ производи метод који конвергира квадратну помоћу 3 множења корак по корак:

${\displaystyle x_{n+1}={\frac {x_{n}}{2}}\cdot (3-S\cdot x_{n}^{2}).}$

• Друга итерација се добија Халејевом методом што је „Householder“ меtod реда два. Ова конвергира кубно, али укључује четири множења по итерацији:

${\displaystyle y_{n}=S\cdot x_{n}^{2}\,,\!}$

${\displaystyle x_{n+1}={\frac {x_{n}}{8}}\cdot (15-y_{n}\cdot (10-3\cdot y_{n})).}$

Голдшмидтов алгоритам (Goldschmidt’s algorithm)

Неки рачунари користе Голдшмидтов алгоритам за истовремено израчунавање ${\displaystyle {\sqrt {S}}}$ and ${\displaystyle 1/{\sqrt {S}}}$. Голдшмидтов алгоритам проналази ${\displaystyle {\sqrt {S}}}$ брже него Њутнова итерација на компјутеру са више упутства. Два начина писања Голдшмидтов алгоритма су:^[2]

${\displaystyle b_{0}=S}$

${\displaystyle Y_{0}\approx 1/{\sqrt {S}}}$

${\displaystyle y_{0}=Y_{0}}$

${\displaystyle x_{0}=Sy_{0}}$

Свака итерација:

${\displaystyle b_{n+1}=b_{n}Y_{n}^{2}}$

${\displaystyle Y_{n+1}=(3-b_{n+1})/2}$

${\displaystyle x_{n+1}=x_{n}Y_{n+1}}$

${\displaystyle y_{n+1}=y_{n}Y_{n+1}}$

све до ${\displaystyle b_{i}}$ је довољно близу 1, или намештеном броју итерација.

што ствара

${\displaystyle {\sqrt {S}}=\lim _{n\to \infty }x_{n}.}$

${\displaystyle 1/{\sqrt {S}}=\lim _{n\to \infty }y_{n}.}$

Може се написати као:

${\displaystyle y_{0}\approx 1/{\sqrt {S}}}$

${\displaystyle x_{0}=Sy_{0}}$

${\displaystyle h_{0}=y_{0}/2}$

Свака итерација: (Све 3 операције у овој петљи)

${\displaystyle r_{n}=(1/2)-x_{n}h_{n}}$

${\displaystyle x_{n+1}=x_{n}+x_{n}r_{n}}$

${\displaystyle h_{n+1}=h_{n}+h_{n}r_{n}}$

све до ${\displaystyle r_{i}}$ довољно близу 0, или намештеном броју итерација. што ствара

${\displaystyle {\sqrt {S}}=\lim _{n\to \infty }x_{n}.}$

${\displaystyle 1/{\sqrt {S}}=\lim _{n\to \infty }2h_{n}.}$

Taylor series

Ако N је апроксимација ${\displaystyle {\sqrt {S}}}$, бољи апроксимација се може наћи помоћу „Тејлоровог низа“ квадратног корена функције:

${\displaystyle {\sqrt {N^{2}+d}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!d^{n}}{(1-2n)n!^{2}4^{n}N^{2n-1}}}=N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}}}+{\frac {d^{3}}{16N^{5}}}-{\frac {5d^{4}}{128N^{7}}}+\cdots }$

Као итеративни метод, редослед конвергенције је једнак броју коришћених термина. Са 2 термина, идентична је Вавилонској методи. Са 3 термина, свака итерација заузима скоро онолико операције као Бакхсхали приближавање, али конвергира спорије. Дакле, ово није нарочито ефикасан начин рачунања. Да би повећали стопу конвергенције, изаберите N тако да ${\displaystyle {\frac {|d|}{N^{2}}}\,}$ > је што је могуће мањи.

Друге методе

Остале методе су мање ефикасније од оних приказаних изнад. Потпуно другачији метод за рачунање квадратног корена заснива се на „CORDIC“ алгоритму, који користи само врло једноставне операције (сабирање, одузимање, претрагу табеле, али не и множење). Квадратни корен S може се добити као решење ${\displaystyle x_{n}}$ помоћу хиперболичног координатног система у векторском систему, са следећим иницијализацијама:

${\displaystyle x_{0}=S+1}$

${\displaystyle y_{0}=S-1}$

${\displaystyle \omega _{0}=0}$

Експанзија верижног разломка

Квадратни ирационални бројеви (бројеви обрасца ${\displaystyle {\frac {a+{\sqrt {b}}}{c}}}$, где су a, b и c су цели бројеви), а нарочито квадратни корени целих бројева, имају периодичне верижне разломке. Понекад није циљ рачунање нумеричке вредности квадратног корена, већ његова експанзија верижног разломка. Следећи итеративни алгоритам може да се користи у ту сврху (S је било који природни број који није „савршени квадратни број“):

${\displaystyle m_{0}=0\,\!}$

${\displaystyle d_{0}=1\,\!}$

${\displaystyle a_{0}=\left\lfloor {\sqrt {S}}\right\rfloor \,\!}$

${\displaystyle m_{n+1}=d_{n}a_{n}-m_{n}\,\!}$

${\displaystyle d_{n+1}={\frac {S-m_{n+1}^{2}}{d_{n}}}\,\!}$

${\displaystyle a_{n+1}=\left\lfloor {\frac {{\sqrt {S}}+m_{n+1}}{d_{n+1}}}\right\rfloor =\left\lfloor {\frac {a_{0}+m_{n+1}}{d_{n+1}}}\right\rfloor \!.}$

При томе су m_n, d_n, и a_n увек цели бројеви. Алгоритам може да се прекине на a_i када a_i = 2 a₀,^[3] што је лакше спровести. Експанзија се понавља од тада. Низ [a₀; a₁, a₂, a₃, …] је експанзија верижног разломка:

${\displaystyle {\sqrt {S}}=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\,\ddots }}}}}}}$

Пример, квадратни корен од 114 као верижни разломак

Почиње се са m₀ = 0; d₀ = 1; и a₀ = 10 (10² = 100 и 11² = 121 > 114 значи 10 је изабран).

${\displaystyle {\begin{aligned}{\sqrt {114}}&={\frac {{\sqrt {114}}+0}{1}}=10+{\frac {{\sqrt {114}}-10}{1}}=10+{\frac {({\sqrt {114}}-10)({\sqrt {114}}+10)}{{\sqrt {114}}+10}}\\&=10+{\frac {114-100}{{\sqrt {114}}+10}}=10+{\frac {1}{\frac {{\sqrt {114}}+10}{14}}}.\end{aligned}}}$

${\displaystyle m_{1}=d_{0}\cdot a_{0}-m_{0}=1\cdot 10-0=10\,.}$

${\displaystyle d_{1}={\frac {S-m_{1}^{2}}{d_{0}}}={\frac {114-10^{2}}{1}}=14\,.}$

${\displaystyle a_{1}=\left\lfloor {\frac {a_{0}+m_{1}}{d_{1}}}\right\rfloor =\left\lfloor {\frac {10+10}{14}}\right\rfloor =\left\lfloor {\frac {20}{14}}\right\rfloor =1\,.}$

Значи, m₁ = 10; d₁ = 14; и a₁ = 1.

${\displaystyle {\frac {{\sqrt {114}}+10}{14}}=1+{\frac {{\sqrt {114}}-4}{14}}=1+{\frac {114-16}{14({\sqrt {114}}+4)}}=1+{\frac {1}{\frac {{\sqrt {114}}+4}{7}}}.}$

Онда, m₂ = 4; d₂ = 7; и a₂ = 2.

${\displaystyle {\frac {{\sqrt {114}}+4}{7}}=2+{\frac {{\sqrt {114}}-10}{7}}=2+{\frac {14}{7({\sqrt {114}}+10)}}=2+{\frac {1}{\frac {{\sqrt {114}}+10}{2}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+10}{2}}=10+{\frac {{\sqrt {114}}-10}{2}}=10+{\frac {14}{2({\sqrt {114}}+10)}}=10+{\frac {1}{\frac {{\sqrt {114}}+10}{7}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+10}{7}}=2+{\frac {{\sqrt {114}}-4}{7}}=2+{\frac {98}{7({\sqrt {114}}+4)}}=2+{\frac {1}{\frac {{\sqrt {114}}+4}{14}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+4}{14}}=1+{\frac {{\sqrt {114}}-10}{14}}=1+{\frac {14}{14({\sqrt {114}}+10)}}=1+{\frac {1}{\frac {{\sqrt {114}}+10}{1}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+10}{1}}=20+{\frac {{\sqrt {114}}-10}{1}}=20+{\frac {14}{{\sqrt {114}}+10}}=20+{\frac {1}{\frac {{\sqrt {114}}+10}{14}}}.}$

Сада, назад на другу једначину горе. Сходно томе, једноставан верижни разломак за квадратни корен од 114 је

${\displaystyle {\sqrt {114}}=[10;1,2,10,2,1,20,1,2,10,2,1,20,1,2,10,2,1,20,\dots ].\,}$

Његова вредност је приближно 10,67707 82520 31311 21....

Генерализовани верижни разломак

Брже метод је да се процени генерализовани верижни разломак. Из формуле изведене:

${\displaystyle {\sqrt {z}}={\sqrt {x^{2}+y}}=x+{\cfrac {y}{2x+{\cfrac {y}{2x+{\cfrac {y}{2x+\ddots }}}}}}=x+{\cfrac {2x\cdot y}{2(2z-y)-y-{\cfrac {y^{2}}{2(2z-y)-{\cfrac {y^{2}}{2(2z-y)-\ddots }}}}}}}$

и чињеница да је 114 2/3 између 10²=100 и 11²=121 резулрира у

${\displaystyle {\sqrt {114}}={\cfrac {\sqrt {1026}}{3}}={\cfrac {\sqrt {32^{2}+2}}{3}}={\cfrac {32}{3}}+{\cfrac {2/3}{64+{\cfrac {2}{64+{\cfrac {2}{64+{\cfrac {2}{64+\ddots }}}}}}}}={\cfrac {32}{3}}+{\cfrac {2}{192+{\cfrac {18}{192+{\cfrac {18}{192+\ddots }}}}}},}$

што је једноставно поменути [10;1,2, 10,2,1, 20,1,2, 10,2,1, 20,1,2, ...] процењен на сваком трећем месту. Комбинацијом парова разломака добија се

${\displaystyle {\sqrt {114}}={\cfrac {\sqrt {32^{2}+2}}{3}}={\cfrac {32}{3}}+{\cfrac {64/3}{2050-1-{\cfrac {1}{2050-{\cfrac {1}{2050-\ddots }}}}}}={\cfrac {32}{3}}+{\cfrac {64}{6150-3-{\cfrac {9}{6150-{\cfrac {9}{6150-\ddots }}}}}},}$

што је сада [10;1,2, 10,2,1,20,1,2, 10,2,1,20,1,2, ...] процењен на треће место, а на сваких шест места након тога.

Пелова једначина

Пелова једначина (позната и као Брамагуптина једначина, јер је он први дао решење за ову конкретну једначину) и њене варијанте дају метод за ефикасно проналажење конвергената верижних разломака квадратних корена целих бројева. Међутим, то може бити компликовано да се изврши, и обично се не генерише сваки конвергент. Идеје иза методе су следеће:

• Ако је (p, q) решење (где су p и q цели бројеви) у једначини ${\displaystyle p^{2}=S\cdot q^{2}\pm 1\!}$, онда ${\displaystyle {\frac {p}{q}}}$ је наставак разломка од ${\displaystyle {\sqrt {S}}}$, и као таква је одлична рационална апроксимација за њега.
• Ако су (p_a, q_a) и (p_b, q_b) решења, онда је и:

${\displaystyle p=p_{a}p_{b}+S\cdot q_{a}q_{b}\,\!}$

${\displaystyle q=p_{a}q_{b}+p_{b}q_{a}\,\!}$

• Генерално, ако је (p₁, q₁) решење, онда је могуће да се направи низ решења (p_n, q_n) задовољавајући:

${\displaystyle p_{m+n}=p_{m}p_{n}+S\cdot q_{m}q_{n}\,\!}$

${\displaystyle q_{m+n}=p_{m}q_{n}+p_{n}q_{m}\,\!}$

Поступак је следећи:

• Проналазе се позитивни цели бројеви p₁ и q₁ такви да ${\displaystyle p_{1}^{2}=S\cdot q_{1}^{2}\pm 1}$. То је тежи део; То може да се уради било погађањем, или помоћу прилично софистициране технике.

• Како би се направио дуг списак конвергената, понавља се:

${\displaystyle p_{n+1}=p_{1}p_{n}+S\cdot q_{1}q_{n}\,\!}$

${\displaystyle q_{n+1}=p_{1}q_{n}+p_{n}q_{1}\,\!}$

• Да би се брзо нашли већи конвергенти, понавља се:

${\displaystyle p_{2n}=p_{n}^{2}+S\cdot q_{n}^{2}\,\!}$

${\displaystyle q_{2n}=2p_{n}q_{n}\,\!}$

Ваља имати у виду да се одговарајући низ разломака поклапа са оним датим Хероновом методом почевши са ${\displaystyle \textstyle {\frac {p_{1}}{q_{1}}}}$.

• У истом случају, ${\displaystyle {\frac {p_{n}}{q_{n}}}}$ рационална апроксимација је задовољена

${\displaystyle \left|{\frac {p_{n}}{q_{n}}}-{\sqrt {S}}\right|<{\frac {1}{q_{n}^{2}\cdot {\sqrt {S}}}}.}$

Апроксимације које зависе од покретне тачке

Број је заступљен покретним зарезом у формату као ${\displaystyle m\times b^{p}}$ који се такође назива „научна нотација“.Њен корен је квадратни ${\displaystyle {\sqrt {m}}\times b^{p/2}}$ и из сличних формула се пријављују за кубне корене и логаритме. На први поглед, ово је било побољшање у једноставности, али претпостављањем да је потребна само апроксимација: Онда само ${\displaystyle b^{p/2}}$ је добро за ред величине. Даље, признају да ће неки, p, бити чудно, па је за 3141.59 = 3.14159x10³ него се баве разломком базе, помножите од базе и одузмите један од њега да се направи још. Кориговани ће постати еквивалент 31.4159x10² тако да ће квадратни корен бити √31.4159 x 10.

Ако је цео део прилагођен да се узима, не може бити само вредности од 1 до 99, и који би се могао користити као индекс у табели од 99 унапред израчунава квадратни корен да заврши процену. Рачунар користи шеснаест базних што би захтевало већу табелу, али употребом базе два ће захтевати само три ставке: могући бит у цео број дела прилагођеним су 01 (може бити још тако да није било смене, сећајући се да је нормализује померајућа тачка број увек има не-нула високи-ред бројке), или ако је напајање било чудно, 10 или 11, то су прва два бита оригиналне поставке. Тако, 6.25 = 110.01 у бинарном, да нормализују 1.1001 x 2² тако да су упарени битови 01, док .625 = 0.101 у бинарном нормализује до 1.01 x 2⁻¹ непарано тако да је прилагођавање 10.1 x 2⁻² и упарени битови су 10. Обавештење да је низак редослед има одјека у високом реду. Чак снага има низак-ред мало нула и кориговани ће почети са 0, док је за непарним да мало је један и кориговани ће почети 1. Стога, када се напајање преполови, то је као да се његова мало помера како би постао први бит на поравнавању.

Табеле са само три ставке могу бити увећане укључивањем додатних делова мантисе. Међутим, са рачунарима, израчунати интерполација у табели, често је боље наћи неки једноставнији рачун који даје еквивалентне резултате. Све сада зависи од тачних детаља формата репрезентације плус који су доступни за приступ и манипулацију делова броја операција. На пример, Фортран нуди експонент (к) функција да добију „моћ“. Труд који је уложен у креирању почетног приближавања је да се надокнади чиме се избегава додатна итерација процеса пречишћавања који би био потребан за „сиромашна“ приближавања. Будући да су неки (једна итерација захтева поделу, додатак, и преполовљавање) ограничење је тешко.

Многи рачунари прате IEEE померање тачке стандард (или довољно сличне), и веома брзо приближавање квадратног корена може да се добије за покретање Њутновог метода. Техника која следи се заснива на чињеници да померање тачке формат (у бази два) апроксимира бази-2 логаритму. То је ${\displaystyle \log _{2}(m\times 2^{p})=p+\log _{2}(m)}$ Дакле, за 32-битну пецизност броја померајуће тачке у IEEE формату (где је посебно да има пристрасност од 127 је додао за представљену форму) можете добити приближни логаритам тумачећи своју бинарну заступљеност као 32-битни цео број, то скалирање од ${\displaystyle 2^{-23}}$, и уклањање пристрасности од 127, односно

${\displaystyle x_{\text{int}}\cdot 2^{-23}-127\approx \log _{2}(x).}$

На пример, 1.0 представља хексадецимални број 0x3F800000, који би представљао ${\displaystyle 1065353216=127\cdot 2^{23}}$ ако се узме као цео број. Користећи формулу изнад добијате ${\displaystyle 1065353216\cdot 2^{-23}-127=0}$, као што се очекивало од ${\displaystyle \log _{2}(1.0)}$. На сличан начин добијате 0.5 од 1.5 (0x3FC00000).

Да бисте добили квадратни корен, поделите логаритам са 2 и претворите вредност назад. Следећи програм демонстрира идеју. Имајте на уму да најнижи бит је као експонент намерно дозвољен да пропагира у „мантисе“. Један од начина да се оправда корак у овом програму је да преузме ${\displaystyle b}$ као експонент пристрасности и ${\displaystyle n}$ као број сачуваних експлицитних битова у „мантисе“ и онда показати да

${\displaystyle (((x_{\text{int}}/2^{n}-b)/2)+b)\cdot 2^{n}=(x_{\text{int}}-2^{n})/2+((b+1)/2)\cdot 2^{n}.}$

float sqrt_approx(float z)
{
    int val_int = *(int*)&z; /* Исти битови али као цели бројеви */
    /*
     * Да би оправдали следећи код, докажите да
     *
     * ((((val_int / 2^m) - b) / 2) + b) * 2^m = ((val_int - 2^m) / 2) + ((b + 1) / 2) * 2^m)
     *
     * где
     *
     * b = експонент пристрасности
     * m = број мантиса битова 
     *
     * .
     */

    val_int -= 1 << 23; /* Одузето са 2^m. */
    val_int >>= 1; /* Подељено са 2. */
    val_int += 1 << 29; /* Додај ((b + 1) / 2) * 2^m. */

    return *(float*)&val_int; 
}

Три математичке операције које чине језгро изнад функције могу се изразити у једној линији. Додатна подешавања могу се додати да се смањи максимална релативна грешка. Дакле, три операције, можемо записати као

val_int = (1 << 29) + (val_int >> 1) - (1 << 22) + a;

где a пристрастан за подешавање приближавање грешке. На пример, са a = 0 резултати су тачни за овлашћења до 2 (нпр., 1.0), већ за друге бројеве резултати ће бити мало превелики (нпр.,1.5 за 2.0 уместо 1.414... са 6% грешке). Са a = -0x4C000, грешке су између -3.5% и 3,5%.

Ако се апроксимација треба користити за иницијалну претпоставку Њутновог метода једначине ${\displaystyle (1/x^{2})-S=0}$, онда је реципрочни облик приказан у следећем одељку приоритетан.

Узајамни/реципрочни квадратни корени

Варијанта ове рутине је приказана у наставку, она се може користити за израчунавање реципрочног квадратног корена, односно ${\displaystyle x^{-{1 \over 2}}}$ уместо, написао је Грег Валсх (Greg Walsh), а спроводи у SGI Indigo Гари Тароли (Gary Tarolli).^[4][5]

Цео број апроксимације производи релативну грешку мање од 4%, а грешка додатно пада на 0,15% са једном итерацијом Њутнове методе на следећој линији^[6] У компјутерској графици је веома ефикасан начин да се нормализује вектор.

float invSqrt(float x)
{
        float xhalf = 0.5f*x;
        union
        {
  	    float x;
            int i;
        } u;
        u.x = x;
        u.i = 0x5f3759df - (u.i >> 1);
        /* Следећа линија може да се понови неограничен број пута за повећање тачности */
        u.x = u.x * (1.5f - xhalf * u.x * u.x);
        return u.x;
}

Негативни или комплексни квадратни корен

Ако S < 0, онда је главни квадратни корен: ${\displaystyle {\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.}$

Ако S = a+bi где a и b су реални и b ≠ 0, онда је главни квадратни корен:

${\displaystyle {\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operatorname {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2}}}\,\,i\,.}$

Ово се може проверити квадрирањем квадратног корена.^[7][8] Овде

${\displaystyle \vert S\vert ={\sqrt {a^{2}+b^{2}}}}$

је модул од S. Главни квадратни корен од комплексног броја се дефинише као корен са не-негативним реалним делом.

Види још

• Математика
• Алгоритам
• Квадратни корен

Референце

1. Heath, Sir Thomas Little (1921). A History of Greek Mathematics. Clarendon Press. стр. 323—. 
2. Markstein, Peter (2004). „Software Division and Square Root Using Goldschmidt's Algorithms”. CiteSeerX: 10.1.1.85.9648.  Недостаје или је празан параметар |url= (помоћ)
3. Gliga, Alexandra Ioana (17. 3. 2006). On continued fractions of the square root of prime numbers (pdf). Corollary 3.3. 
4. Rys (29. 11. 2006). „Origin of Quake3's Fast InvSqrt()”. Beyond3D. Приступљено 19. 04. 2008. 
5. Rys (19. 12. 2006). „Origin of Quake3's Fast InvSqrt() - Part Two”. Beyond3D. Приступљено 19. 04. 2008. 
6. Fast Inverse Square Root by Chris Lomont
7. {{cite book|last1=Abramowitz|first1=Milton|last2=Stegun|first2=Irene A.|title=Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables| url =|year=1964|publisher=Courier Corporation|isbn=978-0-486-61272-0}
8. Cooke, Roger (2008). Classical algebra: its nature, origins, and uses. John Wiley and Sons. стр. 59. ISBN 978-0-470-25952-8. , Extract: pp. 59

Спољашње везе

• Weisstein, Eric W. „Square root algorithms”. MathWorld. 
• Square roots by subtraction Архивирано на сајту Wayback Machine (3. март 2016)
• Integer Square Root Algorithm by Andrija Radović
• Personal Calculator Algorithms I : Square Roots (William E. Egbert), Hewlett-Packard Journal (may 1977) : pp. 22
• Calculator to learn the square root