Come viene implementata la funzione radice quadrata?

Come viene implementata la funzione radice quadrata?

Fonte qui .

Dichiarazione di problema: Dato x> 0, trova y tale che y ^ 2 = x => y = x / y (questo è il passo chiave).

  1. Indovina un valore g per y e testalo.
  2. Calcola x / g.
  3. Se x / g è abbastanza vicino a g, restituisci g. Altrimenti, prova a indovinare meglio.
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 gx / 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 ... | ... 

Semplice implementazione utilizzando la ricerca binaria 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; } 

Si noti che il ciclo while è più comune con la ricerca binaria ma Personalmente preferisco usare for quando si tratta di numeri decimali, salva alcuni casi speciali di gestione e ottiene risultati piuttosto accurati da piccoli loop come 1000 o anche 500 (Entrambi danno lo stesso risultato per quasi tutti i numeri ma solo per sicurezza)

Su hardware Intel, è spesso implementato in aggiunta all’istruzione SQRT dell’hardware. Alcune librerie usano semplicemente il risultato di ciò, alcune potrebbero passare attraverso un paio di giri di ottimizzazione di Newton per renderlo più accurato nei casi d’angolo.

FDLIBM (LIBM liberamente distribuibile) ha una versione documentata abbastanza buona di sqrt. e_sqrt.c .

Hanno una versione che usa l’aritmetica intera e una formula di ricorrenza che modifica un bit alla volta.

Un altro metodo usa il metodo di Newton. Inizia con un po ‘di magia nera e una tabella di ricerca per ottenere i primi 8 bit e quindi applica la formula di ricorrenza

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

dove x è il numero con cui abbiamo iniziato. Questo è il metodo babilonese del metodo di Heron. Risale all’eroe di Alexandra nel primo secolo DC.

Esiste un altro metodo chiamato radice quadrata inversa veloce o reciproot. che usa un “hacking a livello di bit in virgola mobile malvagio” per trovare il valore di 1 / sqrt (x). i = 0x5f3759df - ( i >> 1 ); Sfrutta la rappresentazione binaria di un galleggiante usando la mantisse e l’esponente. Se il nostro numero x è (1 + m) * 2 ^ e, dove m è la mantissa ed e l’esponente e il risultato y = 1 / sqrt (x) = (1 + n) * 2 ^ f. Prendendo i registri

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

Quindi vediamo che la parte esponenziale del risultato è -1/2 l’esponente del numero. La magia nera fondamentalmente esegue uno spostamento bit a bit sull’esponente e utilizza un’approssimazione lineare sulla mantissa.

Una volta ottenuta una buona prima approssimazione, è ansible utilizzare i metodi di Newton per ottenere un risultato migliore e infine alcuni lavori a livello di bit per correggere l’ultima cifra.

Questa è un’implementazione dell’algoritmo di Newton, vedere 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 } 

Quanto segue è una spiegazione matematica della linea magica. Supponiamo di voler trovare la radice del polinomio $ f (x) = x ^ 2 - a $. Con il metodo di Newton, potresti iniziare con un'ipotesi iniziale $ x_0 = 1 $. La prossima ipotesi è $ x_1 = x_0 - f (x_0) / f '(x_0) $, dove $ f' (x) = 2x $. Pertanto, la tua nuova ipotesi è

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

Per calcolare la radice quadrata (senza utilizzare la funzione math.sqrt incorporata):

SquareRootFunction.java

 public class SquareRootFunction { public double squareRoot(double value,int decimalPoints) { int firstPart=0; /*calculating the integer part*/ while(square(firstPart) 

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

sqrt (); funzione Dietro le quinte.

Controlla sempre i punti intermedi in un grafico. Esempio: sqrt (16) = 4; sqrt (4) = 2;

Ora se dai qualsiasi input dentro 16 o 4 come sqrt (10) ==?

Trova il punto medio di 2 e 4 cioè = x, quindi trova nuovamente il punto medio di x e 4 (esclude il limite inferiore in questo input). Ripete questo passaggio ancora e ancora fino a ottenere la risposta perfetta, ad esempio sqrt (10) == 3.16227766017. Si trova in b / n 2 e 4. Tutta questa funzione integrata viene creata utilizzando il calcolo, la differenziazione e l’integrazione.

 long long int floorSqrt(long long int x) { long long r = 0; while((long)(1<= 0){ if(((long)(ans|1< 

Implementazione in Python: il floor del valore root è l’output di questa funzione. Esempio: la radice quadrata di 8 è 2.82842 …, questa funzione darà l’output ‘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 

c’è qualcosa chiamato metodo babilonese.

 static float squareRoot(float n) { /*We are using n itself as initial approximation This can definitely be improved */ float x = n; float y = 1; // e decides the accuracy level double e = 0.000001; while(x - y > e) { x = (x + y)/2; y = n/x; } return x; } 

per maggiori informazioni link: https://www.geeksforgeeks.org/square-root-of-a-perfect-square/