Í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 algoritmus

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 $(a+b)^{2}=a^{2}+2ab+b^{2}$ azonosságot használjuk, ahol $b$ a következő jegy, és $a$ az eddigi eredmény, egy hozzáfűzött nullával, hogy a nagyságrendek helyesek legyenek. Az $a^{2}$ -et már levontuk a radikandusból; már csak az $2ab$ és $b^{2}$ kiszámítása és kivonása van hátra.

A $b$ számot becsléssel találjuk meg. Ha a már ismert $2a$ -val elosztunk, az eredmény $b$ , viszont ezt kivonva a különbség nem lehet kisebb, mint $b^{2}$ . Miután kivontuk az $2ab$ és $b^{2}$ 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élda

2916 négyzetgyöke

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, $25=5\cdot 5$ , tehát a négyzetgyök első jegye 5. $29-25=4$ ; 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 $2\cdot a$ -szor 10-zel (itt $2\cdot 50=100$ ), 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 $x\approx 54{,}00023$ értéket adja. 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öke

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észen 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ámrendszerekben

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ámrendszerben

      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öke

Ú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öke

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öke

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

Teljesítmény

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

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

Menet közben az $r$ maradékot is tárolni kell, amihez $O(k)$ 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 $B$ szerepéről. Nagyobb alap esetén tovább tart $b$ kiválasztása, a szorzótényező $O(\log B)$ . Azonban a nagyobb alapra váltás ugyanennyied részére csökkenti a számjegyek számát. Mindezek miatt az algoritmus $O(\log ^{2}(B))$ -szeresére gyorsul. Hogyha a radikandus kisebb, mint $B$ , azaz 1 szá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ások

Das schriftliche Ziehen von Kubikwurzeln. [2001. június 8-i dátummal az eredetiből archiválva].
Schriftliches Quadratwurzelziehen Ausführliche Erläuterung des schriftlichen Wurzelziehens
ausführliche Erklärung des Algorithmus mit Online-Generator
Why the square root algorithm works "Home School Math". Also related pages giving examples of the long-division-like pencil and paper method for square roots.

Fordítá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 és a szerzői jogokat 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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.