Writing your own square root function
Asked Answered
B

19

80

How do you write your own function for finding the most accurate square root of an integer?

After googling it, I found this (archived from its original link), but first, I didn't get it completely, and second, it is approximate too.

Assume square root as nearest integer (to the actual root) or a float.

Bromic answered 26/10, 2009 at 6:36 Comment(5)
You don't specify whether the result has to be an integer or can be float.Compatible
An integer square root and a square root of integer are entirely different beasts.Outmoded
en.wikipedia.org/wiki/Methods_of_computing_square_rootsConsanguinity
en.wikipedia.org/wiki/Integer_square_rootConsanguinity
Rather than blaming not being able to find where [it](http://nlindblad.org/2007/04/04/write-your-own-square-root-function/) has been moved as a lame excuse, let me plug the web archive.Inference
C
89

The following computes floor(sqrt(N)) for N > 0:

x = 2^ceil(numbits(N)/2)
loop:
    y = floor((x + floor(N/x))/2)
    if y >= x
        return x
    x = y

This is a version of Newton's method given in Crandall & Pomerance, "Prime Numbers: A Computational Perspective". The reason you should use this version is that people who know what they're doing have proven that it converges exactly to the floor of the square root, and it's simple so the probability of making an implementation error is small. It's also fast (although it's possible to construct an even faster algorithm -- but doing that correctly is much more complex). A properly implemented binary search can be faster for very small N, but there you may as well use a lookup table.

To round to the nearest integer, just compute t = floor(sqrt(4N)) using the algorithm above. If the least significant bit of t is set, then choose x = (t+1)/2; otherwise choose t/2. Note that this rounds up on a tie; you could also round down (or round to even) by looking at whether the remainder is nonzero (i.e. whether t^2 == 4N).

Note that you don't need to use floating-point arithmetic. In fact, you shouldn't. This algorithm should be implemented entirely using integers (in particular, the floor() functions just indicate that regular integer division should be used).

Chesterchesterfield answered 26/10, 2009 at 12:49 Comment(8)
Newtwon's method would be the way I would go. It converges in quadratic number of iterations and is very well behaved for most initial guesses.Brainwash
integer square root is not "the most accurate square root of an integer".Outmoded
@fredrikj: your answer always yields an integer. Are you suggesting that "the most accurate square root of an integer" is always integer?Outmoded
Obviously "the most accurate square root" is the square root itself, so for a numerical approximation, you have to specify whether you want the nearest integer, a float of given precision, or something else. In this case the poster did ask for the "nearest integer" which this algorithm gives you.Chesterchesterfield
Actually, I think finding the nearest integer given the floor one is simpler than using another square root function. If the floor of the square root is n then the closest is either n or n+1. Simply square both of those and see which result is closest to the original number.Sheep
@FredrikJohansson What is this line mean ? x = 2^ceil(numbits(N)/2)Tetrarch
@NairG suppose you write a number S and S has K digits. Then 10^K <= S <= 10^{K+1}. This implies 10^(2K) <= S**2 < 10^(2k+2). That said, if you want to find square root of N, it has length between half of length of N and a number one bigger. So the latter is a good starting point. This line does it, but using 2 as base.Roentgenoscope
You gave a way to compute floor(sqrt(x)) and rounding to nearest integer with floor(sqrt(4x)). Please, is there similar trick (or method) for ceil(sqrt(x))? I tried to asked here.Vinasse
S
41

Depending on your needs, a simple divide-and-conquer strategy can be used. It won't converge as fast as some other methods but it may be a lot easier for a novice to understand. In addition, since it's an O(log n) algorithm (halving the search space each iteration), the worst case for a 32-bit float will be 32 iterations.

Let's say you want the square root of 62.104. You pick a value halfway between 0 and that, and square it. If the square is higher than your number, you need to concentrate on numbers less than the midpoint. If it's too low, concentrate on those higher.

With real math, you could keep dividing the search space in two forever (if it doesn't have a rational square root). In reality, computers will eventually run out of precision and you'll have your approximation. The following C program illustrates the point:

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {
    float val, low, high, mid, oldmid, midsqr;
    int step = 0;

    // Get argument, force to non-negative.

    if (argc < 2) {
        printf ("Usage: sqrt <number>\n");
        return 1;
    }
    val = fabs (atof (argv[1]));

    // Set initial bounds and print heading.

    low = 0;
    high = mid = val;
    oldmid = -1;

    printf ("%4s  %10s  %10s  %10s  %10s  %10s    %s\n",
        "Step", "Number", "Low", "High", "Mid", "Square", "Result");

    // Keep going until accurate enough.

    while (fabs(oldmid - mid) >= 0.00001) {
        oldmid = mid;

        // Get midpoint and see if we need lower or higher.

        mid = (high + low) / 2;
        midsqr = mid * mid;
        printf ("%4d  %10.4f  %10.4f  %10.4f  %10.4f  %10.4f  ",
            ++step, val, low, high, mid, midsqr);
        if (mid * mid > val) {
            high = mid;
            printf ("- too high\n");
        } else {
            low = mid;
            printf ("- too low\n");
        }
    }

    // Desired accuracy reached, print it.

    printf ("sqrt(%.4f) = %.4f\n", val, mid);
    return 0;
}

Here's a couple of runs so you hopefully get an idea how it works. For 77:

pax> sqrt 77
Step      Number         Low        High         Mid      Square    Result
   1     77.0000      0.0000     77.0000     38.5000   1482.2500  - too high
   2     77.0000      0.0000     38.5000     19.2500    370.5625  - too high
   3     77.0000      0.0000     19.2500      9.6250     92.6406  - too high
   4     77.0000      0.0000      9.6250      4.8125     23.1602  - too low
   5     77.0000      4.8125      9.6250      7.2188     52.1104  - too low
   6     77.0000      7.2188      9.6250      8.4219     70.9280  - too low
   7     77.0000      8.4219      9.6250      9.0234     81.4224  - too high
   8     77.0000      8.4219      9.0234      8.7227     76.0847  - too low
   9     77.0000      8.7227      9.0234      8.8730     78.7310  - too high
  10     77.0000      8.7227      8.8730      8.7979     77.4022  - too high
  11     77.0000      8.7227      8.7979      8.7603     76.7421  - too low
  12     77.0000      8.7603      8.7979      8.7791     77.0718  - too high
  13     77.0000      8.7603      8.7791      8.7697     76.9068  - too low
  14     77.0000      8.7697      8.7791      8.7744     76.9893  - too low
  15     77.0000      8.7744      8.7791      8.7767     77.0305  - too high
  16     77.0000      8.7744      8.7767      8.7755     77.0099  - too high
  17     77.0000      8.7744      8.7755      8.7749     76.9996  - too low
  18     77.0000      8.7749      8.7755      8.7752     77.0047  - too high
  19     77.0000      8.7749      8.7752      8.7751     77.0022  - too high
  20     77.0000      8.7749      8.7751      8.7750     77.0009  - too high
  21     77.0000      8.7749      8.7750      8.7750     77.0002  - too high
  22     77.0000      8.7749      8.7750      8.7750     76.9999  - too low
  23     77.0000      8.7750      8.7750      8.7750     77.0000  - too low
sqrt(77.0000) = 8.7750

For 62.104:

pax> sqrt 62.104
Step      Number         Low        High         Mid      Square    Result
   1     62.1040      0.0000     62.1040     31.0520    964.2267  - too high
   2     62.1040      0.0000     31.0520     15.5260    241.0567  - too high
   3     62.1040      0.0000     15.5260      7.7630     60.2642  - too low
   4     62.1040      7.7630     15.5260     11.6445    135.5944  - too high
   5     62.1040      7.7630     11.6445      9.7037     94.1628  - too high
   6     62.1040      7.7630      9.7037      8.7334     76.2718  - too high
   7     62.1040      7.7630      8.7334      8.2482     68.0326  - too high
   8     62.1040      7.7630      8.2482      8.0056     64.0895  - too high
   9     62.1040      7.7630      8.0056      7.8843     62.1621  - too high
  10     62.1040      7.7630      7.8843      7.8236     61.2095  - too low
  11     62.1040      7.8236      7.8843      7.8540     61.6849  - too low
  12     62.1040      7.8540      7.8843      7.8691     61.9233  - too low
  13     62.1040      7.8691      7.8843      7.8767     62.0426  - too low
  14     62.1040      7.8767      7.8843      7.8805     62.1024  - too low
  15     62.1040      7.8805      7.8843      7.8824     62.1323  - too high
  16     62.1040      7.8805      7.8824      7.8815     62.1173  - too high
  17     62.1040      7.8805      7.8815      7.8810     62.1098  - too high
  18     62.1040      7.8805      7.8810      7.8807     62.1061  - too high
  19     62.1040      7.8805      7.8807      7.8806     62.1042  - too high
  20     62.1040      7.8805      7.8806      7.8806     62.1033  - too low
  21     62.1040      7.8806      7.8806      7.8806     62.1038  - too low
  22     62.1040      7.8806      7.8806      7.8806     62.1040  - too high
  23     62.1040      7.8806      7.8806      7.8806     62.1039  - too high
sqrt(62.1040) = 7.8806

For 49:

pax> sqrt 49
Step      Number         Low        High         Mid      Square    Result
   1     49.0000      0.0000     49.0000     24.5000    600.2500  - too high
   2     49.0000      0.0000     24.5000     12.2500    150.0625  - too high
   3     49.0000      0.0000     12.2500      6.1250     37.5156  - too low
   4     49.0000      6.1250     12.2500      9.1875     84.4102  - too high
   5     49.0000      6.1250      9.1875      7.6562     58.6182  - too high
   6     49.0000      6.1250      7.6562      6.8906     47.4807  - too low
   7     49.0000      6.8906      7.6562      7.2734     52.9029  - too high
   8     49.0000      6.8906      7.2734      7.0820     50.1552  - too high
   9     49.0000      6.8906      7.0820      6.9863     48.8088  - too low
  10     49.0000      6.9863      7.0820      7.0342     49.4797  - too high
  11     49.0000      6.9863      7.0342      7.0103     49.1437  - too high
  12     49.0000      6.9863      7.0103      6.9983     48.9761  - too low
  13     49.0000      6.9983      7.0103      7.0043     49.0598  - too high
  14     49.0000      6.9983      7.0043      7.0013     49.0179  - too high
  15     49.0000      6.9983      7.0013      6.9998     48.9970  - too low
  16     49.0000      6.9998      7.0013      7.0005     49.0075  - too high
  17     49.0000      6.9998      7.0005      7.0002     49.0022  - too high
  18     49.0000      6.9998      7.0002      7.0000     48.9996  - too low
  19     49.0000      7.0000      7.0002      7.0001     49.0009  - too high
  20     49.0000      7.0000      7.0001      7.0000     49.0003  - too high
  21     49.0000      7.0000      7.0000      7.0000     49.0000  - too low
  22     49.0000      7.0000      7.0000      7.0000     49.0001  - too high
  23     49.0000      7.0000      7.0000      7.0000     49.0000  - too high
sqrt(49.0000) = 7.0000
Sheep answered 26/10, 2009 at 7:34 Comment(4)
That's very slow compared to Newton's method.Pandorapandour
Hence my first paragraph - the intent of this answer was to show a way of doing it that doesn't require an understanding of calculus. Of course, if you want to use Newtons method blind (without understanding), that's fine - it'll blow my method out of the water. But I didn't put all those tables in my answer to prove its speed - they're there to educate.Sheep
How can Newton's method be faster than O(log n) ? What is the time complexity of the Newton's method ?Honorific
lol unconsciously my mind follows this same algorithm while guessing squares of decimal numbers using a calculator!!Harvey
S
17

A simple (but not very fast) method to calculate the square root of X:

squareroot(x)
    if x<0 then Error
    a = 1
    b = x
    while (abs(a-b)>ErrorMargin) 
        a = (a+b)/2
        b = x/a
    endwhile
    return a;

Example: squareroot(70000)

    a       b
    1   70000
35001       2
17502       4
 8753       8
 4381      16
 2199      32
 1116      63
  590     119
  355     197
  276     254
  265     264

As you can see it defines an upper and a lower boundary for the square root and narrows the boundary until its size is acceptable.

There are more efficient methods but this one illustrates the process and is easy to understand.

Just beware to set the Errormargin to 1 if using integers else you have an endless loop.

Subaltern answered 26/10, 2009 at 7:9 Comment(3)
That is the best algorithm I know of for computing an integer square root, but I'm not sure the rounding mode is deterministic (it looks like it's round to nearest integer, but I'm not sure that's always the case). At the end, I return the smaller of a and b, so that the function always returns floor(sqrt(x)).Defloration
This is a very good and famous algorithm. It is also called Herons or Babylonian method. Very Easy to implement!en.wikipedia.org/wiki/Babylonian_method#Babylonian_methodAbirritate
By using a do … while(a-b>ErrorMargin) instead, you avoid using the abs() function and you make it a bit fasterHemstitch
M
14

Let me point out an extremely interesting method of calculating an inverse square root 1/sqrt(x) which is a legend in the world of game design because it is mind-boggingly fast. Or wait, read the following post:

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

PS: I know you just want the square root but the elegance of quake overcame all resistance on my part :)

By the way, the above mentioned article also talks about the boring Newton-Raphson approximation somewhere.

Misreport answered 26/10, 2009 at 6:52 Comment(4)
I remember reading about this a while back. I am not worthy to be in the presence of the one that worked that out ;pUncomfortable
oh come on... it's just newton-raphson ;)Derrik
The method is Newton-Raphson - just using a single-iteration approximation with a bit-fiddling hack. Newton-Raphson can calculate many inverse functions, not just the square root.Amherst
if you want the square root, take inverse square root, multiply by the original number.Algie
P
9

Of course it's approximate; that is how math with floating-point numbers work.

Anyway, the standard way is with Newton's method. This is about the same as using Taylor's series, the other way that comes to mind immediately.

Partly answered 26/10, 2009 at 6:40 Comment(6)
It would be great if you suggest something from implementation point of view in answer.Bromic
WRT the algorithm, it may be approximate, but only within certain bounds that you are free to define. You can repeat the loop until those bounds are as small as you need - in principle (if you're very careful how you code it) you can get down to the same precision as your floating point number representation. So yes, it remains approximate - but only because floating point is always approximate. Even 0.1 can only be approximately represented in binary floating point.Amherst
@Ravi: Newton's method is implemented by the algorithm you linked to -- so just use that. As a starting point, consider finding the 2^n that is closest to the number you want to take the root of, then using 2^(n/2) as your starting point. However, because the function f(x)=x^2 is convex everywhere, Newton's method works pretty well for it independent of the starting point.Grantland
Newton's method is really a taylor series of O(h^2), you are just refining the point about which you are expandingBrainwash
I only distinguished the two because newton's method is iterated until you get "close enough"; you could also hard-code a taylor series expanded out as far as you like and evaluate that at runtime.Partly
Newton's method tends to be a standard in the forum answers. But this is incomplete. What matters is to find a close initial guess otherwise you will waste awful time getting to the correct magnitude. There are different ways, based on close powers of 2..Beseem
O
8

Calculate square root with arbitrary precision in Python

#!/usr/bin/env python
import decimal

def sqrt(n):
    assert n > 0
    with decimal.localcontext() as ctx:
        ctx.prec += 2 # increase precision to minimize round off error
        x, prior = decimal.Decimal(n), None
        while x != prior: 
            prior = x
            x = (x + n/x) / 2 # quadratic convergence 
    return +x # round in a global context


decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()

Output:

111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True
Outmoded answered 26/10, 2009 at 8:35 Comment(0)
D
6

Found a great article about Integer Square Roots.

This is a slightly improved version that it presents there:

unsigned long sqrt(unsigned long a){
    int i;
    unsigned long rem = 0;
    unsigned long root = 0;
    for (i = 0; i < 16; i++){
        root <<= 1;
        rem = (rem << 2) | (a >> 30);
        a <<= 2;
        if(root < rem){
            root++;
            rem -= root;
            root++;
        }
    }
    return root >> 1;
}
Decrial answered 26/10, 2009 at 13:0 Comment(1)
Here's another article explaining this algorithm (which is easy enough to execute by hand using paper and pencil): mathforum.org/library/drmath/view/52610.htmlConsanguinity
H
6

It's a common interview question asked by Facebook etc. I don't think it's a good idea to use the Newton's method in an interview. What if the interviewer ask you the mechanism of the Newton's method when you don't really understand it?

I provided a binary search based solution in Java which I believe everyone can understand.

public int sqrt(int x) {

    if(x < 0) return -1;
    if(x == 0 || x == 1) return x;

    int lowerbound = 1;
    int upperbound = x;
    int root = lowerbound + (upperbound - lowerbound)/2;

    while(root > x/root || root+1 <= x/(root+1)){
        if(root > x/root){
            upperbound = root;
        } else {
            lowerbound = root;
        }
        root = lowerbound + (upperbound - lowerbound)/2;
    }
    return root;
}

You can test my code here: leetcode: sqrt(x)

Henbane answered 23/2, 2013 at 23:42 Comment(3)
Its not that hard to understand. Newton-Raphson is just a normal Taylor series...Wallin
Two divisions inside the loop: you are not hired !Beseem
@patrik: harder than you believe, though: Newton-Raphson is not at all a Taylor series. Not even close.Beseem
S
4

There is an algorithm that I studied in school that you can use to compute exact square roots (or of arbitrarily large precision if the root is an irrational number). It is definitely slower than Newton's algorithms but it is exact. Lets say you want to compute the square root of 531.3025

First thing is you divide your number starting from the decimal point into groups of 2 digits:
{5}{31}.{30}{25}
Then:
1) Find the closest square root for first group that is smaller or equal to the actual square root of first group: sqrt({5}) >= 2. This square root is the first digit of your final answer. Lets denote the digits we have already found of our final square root as B. So at the moment B = 2.
2) Next compute the difference between {5} and B^2: 5 - 4 = 1.
3) For all subsequent 2 digit groups do the following:
Multiply the remainder by 100, then add it to the second group: 100 + 31 = 131.
Find X - next digit of your root, such that 131 >=((B*20) + X)*X. X = 3. 43 * 3 = 129 < 131. Now B = 23. Also because you have no more 2-digit groups to the left of decimal points, you have found all integer digits of your final root.
4)Repeat the same for {30} and {25}. So you have:
{30} : 131 - 129 = 2. 2 * 100 + 30 = 230 >= (23*2*10 + X) * X -> X = 0 -> B = 23.0
{25} : 230 - 0 = 230. 230 * 100 + 25 = 23025. 23025 >= (230 * 2 * 10 + X) * X -> X = 5 -> B = 23.05
Final result = 23.05.
The algorithm looks complicated this way but it is much simpler if you do it on paper using the same notation you use for "long division" you have studied in school, except that you don't do division but instead compute the square root.

Sonia answered 10/1, 2013 at 18:55 Comment(0)
E
4

Here's a way of obtaining a square root using trigonometry. It's not the fastest algorithm by a longshot, but it is precise. Code is in javascript:

var x = 5;
var sqrt = Math.cos(Math.asin((x-1)/(x+1)))*(x+1)/2;
alert(sqrt);
Evangelia answered 1/7, 2013 at 17:57 Comment(0)
S
3

The first thing comes to my mind is: this is a good place to use Binary search (inspired by this great tutorials.)

To find the square root of vaule ,we are searching the number in (1..value) where the predictor is true for the first time. The predictor we are choosing is number * number - value > 0.00001.

double square_root_of(double value)
{
     assert(value >= 1);
     double lo = 1.0;
     double hi = value;

     while( hi - lo > 0.00001)
     {
          double mid = lo + (hi - lo) / 2 ;
          std::cout << lo << "," << hi << "," << mid << std::endl;
          if( mid * mid - value > 0.00001)    //this is the predictors we are using 
          {
              hi = mid;
          } else {
              lo = mid;
          }

     }

    return lo;
 }
Spatterdash answered 26/10, 2009 at 7:43 Comment(0)
K
3
// Fastest way I found, an (extreme) C# unrolled version of:
// http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt         (isqrt4)

// It's quite a lot of code, basically a binary search (the "if" statements)
// followed by an unrolled loop (the labels).
// Most important: it's fast, twice as fast as "Math.Sqrt".
// On my pc: Math.Sqrt ~35 ns, sqrt <16 ns (mean <14 ns)

private static uint sqrt(uint x)
{
    uint y, z;
    if (x < 1u << 16)
    {
        if (x < 1u << 08)
        {
            if (x < 1u << 04) return x < 1u << 02 ? x + 3u >> 2 : x + 15u >> 3;
            else
            {
                if (x < 1u << 06)
                { y = 1u << 03; x -= 1u << 04; if (x >= 5u << 02) { x -= 5u << 02; y |= 1u << 02; } goto L0; }
                else
                { y = 1u << 05; x -= 1u << 06; if (x >= 5u << 04) { x -= 5u << 04; y |= 1u << 04; } goto L1; }
            }
        }
        else                                             // slower (on my pc): .... y = 3u << 04; } goto L1; }
        {
            if (x < 1u << 12)
            {
                if (x < 1u << 10)
                { y = 1u << 07; x -= 1u << 08; if (x >= 5u << 06) { x -= 5u << 06; y |= 1u << 06; } goto L2; }
                else
                { y = 1u << 09; x -= 1u << 10; if (x >= 5u << 08) { x -= 5u << 08; y |= 1u << 08; } goto L3; }
            }
            else
            {
                if (x < 1u << 14)
                { y = 1u << 11; x -= 1u << 12; if (x >= 5u << 10) { x -= 5u << 10; y |= 1u << 10; } goto L4; }
                else
                { y = 1u << 13; x -= 1u << 14; if (x >= 5u << 12) { x -= 5u << 12; y |= 1u << 12; } goto L5; }
            }
        }
    }
    else
    {
        if (x < 1u << 24)
        {
            if (x < 1u << 20)
            {
                if (x < 1u << 18)
                { y = 1u << 15; x -= 1u << 16; if (x >= 5u << 14) { x -= 5u << 14; y |= 1u << 14; } goto L6; }
                else
                { y = 1u << 17; x -= 1u << 18; if (x >= 5u << 16) { x -= 5u << 16; y |= 1u << 16; } goto L7; }
            }
            else
            {
                if (x < 1u << 22)
                { y = 1u << 19; x -= 1u << 20; if (x >= 5u << 18) { x -= 5u << 18; y |= 1u << 18; } goto L8; }
                else
                { y = 1u << 21; x -= 1u << 22; if (x >= 5u << 20) { x -= 5u << 20; y |= 1u << 20; } goto L9; }
            }
        }
        else
        {
            if (x < 1u << 28)
            {
                if (x < 1u << 26)
                { y = 1u << 23; x -= 1u << 24; if (x >= 5u << 22) { x -= 5u << 22; y |= 1u << 22; } goto La; }
                else
                { y = 1u << 25; x -= 1u << 26; if (x >= 5u << 24) { x -= 5u << 24; y |= 1u << 24; } goto Lb; }
            }
            else
            {
                if (x < 1u << 30)
                { y = 1u << 27; x -= 1u << 28; if (x >= 5u << 26) { x -= 5u << 26; y |= 1u << 26; } goto Lc; }
                else
                { y = 1u << 29; x -= 1u << 30; if (x >= 5u << 28) { x -= 5u << 28; y |= 1u << 28; } }
            }
        }
    }
    z = y | 1u << 26; y /= 2; if (x >= z) { x -= z; y |= 1u << 26; }
Lc: z = y | 1u << 24; y /= 2; if (x >= z) { x -= z; y |= 1u << 24; }
Lb: z = y | 1u << 22; y /= 2; if (x >= z) { x -= z; y |= 1u << 22; }
La: z = y | 1u << 20; y /= 2; if (x >= z) { x -= z; y |= 1u << 20; }
L9: z = y | 1u << 18; y /= 2; if (x >= z) { x -= z; y |= 1u << 18; }
L8: z = y | 1u << 16; y /= 2; if (x >= z) { x -= z; y |= 1u << 16; }
L7: z = y | 1u << 14; y /= 2; if (x >= z) { x -= z; y |= 1u << 14; }
L6: z = y | 1u << 12; y /= 2; if (x >= z) { x -= z; y |= 1u << 12; }
L5: z = y | 1u << 10; y /= 2; if (x >= z) { x -= z; y |= 1u << 10; }
L4: z = y | 1u << 08; y /= 2; if (x >= z) { x -= z; y |= 1u << 08; }
L3: z = y | 1u << 06; y /= 2; if (x >= z) { x -= z; y |= 1u << 06; }
L2: z = y | 1u << 04; y /= 2; if (x >= z) { x -= z; y |= 1u << 04; }
L1: z = y | 1u << 02; y /= 2; if (x >= z) { x -= z; y |= 1u << 02; }
L0: return x > y ? y / 2 | 1u : y / 2;
}
Kathaleenkatharevusa answered 24/9, 2013 at 13:22 Comment(0)
V
3

use binary search

public class FindSqrt {

    public static void main(String[] strings) {

        int num = 10000;
        System.out.println(sqrt(num, 0, num));
    }

    private static int sqrt(int num, int min, int max) {
        int middle = (min + max) / 2;
        int x = middle * middle;
        if (x == num) {
            return middle;
        } else if (x < num) {
            return sqrt(num, middle, max);
        } else {
            return sqrt(num, min, middle);
        }
    }
}
Volscian answered 14/6, 2016 at 13:25 Comment(1)
use floats instead of int to get the accurate resultBanns
C
1

In general the square root of an integer (like 2, for example) can only be approximated (not because of problems with floating point arithmetic, but because they're irrational numbers which can't be calculated exactly).

Of course, some approximations are better than others. I mean, of course, that the value 1.732 is a better approximation to the square root of 3, than 1.7

The method used by the code at that link you gave works by taking a first approximation and using it to calculate a better approximation.

This is called Newton's Method, and you can repeat the calculation with each new approximation until it's accurate enough for you.

In fact there must be some way to decide when to stop the repetition or it will run forever.

Usually you would stop when the difference between approximations is less than a value you decide.

EDIT: I don't think there can be a simpler implementation than the two you already found.

Chandrachandragupta answered 26/10, 2009 at 6:47 Comment(3)
Beware! Do you want to die like Hippasus ? en.wikipedia.org/wiki/Hippasus ?Derrik
If irrational numbers were lethal, we'd all be dead for talking about circles.Chandrachandragupta
Sounds like the ancient Greek equivalent of the DCMA.Bookkeeper
B
1

The inverse, as the name says, but sometimes "close enough" is "close enough"; an interesting read anyway.

Origin of Quake3's Fast InvSqrt()

Beard answered 1/11, 2009 at 21:26 Comment(0)
T
1

A simple solution that can deal with float square root and arbitrary precision using binary search

coded in ruby

include Math

def sqroot_precision num, precision
  upper   = num
  lower   = 0
  middle  = (upper + lower)/2.0

  while true do
    diff = middle**2 - num

    return middle if diff.abs <= precision

    if diff > 0
      upper = middle
    else diff < 0
      lower = middle
    end

    middle = (upper + lower)/2.0
  end 
end

puts sqroot_precision 232.3, 0.0000000001
Trumpeter answered 27/3, 2014 at 6:42 Comment(0)
L
1

Let's say we are trying to find the square root of 2, and you have an estimate of 1.5. We'll say a = 2, and x = 1.5. To compute a better estimate, we'll divide a by x. This gives a new value y = 1.333333. However, we can't just take this as our next estimate (why not?). We need to average it with the previous estimate. So our next estimate, xx will be (x + y) / 2, or 1.416666.

Double squareRoot(Double a, Double epsilon) {
    Double x = 0d;
    Double y = a;
    Double xx = 0d;

    // Make sure both x and y != 0.
    while ((x != 0d || y != 0d) && y - x > epsilon) {
        xx = (x + y) / 2;

        if (xx * xx >= a) {
            y = xx;
        } else {
            x = xx;
        }
    }

    return xx;
}

Epsilon determines how accurate the approximation needs to be. The function should return the first approximation x it obtains that satisfies abs(x*x - a) < epsilon, where abs(x) is the absolute value of x.

square_root(2, 1e-6)
Output: 1.4142141342163086
Lamina answered 10/4, 2015 at 0:24 Comment(0)
C
1

Well there are already quite a few answers, but here goes mine It's the most simplest piece of code ( for me ), here is the algorithm for it.

And code in python 2.7:

from __future__ import division 
val = 81
x = 10
def sqr(data,x):
    temp = x - ( (x**2 - data)/(2*x))
    if temp == x:
        print temp
        return
    else:
        x = temp
        return sqr(data,x)
    #x =temp 
    #sqr(data,x)
sqr(val,x)
Caa answered 11/8, 2016 at 15:34 Comment(0)
P
-5

To calculate the square root of a number by help of inbuilt function

# include"iostream.h"
# include"conio.h"
# include"math.h"
void main()
{
clrscr();
float x;
cout<<"Enter the Number";
cin>>x;

 float squreroot(float);  
 float z=squareroot(x);
 cout<<z;


float squareroot(int x)
    {


 float s;
 s = pow(x,.5)  
 return(s);
 }    
Pry answered 25/10, 2013 at 3:51 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.