function - resueltos - raiz cuadrada

¿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

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

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

Otro método usa el método de Newton. Comienza con algo de magia negra y una tabla de búsqueda para obtener los primeros 8 bits y luego aplica la fórmula de recurrencia

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

donde x es el número con el que comenzamos. Este es el método babilónico del método de Heron. Se remonta a Hero of Alexandra en el primer DC centuary.

Existe otro método llamado Fast square reverse 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)

Entonces 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 utiliza 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 2

En el hardware de Intel, a menudo se implementa sobre la instrucción SQRT de hardware. 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 3

Esta es una implementación del algoritmo de Newton, ver https://tour.golang.org/flowcontrol/8 .

func Sqrt(x float64) float64 {
  // let initial guess to be 1
  z := 1.0
  for i := 1; i <= 10; i++ {
    z -= (z*z - x) / (2*z) // MAGIC LINE!!
    fmt.Println(z)
  }
  return z
}

La siguiente es una explicación matemática de la línea mágica. Supongamos que quiere encontrar la raíz del polinomio $ f (x) = x ^ 2 - a $. Según el método de Newton, podrías comenzar con una conjetura inicial $ x_0 = 1 $. La siguiente suposición es $ x_1 = x_0 - f (x_0) / f ''(x_0) $, donde $ f'' (x) = 2x $. Por lo tanto, su nueva suposición es

$ x_1 = x_0 - (x_0 ^ 2 - a) / 2x_0 $

Answer 4

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 5

Implementació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 que el bucle es más común con la búsqueda binaria pero Personalmente prefiero usar for cuando se trata de números decimales, guarda algunos casos especiales de manejo y obtiene resultados bastante precisos de bucles pequeños como 1000 o incluso 500 (Ambos darán el mismo resultado para casi todos los números pero solo para estar seguros)

Answer 6

Para calcular la raíz cuadrada (sin usar la función math.sqrt incorporada):

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 7

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

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

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

Encuentra el punto medio de 2 y 4 ie = 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 8

Implementación en Python: el piso del valor raíz es el resultado de esta función. Ejemplo: la raíz cuadrada de 8 es 2.82842 ..., esta función dará salida ''2''

def mySqrt(x):
        # return int(math.sqrt(x))
        if x==0 or x==1:
            return x
        else:
            start = 0
            end = x  
            while (start <= end):
                mid = int((start + end) / 2)
                if (mid*mid == x):
                    return mid
                elif (mid*mid < x):
                    start = mid + 1
                    ans = mid
                else:
                    end = mid - 1
            return ans

Answer 9

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;
}