Enrere Mòdul 3
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Resum teòric Exercicis
Pràctica d'ampliació

 
Un algoritme molt eficient pel càlcul de l'arrel quadrada

En aquesta pràctica veurem una altra aplicació curiosa de la iteració. Es tracta d'un algorisme molt eficient per al càlcul de l'arrel quadrada.

 

Desenvolupament de la pràctica

Creeu un nou arxiu del tipus C anomenat m3p07.c i escriviu el següent codi:

//m3p08.c - Càlcul de l'arrel quadrada -

#include<stdio.h>

int main(){

   double llavor;
   double a;
   int ct, iter;

   system("clear");

   printf("a= ");

   scanf("%lf",&a);
   printf("\nllavor= "); scanf("%lf",&llavor);
   printf("\nnombre d'iteracions"); scanf ("%d",&iter);

   for(ct=0;ct<=iter;ct++){
       llavor=a/2/llavor+llavor/2;
       printf("\n%d: %.20lf",ct,llavor);
   }
return 0;
}

 

Captura de l'execució del programa.

 

 


 

Explicació del programa

Tots nosaltres hem après a l'escola un algorisme per al càlcul de l'arrel quadrada d'un número. L'enorme difusió de calculadores que fan aquest càlcul amb la pulsació d'una tecla ha fet que gairebé tots ens haguem oblidat de com es feia a mà una arrel quadrada. No recordarem aquest algorisme, només assenyalarem que per trobar un decimal de l'arrel quadrada s'havia de fer un munt d'operacions: multiplicar per dos, dividir, multiplicar, restar, etc. Aquí presentarem un altre algorisme molt més eficient per al càlcul de l'arrel quadrada. Aquest algorisme és un algorisme iteratiu que convergeix rapidísimament.

Si es vol calcular l'arrel quadrada d'un nombre a partirem d'una estimació inicial x0. Si anomenem e a l'error comès, es té:  

a = (x0+e)2 = x02+2x0e+e2. 

Si x0 no és 0 podem expressar l'error de la següent forma:

Si la nostra estimació inicial era suficientment bona, es pot suposar que:

Amb el que quedarà:

Per tant, la nova aproximació serà:

i en general:

Es pot provar, amb consideracions que no exposarem,  que el procés iteratiu anterior convergeix sempre que es verifiqui que:

Una bona elecció d'x0 pot ser l'aproximació entera per excés de l'arrel d'a. Per exemple, si a=2, un bon valor inicial és x0=2.

El que és realment sorprenent és que amb només 3 o 4 vegades, aquest procés iteratiu es pot trobar l'arrel quadrada amb tota la precisió que els nombres de tipus double poden tenir. 

Tot el càlcul es fa en aquest bucle: 

 
for(ct=0;ct<=iter;ct++){
        llavor=a/2/llavor+llavor/2;
        printf("\n%d: %.20lf",ct,llavor);
    }

que implementa la fórmula iterativa:

iter és el nombre d'iteracions que es farà. No fa falta introduir valors alts per aquesta variable. En la majoria dels casos un nombre entre 3 i 5 donarà una precisió suficient (espectacular en molts casos) per calcular qualsevol arrel quadrada.

A més del valor d'a i el nombre d'iteracions iter és necessari introduir la llavor o estimació inicial.