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

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

$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)$

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

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

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

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

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

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

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

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

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

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

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

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

$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 све док се не постигне жељена тачност

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

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

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

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

Пример

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

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

$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$

$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$

$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$

$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$

$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 буде дефинисана са

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

тада је

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

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

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

тако да важи

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

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

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

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

${\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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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}}$

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

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

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

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

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

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

$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},$

$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)}.$

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

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

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

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

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

1. Почевши са леве стране, спусти најзначајнији (скроз лево) пар цифара који није искоришћен (ако су се искористиле све цифре, пишите "00") и упишите их на десној страни остатка из претходног корака (за први корак, неће бити остатка). Другим речима, помножите остатак са 100 и додајте две цифре. То ће бити 'тренутна вредност' c '.
2. Нађите p, y и x, као следеће:
   • Нека p буде део корена који је пронађен, игноришући било децимални зарез. (За први корак, p = 0).
   • Одредите највећу цифру x такву да $x(20p+x)\leq c$. Користићемо нову променљиву y = x(20p + x).
     • Пажња: 20p + x је просто дупло p, са цифром x која се појављује десно).
     • Пажња: Можете пронаћи x погађањем шта је c/(20•p) и шта ради у пробном рачунању y, онда подешавањем x навише или наниже према потреби.
   • Ставите цифру $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)

Својствено цифра-по-цифру алгоритму је претрага и тест тих корака: пронаћи цифру, $\,e$, када се десно дода од текућег решења $\,r$, тако $\,(r+e)\cdot (r+e)\leq x$, где $\,x$ је вредност за коју се тражи корен. Проширење: $\,r\cdot r+2re+e\cdot e\leq x$. Тренутна вредност $\,r\cdot r$—или, обично, остатак може да се постепено-ажурира ефикасно када се ради у бинарном, као вредност $\,e$ ће имати један комплет бита („моћ двојке“) и операције које су потребне за рачунање $\,2\cdot r\cdot e$ и $\,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, користећи идентитет пронађеног помоћу својства од логаритама ($\ln x^{n}=n\ln x$) и експонената ($e^{\ln x}=x$):

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

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

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

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

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

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

$A=N+P\,\!$

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

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

${\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)}}$

Пример

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

$N=3\,\!$

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

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

$A=3+0.0391=3.0391\,\!$

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

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

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

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

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

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

$=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}.$

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

$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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$b_{0}=S$

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

$y_{0}=Y_{0}$

$x_{0}=Sy_{0}$

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

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

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

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

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

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

што ствара

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

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

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

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

$x_{0}=Sy_{0}$

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

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

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

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

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

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

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

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

Taylor series

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

${\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 тако да ${\frac {|d|}{N^{2}}}\,$ > је што је могуће мањи.

Друге методе

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

$x_{0}=S+1$

$y_{0}=S-1$

$\omega _{0}=0$

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

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

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

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

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

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

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

$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₀, што је лакше спровести. Експанзија се понавља од тада. Низ [a₀; a₁, a₂, a₃, …] је експанзија верижног разломка:

${\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 је изабран).

${\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}}$

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

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

$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.

${\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.

${\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}}}.$

${\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}}}.$

${\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}}}.$

${\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}}}.$

${\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 је

${\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....

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

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

${\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 резулрира у

${\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, ...] процењен на сваком трећем месту. Комбинацијом парова разломака добија се

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Број је заступљен покретним зарезом у формату као $m\times b^{p}$ који се такође назива „научна нотација“.Њен корен је квадратни ${\sqrt {m}}\times b^{p/2}$ и из сличних формула се пријављују за кубне корене и логаритме. На први поглед, ово је било побољшање у једноставности, али претпостављањем да је потребна само апроксимација: Онда само $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 логаритму. То је $\log _{2}(m\times 2^{p})=p+\log _{2}(m)$ Дакле, за 32-битну пецизност броја померајуће тачке у IEEE формату (где је посебно да има пристрасност од 127 је додао за представљену форму) можете добити приближни логаритам тумачећи своју бинарну заступљеност као 32-битни цео број, то скалирање од $2^{-23}$, и уклањање пристрасности од 127, односно

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

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

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

$(((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%.

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

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

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

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

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, онда је главни квадратни корен: ${\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.$

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

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

Ово се може проверити квадрирањем квадратног корена. Овде

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

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

Види још

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

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

• 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