raices - raiz cuadrada en c++ codeblocks

¿Encontrar raíz cuadrada sin usar la función sqrt?

Question

Estaba descubriendo el algoritmo para averiguar la raíz cuadrada sin usar la función sqrt y luego intenté poner en programación. Terminé con este código de trabajo en C ++

    #include <iostream>
    using namespace std;

    double SqrtNumber(double num)
    {
             double lower_bound=0; 
             double upper_bound=num;
             double temp=0;                    /* ek edited this line */

             int nCount = 50;

        while(nCount != 0)
        {
               temp=(lower_bound+upper_bound)/2;
               if(temp*temp==num) 
               {
                       return temp;
               }
               else if(temp*temp > num)

               {
                       upper_bound = temp;
               }
               else
               {
                       lower_bound = temp;
               }
        nCount--;
     }
        return temp;
     }

     int main()
     {
     double num;
     cout<<"Enter the number/n";
     cin>>num;

     if(num < 0)
     {
     cout<<"Error: Negative number!";
     return 0;
     }

     cout<<"Square roots are: +"<<sqrtnum(num) and <<" and -"<<sqrtnum(num);
     return 0;
     } 

Ahora el problema es inicializar el número de iteraciones nCount en la declaración (aquí es 50). Por ejemplo, para averiguar la raíz cuadrada de 36 se necesitan 22 iteraciones, por lo que no hay problema, mientras que encontrar la raíz cuadrada de 15625 requiere más de 50 iteraciones, por lo que devolvería el valor de temp después de 50 iteraciones. Por favor, dar una solución para esto.

Answer 1

¿Por qué no tratar de usar el método babilónico para encontrar una raíz cuadrada?

Aquí está mi código para ello:

double sqrt(double number)
{
    double error = 0.00001; //define the precision of your result
    double s = number;

    while ((s - number / s) > error) //loop until precision satisfied 
    {
        s = (s + number / s) / 2;
    }
    return s;
}

¡Buena suerte!

Answer 2

Aquí hay un código impresionante para encontrar sqrt e incluso más rápido que la función sqrt original.

float InvSqrt (float x) 
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f375a86 - (i>>1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    x = x*(1.5f - xhalf*x*x);
    x = x*(1.5f - xhalf*x*x);
    x=1/x;
    return x;
}

Answer 3

Como encontré, esta pregunta es antigua y tiene muchas respuestas, pero tengo una respuesta que es simple y funciona muy bien.

#define EPSILON 0.0000001 // least minimum value for comparison
double SquareRoot(double _val) {
    double low = 0; 
    double high = _val;
    double mid = 0; 

    while (high - low > EPSILON) {
            mid = low + (high - low) / 2; // finding mid value
            if (mid*mid > _val) {
                high = mid;
            } else {
                low = mid;
            }    
    }   
    return mid;
}

Espero que sea de utilidad para futuros usuarios.

Answer 4

Después de ver las respuestas anteriores, espero que esto ayude a resolver cualquier ambigüedad. En caso de que las similitudes en las soluciones anteriores y mi solución sean ilusorias, o este método de resolución de raíces no esté claro, también he hecho un gráfico que se puede encontrar here .

Esta es una función de raíz de trabajo capaz de resolver cualquier raíz nth

(por defecto es raíz cuadrada por el bien de esta pregunta )

#include <cmath> 
// for "pow" function

double sqrt(double A, double root = 2) {
    const double e = 2.71828182846;
    return pow(e,(pow(10.0,9.0)/root)*(1.0-(pow(A,-pow(10.0,-9.0)))));
}

Explicación :

here

Esto funciona a través de series de Taylor, propiedades logarítmicas y un poco de álgebra.

Tomar como ejemplo:

log A = N
   x

* Nota : para la raíz cuadrada, N = 2; para cualquier otra raíz solo necesitas cambiar una variable, N.

1) Cambie la base, convierta la función de registro ''x'' de base al registro natural,

log A   =>   ln(A)/ln(x) = N
   x

2) Reorganizar para aislar ln (x), y finalmente solo ''x'',

ln(A)/N = ln(x)

3) Establecer ambos lados como exponentes de ''e'',

e^(ln(A)/N) = e^(ln(x))  >~{ e^ln(x) == x }~>  e^(ln(A)/N) = x

4) La serie de Taylor representa "ln" como una serie infinita,

ln(x) = (k=1)Sigma: (1/k)(-1^(k+1))(k-1)^n

           <~~~ expanded ~~~>

[(x-1)] - [(1/2)(x-1)^2] + [(1/3)(x-1)^3] - [(1/4)(x-1)^4] + . . .

* Nota : Continuar la serie para mayor precisión. Para mayor brevedad, 10 ^ 9 se utiliza en mi función que expresa la convergencia en serie para el registro natural con aproximadamente 7 dígitos, o el lugar de 10 millonésimas, para mayor precisión.

ln(x) = 10^9(1-x^(-10^(-9)))

5) Ahora, simplemente conecte esta ecuación para el registro natural en la ecuación simplificada obtenida en el paso 3.

e^[((10^9)/N)(1-A^(-10^-9)] = nth-root of (A)

6) Esta implementación puede parecer una exageración; sin embargo, su propósito es demostrar cómo puede resolver raíces sin tener que adivinar y verificar. Además, le permitiría reemplazar la función pow de la biblioteca cmath con su propia función pow:

double power(double base, double exponent) {
    if (exponent == 0) return 1;
    int wholeInt = (int)exponent;
    double decimal = exponent - (double)wholeInt;
    if (decimal) {
        int powerInv = 1/decimal;
        if (!wholeInt) return root(base,powerInv);
        else return power(root(base,powerInv),wholeInt,true);
    }
    return power(base, exponent, true);
}

double power(double base, int exponent, bool flag) {
    if (exponent < 0) return 1/power(base,-exponent,true);
    if (exponent > 0) return base * power(base,exponent-1,true);
    else return 1;
}

int root(int A, int root) {
    return power(E,(1000000000000/root)*(1-(power(A,-0.000000000001))));
}

Answer 5

Elimine su nCount completo (ya que hay algunas raíces para las cuales este algoritmo tomará muchas iteraciones).

double SqrtNumber(double num)
{
    double lower_bound=0; 
    double upper_bound=num;
    double temp=0;

    while(fabs(num - (temp * temp)) > SOME_SMALL_VALUE)
    {
           temp = (lower_bound+upper_bound)/2;
           if (temp*temp >= num)
           {
                   upper_bound = temp;
           }
           else
           {
                   lower_bound = temp;
           }
    }
    return temp;
 }

Answer 6

Este es un enfoque muy simple pero inseguro para encontrar la raíz cuadrada de un número. Inseguro porque solo funciona con números naturales, donde se sabe que la base, respectivamente, el exponente son números naturales. Tuve que usarlo para una tarea en la que no se me permitió usar la biblioteca #include <cmath> , ni se me permitió usar punteros.

potencia = base ^ exponente

// FUNCTION: square-root
int sqrt(int x)
{
    int quotient = 0;
    int i = 0;

    bool resultfound = false;
    while (resultfound == false) {
        if (i*i == x) {
          quotient = i;
          resultfound = true;
        }
        i++;
    }
    return quotient;
}

Answer 7

Este es un enfoque recursivo muy simple.

double mySqrt(double v, double test) {
    if (abs(test * test - v) < 0.0001) {
        return test;
    }

    double highOrLow = v / test;
    return mySqrt(v, (test + highOrLow) / 2.0);
}
double mySqrt(double v) {
    return mySqrt(v, v/2.0);
}

Answer 8

Hay un algoritmo mejor, que necesita como máximo 6 iteraciones para converger a la máxima precisión para los números dobles:

#include <math.h>

double sqrt(double x) {
    if (x <= 0)
        return 0;       // if negative number throw an exception?
    int exp = 0;
    x = frexp(x, &exp); // extract binary exponent from x
    if (exp & 1) {      // we want exponent to be even
        exp--;
        x *= 2;
    }
    double y = (1+x)/2; // first approximation
    double z = 0;
    while (y != z) {    // yes, we CAN compare doubles here!
        z = y;
        y = (y + x/y) / 2;
    }
    return ldexp(y, exp/2); // multiply answer by 2^(exp/2)
}

El algoritmo comienza con 1 como primera aproximación para el valor de la raíz cuadrada. Luego, en cada paso, mejora la siguiente aproximación tomando el promedio entre el valor actual y y x/y . Si y = sqrt(x) , será el mismo. Si y > sqrt(x) , entonces x/y < sqrt(x) aproximadamente la misma cantidad. En otras palabras, convergerá muy rápido.

ACTUALIZACIÓN : para acelerar la convergencia en números muy grandes o muy pequeños, la función sqrt() modificada extrae el exponente binario y calcula la raíz cuadrada del número en el rango [1, 4) . Ahora necesita frexp() de <math.h> para obtener un exponente binario, pero es posible obtener este exponente extrayendo bits del formato de número IEEE-754 sin usar frexp() .

Answer 9

Si necesita encontrar una raíz cuadrada sin usar sqrt() , use root=pow(x,0.5) .

Donde x es el valor cuya raíz cuadrada necesitas encontrar.

Answer 10

//long division method.
#include<iostream>
using namespace std;
int main() {
int n, i = 1, divisor, dividend, j = 1, digit;
cin >> n;
while (i * i < n) {
    i = i + 1;
}
i = i - 1;
cout << i << ''.'';

divisor  = 2 * i;
dividend = n - (i * i );
while( j <= 5) {
    dividend = dividend * 100;
    digit = 0;
    while ((divisor * 10 + digit) * digit < dividend) {
        digit = digit + 1;
    }
    digit = digit  - 1;
    cout << digit;
    dividend = dividend - ((divisor * 10 + digit) * digit);
    divisor = divisor * 10 + 2*digit;
    j = j + 1;
}
cout << endl;
return 0;
}