How is the square root function implemented?

Question

How is the square root function implemented?

Answer 1

The source is here .

Task operator: if x> 0, find y so that y ^ 2 = x => y = x / y (this is a key step).

1. Guess some g value for y and check it out.
2. Calculate x / g.
3. If x / g is close enough to g, return g. Otherwise, try to guess better.

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 ... | ... 

Answer 2

Simple implementation using binary search with 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; } 

Please note that while loop is the most common with binary search, but personally I prefer to use for when working with decimal numbers, it saves some special processing cases and gets pretty accurate results from small loops, like this 1000 or even 500 (both will give the same result for almost all numbers, but only for security).

Edit: check out this Wikipedia article on various -special purpose- methods specializing in square root computation.

Answer 3

On Intel hardware, it is often implemented on top of the SQRT hardware instruction. Some libraries just use the result of this right away, some of them can go through a couple of rounds of Newton's optimization to make it more accurate in corner cases.

Answer 4

There are many ways to calculate the square root. Wikipedia contains details for a pseudo-computer algorithm. Are you looking for an implementation in a particular library or for a certain accuracy?

Answer 5

FDLIBM (freeware LIBM) has a pretty good documented version of sqrt. e_sqrt.c .

There is one version that uses integer arithmetic and a repetition formula that changes one bit at a time.

Another method uses the Newton method. It starts with black magic and a lookup table to get the first 8 bits, and then applies the repeat formula

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

where x is the number we started from. This is the Babylonian method of the Heron method. It dates back to the Hero of Alexandra in the first century AD.

There is another method called Quick Reverse Square Root or reciproot. which uses some "malicious hacking bit level floating point" to find the value 1 / sqrt (x). i = 0x5f3759df - ( i >> 1 ); It uses binary float representation using mantissa and exponent. If our number x is (1 + m) * 2 ^ e, where m is the mantissa, e is the exponent, and the result is y = 1 / sqrt (x) = (1 + n) * 2 ^ f. Taking magazines

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

So, we see that the exponential part of the result is -1/2 a measure of the number. Black magic basically performs a bitwise bias of the exponent and uses linear approximation on the mantissa.

Once you have a good first approximation, you can use Newton's methods to get a better result, and finally some bit level to correct the last digit.

Answer 6

This is an implementation of the Newton algorithm, see 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 } 

The following is a mathematical explanation of the magic line. Suppose you want to find the root of the polynomial $ f (x) = x ^ 2 - a $. By Newton’s method, you can start with the initial assumption $ x_0 = 1 $. The following assumption: $ x_1 = x_0 - f (x_0) / f '(x_0) $, where $ f' (x) = 2x $. Therefore your new guess

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

Answer 7

SQRT (); Function Behind the Scenes.

It always checks the midpoints of the chart. Example: sqrt (16) = 4; SQRT (4) = 2;

Now, if you give any input inside 16 or 4, how sqrt (10) ==?

It finds the midpoint 2 and 4 ie = x, then again finds the midpoint x and 4 (it excludes the lower boundary of this input). He repeats this step over and over until he gets the perfect answer. Ie sqrt (10) == 3.16227766017. It lies b / w 2 and 4. All of these built-in functions are created using calculus, differentiation and integration.

Answer 8

Implementation in Python: the floor of the root value is the result of this function. Example: the square root of 8 is 2.82842 ..., this function will give the 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 

Answer 9

To calculate the square root (without using the built-in math.sqrt function):

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 10

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

Answer 11

there is something called the Babylonian method.

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

for more information link: https://www.geeksforgeeks.org/square-root-of-a-perfect-square/

Answer 12

Thus, in case there are no specifications as to whether to use the built-in ceil or round function, Java uses a recursive approach to finding the square root of an unsigned number using the Newton-Raphson method.

 public class FindSquareRoot { private static double newtonRaphson(double N, double X, double oldX) { if(N <= 0) return 0; if (Math.round(X) == Math.ceil(oldX)) return X; return newtonRaphson(N, X - ((X * X) - N)/(2 * X), X); } //Driver method public static void main (String[] args) { System.out.println("Square root of 48.8: " + newtonRaphson(48.8, 10, 0)); } } 

Answer 13

I am doing the sqrt function too, 100,000,000 iterations take 14 seconds, but still nothing compared to 1 seconds for sqrt

 double mysqrt(double n) { double x = n; int it = 4; if (n >= 90) { it = 6; } if (n >= 5000) { it = 8; } if (n >= 20000) { it = 10; } if (n >= 90000) { it = 11; } if (n >= 200000) { it = 12; } if (n >= 900000) { it = 13; } if (n >= 3000000) { it = 14; } if (n >= 10000000) { it = 15; } if (n >= 30000000) { it = 16; } if (n >= 100000000) { it = 17; } if (n >= 300000000) { it = 18; } if (n >= 1000000000) { it = 19; } for (int i = 0; i < it; i++) { x = 0.5*(x+n/x); } return x; } 

But the fastest implementation:

 float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y; } float mysqrt(float n) {return 1/Q_rsqrt(n);} 

Answer 14

After my decision in the Golang.

 package main import ( "fmt" ) func Sqrt(x float64) float64 { z := 1.0 // initial guess to be 1 i := 0 for int(z*z) != int(x) { // until find the first approximation // Newton root algorithm z -= (z*z - x) / (2 * z) i++ } return z } func main() { fmt.Println(Sqrt(8900009870)) } 

Following the classic / general solution.

 package main import ( "fmt" "math" ) func Sqrt(num float64) float64 { const DIFF = 0.0001 // To fix the precision z := 1.0 for { z1 := z - (((z * z) - num) / (2 * z)) // Return a result when the diff between the last execution // and the current one is lass than the precision constant if (math.Abs(z1 - z) < DIFF) { break } z = z1 } return z } func main() { fmt.Println(Sqrt(94339)) } 

Check here for more information.