¿Cómo se implementa la función de raíz cuadrada?

Question

¿Cómo se implementa la función de raíz cuadrada?

Answer 1

En el hardware Intel, a menudo se implementa sobre las instrucciones de hardware SQRT. Algunas bibliotecas simplemente usan el resultado de inmediato, algunos pueden pasar por un par de rondas de optimización de Newton para hacerlo más preciso en los casos de esquina.

Answer 2

Fuente here.

Enunciado del problema: Dado x> 0, encuentre y tal que y^2 = x => y = x/y (este es el paso clave).

1) Adivina un valor g para y y pruébalo.
2) Calcula x/g.
3) Si x/g es lo suficientemente cerca de g, devuelve g. De lo contrario, intenta adivinar mejor.

double test(double x, double g) { 
    if closeEnough(x/g, g) 
     return g; 
    else 
     return test(x, betterGuess(x, g)); 
} 

boolean closeEnough(double a, double b) { 
    return (Math.abs(a - b) < .001); 
} 

double betterGuess(double x, double g) { 
    return ((g + x/g)/2); 
} 

---

sqrt(2)   | Guess g x/g    | New guess, (g + x/g)/2 
----------------|------------------------------|------------------------------- 
test(2, 1)  | 1  2/1  = 2  | (2  +  1)/2 = 1.5 
test(2, 1.5) | 1.5  2/1.5 = 1.3333 | (1.3333 + 1.5)/2 = 1.4167 
test(2, 1.4167) | 1.4167 2/1.4167 = 1.4118 | (1.4167 + 1.4118)/2 = 1.4142 
test(2, 1.4142) | 1.4142 ...     | ... 

Answer 3

Para el cálculo de la raíz cuadrada (sin utilizar la función incorporada math.sqrt):

SquareRootFunction.java

public class SquareRootFunction { 

    public double squareRoot(double value,int decimalPoints) 
    { 
     int firstPart=0; 


     /*calculating the integer part*/ 
     while(square(firstPart)<value) 
     { 
      firstPart++;    
     } 

     if(square(firstPart)==value) 
      return firstPart; 
     firstPart--; 

     /*calculating the decimal values*/ 
     double precisionVal=0.1; 
     double[] decimalValues=new double[decimalPoints]; 
     double secondPart=0; 

     for(int i=0;i<decimalPoints;i++) 
     { 
      while(square(firstPart+secondPart+decimalValues[i])<value) 
      { 
       decimalValues[i]+=precisionVal; 
      } 

      if(square(firstPart+secondPart+decimalValues[i])==value) 
      { 
       return (firstPart+secondPart+decimalValues[i]); 
      } 

      decimalValues[i]-=precisionVal; 
      secondPart+=decimalValues[i]; 
      precisionVal*=0.1; 
     } 

     return(firstPart+secondPart); 

    } 


    public double square(double val) 
    { 
     return val*val; 
    } 

} 

MainApp.java

import java.util.Scanner; 

public class MainApp { 

public static void main(String[] args) { 

    double number; 
    double result; 
    int decimalPoints; 
    Scanner in = new Scanner(System.in); 

    SquareRootFunction sqrt=new SquareRootFunction(); 
    System.out.println("Enter the number\n");    
    number=in.nextFloat(); 

    System.out.println("Enter the decimal points\n");   
    decimalPoints=in.nextInt(); 

    result=sqrt.squareRoot(number,decimalPoints); 

    System.out.println("The square root value is "+ result); 

    in.close(); 

    } 

} 

Answer 4

aplicación simple usando Binary Search con C++

double root(double n){ 
    double lo = 0, hi = n, mid; 
    for(int i = 0 ; i < 1000 ; i++){ 
     mid = (lo+hi)/2; 
     if(mid*mid == n) return mid; 
     if(mid*mid > n){ 
      hi = mid; 
     }else{ 
      lo = mid; 
     } 
    } 
    return mid; 
} 

Tenga en cuenta que while bucle es más común con la búsqueda binaria, pero personalmente prefiero utilizar for cuando se trata de números decimales, se ahorra algunos casos especiales de manipulación y obtiene resultado bastante preciso de pequeños bucles como el 1000 o incluso el 500 (Ambos darán el mismo resultado para casi todos los números pero solo para estar seguros)

Answer 5

El FDLIBM (Libremente Distribuible LIBM) tiene una versión documentada muy bonita de sqrt. e_sqrt.c.

Tiene una versión que utiliza la aritmética de enteros y una fórmula de recurrencia que modifica un bit a la vez.

Otro método utiliza el método de Newton. Se inicia con un poco de magia negro y una tabla de búsqueda para obtener los primeros 8 bits y luego se aplica la fórmula de recurrencia

y_{i+1} = 1/2 * (y_i + x/y_i) 

donde x es el número que empezamos. Este es el Babylonian method del método de Heron. Se remonta a Hero of Alexandra en el primer DC centuary.

Hay otro método llamado Fast inverse square root o reciproot. que usa algún "pirateo de nivel de bit de coma flotante malvado" para encontrar el valor de 1/sqrt (x). i = 0x5f3759df - (i >> 1); Explota la representación binaria de un flotante utilizando la mantis y el exponente. Si nuestro número x es (1 + m) * 2^e, donde m es la mantisa y e el exponente y el resultado y = 1/sqrt (x) = (1 + n) * 2^f.Tomando registros

lg(y) = - 1/2 lg(x) 
f + lg(1+n) = -1/2 e - 1/2 lg(1+m) 

Así que vemos que la parte exponente del resultado es -1/2 el exponente del número. La magia negra básicamente realiza un desplazamiento en modo bit sobre el exponente y usa una aproximación lineal en la mantisa.

Una vez que tenga una buena primera aproximación, puede usar los métodos de Newton para obtener un mejor resultado y finalmente un poco de nivel de trabajo para arreglar el último dígito.

Answer 6

sqrt(); función Detrás de las escenas.

Siempre comprueba los puntos medios en un gráfico. Ejemplo: sqrt (16) = 4; sqrt (4) = 2;

Ahora, si da alguna entrada dentro de 16 o 4 como sqrt (10) ==?

Encuentra el punto medio de 2 y 4 i.e = x, luego nuevamente encuentra el punto medio de xy 4 (Excluye el límite inferior en esta entrada). Repite este paso una y otra vez hasta que obtiene la respuesta perfecta, es decir, sqrt (10) == 3.16227766017. Se encuentra b/w 2 y 4.Toda esta función incorporada se crea utilizando cálculo, diferenciación e integración.

Answer 7

long long int floorSqrt(long long int x) 
{ 
    long long r = 0; 
    while((long)(1<<r)*(long)(1<<r) <= x){ 
     r++; 
    } 
    r--; 
    long long b = r -1; 
    long long ans = 1 << r; 
    while(b >= 0){ 
     if(((long)(ans|1<<b)*(long)(ans|1<<b))<=x){ 
      ans |= (1<<b); 
     } 
     b--; 
    } 
    return ans; 
}