Írásbeli gyökvonás

Az írásbeli gyökvonás egy racionális szám gyökének meghatározására alkalmas módszer, melyhez nincs szükség számítógépre. Hasonlóan az írásbeli osztáshoz, minden lépéssel az eredmény egy újabb jegyét ismerhetjük meg. A binomiális képleteken alapul.

Régebben is ritkán volt rá szükség, ma már kevés helyen tanítják. Ennek oka az, hogy kevés gyakorlati alkalmazása van, így inkább az alapműveleteket gyakoroltatják többet. Iteratív eljárások, mint a Héron-módszer egyszerűbben kivitelezhetők, és többnyire gyorsabban szolgáltatnak ugyanolyan pontos eredményt.

Az írásbeli köbgyökvonás a négyzetgyökvonáshoz hasonló elven működik. Még ritkábban alkalmazzák. Magasabb kitevős gyökök is vonhatók hasonló módon. Mindezek a módszerek függetlenek attól, hogy milyen számrendszert használunk.

Négyzetgyökvonási algoritmusSzerkesztés

A radikandust a tizedesvesszőtől jobbra és balra kiindulva két számjegyes csoportokra osztjuk. Ezután tekintjük a legnagyobb helyi értékű, egy vagy két számjegyből álló csoportot. Keressük azt a legnagyobb számjegyet, melynek négyzete nem nagyobb ennél a csoportnál. Ennek négyzetét kivonjuk a radikandus első számjegycsoportjából, a különbséget leírjuk az első számjegycsoport alá, és kiegészítjük a következő számjegycsoporttal.

A következő jegyek megkereséséhez az   azonosságot használjuk, ahol   a következő jegy, és   az eddigi eredmény, egy hozzáfűzött nullával, hogy a nagyságrendek helyesek legyenek. Az  -et már levontuk a radikandusból; már csak az   és   kiszámítása és kivonása van hátra.

A  számot becsléssel találjuk meg. Ha a már ismert  -val elosztunk, az eredmény  , viszont ezt kivonva a különbség nem lehet kisebb, mint  . Miután kivontuk az   és   számokat, a különbség után írjuk a következő kettes csoportot, és folytatjuk a következő lépéssel.

Ha a radikandus négyzetszám vagy két négyzetszám hányadosa, akkor az eljárás véges sok lépés után véget ér. Ha nem, akkor a kívánt pontosságig kell számolni. Hogyha elfogytak közben a radikandus kettes jegycsoportjai, akkor dupla nullás csoportokkal lehet folytatni.

PéldaSzerkesztés

2916 négyzetgyökeSzerkesztés

Példaként 2916 négyzetgyökét keressük.

Első lépésként kettes számjegycsoportjukra osztjuk a számot. Egész szám esetén a kiindulópont az egyes helyi értékű számjegy.

√ 29 16 = ?

A legnagyobb négyzetszám, ami nem nagyobb, mint 29,  , tehát a négyzetgyök első jegye 5.  ; a 4 után fűzzük a radikandus következő két jegyét, így lesz a következő szám 416:

√ 29 16 = 5
 -25
   4 16

Ahhoz, hogy megkapjuk a következő jegyet (b), osztunk  -val (itt  ), hogy nemnegatív maradék maradjon: 416 : 100 = 4, a maradék 16 = 4². Ezzel az eljárás maradék nélkül zárul, 2916 négyzetszám.

√ 29 16 = 54
 -25
  __
   4 16
  -4 00
  -  16
   ____
      0

Az írásbeli osztáshoz hasonlóan helyi érték szerint behúzva, ezért mindig relevánsan tudtuk ábrázolni a jegyeket.

Ez a számítás próbaszámítás nélkül kideríti, hogy itt tényleg négyzetszámról van szó, amire az iteratív eljárások nem képesek, mivel közelítő értéket adnak. A Héron-eljárás a 2916 esetén az 50-nel mint kiindulási értékkel két lépés után az   értéket kapjuk. Ellenben a 2916, mint kiinduló érték csak tíz lépés után ad hasonlóan pontos eredményt.

2538413,6976 négyzetgyökeSzerkesztés

 
Az algoritmus működése a 2538413,6976 négyzetgyökének kiszámításában

Az algoritmus egy másik változatát a 2538413,6976 négyzetgyökének meghatározására használjuk:

A 2 53 84 13,69 76 négyzetgyökének számításának lépései:

1. Megkeressük a legnagyobb számot, aminek négyzete nem nagyobb az első számjegycsoportnál. Ez most 1.
2. A szám négyzetét kivonjuk az első jegycsoportból: (2 − 1).
3. A különbséghez hozzáfűzzük a következő két számjegyet (153).
4. Az új számnak elhagyjuk az utolsó jegyét (15), és ezt osztjuk az eddigi eredménnyel (15 : 2).
5. A lefelé kerekített hányadost (7) a következő lépés szorzásában tényezőként szerepel. Az értéket hozzáírjuk az osztóhoz (2), és megszorozzuk a már említett tényezővel (27·7). Ha a hányados nagyobb, mint 9, akkor helyette a szorzó 9. Ha a szorzat nagyobb, mint a 3. lépésben alkotott szám (153), akkor mindkét tényezőt csökkentjük eggyel, mindaddig, amíg olyan számot kapunk, ami nem nagyobb nála (27·7 = 189 > 153 → 26·6 = 156 > 153 → 25·5 = 125 < 153).
6. A tényező utolsó jegye a a gyök következő jegye (5).
7. Az eljárás folytatódik a harmadik lépéssel, egésdzen addig, amíg el nem érjük a kívánt pontosságot.

A mellékelt ábra szerint ez a szám két négyzetszám hányadosa.

Számolás további kitevőkkel és más számrendszerekbenSzerkesztés

Ha a gyök kitevője magasabb, akkor a blokkok hossza nem 2, hanem egyezik a gyökkitevővel. Más helyi értékes számrendszerben is elvégezhető a számítás, ahol az adott számrendszer alapján kell számolni.

A 2 négyzetgyöke kettes számrendszerbenSzerkesztés

      1, 0  1  1  0  1
    ------------------
   / 10,00 00 00 00 00     1
/\/   1                  + 1
     -----               ----
      1 00                100
         0               +  0
     --------            -----
      1 00 00             1001
        10 01            +   1
     -----------         ------
         1 11 00          10101
         1 01 01         +    1
         ----------      -------
            1 11 00       101100
                  0      +     0
            ----------   --------
            1 11 00 00    1011001
            1 01 10 01          1
            ----------
               1 01 11 maradék

A három négyzetgyökeSzerkesztés

Újra tízes számrendszerben számolunk:

     1, 7  3  2  0  5
    ----------------------
   / 3.00 00 00 00 00
/\/  1 = 20*0*1+1^2
     -
     2 00
     1 89 = 20*1*7+7^2
     ----
       11 00
       10 29 = 20*17*3+3^2
       -----
          71 00
          69 24 = 20*173*2+2^2
          -----
           1 76 00
                 0 = 20*1732*0+0^2
           -------
           1 76 00 00
           1 73 20 25 = 20*17320*5+5^2
           ----------
              2 79 75

Az öt köbgyökeSzerkesztés

Tízes számrendszerben:

     1,  7   0   9   9   7
    ----------------------
  3/ 5,000 000 000 000 000
/\/  1 = 300*(0^2)*1+30*0*(1^2)+1^3
     -
     4 000
     3 913 = 300*(1^2)*7+30*1*(7^2)+7^3
     -----
        87 000
             0 = 300*(17^2)*0+30*17*(0^2)+0^3
       -------
        87 000 000
        78 443 829 = 300*(170^2)*9+30*170*(9^2)+9^3
        ----------
         8 556 171 000
         7 889 992 299 = 300*(1709^2)*9+30*1709*(9^2)+9^3
         -------------
           666 178 701 000
           614 014 317 973 = 300*(17099^2)*7+30*17099*(7^2)+7^3
           ---------------
            52 164 383 027

A hét negyedik gyökeSzerkesztés

Tízes számrendszerben:

     1,   6    2    6    5    7
    ---------------------------
  4/ 7,
/\/  -
     6 0000
     5 5536 = 4000*(1^3)*6+600*(1^2)*(6^2)+40*1*(6^3)+6^4
     ------
       4464 0000
       3338 7536 = 4000*(16^3)*2+600*(16^2)*(2^2)+40*16*(2^3)+2^4
       ---------
       1125 2464 0000
       1026 0494 3376 = 4000*(162^3)*6+600*(162^2)*(6^2)+40*162*(6^3)+6^4
       --------------
         99 1969 6624 0000
         86 0185 1379 0625 = 4000*(1626^3)*5+600*(1626^2)*(5^2)+
         -----------------   40*1626*(5^3)+5^4
         13 1784 5244 9375 0000
         12 0489 2414 6927 3201 = 4000*(16265^3)*7+600*(16265^2)*(7^2)+
         ----------------------   40*16265*(7^3)+7^4
          1 1295 2830 2447 6799

PerformanciaSzerkesztés

A továbbiakban   az eddig kiszámolt eredmény,   jelöli az újabb számjegyet,   a gyökkitevőt, és   annak a számrendszernek azt alapját, amiben a számításokat végezzük.

A legidőtrablóbb lépés   megtalálása. Mivel   lehetséges érték van, azért   összehasonlítással megtalálhatjuk az értéket. Minden összehasonlításhoz ki kell számolni ezt:  . A k-adik iterációban   jegyeinek száma  , így a polinom   szorzással értékelhető ki, legfeljebb   jegyű számokkal. Az összeadások száma  , és szintén legfeljebb   jegyű számokkal kell számolni, ha ismerjük   és   hatványait egészen  -ig. Mármost   csak korlátozott számú értéket vehet fel, így hatványai konstans időben számíthatók. Az   hatványai   szorzással megkaphatók. Feltéve, hogy az   jegyű szorzások  , az   jegyű összeadások   időbe kerülnek, kapjuk, hogy egy összehasonlítás ideje  , és   megtalálása   időbe telik. A maradék számítása összeadást és kivonást igényel, így   időben megvan, tehát egy iteráció időigénye  . Az összes   jegy feldolgozásához szükséges idő  .

Menet közben az   maradékot is tárolni kell, amihez   jegy kell a k-adik iterációhoz. Ez azonban nincs korlátozva, és mivel az eredmény feltehetően irracionális, a teljes periódus kiszámítása sem segít. Az elemibb számítási módszerekkel szemben ez korlátozza a fejben kiszámolható jegyek számát. Egy korlátos állapotgép periodikus bemenetekből csak periodikus kimenetet tud véges algoritmussal kiszámolni, így nem tudhat racionális bemenetből irracionális kimenetet kiszámolni, ami kizárja véges gyökszámító algoritmus létét, a gyök csak adott pontosságig számolható ki.

Végül ejtsünk szót   szerepéről. Nagyobb alap esetén tovább tart   kiválasztása, a szorzótényező  . Azonban a nagyobb alapra váltás ugyanennyied részére csökkenti a számjegyek számát. Mindezek miatt az algoritmus  -szeresésre gyorsul. Hogyha a radikandus kisebb, mint  , azaz egyszámjegyűvé válik, akkor az eljárás bináris kereséssé változik, ami egyszerűbb. Emiatt legfeljebb csak gyakorlásként érdemes az írásbeli gyökvonást leprogramozni, mivel a bináris keresés egyszerűbb.

ForrásokSzerkesztés

Sablon:Wikisource Meyers

FordításSzerkesztés

Ez a szócikk részben vagy egészben a Schriftliches Wurzelziehen című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként. Ez a szócikk részben vagy egészben a Shifting nth root algorithm című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.