Algoritmes d'arrel quadrada

Els algoritmes d'arrel quadrada calculen l'arrel quadrada no negativa ${\sqrt {S}}$ d'un nombre real positiu $S$. Com que totes les arrels quadrades dels nombres naturals, excepte les dels quadrats perfectes, són irracionals, les arrels quadrades normalment només es poden calcular amb una precisió finita: aquests algoritmes solen construir una sèrie d'aproximacions cada cop més precises.

La majoria dels mètodes de càlcul d'arrel quadrada són iteratius: després de triar una estimació inicial adequada de ${\sqrt {S}}$, es realitza un refinament iteratiu fins que es compleix algun criteri de terminació. Un esquema de refinament és el mètode d'Heron, un cas especial del mètode de Newton. Si la divisió és molt més costosa que la multiplicació, pot ser preferible calcular l'arrel quadrada inversa.

Hi ha altres mètodes disponibles per calcular l'arrel quadrada dígit a dígit, o utilitzant sèries de Taylor. Les aproximacions racionals d'arrels quadrades es poden calcular utilitzant expansions de fraccions contínues.

El mètode emprat depèn de la precisió necessària, i de les eines i la potència computacional disponibles. Els mètodes es poden classificar aproximadament com els que són adequats per al càlcul mental, els que normalment requereixen com a mínim paper i llapis, i els que s'implementen com a programes per ser executats en un ordinador electrònic digital o un altre dispositiu informàtic. Els algoritmes poden tenir en compte la convergència (quantes iteracions es requereixen per aconseguir una precisió especificada), la complexitat computacional de les operacions individuals (és a dir, la divisió) o iteracions, i la propagació d'errors (la precisió del resultat final).

Alguns mètodes, com la divisió sintètica amb llapis i paper i l'expansió en sèrie, no requereixen un valor inicial. En algunes aplicacions, es requereix una arrel quadrada entera, que és l'arrel quadrada arrodonida o truncada a l'enter més proper (en aquest cas es pot emprar un procediment modificat).

Història

Els procediments per trobar arrels quadrades (en particular l'arrel quadrada de 2) es coneixen des d'almenys el període de l'antiga Babilònia al segle XVII aC. Els matemàtics babilonis calculaven l'arrel quadrada de 2 a tres "dígits" sexagesimals després de l'1, però no se sap exactament com. Sabien com aproximar una hipotenusa utilitzant$${\sqrt {a^{2}+b^{2}}}\approx a+{\frac {b^{2}}{2a}}$$ (donant per exemple ${\frac {41}{60}}+{\frac {15}{3600}}$ per a la diagonal d'una porta l'alçada de la qual és ${\frac {40}{60}}$ barres i l'amplada de les quals és ${\frac {10}{60}}$ barres) i poden haver utilitzat un enfocament similar per trobar l'aproximació de ${\sqrt {2}}.$

El mètode d'Heró, del segle I a Egipte, va ser el primer algorisme comprovable per calcular l'arrel quadrada.

Els mètodes analítics moderns van començar a desenvolupar-se després de la introducció del sistema de numeració aràbiga a l'Europa occidental a principis del Renaixement.

Avui dia, gairebé tots els dispositius informàtics tenen una funció d'arrel quadrada ràpida i precisa, ja sigui com a construcció d'un llenguatge de programació, una funció intrínseca o de biblioteca del compilador, o com a operador de maquinari, basada en un dels procediments descrits.

Estimació inicial

Molts algoritmes iteratius d'arrel quadrada requereixen un valor inicial de llavor. La llavor ha de ser un nombre positiu diferent de zero; ha d'estar entre 1 i $S$, el nombre del qual es vol obtenir l'arrel quadrada, perquè l'arrel quadrada ha d'estar dins d'aquest interval. Si la llavor és lluny de l'arrel, l'algoritme requerirà més iteracions. Si s'inicialitza amb $x_{0}=1$ (o $S$ ), aleshores aproximadament ${\tfrac {1}{2}}\vert \log _{2}S\vert$ es malgastaran iteracions només per obtenir l'ordre de magnitud de l'arrel. Per tant, és útil tenir una estimació aproximada, que pot tenir una precisió limitada però és fàcil de calcular. En general, com millor sigui l'estimació inicial, més ràpida serà la convergència. Per al mètode de Newton, una llavor una mica més gran que l'arrel convergirà lleugerament més ràpid que una llavor una mica més petita que l'arrel.

En general, una estimació es fa segons un interval arbitrari que se sap que conté l'arrel (com ara $[x_{0},S/x_{0}]$). L'estimació és un valor específic d'una aproximació funcional a $f(x)={\sqrt {x}}$ durant l'interval. Obtenir una millor estimació implica obtenir límits més ajustats a l'interval o trobar una millor aproximació funcional per a $f(x)$. Això últim normalment significa utilitzar un polinomi d'ordre superior en l'aproximació, tot i que no totes les aproximacions són polinòmiques. Els mètodes d'estimació habituals inclouen l'escalar, el lineal, l'hiperbòlic i el logarítmic. La base decimal s'utilitza normalment per a l'estimació mental o amb llapis i paper. Una base binària és més adequada per a estimacions informàtiques. En les estimacions, l'exponent i la mantissa se solen tractar per separat, ja que el nombre s'expressaria en notació científica.

Mètode d'Heró

Gràfics semilogarítmics que comparen la velocitat de convergència del mètode d'Heron per trobar l'arrel quadrada de 100 per a diferents aproximacions inicials. Les aproximacions negatives convergeixen a l'arrel negativa, les positives a l'arrel positiva. Tingueu en compte que els valors més propers a l'arrel convergeixen més ràpidament i totes les aproximacions són sobreestimacions. Al fitxer SVG, passeu el cursor per sobre d'un gràfic per mostrar-ne els punts.

El primer algorisme explícit per aproximar $\ {\sqrt {S~}}\$ es coneix com a mètode d'Heró, en honor al matemàtic grec del segle I , Heró d'Alexandria, que va descriure el mètode a la seva obra *Mètrica* de l'any 60 dC. Aquest mètode també s'anomena mètode babilònic (no s'ha de confondre amb el mètode babilònic per aproximar hipotenuses), tot i que no hi ha proves que el mètode fos conegut pels babilonis.

Donat un nombre real positiu $S$, sigui x₀ > 0 qualsevol estimació inicial positiva. El mètode d'Heron consisteix a calcular iterativament $$x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),$$ fins que s'aconsegueixi la precisió desitjada. La seqüència $\ {\bigl (}\ x_{0},\ x_{1},\ x_{2},\ x_{3},\ \ldots \ {\bigr )}\$ definit per aquesta equació convergeix a $\ \lim _{n\to \infty }x_{n}={\sqrt {S~}}~.$

Això és equivalent a utilitzar el mètode de Newton per resoldre $x^{2}-S=0$. Aquest algorisme és quadràticament convergent: el nombre de dígits correctes de $x_{n}$ aproximadament es duplica amb cada iteració.

Mètode Bakhshali

Aquest mètode per trobar una aproximació a una arrel quadrada es va descriure en un antic manuscrit indi, anomenat manuscrit Bakhshali. És algebraicament equivalent a dues iteracions del mètode d'Heron i, per tant, quàrticament convergent, és a dir, que el nombre de dígits correctes de l'aproximació es quadruplica aproximadament amb cada iteració. La presentació original, utilitzant la notació moderna, és la següent: Per calcular ${\sqrt {S}}$, deixem $x_{0}^{2}$ sigui l'aproximació inicial de $S$. Aleshores, itera successivament com: $${\begin{aligned}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\x_{n+1}&=x_{n}+a_{n},\\x_{n+2}&=x_{n+1}-{\frac {a_{n}^{2}}{2x_{n+1}}}.\end{aligned}}$$

Els valors $x_{n+1}$ i $x_{n+2}$ són exactament iguals als calculats pel mètode d'Heron. Per veure això, el segon pas del mètode d'Heron calcularia $$x_{n+2}={\frac {x_{n+1}^{2}+S}{2x_{n+1}}}=x_{n+1}+{\frac {S-x_{n+1}^{2}}{2x_{n+1}}}$$ i podem utilitzar les definicions de $x_{n+1}$ i $a_{n}$ per reordenar el numerador en: $${\begin{aligned}S-x_{n+1}^{2}&=S-(x_{n}+a_{n})^{2}\\&=S-x_{n}^{2}-2x_{n}a_{n}-a_{n}^{2}\\&=S-x_{n}^{2}-(S-x_{n}^{2})-a_{n}^{2}\\&=-a_{n}^{2}.\end{aligned}}$$Això es pot utilitzar per construir una aproximació racional de l'arrel quadrada començant amb un nombre enter. Si

$x_{0}=N$ és un enter escollit de manera que $N^{2}$ és a prop de $S$, i $d=S-N^{2}$ és la diferència el valor absolut de la qual es minimitza, aleshores la primera iteració es pot escriure com: $${\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)}}.$$

Càlcul dígit a dígit

Aquest és un mètode per trobar cada dígit de l'arrel quadrada d'una seqüència. Aquest mètode es basa en el teorema del binomi i bàsicament en un algorisme invers que resol $(x+y)^{2}=x^{2}+2xy+y^{2}$. És més lent que el mètode babilònic, però té diversos avantatges:

• Pot ser més fàcil per a càlculs manuals.
• Se sap que tots els dígits de l'arrel trobats són correctes, és a dir, no cal canviar-los més tard.
• Si l'arrel quadrada té una expansió que acaba, l'algoritme acaba després de trobar l'últim dígit. Per tant, es pot utilitzar per comprovar si un nombre enter donat és un nombre quadrat.
• L'algoritme funciona per a qualsevol base i, naturalment, la manera com procedeix depèn de la base escollida.

Els desavantatges són:

• Es torna inmanejable per a arrels més altes.
• No tolera conjectures inexactes ni subcàlculs; aquests errors fan que tots els dígits següents del resultat siguin incorrectes, a diferència del mètode de Newton, que autocorregeix qualsevol error d'aproximació.
• Tot i que el càlcul dígit a dígit és prou eficient sobre el paper, és massa car per a implementacions de programari. Cada iteració implica nombres més grans, que requereixen més memòria, però només avança la resposta un dígit correcte. Per tant, l'algoritme triga més temps per cada dígit addicional.

Els ossos de Napier inclouen una ajuda per a l'execució d'aquest algorisme. L'algoritme d'arrel n desplaçadora és una generalització d'aquest mètode.

Identitat exponencial

Les calculadores de butxaca solen implementar bones rutines per calcular la funció exponencial i el logaritme natural, i després calculen l'arrel quadrada de S utilitzant la identitat trobada mitjançant les propietats dels logaritmes ( $\ln x^{n}=n\ln x$ ) i exponencials ($e^{\ln x}=x$) : $${\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.$$ El denominador de la fracció correspon a l'arrel enèsima. En el cas anterior el denominador és 2, per tant, l'equació especifica que s'ha de trobar l'arrel quadrada. La mateixa identitat s'utilitza quan es calculen arrels quadrades amb taules de logaritmes o regles de càlcul.

Un mètode iteratiu de dues variables

Aquest mètode és aplicable per trobar l'arrel quadrada de $0<S<3\,\!$ i convergeix millor per a $S\approx 1$. Tanmateix, això no és una limitació real per a un càlcul basat en ordinador, ja que en representacions de coma flotant i de coma fixa en base 2, és trivial multiplicar $S\,\!$ per una potència entera de 4, i per tant ${\sqrt {S}}$ per la potència corresponent de 2, canviant l'exponent o desplaçant-lo, respectivament. Per tant, $S\,\!$ es pot traslladar a la gamma ${\textstyle {\tfrac {1}{2}}\leq S<2}$. A més, el mètode següent no empra divisions generals, sinó només sumes, restes, multiplicacions i divisions per potències de dos, que també són trivials d'implementar. Un desavantatge del mètode és que els errors numèrics s'acumulen, a diferència dels mètodes iteratius d'una sola variable com el babilònic.

Mètodes iteratius per a arrels quadrades recíproques

Els següents són mètodes iteratius per trobar l'arrel quadrada recíproca de S que és $1/{\sqrt {S}}$. Un cop s'hagi trobat, trobeu ${\sqrt {S}}$ per multiplicació simple: ${\sqrt {S}}=S\cdot (1/{\sqrt {S}})$. Aquestes iteracions només impliquen multiplicació i no divisió. Per tant, són més ràpids que el mètode babilònic. No obstant això, no són estables. Si el valor inicial no és proper a l'arrel quadrada recíproca, les iteracions divergiran en lloc de convergir-hi. Per tant, pot ser avantatjós realitzar una iteració del mètode babilònic sobre una estimació aproximada abans de començar a aplicar aquests mètodes.

Sèrie de Taylor

Si N és una aproximació de ${\sqrt {S}}$, es pot trobar una millor aproximació utilitzant la sèrie de Taylor de la funció arrel quadrada: $${\sqrt {N^{2}+d}}=N\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!}{(1-2n)n!^{2}4^{n}}}{\frac {d^{n}}{N^{2n}}}=N\left(1+{\frac {d}{2N^{2}}}-{\frac {d^{2}}{8N^{4}}}+{\frac {d^{3}}{16N^{6}}}-{\frac {5d^{4}}{128N^{8}}}+\cdots \right)$$

Com a mètode iteratiu, l'ordre de convergència és igual al nombre de termes utilitzats. Amb dos termes, és idèntic al mètode babilònic. Amb tres termes, cada iteració requereix gairebé tantes operacions com l'aproximació de Bakhshali, però convergeix més lentament. Per tant, aquesta no és una manera de càlcul particularment eficient. Per maximitzar la taxa de convergència, triem N de manera que ${\frac {|d|}{N^{2}}}\,$ és tan petit com sigui possible.

Expansió de fraccions contínua

La representació de fracció contínua d'un nombre real es pot utilitzar en lloc de la seva expansió decimal o binària, i aquesta representació té la propietat que l'arrel quadrada de qualsevol nombre racional (que no és ja un quadrat perfecte) té una expansió periòdica i repetitiva, similar a com els nombres racionals tenen expansions repetitives en el sistema de notació decimal.

Aproximacions que depenen de la representació en coma flotant

Un nombre es representa en format de coma flotant com a $m\times b^{p}$ que també s'anomena notació científica. La seva arrel quadrada és ${\sqrt {m}}\times b^{p/2}$ i fórmules similars s'aplicarien per a arrels cúbiques i logaritmes. A primera vista, això no suposa cap millora en la simplicitat, però suposem que només cal una aproximació: aleshores només $b^{p/2}$ és bo fins a un ordre de magnitud. A continuació, cal reconèixer que algunes potències, p, seran senars, per tant, per a 3141,59 = 3,14159 ×10³ en lloc de tractar amb potències fraccionàries de la base, cal multiplicar la mantissa per la base i restar-ne una a la potència per fer-la parell. La representació ajustada esdevindrà l'equivalent de 31,4159 ×10² de manera que l'arrel quadrada serà √31.4159 ×10¹