Duda calcular raiz cuadrada sin sqrt C++

Iniciado por seryioo, 21 Julio 2015, 11:25 AM

0 Miembros y 1 Visitante están viendo este tema.

seryioo

Buenas, soy estudiante de Ingeniería de primer año. Si, estoy estudiando en verano para recuperar Programación.

La duda es que tengo un problema en el que una de las cosas que se me pide es calcular una raiz cuadrada sin usar sqrt.

Este es mi codigo, estaba comprobando lo que pasaba dentro del bucle while, ya que en la ejecución le de el valor que le de a num cae siempre en bucle infinito de ceros.
Mi idea era que el bucle se ejecutase mientras num-res>=0,0001 (res= resultado de la raiz cuadrada aproximandonos por tanteo) y que por tanto, saliera del bucle cuando tuviera un res valido aproximado al valor real de la raiz cuadrada de num.


int main(){
   int num;
   double res=0.000;
   cin>>num;

   while((num-res)>=0,001){
       res+=0,001;
       cout<<res<<endl;
}


return 0;
}



ivancea96


user-marcos

Aquí tienes una solución como siempre en c++ hay n posibles.

Código (cpp) [Seleccionar]

#include <iostream>
using namespace std;

int main(){
   int num;
   double res = 0.00;
   const float INCREMENTO = 0.00001;
   cin >> num;
   
   while(res += INCREMENTO, res*res < num)
     continue;
   
   cout << (res += -INCREMENTO);//hay que corregir un incremento

return 0;
}

seryioo

#3
Señores, gracias olvidadLo... tenia bien la condicion del while, la cambié y la puse mal, tal y como os he copiado...

El gran error de noob que he cometido ha sido poner comas en los numeros en vez de puntos, por eso no funcionaba....


Problema resuelto, gracias!

Pongo el código que he usado yo:


#include <iostream>
using namespace std;


int main(){
    int num;
    double res=0.000;
    cin>>num;


    while((num-res*res)>=0.001){
        res+=0.001;
        cout<<res<<endl;
}


return 0;
}


do-while

#4
¡Buenas!

Ese algoritmo tiene bastantes pegas, si el número cuya raíz cuadrada quieres calcular es menor que 10-6 te devolverá el mismo número, luego dependiendo de la precisión que utilices no estarás calculando la raíz cuadrada de nada, además ten en cuenta que si el número es de orden de k·10n, en m iteraciones tendrás una aproximacion m·10-3 y la comparación seria: k·10n - m210-6 >=10-3, luego para llegar a una aproximación con un error menor que el indicado tendrías que realizar (k·10n+6 - 103)1/2 operaciones (quédate con la parte entera mas uno), por poner un ejemplo, para calcular la raíz cuadrada de 104 tendrías que realizar unas 105= 100.000 iteraciones.

Ya que estás estudiando ingeniería puedes intentar usar un poco ese cerebro que Dios te ha dado y utilizar algo más efectivo, como el teorema de Bolzano (no entro en otros métodos numéricos, ya que en cualquier curso básico de análisis se estudia Bolzano, y con esto es suficiente), que deberías conocer, pero por si no te acuerdas aquí te dejo el enunciado:

Si una función continua sobre un intervalo J tiene signos opuestos evaluada en sus extremos, entonces existe al menos un punto en J cuya imagen es cero.

Es decir, si f:J=[a,b]---->R cumple que f(a)·f(b) < 0 => existe un número real c, a < c < b, tal que f(c)=0.

En este caso tienes la función f(x)=a-x2, ya que si a-x2=0 entonces x=sqrt(a).

Así, si a = 1 ó a = 0, ya tienes la solución. Si a > 1 a > squrt(a) > 1 y tendrás que buscar la solución en el intervalo inicial [1,a], y si 0 < a < 1 a < sqrt(a) < 1 y el intervalo inicial será [a,1],

Sea cual sea el intervalo inicial lo llamaremos [a0,b0] y sabemos que f(a0)·f(b0) < 0. así que escogemos m0=(a0+b0)/2

Si f(m0) <= error_aceptado ya tenemos la solución buscada, sino, estaremos en uno de los dos siguientes casos:

- f(a0)·f(m0) < 0: En este caso hacemos a1=a0, b1=m0

-f(m0)·f(b0) < 0: Y hacemos a1=m0, b1=b0

Y aplicamos el proceso anterior al nuevo intervalo [a1,b1]

Tras el paso n, la longitud del intervalo [an,bn] será (b0-a0)·2-n, así que en el peor de los casos tendremos que llegar a que esta longitud sea menor que el error aceptado, y en este caso el número de iteraciones será log(2)-1·log((b0-a0)/error)

si a=104 y error=10-3 entonces log(2)-1·log((b0-a0)/error)=23,2533... y como máximo en 24 iteraciones llegaremos al valor que buscamos, lo que es una mejora considerable con respecto al algoritmo inicial.

Si el error utilizado es muy pequeño puede darse el caso de que la longitud del intervalo no pueda reducirse debido a que la distancia del punto medio con respecto a cualquiera de los extremos sea menor que el incremento mínimo que ofrece un número de coma flotante. También tendrás que detectar este caso, es decir, tendrás que comprobar que el nuevo punto medio sea distinto del de la iteración anterior, y si fuesen iguales este será la mejor aproximación que puedas obtener con el error que hayas elegido.

Otra cosa más. La derivada f'(x) = -2x toma valores positivos para valores negativos de x y valores negativos para valores positivos de x, pero teniendo en cuenta que la raíz cuadrada de un número negativo no es un número real, descartamos directamente los valores negativos de a, luego los valores de la variable x serán siempre positivos y así f siempre será decreciente en los intervalos considerados, por lo que la raíz será única y no llegaremos a bucles infinitos salvo en el caso descrito en el párrafo anterior.

¡Saludos!
- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!