In algoritmiikan ja numeerinen analyysi , neliöjuuri uutto on prosessi, annetaan numero, laskemalla sen neliöjuuri . Tämän laskennan suorittamiseksi on monia menetelmiä. Tämä on erityinen tapaus n: nnen juuren laskennan etsimiselle .
Koska luvun neliöjuuri voi olla irrationaalinen luku , neliöjuuren poiminta on yleensä likimääräinen.
A: n neliöjuuren purkaminen on sama kuin yhtälön ratkaiseminen . Siksi sovelletaan yleisiä menetelmiä polynomiyhtälöiden ratkaisemiseksi ja yleisemmin algoritmeja funktion nollan löytämiseksi . Samoja työkaluja käytetään mittaamaan menetelmien suorituskykyä.
Kun ylimääräistä tarkkuutta ei anneta, neliöjuuren poiminta tehdään reaalilukujoukossa . Voimme kuitenkin olla kiinnostuneita muista numerosarjoista, kuten kompleksiluvuista tai renkaista , kuten ℤ / nℤ .
Menetelmä Heron on historiallinen kehittämää babylonialaiset . Nykyaikaisemmin sanottuna tämä on Newtonin menetelmän erityistapaus .
(Positiivisen) luvun a neliöjuurin määrittämiseksi on siksi otettava huomioon induktiolla määritelty sekvenssi seuraavasti: ensimmäinen termi on valittu, jos mahdollista "tarpeeksi lähellä" on √ , yleensä kokonaisluku osa on √ .
Nopeus lähentyminen peräkkäisten likiarvojen kohti tarkkaa arvoa on neliömäinen .
Se löytyy Intian käsikirjoitus, sanoi Bakshali käsikirjoitus, ehkä vuodelta VII : nnen vuosisadan erilainen korjaus Heronin menetelmä, uusi arvo on arviolta . Se vastaa Heronin menetelmän soveltamista kahdesti peräkkäin. Tämän viimeisen menetelmän iterointi antaa kahden asteen lähentymisnopeuden:
Tarkastellaan sekvenssejä u ja v, jotka määritellään seuraavasti:
Sekvenssit u ja v ovat vierekkäisiä ja yhtenevät kohti samaa rajaa: √ a . Virhe kasvaa erolla . Sekvenssi v ei ole mikään muu kuin sekvenssi, joka on saatu iteroimalla Heronin menetelmä arvosta 1 .
Huomaa tämän esityksen omaperäisyys, jossa yhdistyvät harmoniset, geometriset ja aritmeettiset keskiarvot. Todellakin, √ ei ole mikään muu kuin geometrinen keskiarvo 1 ja , ja jos me korvata millä tahansa tiukasti positiivinen reaaliluku b , sekvenssit u ja v yhtyvät kohti geometrinen keskiarvo √ ab of ja b .
Numeroiden desimaalimerkinnän käyttöönotto sijainnin mukaan mahdollisti algoritmin kehittämisen hyödyntämällä tätä merkintää. Löydämme maininnan siitä intialaisen matemaatikon Âryabhatan teoksessa noin 499 jKr. AD Sitä käytettiin useiden vuosisatojen vasta puolivälissä XX : nnen vuosisadan ennen keksintö elektronisia tietokoneita. Aryabhata antaa myös vastaavan algoritmin laskemiseksi kuutiometriä juuret .
Erota luvun numerot pareittain desimaalipisteestä alkaen. Sijoitamme numeron, josta haluamme poimia juuren, ylhäältä samalla tavalla kuin suoritettaessa jako klassisen menetelmän mukaisesti; neliöjuuri merkitään jakajalle normaalisti varattuun paikkaan tavanomaisessa poseeratussa jaossa .
Jokaisessa vaiheessa:
Huomaa, että x : n etsiminen laiminlyömällä termi x 2: ssa ei ole kukaan muu kuin Heronin menetelmä.
Esimerkki: √ 152,2756 = 12,34 hirsipuu-menetelmällä(Huomaa: Juuren muodostavien numeroiden sekvenssi merkitään jakelijalle siirrettyyn paikkaan klassisessa jaossa, jolloin saadaan tulos: 12.34. Pilkun paikka on merkittävä, mutta sitä ei tarvitse ottaa huomioon huomioi se laskun aikana)
1 | 52 | , 27 | 56 | 1 2 , 3 4 | Juuren r progressiivinen rakenne . Laske ensimmäinen viipale. | |
1 | ? ×? | Etsimme suurinta x, niin että x ² ei ylitä arvoa 1. Se on 1 . Täydennämme r . | ||||
-1 | 1 × 1 = 1 | että yksi ottaa pois nykyisestä lopusta ja toinen laskee seuraavan viipaleen. | ||||
0 | 52 | 2? ×? | r = 1, etsimme suurinta x siten, että (20+ x ) x ei ylitä 52. Se on 2 . Täydennämme r . | |||
- | 44 | 2 2 × 2 = 44 | että yksi ottaa pois nykyisestä jäljellä olevasta ja toinen laskee seuraavan erän. Laitamme pilkun r: ään . | |||
8 | 27 | 24? ×? | r = 12, etsimme suurinta x siten, että (240+ x ) x ei ylitä 827. Se on 3 . Täydennämme r . | |||
-7 | 29 | 24 3 × 3 = 729 | että yksi ottaa pois nykyisestä lopusta ja toinen laskee seuraavan viipaleen. | |||
98 | 56 | 246? ×? | r = 123, etsimme suurinta x siten, että (2460+ x ) x ei ylitä 9856. Tämä on 4 . Täydennämme r . | |||
- | 98 | 56 | 246 4 × 4 = 9856 | että otamme pois nykyisestä leposta | ||
0 | Loppu |
Tähän algoritmiin käytettiin yleisesti XX - luvulle saakka nopeuttamalla laskutoimituksia abakilla, joka muodosti joukon nauhoja: Napier-tikkuja .
Vaikka tässä kuvataan tukiasemaan 10 kirjoitetuille numeroille, menettely toimii missä tahansa numeropohjassa, esimerkiksi kannassa 2 .
Ruffini-Horner-menetelmäA: n neliöjuuren löytäminen on polynomin P (X) = X² - A positiivisen juuren löytäminen. Olkoon a suurin kokonaisluku siten, että P (a) on negatiivinen tai nolla. A: n juuri on kokonaisluku a: n ja + 1: n välillä. Asetamme sitten X = a + Y / 10. P (X) = P (a + Y / 10) = P 1 (Y). Neliöjuuri A on sitten yhtä kuin + r / 10, jossa r on juuri polynomin P 1 . Jos b on suurin kokonaisluku siten, että P 1 (b) on negatiivinen, niin juuri A on välillä + b / 10 ja a + b / 10 + 1/10. Sen jälkeen määritetään Y = b + Z / 10, P 1 (Y) = P 2 (Z). Etsimme sitten P 2 : n juurta jne.
Ruffini-Horner menetelmän avulla on helppo vaihtaa muuttujiin
Esimerkki: √ 152,2756 = 12,34 Hornerin menetelmälläP (X) = X2 - 152,2756
a = 12, koska P (12) <0 ja P (13)> 0
Muuttujan X = 12 + Y / 10 muutos polynomissa P suoritetaan Hornerin menetelmän mukaisesti:
P: n kertoimet | 1 | 0 | - 153,2756 |
1 | 12 | 144-152,2756 = -8,2756 | |
1 | 12 + 12 = 24 | ||
1 |
Siksi
Suurin kokonaisluku b, kuten P 1 (b) on negatiivinen, on 3 (etsimme arvoa, joka on lähellä arvoa 827/240). Etsitty juuri on siis välillä 12,3–12,4
Teemme muutoksen muuttujan Y = 3 + Z / 10 polynomin P 1
Kertoimet P 1 | 1 | 240 | - 827,56 |
1 | 3 × 1 + 240 = 243 | 3 × 243 -827,56 = -98,56 | |
1 | 3 × 1 + 243 = 246 | ||
1 |
Siksi
4 on P 2: n juuri . Joten 152.2756: n neliöjuuri on 12.34
Uuttaminen peräkkäisinä parittomina summinaTämä menetelmä joskus opetti XIX : nnen vuosisadan eduksi alennetaan useita lisäyksiä (enintään 9 kohti haetaan desimaalin) peräkkäisten pariton
Se koostuu peräkkäisten neliöiden taulukon ja niiden eron hyödyntämisestä huomioimalla se . Neliötaulukon skannaus koostuu siis peräkkäisten parittomien numeroiden lisäämisestä. Leikattuamme numeron kahden numeron viipaleiksi alkaen oikealta, löydämme neliön heti ryhmän alapuolelta, joka on kauimpana vasemmalla. Antaa olla tämän juuri alemman neliön neliöjuuri. Kerrotaan löydetty kokonaisluku ja pyyhkäistään neliötaulukko alkaen (ja ) lähestyäksesi kahden vasemmanpuoleisen ryhmän muodostamaa lukua. Tämä luku löydetään, kerrotaan se selaamalla neliötaulukkoa alkaen jne.
Ennen kuin skannataan neliötaulukko, 5: llä päättyvien kokonaislukujen neliöiden helppo laskettavuus voi joissakin tapauksissa antaa mahdollisuuden päästä eroon viidestä lisäyksestä testaamalla, pysyykö kumpikaan myös alhaisemmalla (vai ei) etsivät juurta. Jos näin on, on parempi jatkaa algoritmia alkaen kuin .
Esimerkiksi haluamme pyöristää lähellä . Tämän tarkkuuden kunnioittamiseksi meidän on etsittävä juuret . Riittää sitten lopullisen juuren jakaminen .
Kuten sanoen , meillä on: . Mutta ollessa lähempänä kuin , on lähempänä kuin .
Sen sijaan, että alkaa pyyhkäisemään ja voimme, tässä tapauksessa, prosessin aloittamiseksi : . Se oli hyvä, kuten odotettiin .
Algoritmi (joka on yksityiskohtainen seuraavassa esimerkissä) tuo meidät vähitellen, johon lisäämme , mikä on lähempänä kuin . Päättelemme: on suljettava.
Esimerkki: √ 152,2756 = 12,34 peräkkäisten parittomien lukumäärien menetelmälläNeliöjuuri 1,522,756 antaa kertoimelle 100 halutun neliöjuuren. Tämä luku on leikattu 2-numeroisiksi viipaleiksi 1 52 27 56. Ensimmäistä ryhmää lähinnä oleva neliö on 1.
Skannataan sitten neliötaulukko 10: stä lähestymään 152
ei | n² | 2n + 1 = (n + 1) 2 - n2 |
---|---|---|
10 | 100 | 21 |
11 | 100 + 21 = 121 | 23 |
12 | 121 + 23 = 144 | 25 |
25 lisääminen johtaisi ylittämään 152. Siksi siirrymme seuraavaan kymmeneen käymällä neliötaulukon läpi 120: stä lähestyessä 15227.
ei | n² | 2n + 1 = (n + 1) 2 - n2 |
---|---|---|
120 | 14400 | 241 |
121 | 14400 + 241 = 14641 | 243 |
122 | 14641 + 243 = 14884 | 245 |
123 | 14884 + 245 = 15129 | 247 |
247: n lisääminen johtaisi 15227: n ylitykseen. Siksi siirrymme seuraavaan kymmeneen selaamalla neliötaulukkoa vuodelta 1230 lähestyessä 1522756.
ei | n² | 2n + 1 = (n + 1) 2 - n2 |
---|---|---|
1230 | 1512900 | 2461 |
1231 | 1512900 + 2461 = 1515361 | 2463 |
1232 | 1515361 + 2463 = 1517824 | 2465 |
1233 | 1517824 + 2465 = 1520289 | 2467 |
1234 | 1520289 + 2467 = 1522756 |
1522756 on siis neliön 1234 ja 152.2756 neliön 12.34 neliö
Tätä samaa periaatetta käytetään neliöjuuren uuttamisessa tippumismenetelmällä .
Tällä hyvin yksinkertaisella menetelmällä on erityispiirre, kun käytetään vain hyvin yksinkertaisia operaatioita: summaus, vähennys ja 0: n summa. Harkitse sekvenssejä a ja b, jotka määritellään
Siten numeroiden määrä lähestyy yhä enemmän numeroiden lukumäärää . Huomaa, että se on kokonaisluku (yhä suurempi), joten se ei ole suuntaus kohti, vaan vain sen numerot desimaaliesityksessä.
Esimerkki: √ 3 ≈ 1,732 summaamalla ja vähentämällä,
Kommentit | |||
---|---|---|---|
0 | 15 | 5 | Voimme vähentää |
1 | 10 | 1 5 | Emme voi enää vähentää |
2 | 1000 | 105 | Voimme vähentää |
3 | 895 | 115 | Voimme vähentää |
4 | 780 | 125 | Voimme vähentää |
5 | 655 | 135 | Voimme vähentää |
6 | 520 | 145 | Voimme vähentää |
7 | 375 | 155 | Voimme vähentää |
8 | 220 | 165 | Voimme vähentää |
9 | 55 | 17 5 | Emme voi enää vähentää |
10 | 5500 | 1705 | Voimme vähentää |
11 | 3795 | 1715 | Voimme vähentää |
12 | 2080 | 1725 | Voimme vähentää |
13 | 355 | 173 5 | Emme voi enää vähentää |
14 | 35500 | 17305 | Voimme vähentää |
15 | 18195 | 17315 | Voimme vähentää |
16 | 880 | 1732 5 | emme voi enää vähentää |
... |
Jos sen sijaan, että 5 m , otamme -lyhennyksiin välein kaksi numeroa ja lisäämisen sijaan kaksi nollaa ja n , me laskemme seuraavat lisäykset, me päätyä muunnos 5 pisaran menetelmää. Pisaralta.
Jatkuva osa irrationaalisen on sekvenssi sen "optimaalinen" likiarvoja fraktioilla, toisin sanoen, että jos p / q on yksi arvoista tämän sekvenssin, niin ei osa / b , jossa b < q ei lähestyy tarkemmin todellisuutta. Tietyssä tapauksessa neliön juuret, yksi laskee suhteellisen yksinkertaisesti tämän sekvenssin, sekä alasekvenssi , joka vastaa tiettyä tapauksessa menetelmä Heron .
On myös mahdollista edetä dikotomialla edellyttäen, että halutulle neliöjuurelle on olemassa kehys. Tätä varten voimme käyttää neliöjuuren etsimän numeron lukumäärää. Tällä juurella olisi puolet niin monta numeroa. Jos luvulla on 1024 numeroa, sen neliöjuuren välillä on 511 - 513. Voimme myös ensin käyttää aikaisempia menetelmiä saadaksesi ensimmäisen likimääräisen neliöjuuren arvon, ennen kuin jatkat kaksisuuntaisuuteen.
Dikotomialgoritmi on seuraava. Se välttää jakamisten suorittamisen (muu kuin jakaminen 2: lla, joka on vain rekisterisiirtymä, jos numerot ovat binäärikoodattuja. Tämä jako on merkitty alla olevaan shr 1).
function Racine_64(C: int64): int64; var A, B, D, D2: int64; begin A := borne basse; B := borne haute; repeat D := (A + B) shr 1; D2 := D * D; ⇐ on élève au carré avant de tester if D2 > C then A := D - 1 else if C > D2 then B := D + 1 else Result := A; until B > A; end;Samaa menetelmää sovelletaan n: nteen juuriin korvaamalla D2 = D * D: n laskenta D ^ n: n laskennalla.
Dikotomimenetelmällä on kuitenkin hitaampi lähentymisnopeus kuin Heronin menetelmän iteroinnilla.
Yritämme ratkaista yhtälö . Voimme sitten erottaa kolme tapausta:
Jos on olemassa ratkaisu, eli jos on modulo neliönjäännös , yksi on tehokkaita algoritmeja löytää sen kahdessa ensimmäisessä tapauksessa. Jos on yhdistetty luku, tällä hetkellä meillä on vain tehokas algoritmi, jos tekijöihinjako ja on tunnettua. Lisäksi voimme osoittaa, että jos olisi ollut tehokas algoritmi neliöjuuren laskemiseksi ilman tekijöiden jakamista , tätä algoritmia voitaisiin käyttää tehokkaan tekijäalgoritmin saamiseen . Siksi emme voi laskea tehokkaasti modulo-neliöjuuria, ennen kuin voimme tehokkaasti laskea minkä tahansa kokonaisluvun ja päinvastoin.