Calculating the square root of 2

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
9
down vote

favorite
2












Since $sqrt2$ is irrational, is there a way to compute the first 20 digits of it?



What I have done so far



I started the first digit decimal of the $sqrt2$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



beginalign
sqrt 2 & = 1.4^2 equiv 1.96\
sqrt 2 & = 1.41^2 equiv 1.9881\
sqrt 2 & = 1.414^2 equiv 1.999396\
& ldots
endalign



First I tell whether it passes such that $1.x^2$ would be not greater than 3.



If that passes, I will add a new decimal to it. Let's say $y.$ $1.xy^2$

If that y fails, I increment $y$ by 1 and square it again.



The process will keep repeating. Unfortunately, the process takes so much time.










share|cite|improve this question



















  • 4




    You can go on trying to compute the square of $1.414x$, where $x$ is a number between $0$ and $9$. The greatest number between $1.4140$ and $1.4149$ such that its square is less then $2$ is your next candidate to repeat the process.
    – Gibbs
    23 hours ago






  • 1




    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    – lhf
    23 hours ago










  • @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    – MMJM
    23 hours ago






  • 2




    Possible duplicate of 1. calculate-more-digits-of-square-root-of-2 2. is-there-any-simple-method-to-calculate-sqrt-x-without-using-logarithm 3.
    – user202729
    20 hours ago






  • 1




    @Gibbs Please don't post answers as comments.
    – David Richerby
    17 hours ago














up vote
9
down vote

favorite
2












Since $sqrt2$ is irrational, is there a way to compute the first 20 digits of it?



What I have done so far



I started the first digit decimal of the $sqrt2$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



beginalign
sqrt 2 & = 1.4^2 equiv 1.96\
sqrt 2 & = 1.41^2 equiv 1.9881\
sqrt 2 & = 1.414^2 equiv 1.999396\
& ldots
endalign



First I tell whether it passes such that $1.x^2$ would be not greater than 3.



If that passes, I will add a new decimal to it. Let's say $y.$ $1.xy^2$

If that y fails, I increment $y$ by 1 and square it again.



The process will keep repeating. Unfortunately, the process takes so much time.










share|cite|improve this question



















  • 4




    You can go on trying to compute the square of $1.414x$, where $x$ is a number between $0$ and $9$. The greatest number between $1.4140$ and $1.4149$ such that its square is less then $2$ is your next candidate to repeat the process.
    – Gibbs
    23 hours ago






  • 1




    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    – lhf
    23 hours ago










  • @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    – MMJM
    23 hours ago






  • 2




    Possible duplicate of 1. calculate-more-digits-of-square-root-of-2 2. is-there-any-simple-method-to-calculate-sqrt-x-without-using-logarithm 3.
    – user202729
    20 hours ago






  • 1




    @Gibbs Please don't post answers as comments.
    – David Richerby
    17 hours ago












up vote
9
down vote

favorite
2









up vote
9
down vote

favorite
2






2





Since $sqrt2$ is irrational, is there a way to compute the first 20 digits of it?



What I have done so far



I started the first digit decimal of the $sqrt2$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



beginalign
sqrt 2 & = 1.4^2 equiv 1.96\
sqrt 2 & = 1.41^2 equiv 1.9881\
sqrt 2 & = 1.414^2 equiv 1.999396\
& ldots
endalign



First I tell whether it passes such that $1.x^2$ would be not greater than 3.



If that passes, I will add a new decimal to it. Let's say $y.$ $1.xy^2$

If that y fails, I increment $y$ by 1 and square it again.



The process will keep repeating. Unfortunately, the process takes so much time.










share|cite|improve this question















Since $sqrt2$ is irrational, is there a way to compute the first 20 digits of it?



What I have done so far



I started the first digit decimal of the $sqrt2$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



beginalign
sqrt 2 & = 1.4^2 equiv 1.96\
sqrt 2 & = 1.41^2 equiv 1.9881\
sqrt 2 & = 1.414^2 equiv 1.999396\
& ldots
endalign



First I tell whether it passes such that $1.x^2$ would be not greater than 3.



If that passes, I will add a new decimal to it. Let's say $y.$ $1.xy^2$

If that y fails, I increment $y$ by 1 and square it again.



The process will keep repeating. Unfortunately, the process takes so much time.







approximation radicals






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 18 mins ago









amWhy

190k26221433




190k26221433










asked 23 hours ago









MMJM

1067




1067







  • 4




    You can go on trying to compute the square of $1.414x$, where $x$ is a number between $0$ and $9$. The greatest number between $1.4140$ and $1.4149$ such that its square is less then $2$ is your next candidate to repeat the process.
    – Gibbs
    23 hours ago






  • 1




    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    – lhf
    23 hours ago










  • @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    – MMJM
    23 hours ago






  • 2




    Possible duplicate of 1. calculate-more-digits-of-square-root-of-2 2. is-there-any-simple-method-to-calculate-sqrt-x-without-using-logarithm 3.
    – user202729
    20 hours ago






  • 1




    @Gibbs Please don't post answers as comments.
    – David Richerby
    17 hours ago












  • 4




    You can go on trying to compute the square of $1.414x$, where $x$ is a number between $0$ and $9$. The greatest number between $1.4140$ and $1.4149$ such that its square is less then $2$ is your next candidate to repeat the process.
    – Gibbs
    23 hours ago






  • 1




    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    – lhf
    23 hours ago










  • @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    – MMJM
    23 hours ago






  • 2




    Possible duplicate of 1. calculate-more-digits-of-square-root-of-2 2. is-there-any-simple-method-to-calculate-sqrt-x-without-using-logarithm 3.
    – user202729
    20 hours ago






  • 1




    @Gibbs Please don't post answers as comments.
    – David Richerby
    17 hours ago







4




4




You can go on trying to compute the square of $1.414x$, where $x$ is a number between $0$ and $9$. The greatest number between $1.4140$ and $1.4149$ such that its square is less then $2$ is your next candidate to repeat the process.
– Gibbs
23 hours ago




You can go on trying to compute the square of $1.414x$, where $x$ is a number between $0$ and $9$. The greatest number between $1.4140$ and $1.4149$ such that its square is less then $2$ is your next candidate to repeat the process.
– Gibbs
23 hours ago




1




1




See en.wikipedia.org/wiki/Methods_of_computing_square_roots
– lhf
23 hours ago




See en.wikipedia.org/wiki/Methods_of_computing_square_roots
– lhf
23 hours ago












@Gibbs I tried that so far. But the reason is that it takes more time to compute it.
– MMJM
23 hours ago




@Gibbs I tried that so far. But the reason is that it takes more time to compute it.
– MMJM
23 hours ago




2




2




Possible duplicate of 1. calculate-more-digits-of-square-root-of-2 2. is-there-any-simple-method-to-calculate-sqrt-x-without-using-logarithm 3.
– user202729
20 hours ago




Possible duplicate of 1. calculate-more-digits-of-square-root-of-2 2. is-there-any-simple-method-to-calculate-sqrt-x-without-using-logarithm 3.
– user202729
20 hours ago




1




1




@Gibbs Please don't post answers as comments.
– David Richerby
17 hours ago




@Gibbs Please don't post answers as comments.
– David Richerby
17 hours ago










10 Answers
10






active

oldest

votes

















up vote
27
down vote



accepted










Calculating the square root of a number is one of the first problems tackled with numerical methods, known I think to the ancient Babylonians. The observation is that if $x,,y>0$ and $ynesqrtx$ the $y,,x/y$ will be on opposite sides of $sqrtx$, and we could try averaging them. So try $y_0=1,,y_n+1=frac12(y_n+fracxy_n)$. This is actually the Newton-Raphson method 5xum mentioned. The number of correct decimal places approximately doubles at each stage, i.e. you probably only have to go as far as $y_5$ or so.






share|cite|improve this answer
















  • 9




    Definitely one of the fastest methods: $$ y_0 = 1.colortan0;\ y_1 = 1.colortan5;\ y_2 = 1.41colortan666666666666666666666666666...;\ y_3 = 1.41421colortan568627450980392156862745...;\ y_4 = 1.41421356237colortan468991062629557889...;\ y_5 = 1.41421356237309504880168colortan962350...;\ cdots $$
    – Oleg567
    23 hours ago







  • 6




    @Oleg567 We could go even faster with post-Newton Householder methods, but the individual steps become more computationally complex. BTW the calculator you used to check that probably also used Newton-Raphson for the division.
    – J.G.
    23 hours ago






  • 2




    The beauty of this method is that the initial estimate can be way off and the method will converge quickly anyway. of course, making an educated guess to pick the initial estimate helps to reduce the number of iterations.
    – Vasya
    23 hours ago






  • 3




    Love the intuitive explanation for it!
    – dbx
    23 hours ago






  • 1




    @Paul Since it's Newton-Raphson it'll be about $2^n$ of them, but a more detailed answer than that can't be obtained without careful analysis of the specifics of the problem. However, if you look at how which digits have "gotten stuck", you can be confident from the shrinking error terms that they won't change. See the black digits in Oleg567's comment for an example.
    – J.G.
    13 hours ago

















up vote
10
down vote













Here's the way I learnt to obtain decimal digit after decimal digit when I began middle school:



beginarraylcl
2&big( &colorred1.414,2dots \[1ex]
1,00&& 24times colorred4=96<100\
-96,&& 25times5=125>100\[1ex]
phantom-04,00&&281timescolorred1<400\
;:-2,81&&282times2>400\[1ex]
phantom-0119,00&&2824timescolorred4<11900\
phantom0-112,96&&2825times5>11900 \[1ex]
phantom00;604,00&&28282timescolorred2 < 60400 \
&&28283times3> 60400
endarray
&c.



Let me explain the procedure on the first two steps. It relies on a clever use of the identity $(x+y)^2=x^2+2xy+y^2$. Suppose more generally we want to find the square root of a number $a$.



  1. We first find the greatest natural number $n$ such that $n^2le a$.

  2. If $a$ is not a perfect square, i.e. if $n^2<a$, let $d$ be the first decimal digit of the square root. This is the greatest digit such that $;Bigl(n+frac d10Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
    beginalign
    Bigl(n+frac d10Bigr)^2le a&iff frac2n10d+fracd^2100<a -n^2\
    &iff (10times 2n+d)times dle (a-n^2)times 100
    endalign
    In practice, this means, we calculate the difference $a-n^2$ and add two 0s. Then we double $n$, add a digit d (this is the result of calculating $10times 2n+d$) and multiply what we obtain by this digit. Last, we test whether the result is less than $100(a-n^2)$, and retain the largest possible digit.





share|cite|improve this answer


















  • 4




    Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
    – goblin
    9 hours ago











  • @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
    – shoover
    6 hours ago










  • @goblin: I've added an explanation for the first two steps. The following stepsruns along te same lines, only the first step is different. Hope this will make it clear.
    – Bernard
    2 hours ago










  • @Bernard, thanks.
    – goblin
    2 hours ago










  • @goblin You start off with 1 because 1 is the largest integer whoose square is less than 2. Then extend 1 by the next two digits, 00, to get 100. Now double the 1 just obtained and find the largest digit such that 2x times x is less than 100.
    – Paul Evans
    2 hours ago


















up vote
5
down vote













The number $sqrt2$ is the solution to the equation $x^2-2=0$, so any method for numerically approximating the roots of an equation (such as the Newton method) will be able to approximate $sqrt2$.






share|cite|improve this answer



























    up vote
    3
    down vote













    On a similar note to the answer by R. Romero: in the special case of taking the square root of an integer $N$, it is fairly straightforward to calculate the continued fraction representation of $sqrtN$.



    In the particular case $N=2$, we have:
    $$ sqrt2 = 1 + frac12 + frac12 + frac12 + ddots. $$
    (This follows from the fact that if $x = sqrt2-1$, then $x = sqrt2-1 = frac1sqrt2+1 = frac12+x$.)



    Now, from this we can calculate subsequent rational approximations to $sqrt2$:



    $$
    beginmatrix
    & & 1 & 2 & 2 & 2 & 2 & 2 & cdots \
    0 & 1 & 1 & 3 & 7 & 17 & 41 & 99 & cdots \
    1 & 0 & 1 & 2 & 5 & 12 & 29 & 70 & cdots
    endmatrix $$
    So, for example $frac9970 approx 1.4142857$ whereas $sqrt2 approx 1.4142136$.



    (It also happens that this procedure generates solutions to Pell's equation $a^2 - 2 b^2 = pm 1$; for example, $99^2 - 2 cdot 70^2 = 1$. The connection is: if $a^2 - 2 b^2 = pm 1$ then $a - b sqrt2 = pm frac1a + b sqrt2$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt2 approx pmfrac12a$ which implies $fracab - sqrt2 approx pmfrac12ab approx pmfrac1a^2sqrt2$.)






    share|cite|improve this answer
















    • 1




      Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
      – goblin
      9 hours ago

















    up vote
    1
    down vote













    There's a general method that converges about as quickly as Newton-Raphson but is somewhat more general. It's based off of Continued Fractions:



    Suppose you want to find the square root of $N$. Let $a+b = N$ where $b$ has an easy to calculate square root.



    let $y_n+1 = sqrt b + fraca sqrt b + y_n$



    $y_n+1$ converges to $sqrt N$.






    share|cite|improve this answer





























      up vote
      1
      down vote













      Suppose you want to find the square root of $p$ and suppose your initial guess is $x/y$:



      Let $mathbf M=beginbmatrix 1 & p \ 1 & 1 endbmatrix$ and $mathbf q=beginpmatrix x \ y endpmatrix$
      Then $mathbf Mmathbf Mmathbf M...mathbf q$ gives a numerator and denominator the ratio of which converges to the square root of $p$. This gives an approximation to the square root of $2$ as fast as the other methods but with no floating point arithmetic until the final division.



      Performs well for calculation tools optimized for Matrix arithmetic. This also gives you solutions for Pell's equation for $p=2$ as mentioned by Daniel Schepler.






      share|cite|improve this answer





























        up vote
        0
        down vote













        You can compute it manually using the algorithm:



        1. $p=0$, $r=0$, $i=0$

        2. Split the number into sections of two digits

        3. Take i'th section $n_i$, let $k=100t+n_i$

        4. Find the greatest number $x$, such that $$y=x(20p+x)leq k$$

        5. Assign $p=10 p + x$, $i=i+1$, if the accyracy of the result is not satisfied, then return to 3.

        Example:




        02.00 00 00 00 00




        • $n_0 = 2$, $k=2$, therefore for $x=1$: $y=1$ and $p=1$

        • $n_1=0$, $k=100$, so for $x=4$: $y=24*4=96<100$ and $p=14$

        • $n_2=0$, $k=400$, so for $x=1$, $y=281*1=281<400$ and $p=141$

        • $n_3=0$, $k=11900$, so for $x=4$, $y=2824*4=11296<11900$ and $p=1414$

        • $n_4=0$, $k=60400$, so for $x=2$, $y=28282*2=56564<60400$ and $p=14142$

        • $n_5=0$, $k=383600$, so for $x=1$, $y=282841*1=282841<383600$ and $p=141421$

        • ...

        After all just remember to point the comma in place, where it should be, ie. after first number (it depends how many sections were there on the left side of our number), so you'll have:
        $$sqrt2approx 1.41421$$



        To obtain accuracy of 20 numbers after the comma, you should append 20 sections of 00 in the step 2. , ie.:




        02.00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00







        share|cite|improve this answer



























          up vote
          0
          down vote













          Using the fact that $sin fracpi4 = fracsqrt22$, then we have to find $2 sin fracpi4$.



          We can approximate $sin x$ using the Taylor series to three terms:



          $$sin x = x - fracx^33! + fracx^55! + O(x^6),$$



          so we have:



          $$sin fracpi4 approx fracpi4 - frac(pi/4)^33! + frac(pi/4)^55! .$$



          If we approximate $pi$ as $frac227$, then we have $fracpi4 = frac1114$, then we have:



          $$sin fracpi4 approxfrac1114 - frac(11/14)^33! + frac(11/14)^55!,$$



          which when you multiply by $2$ to get $sqrt2$, gives $1.4147$, while the actual value is $1.4142$.



          If we expand the Taylor series to more terms, or improve the approximation of $pi$ (such as $frac355113$), then we can get to $20$ correct digits.






          share|cite|improve this answer
















          • 1




            Don’t you need pi to nearly 20 digits for this to work?
            – JoeTaxpayer
            9 hours ago

















          up vote
          0
          down vote













          Let us start with an initial guess $x$ for the square root of $2$. Then add a correction term $y$. Write down $(x+y)^2 - 2 = 0$. Solve this equation for $y$ by expanding it up to third order in the difference $(2-x^2)$. This is a straightforward calculation. Combining all contributions, the result is simple and elegant:



          $$y = (x^4+12x^2+4)/(4x^3+8x)$$



          For a rational initial guess $x$ the result $y$ is also rational, but far more close to the desired value. For example if we take $x = 3/2$, then $y=577/408$, which differs from the square root of 2 by a factor 1.0000015.






          share|cite|improve this answer



























            up vote
            0
            down vote













            Newton-Rhapson is a good idea because of the convergence rate. However, I am more of a fan of using Taylor's expansions here since it is super easy to derive on the go to give fairly ok estimates in quite a reasonable time. So, the way to go to find $sqrtx$ is to find first the closest integer which approximates $sqrtx$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
            $$ sqrtx approx a + (x-a^2)cdot frac12 a - (x-a^2)^2/2 cdot frac14 a^3 + cdots. $$
            The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrtx$, then the error of a $n$th order approximation (i.e., going as far as $(x-a^2)^n/n! cdot f^(n)(a^2)$ in the approximation above) is given by $$ (x-a)^n+1/(n+1)! cdot f^(n+1)(xi)$$ for a certain $xi$ between $a^2$ and $x$. This can be estimated quite easily since this $f^(n+1)$ is monotone around $x$. Thus look at the boundaries of the domain of $xi$ and find the 'best' maximal value which you can calculate without a calculator.



            Example for $x=2$. Apparently $1$ is the closest integer to $sqrt2$ and thus we will take $a=1$. Then, let's take a second order approximation
            $$sqrt2 approx 1 + (2-1)cdot frac12 - (2-1)^2/2cdot frac14 = 1 + 0.5 - 0.125 = 1.375 $$
            and the absolute error is given by
            $$ E=left|(2-1)^3/3!cdot frac38 cdot xi^2sqrtxiright| = frac116 cdot frac1$$
            for a certain $xi$ between $1$ and $2$. Since this is a decreasing function on $(1,2)$. The maximum is attained at $1$ and hence the error is bounded by
            $$ E leq frac116 $$
            which seems to be a good estimate since $E = 0.039dots$ and $1/16 = 0.0625$.



            Edit As some of you noted this method 'looks' more difficult than Newton-Rhapson and the convergence is slower. The last part is obviously true and I would answer this question with: How quick do you need it to be and do you want to calculate it in your head or do you have a computer? Do you need to have a quick guess which is approximately equal to the value of $sqrt2$ or do you need a precise estimate. If you don't have a computer but pen and paper, the best method is Newton-Rhapson.

            I would argue that my method is better if you don't have pen and paper or a computer and you are asked to give an estimation of $sqrt10$ on the go (especially for $sqrtx$ with $x$ big, the Taylor approximation is better since the $sqrtbullet$ function becomes more linear as $x$ grows).

            I agree that my method looks way more difficult but it isn't if you get more familiar with it. Also, this method is super quick in terms of calculation time in your head and if you practice a little with it, it becomes way easier. Also, this method works particularly nice for $sqrtx$ where $x$ differs one from a perfect square because then the $(x-a^2)^n$ term will always be one.

            Let's look at an example here. Suppose you need to calculate $sqrt122$, then first order approximation of my method gives
            $$ sqrt122 approx 11 + frac12cdot 11. $$
            It took me less than one second to find this approximation and the second order approximation works almost as quick here. You just need to add $frac-18cdot 11^3$. Please note that the error of the first order approximation here is approximately equal to $10^-4$.

            If you apply Newton-Rhapson here you get the same approximation after one step if you choose $x_0=11$. The only thing is that I always forget what the exact form is of Newton-Rhapson. So when I want to apply it, I have to think about it where I could have immediately applied Taylor but I would say that is just my particular preference.






            share|cite|improve this answer


















            • 2




              I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
              – leftaroundabout
              21 hours ago











            • I would say it is less difficult since when you apply Newton-Rhapson you always have to find the exact algorithm and this method can be applied to find $sqrt2.243$ also quite quickly.
              – Stan Tendijck
              20 hours ago










            • I agree with @leftaroundabout, but perhaps if you edit into your post an illustration of how this method could be used by hand to compute rad 2 to high accuracy, it would appear simpler. Right now, it looks much more difficult.
              – Wildcard
              17 hours ago






            • 2




              Taylor's converges much more slowly than Newton Raphson. Note the second order term starting with initial guess 1 is 1.4166.... already correct to two digits behind the decimal. You might get an additional correct digit at each step of the calculation heavy Taylor series. The accuracy doubles per step for Newton Raphson without the difficulty of calculating the Taylor coefficients. There might be ways to patch it up. There's an alternative series to the Taylor series for arctan that converges much faster than Taylor.
              – TurlocTheRed
              9 hours ago










            Your Answer




            StackExchange.ifUsing("editor", function ()
            return StackExchange.using("mathjaxEditing", function ()
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            );
            );
            , "mathjax-editing");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "69"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            convertImagesToLinks: true,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );













             

            draft saved


            draft discarded


















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2916718%2fcalculating-the-square-root-of-2%23new-answer', 'question_page');

            );

            Post as a guest






























            10 Answers
            10






            active

            oldest

            votes








            10 Answers
            10






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            27
            down vote



            accepted










            Calculating the square root of a number is one of the first problems tackled with numerical methods, known I think to the ancient Babylonians. The observation is that if $x,,y>0$ and $ynesqrtx$ the $y,,x/y$ will be on opposite sides of $sqrtx$, and we could try averaging them. So try $y_0=1,,y_n+1=frac12(y_n+fracxy_n)$. This is actually the Newton-Raphson method 5xum mentioned. The number of correct decimal places approximately doubles at each stage, i.e. you probably only have to go as far as $y_5$ or so.






            share|cite|improve this answer
















            • 9




              Definitely one of the fastest methods: $$ y_0 = 1.colortan0;\ y_1 = 1.colortan5;\ y_2 = 1.41colortan666666666666666666666666666...;\ y_3 = 1.41421colortan568627450980392156862745...;\ y_4 = 1.41421356237colortan468991062629557889...;\ y_5 = 1.41421356237309504880168colortan962350...;\ cdots $$
              – Oleg567
              23 hours ago







            • 6




              @Oleg567 We could go even faster with post-Newton Householder methods, but the individual steps become more computationally complex. BTW the calculator you used to check that probably also used Newton-Raphson for the division.
              – J.G.
              23 hours ago






            • 2




              The beauty of this method is that the initial estimate can be way off and the method will converge quickly anyway. of course, making an educated guess to pick the initial estimate helps to reduce the number of iterations.
              – Vasya
              23 hours ago






            • 3




              Love the intuitive explanation for it!
              – dbx
              23 hours ago






            • 1




              @Paul Since it's Newton-Raphson it'll be about $2^n$ of them, but a more detailed answer than that can't be obtained without careful analysis of the specifics of the problem. However, if you look at how which digits have "gotten stuck", you can be confident from the shrinking error terms that they won't change. See the black digits in Oleg567's comment for an example.
              – J.G.
              13 hours ago














            up vote
            27
            down vote



            accepted










            Calculating the square root of a number is one of the first problems tackled with numerical methods, known I think to the ancient Babylonians. The observation is that if $x,,y>0$ and $ynesqrtx$ the $y,,x/y$ will be on opposite sides of $sqrtx$, and we could try averaging them. So try $y_0=1,,y_n+1=frac12(y_n+fracxy_n)$. This is actually the Newton-Raphson method 5xum mentioned. The number of correct decimal places approximately doubles at each stage, i.e. you probably only have to go as far as $y_5$ or so.






            share|cite|improve this answer
















            • 9




              Definitely one of the fastest methods: $$ y_0 = 1.colortan0;\ y_1 = 1.colortan5;\ y_2 = 1.41colortan666666666666666666666666666...;\ y_3 = 1.41421colortan568627450980392156862745...;\ y_4 = 1.41421356237colortan468991062629557889...;\ y_5 = 1.41421356237309504880168colortan962350...;\ cdots $$
              – Oleg567
              23 hours ago







            • 6




              @Oleg567 We could go even faster with post-Newton Householder methods, but the individual steps become more computationally complex. BTW the calculator you used to check that probably also used Newton-Raphson for the division.
              – J.G.
              23 hours ago






            • 2




              The beauty of this method is that the initial estimate can be way off and the method will converge quickly anyway. of course, making an educated guess to pick the initial estimate helps to reduce the number of iterations.
              – Vasya
              23 hours ago






            • 3




              Love the intuitive explanation for it!
              – dbx
              23 hours ago






            • 1




              @Paul Since it's Newton-Raphson it'll be about $2^n$ of them, but a more detailed answer than that can't be obtained without careful analysis of the specifics of the problem. However, if you look at how which digits have "gotten stuck", you can be confident from the shrinking error terms that they won't change. See the black digits in Oleg567's comment for an example.
              – J.G.
              13 hours ago












            up vote
            27
            down vote



            accepted







            up vote
            27
            down vote



            accepted






            Calculating the square root of a number is one of the first problems tackled with numerical methods, known I think to the ancient Babylonians. The observation is that if $x,,y>0$ and $ynesqrtx$ the $y,,x/y$ will be on opposite sides of $sqrtx$, and we could try averaging them. So try $y_0=1,,y_n+1=frac12(y_n+fracxy_n)$. This is actually the Newton-Raphson method 5xum mentioned. The number of correct decimal places approximately doubles at each stage, i.e. you probably only have to go as far as $y_5$ or so.






            share|cite|improve this answer












            Calculating the square root of a number is one of the first problems tackled with numerical methods, known I think to the ancient Babylonians. The observation is that if $x,,y>0$ and $ynesqrtx$ the $y,,x/y$ will be on opposite sides of $sqrtx$, and we could try averaging them. So try $y_0=1,,y_n+1=frac12(y_n+fracxy_n)$. This is actually the Newton-Raphson method 5xum mentioned. The number of correct decimal places approximately doubles at each stage, i.e. you probably only have to go as far as $y_5$ or so.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered 23 hours ago









            J.G.

            14.5k11626




            14.5k11626







            • 9




              Definitely one of the fastest methods: $$ y_0 = 1.colortan0;\ y_1 = 1.colortan5;\ y_2 = 1.41colortan666666666666666666666666666...;\ y_3 = 1.41421colortan568627450980392156862745...;\ y_4 = 1.41421356237colortan468991062629557889...;\ y_5 = 1.41421356237309504880168colortan962350...;\ cdots $$
              – Oleg567
              23 hours ago







            • 6




              @Oleg567 We could go even faster with post-Newton Householder methods, but the individual steps become more computationally complex. BTW the calculator you used to check that probably also used Newton-Raphson for the division.
              – J.G.
              23 hours ago






            • 2




              The beauty of this method is that the initial estimate can be way off and the method will converge quickly anyway. of course, making an educated guess to pick the initial estimate helps to reduce the number of iterations.
              – Vasya
              23 hours ago






            • 3




              Love the intuitive explanation for it!
              – dbx
              23 hours ago






            • 1




              @Paul Since it's Newton-Raphson it'll be about $2^n$ of them, but a more detailed answer than that can't be obtained without careful analysis of the specifics of the problem. However, if you look at how which digits have "gotten stuck", you can be confident from the shrinking error terms that they won't change. See the black digits in Oleg567's comment for an example.
              – J.G.
              13 hours ago












            • 9




              Definitely one of the fastest methods: $$ y_0 = 1.colortan0;\ y_1 = 1.colortan5;\ y_2 = 1.41colortan666666666666666666666666666...;\ y_3 = 1.41421colortan568627450980392156862745...;\ y_4 = 1.41421356237colortan468991062629557889...;\ y_5 = 1.41421356237309504880168colortan962350...;\ cdots $$
              – Oleg567
              23 hours ago







            • 6




              @Oleg567 We could go even faster with post-Newton Householder methods, but the individual steps become more computationally complex. BTW the calculator you used to check that probably also used Newton-Raphson for the division.
              – J.G.
              23 hours ago






            • 2




              The beauty of this method is that the initial estimate can be way off and the method will converge quickly anyway. of course, making an educated guess to pick the initial estimate helps to reduce the number of iterations.
              – Vasya
              23 hours ago






            • 3




              Love the intuitive explanation for it!
              – dbx
              23 hours ago






            • 1




              @Paul Since it's Newton-Raphson it'll be about $2^n$ of them, but a more detailed answer than that can't be obtained without careful analysis of the specifics of the problem. However, if you look at how which digits have "gotten stuck", you can be confident from the shrinking error terms that they won't change. See the black digits in Oleg567's comment for an example.
              – J.G.
              13 hours ago







            9




            9




            Definitely one of the fastest methods: $$ y_0 = 1.colortan0;\ y_1 = 1.colortan5;\ y_2 = 1.41colortan666666666666666666666666666...;\ y_3 = 1.41421colortan568627450980392156862745...;\ y_4 = 1.41421356237colortan468991062629557889...;\ y_5 = 1.41421356237309504880168colortan962350...;\ cdots $$
            – Oleg567
            23 hours ago





            Definitely one of the fastest methods: $$ y_0 = 1.colortan0;\ y_1 = 1.colortan5;\ y_2 = 1.41colortan666666666666666666666666666...;\ y_3 = 1.41421colortan568627450980392156862745...;\ y_4 = 1.41421356237colortan468991062629557889...;\ y_5 = 1.41421356237309504880168colortan962350...;\ cdots $$
            – Oleg567
            23 hours ago





            6




            6




            @Oleg567 We could go even faster with post-Newton Householder methods, but the individual steps become more computationally complex. BTW the calculator you used to check that probably also used Newton-Raphson for the division.
            – J.G.
            23 hours ago




            @Oleg567 We could go even faster with post-Newton Householder methods, but the individual steps become more computationally complex. BTW the calculator you used to check that probably also used Newton-Raphson for the division.
            – J.G.
            23 hours ago




            2




            2




            The beauty of this method is that the initial estimate can be way off and the method will converge quickly anyway. of course, making an educated guess to pick the initial estimate helps to reduce the number of iterations.
            – Vasya
            23 hours ago




            The beauty of this method is that the initial estimate can be way off and the method will converge quickly anyway. of course, making an educated guess to pick the initial estimate helps to reduce the number of iterations.
            – Vasya
            23 hours ago




            3




            3




            Love the intuitive explanation for it!
            – dbx
            23 hours ago




            Love the intuitive explanation for it!
            – dbx
            23 hours ago




            1




            1




            @Paul Since it's Newton-Raphson it'll be about $2^n$ of them, but a more detailed answer than that can't be obtained without careful analysis of the specifics of the problem. However, if you look at how which digits have "gotten stuck", you can be confident from the shrinking error terms that they won't change. See the black digits in Oleg567's comment for an example.
            – J.G.
            13 hours ago




            @Paul Since it's Newton-Raphson it'll be about $2^n$ of them, but a more detailed answer than that can't be obtained without careful analysis of the specifics of the problem. However, if you look at how which digits have "gotten stuck", you can be confident from the shrinking error terms that they won't change. See the black digits in Oleg567's comment for an example.
            – J.G.
            13 hours ago










            up vote
            10
            down vote













            Here's the way I learnt to obtain decimal digit after decimal digit when I began middle school:



            beginarraylcl
            2&big( &colorred1.414,2dots \[1ex]
            1,00&& 24times colorred4=96<100\
            -96,&& 25times5=125>100\[1ex]
            phantom-04,00&&281timescolorred1<400\
            ;:-2,81&&282times2>400\[1ex]
            phantom-0119,00&&2824timescolorred4<11900\
            phantom0-112,96&&2825times5>11900 \[1ex]
            phantom00;604,00&&28282timescolorred2 < 60400 \
            &&28283times3> 60400
            endarray
            &c.



            Let me explain the procedure on the first two steps. It relies on a clever use of the identity $(x+y)^2=x^2+2xy+y^2$. Suppose more generally we want to find the square root of a number $a$.



            1. We first find the greatest natural number $n$ such that $n^2le a$.

            2. If $a$ is not a perfect square, i.e. if $n^2<a$, let $d$ be the first decimal digit of the square root. This is the greatest digit such that $;Bigl(n+frac d10Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
              beginalign
              Bigl(n+frac d10Bigr)^2le a&iff frac2n10d+fracd^2100<a -n^2\
              &iff (10times 2n+d)times dle (a-n^2)times 100
              endalign
              In practice, this means, we calculate the difference $a-n^2$ and add two 0s. Then we double $n$, add a digit d (this is the result of calculating $10times 2n+d$) and multiply what we obtain by this digit. Last, we test whether the result is less than $100(a-n^2)$, and retain the largest possible digit.





            share|cite|improve this answer


















            • 4




              Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
              – goblin
              9 hours ago











            • @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
              – shoover
              6 hours ago










            • @goblin: I've added an explanation for the first two steps. The following stepsruns along te same lines, only the first step is different. Hope this will make it clear.
              – Bernard
              2 hours ago










            • @Bernard, thanks.
              – goblin
              2 hours ago










            • @goblin You start off with 1 because 1 is the largest integer whoose square is less than 2. Then extend 1 by the next two digits, 00, to get 100. Now double the 1 just obtained and find the largest digit such that 2x times x is less than 100.
              – Paul Evans
              2 hours ago















            up vote
            10
            down vote













            Here's the way I learnt to obtain decimal digit after decimal digit when I began middle school:



            beginarraylcl
            2&big( &colorred1.414,2dots \[1ex]
            1,00&& 24times colorred4=96<100\
            -96,&& 25times5=125>100\[1ex]
            phantom-04,00&&281timescolorred1<400\
            ;:-2,81&&282times2>400\[1ex]
            phantom-0119,00&&2824timescolorred4<11900\
            phantom0-112,96&&2825times5>11900 \[1ex]
            phantom00;604,00&&28282timescolorred2 < 60400 \
            &&28283times3> 60400
            endarray
            &c.



            Let me explain the procedure on the first two steps. It relies on a clever use of the identity $(x+y)^2=x^2+2xy+y^2$. Suppose more generally we want to find the square root of a number $a$.



            1. We first find the greatest natural number $n$ such that $n^2le a$.

            2. If $a$ is not a perfect square, i.e. if $n^2<a$, let $d$ be the first decimal digit of the square root. This is the greatest digit such that $;Bigl(n+frac d10Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
              beginalign
              Bigl(n+frac d10Bigr)^2le a&iff frac2n10d+fracd^2100<a -n^2\
              &iff (10times 2n+d)times dle (a-n^2)times 100
              endalign
              In practice, this means, we calculate the difference $a-n^2$ and add two 0s. Then we double $n$, add a digit d (this is the result of calculating $10times 2n+d$) and multiply what we obtain by this digit. Last, we test whether the result is less than $100(a-n^2)$, and retain the largest possible digit.





            share|cite|improve this answer


















            • 4




              Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
              – goblin
              9 hours ago











            • @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
              – shoover
              6 hours ago










            • @goblin: I've added an explanation for the first two steps. The following stepsruns along te same lines, only the first step is different. Hope this will make it clear.
              – Bernard
              2 hours ago










            • @Bernard, thanks.
              – goblin
              2 hours ago










            • @goblin You start off with 1 because 1 is the largest integer whoose square is less than 2. Then extend 1 by the next two digits, 00, to get 100. Now double the 1 just obtained and find the largest digit such that 2x times x is less than 100.
              – Paul Evans
              2 hours ago













            up vote
            10
            down vote










            up vote
            10
            down vote









            Here's the way I learnt to obtain decimal digit after decimal digit when I began middle school:



            beginarraylcl
            2&big( &colorred1.414,2dots \[1ex]
            1,00&& 24times colorred4=96<100\
            -96,&& 25times5=125>100\[1ex]
            phantom-04,00&&281timescolorred1<400\
            ;:-2,81&&282times2>400\[1ex]
            phantom-0119,00&&2824timescolorred4<11900\
            phantom0-112,96&&2825times5>11900 \[1ex]
            phantom00;604,00&&28282timescolorred2 < 60400 \
            &&28283times3> 60400
            endarray
            &c.



            Let me explain the procedure on the first two steps. It relies on a clever use of the identity $(x+y)^2=x^2+2xy+y^2$. Suppose more generally we want to find the square root of a number $a$.



            1. We first find the greatest natural number $n$ such that $n^2le a$.

            2. If $a$ is not a perfect square, i.e. if $n^2<a$, let $d$ be the first decimal digit of the square root. This is the greatest digit such that $;Bigl(n+frac d10Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
              beginalign
              Bigl(n+frac d10Bigr)^2le a&iff frac2n10d+fracd^2100<a -n^2\
              &iff (10times 2n+d)times dle (a-n^2)times 100
              endalign
              In practice, this means, we calculate the difference $a-n^2$ and add two 0s. Then we double $n$, add a digit d (this is the result of calculating $10times 2n+d$) and multiply what we obtain by this digit. Last, we test whether the result is less than $100(a-n^2)$, and retain the largest possible digit.





            share|cite|improve this answer














            Here's the way I learnt to obtain decimal digit after decimal digit when I began middle school:



            beginarraylcl
            2&big( &colorred1.414,2dots \[1ex]
            1,00&& 24times colorred4=96<100\
            -96,&& 25times5=125>100\[1ex]
            phantom-04,00&&281timescolorred1<400\
            ;:-2,81&&282times2>400\[1ex]
            phantom-0119,00&&2824timescolorred4<11900\
            phantom0-112,96&&2825times5>11900 \[1ex]
            phantom00;604,00&&28282timescolorred2 < 60400 \
            &&28283times3> 60400
            endarray
            &c.



            Let me explain the procedure on the first two steps. It relies on a clever use of the identity $(x+y)^2=x^2+2xy+y^2$. Suppose more generally we want to find the square root of a number $a$.



            1. We first find the greatest natural number $n$ such that $n^2le a$.

            2. If $a$ is not a perfect square, i.e. if $n^2<a$, let $d$ be the first decimal digit of the square root. This is the greatest digit such that $;Bigl(n+frac d10Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
              beginalign
              Bigl(n+frac d10Bigr)^2le a&iff frac2n10d+fracd^2100<a -n^2\
              &iff (10times 2n+d)times dle (a-n^2)times 100
              endalign
              In practice, this means, we calculate the difference $a-n^2$ and add two 0s. Then we double $n$, add a digit d (this is the result of calculating $10times 2n+d$) and multiply what we obtain by this digit. Last, we test whether the result is less than $100(a-n^2)$, and retain the largest possible digit.






            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited 2 hours ago

























            answered 23 hours ago









            Bernard

            112k635104




            112k635104







            • 4




              Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
              – goblin
              9 hours ago











            • @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
              – shoover
              6 hours ago










            • @goblin: I've added an explanation for the first two steps. The following stepsruns along te same lines, only the first step is different. Hope this will make it clear.
              – Bernard
              2 hours ago










            • @Bernard, thanks.
              – goblin
              2 hours ago










            • @goblin You start off with 1 because 1 is the largest integer whoose square is less than 2. Then extend 1 by the next two digits, 00, to get 100. Now double the 1 just obtained and find the largest digit such that 2x times x is less than 100.
              – Paul Evans
              2 hours ago













            • 4




              Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
              – goblin
              9 hours ago











            • @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
              – shoover
              6 hours ago










            • @goblin: I've added an explanation for the first two steps. The following stepsruns along te same lines, only the first step is different. Hope this will make it clear.
              – Bernard
              2 hours ago










            • @Bernard, thanks.
              – goblin
              2 hours ago










            • @goblin You start off with 1 because 1 is the largest integer whoose square is less than 2. Then extend 1 by the next two digits, 00, to get 100. Now double the 1 just obtained and find the largest digit such that 2x times x is less than 100.
              – Paul Evans
              2 hours ago








            4




            4




            Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
            – goblin
            9 hours ago





            Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
            – goblin
            9 hours ago













            @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
            – shoover
            6 hours ago




            @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
            – shoover
            6 hours ago












            @goblin: I've added an explanation for the first two steps. The following stepsruns along te same lines, only the first step is different. Hope this will make it clear.
            – Bernard
            2 hours ago




            @goblin: I've added an explanation for the first two steps. The following stepsruns along te same lines, only the first step is different. Hope this will make it clear.
            – Bernard
            2 hours ago












            @Bernard, thanks.
            – goblin
            2 hours ago




            @Bernard, thanks.
            – goblin
            2 hours ago












            @goblin You start off with 1 because 1 is the largest integer whoose square is less than 2. Then extend 1 by the next two digits, 00, to get 100. Now double the 1 just obtained and find the largest digit such that 2x times x is less than 100.
            – Paul Evans
            2 hours ago





            @goblin You start off with 1 because 1 is the largest integer whoose square is less than 2. Then extend 1 by the next two digits, 00, to get 100. Now double the 1 just obtained and find the largest digit such that 2x times x is less than 100.
            – Paul Evans
            2 hours ago











            up vote
            5
            down vote













            The number $sqrt2$ is the solution to the equation $x^2-2=0$, so any method for numerically approximating the roots of an equation (such as the Newton method) will be able to approximate $sqrt2$.






            share|cite|improve this answer
























              up vote
              5
              down vote













              The number $sqrt2$ is the solution to the equation $x^2-2=0$, so any method for numerically approximating the roots of an equation (such as the Newton method) will be able to approximate $sqrt2$.






              share|cite|improve this answer






















                up vote
                5
                down vote










                up vote
                5
                down vote









                The number $sqrt2$ is the solution to the equation $x^2-2=0$, so any method for numerically approximating the roots of an equation (such as the Newton method) will be able to approximate $sqrt2$.






                share|cite|improve this answer












                The number $sqrt2$ is the solution to the equation $x^2-2=0$, so any method for numerically approximating the roots of an equation (such as the Newton method) will be able to approximate $sqrt2$.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered 23 hours ago









                5xum

                83k384148




                83k384148




















                    up vote
                    3
                    down vote













                    On a similar note to the answer by R. Romero: in the special case of taking the square root of an integer $N$, it is fairly straightforward to calculate the continued fraction representation of $sqrtN$.



                    In the particular case $N=2$, we have:
                    $$ sqrt2 = 1 + frac12 + frac12 + frac12 + ddots. $$
                    (This follows from the fact that if $x = sqrt2-1$, then $x = sqrt2-1 = frac1sqrt2+1 = frac12+x$.)



                    Now, from this we can calculate subsequent rational approximations to $sqrt2$:



                    $$
                    beginmatrix
                    & & 1 & 2 & 2 & 2 & 2 & 2 & cdots \
                    0 & 1 & 1 & 3 & 7 & 17 & 41 & 99 & cdots \
                    1 & 0 & 1 & 2 & 5 & 12 & 29 & 70 & cdots
                    endmatrix $$
                    So, for example $frac9970 approx 1.4142857$ whereas $sqrt2 approx 1.4142136$.



                    (It also happens that this procedure generates solutions to Pell's equation $a^2 - 2 b^2 = pm 1$; for example, $99^2 - 2 cdot 70^2 = 1$. The connection is: if $a^2 - 2 b^2 = pm 1$ then $a - b sqrt2 = pm frac1a + b sqrt2$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt2 approx pmfrac12a$ which implies $fracab - sqrt2 approx pmfrac12ab approx pmfrac1a^2sqrt2$.)






                    share|cite|improve this answer
















                    • 1




                      Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                      – goblin
                      9 hours ago














                    up vote
                    3
                    down vote













                    On a similar note to the answer by R. Romero: in the special case of taking the square root of an integer $N$, it is fairly straightforward to calculate the continued fraction representation of $sqrtN$.



                    In the particular case $N=2$, we have:
                    $$ sqrt2 = 1 + frac12 + frac12 + frac12 + ddots. $$
                    (This follows from the fact that if $x = sqrt2-1$, then $x = sqrt2-1 = frac1sqrt2+1 = frac12+x$.)



                    Now, from this we can calculate subsequent rational approximations to $sqrt2$:



                    $$
                    beginmatrix
                    & & 1 & 2 & 2 & 2 & 2 & 2 & cdots \
                    0 & 1 & 1 & 3 & 7 & 17 & 41 & 99 & cdots \
                    1 & 0 & 1 & 2 & 5 & 12 & 29 & 70 & cdots
                    endmatrix $$
                    So, for example $frac9970 approx 1.4142857$ whereas $sqrt2 approx 1.4142136$.



                    (It also happens that this procedure generates solutions to Pell's equation $a^2 - 2 b^2 = pm 1$; for example, $99^2 - 2 cdot 70^2 = 1$. The connection is: if $a^2 - 2 b^2 = pm 1$ then $a - b sqrt2 = pm frac1a + b sqrt2$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt2 approx pmfrac12a$ which implies $fracab - sqrt2 approx pmfrac12ab approx pmfrac1a^2sqrt2$.)






                    share|cite|improve this answer
















                    • 1




                      Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                      – goblin
                      9 hours ago












                    up vote
                    3
                    down vote










                    up vote
                    3
                    down vote









                    On a similar note to the answer by R. Romero: in the special case of taking the square root of an integer $N$, it is fairly straightforward to calculate the continued fraction representation of $sqrtN$.



                    In the particular case $N=2$, we have:
                    $$ sqrt2 = 1 + frac12 + frac12 + frac12 + ddots. $$
                    (This follows from the fact that if $x = sqrt2-1$, then $x = sqrt2-1 = frac1sqrt2+1 = frac12+x$.)



                    Now, from this we can calculate subsequent rational approximations to $sqrt2$:



                    $$
                    beginmatrix
                    & & 1 & 2 & 2 & 2 & 2 & 2 & cdots \
                    0 & 1 & 1 & 3 & 7 & 17 & 41 & 99 & cdots \
                    1 & 0 & 1 & 2 & 5 & 12 & 29 & 70 & cdots
                    endmatrix $$
                    So, for example $frac9970 approx 1.4142857$ whereas $sqrt2 approx 1.4142136$.



                    (It also happens that this procedure generates solutions to Pell's equation $a^2 - 2 b^2 = pm 1$; for example, $99^2 - 2 cdot 70^2 = 1$. The connection is: if $a^2 - 2 b^2 = pm 1$ then $a - b sqrt2 = pm frac1a + b sqrt2$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt2 approx pmfrac12a$ which implies $fracab - sqrt2 approx pmfrac12ab approx pmfrac1a^2sqrt2$.)






                    share|cite|improve this answer












                    On a similar note to the answer by R. Romero: in the special case of taking the square root of an integer $N$, it is fairly straightforward to calculate the continued fraction representation of $sqrtN$.



                    In the particular case $N=2$, we have:
                    $$ sqrt2 = 1 + frac12 + frac12 + frac12 + ddots. $$
                    (This follows from the fact that if $x = sqrt2-1$, then $x = sqrt2-1 = frac1sqrt2+1 = frac12+x$.)



                    Now, from this we can calculate subsequent rational approximations to $sqrt2$:



                    $$
                    beginmatrix
                    & & 1 & 2 & 2 & 2 & 2 & 2 & cdots \
                    0 & 1 & 1 & 3 & 7 & 17 & 41 & 99 & cdots \
                    1 & 0 & 1 & 2 & 5 & 12 & 29 & 70 & cdots
                    endmatrix $$
                    So, for example $frac9970 approx 1.4142857$ whereas $sqrt2 approx 1.4142136$.



                    (It also happens that this procedure generates solutions to Pell's equation $a^2 - 2 b^2 = pm 1$; for example, $99^2 - 2 cdot 70^2 = 1$. The connection is: if $a^2 - 2 b^2 = pm 1$ then $a - b sqrt2 = pm frac1a + b sqrt2$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt2 approx pmfrac12a$ which implies $fracab - sqrt2 approx pmfrac12ab approx pmfrac1a^2sqrt2$.)







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 13 hours ago









                    Daniel Schepler

                    7,1181514




                    7,1181514







                    • 1




                      Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                      – goblin
                      9 hours ago












                    • 1




                      Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                      – goblin
                      9 hours ago







                    1




                    1




                    Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                    – goblin
                    9 hours ago




                    Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                    – goblin
                    9 hours ago










                    up vote
                    1
                    down vote













                    There's a general method that converges about as quickly as Newton-Raphson but is somewhat more general. It's based off of Continued Fractions:



                    Suppose you want to find the square root of $N$. Let $a+b = N$ where $b$ has an easy to calculate square root.



                    let $y_n+1 = sqrt b + fraca sqrt b + y_n$



                    $y_n+1$ converges to $sqrt N$.






                    share|cite|improve this answer


























                      up vote
                      1
                      down vote













                      There's a general method that converges about as quickly as Newton-Raphson but is somewhat more general. It's based off of Continued Fractions:



                      Suppose you want to find the square root of $N$. Let $a+b = N$ where $b$ has an easy to calculate square root.



                      let $y_n+1 = sqrt b + fraca sqrt b + y_n$



                      $y_n+1$ converges to $sqrt N$.






                      share|cite|improve this answer
























                        up vote
                        1
                        down vote










                        up vote
                        1
                        down vote









                        There's a general method that converges about as quickly as Newton-Raphson but is somewhat more general. It's based off of Continued Fractions:



                        Suppose you want to find the square root of $N$. Let $a+b = N$ where $b$ has an easy to calculate square root.



                        let $y_n+1 = sqrt b + fraca sqrt b + y_n$



                        $y_n+1$ converges to $sqrt N$.






                        share|cite|improve this answer














                        There's a general method that converges about as quickly as Newton-Raphson but is somewhat more general. It's based off of Continued Fractions:



                        Suppose you want to find the square root of $N$. Let $a+b = N$ where $b$ has an easy to calculate square root.



                        let $y_n+1 = sqrt b + fraca sqrt b + y_n$



                        $y_n+1$ converges to $sqrt N$.







                        share|cite|improve this answer














                        share|cite|improve this answer



                        share|cite|improve this answer








                        edited 13 hours ago









                        asky

                        1318




                        1318










                        answered 15 hours ago









                        TurlocTheRed

                        695




                        695




















                            up vote
                            1
                            down vote













                            Suppose you want to find the square root of $p$ and suppose your initial guess is $x/y$:



                            Let $mathbf M=beginbmatrix 1 & p \ 1 & 1 endbmatrix$ and $mathbf q=beginpmatrix x \ y endpmatrix$
                            Then $mathbf Mmathbf Mmathbf M...mathbf q$ gives a numerator and denominator the ratio of which converges to the square root of $p$. This gives an approximation to the square root of $2$ as fast as the other methods but with no floating point arithmetic until the final division.



                            Performs well for calculation tools optimized for Matrix arithmetic. This also gives you solutions for Pell's equation for $p=2$ as mentioned by Daniel Schepler.






                            share|cite|improve this answer


























                              up vote
                              1
                              down vote













                              Suppose you want to find the square root of $p$ and suppose your initial guess is $x/y$:



                              Let $mathbf M=beginbmatrix 1 & p \ 1 & 1 endbmatrix$ and $mathbf q=beginpmatrix x \ y endpmatrix$
                              Then $mathbf Mmathbf Mmathbf M...mathbf q$ gives a numerator and denominator the ratio of which converges to the square root of $p$. This gives an approximation to the square root of $2$ as fast as the other methods but with no floating point arithmetic until the final division.



                              Performs well for calculation tools optimized for Matrix arithmetic. This also gives you solutions for Pell's equation for $p=2$ as mentioned by Daniel Schepler.






                              share|cite|improve this answer
























                                up vote
                                1
                                down vote










                                up vote
                                1
                                down vote









                                Suppose you want to find the square root of $p$ and suppose your initial guess is $x/y$:



                                Let $mathbf M=beginbmatrix 1 & p \ 1 & 1 endbmatrix$ and $mathbf q=beginpmatrix x \ y endpmatrix$
                                Then $mathbf Mmathbf Mmathbf M...mathbf q$ gives a numerator and denominator the ratio of which converges to the square root of $p$. This gives an approximation to the square root of $2$ as fast as the other methods but with no floating point arithmetic until the final division.



                                Performs well for calculation tools optimized for Matrix arithmetic. This also gives you solutions for Pell's equation for $p=2$ as mentioned by Daniel Schepler.






                                share|cite|improve this answer














                                Suppose you want to find the square root of $p$ and suppose your initial guess is $x/y$:



                                Let $mathbf M=beginbmatrix 1 & p \ 1 & 1 endbmatrix$ and $mathbf q=beginpmatrix x \ y endpmatrix$
                                Then $mathbf Mmathbf Mmathbf M...mathbf q$ gives a numerator and denominator the ratio of which converges to the square root of $p$. This gives an approximation to the square root of $2$ as fast as the other methods but with no floating point arithmetic until the final division.



                                Performs well for calculation tools optimized for Matrix arithmetic. This also gives you solutions for Pell's equation for $p=2$ as mentioned by Daniel Schepler.







                                share|cite|improve this answer














                                share|cite|improve this answer



                                share|cite|improve this answer








                                edited 8 hours ago









                                Tyberius

                                7572621




                                7572621










                                answered 10 hours ago









                                TurlocTheRed

                                695




                                695




















                                    up vote
                                    0
                                    down vote













                                    You can compute it manually using the algorithm:



                                    1. $p=0$, $r=0$, $i=0$

                                    2. Split the number into sections of two digits

                                    3. Take i'th section $n_i$, let $k=100t+n_i$

                                    4. Find the greatest number $x$, such that $$y=x(20p+x)leq k$$

                                    5. Assign $p=10 p + x$, $i=i+1$, if the accyracy of the result is not satisfied, then return to 3.

                                    Example:




                                    02.00 00 00 00 00




                                    • $n_0 = 2$, $k=2$, therefore for $x=1$: $y=1$ and $p=1$

                                    • $n_1=0$, $k=100$, so for $x=4$: $y=24*4=96<100$ and $p=14$

                                    • $n_2=0$, $k=400$, so for $x=1$, $y=281*1=281<400$ and $p=141$

                                    • $n_3=0$, $k=11900$, so for $x=4$, $y=2824*4=11296<11900$ and $p=1414$

                                    • $n_4=0$, $k=60400$, so for $x=2$, $y=28282*2=56564<60400$ and $p=14142$

                                    • $n_5=0$, $k=383600$, so for $x=1$, $y=282841*1=282841<383600$ and $p=141421$

                                    • ...

                                    After all just remember to point the comma in place, where it should be, ie. after first number (it depends how many sections were there on the left side of our number), so you'll have:
                                    $$sqrt2approx 1.41421$$



                                    To obtain accuracy of 20 numbers after the comma, you should append 20 sections of 00 in the step 2. , ie.:




                                    02.00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00







                                    share|cite|improve this answer
























                                      up vote
                                      0
                                      down vote













                                      You can compute it manually using the algorithm:



                                      1. $p=0$, $r=0$, $i=0$

                                      2. Split the number into sections of two digits

                                      3. Take i'th section $n_i$, let $k=100t+n_i$

                                      4. Find the greatest number $x$, such that $$y=x(20p+x)leq k$$

                                      5. Assign $p=10 p + x$, $i=i+1$, if the accyracy of the result is not satisfied, then return to 3.

                                      Example:




                                      02.00 00 00 00 00




                                      • $n_0 = 2$, $k=2$, therefore for $x=1$: $y=1$ and $p=1$

                                      • $n_1=0$, $k=100$, so for $x=4$: $y=24*4=96<100$ and $p=14$

                                      • $n_2=0$, $k=400$, so for $x=1$, $y=281*1=281<400$ and $p=141$

                                      • $n_3=0$, $k=11900$, so for $x=4$, $y=2824*4=11296<11900$ and $p=1414$

                                      • $n_4=0$, $k=60400$, so for $x=2$, $y=28282*2=56564<60400$ and $p=14142$

                                      • $n_5=0$, $k=383600$, so for $x=1$, $y=282841*1=282841<383600$ and $p=141421$

                                      • ...

                                      After all just remember to point the comma in place, where it should be, ie. after first number (it depends how many sections were there on the left side of our number), so you'll have:
                                      $$sqrt2approx 1.41421$$



                                      To obtain accuracy of 20 numbers after the comma, you should append 20 sections of 00 in the step 2. , ie.:




                                      02.00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00







                                      share|cite|improve this answer






















                                        up vote
                                        0
                                        down vote










                                        up vote
                                        0
                                        down vote









                                        You can compute it manually using the algorithm:



                                        1. $p=0$, $r=0$, $i=0$

                                        2. Split the number into sections of two digits

                                        3. Take i'th section $n_i$, let $k=100t+n_i$

                                        4. Find the greatest number $x$, such that $$y=x(20p+x)leq k$$

                                        5. Assign $p=10 p + x$, $i=i+1$, if the accyracy of the result is not satisfied, then return to 3.

                                        Example:




                                        02.00 00 00 00 00




                                        • $n_0 = 2$, $k=2$, therefore for $x=1$: $y=1$ and $p=1$

                                        • $n_1=0$, $k=100$, so for $x=4$: $y=24*4=96<100$ and $p=14$

                                        • $n_2=0$, $k=400$, so for $x=1$, $y=281*1=281<400$ and $p=141$

                                        • $n_3=0$, $k=11900$, so for $x=4$, $y=2824*4=11296<11900$ and $p=1414$

                                        • $n_4=0$, $k=60400$, so for $x=2$, $y=28282*2=56564<60400$ and $p=14142$

                                        • $n_5=0$, $k=383600$, so for $x=1$, $y=282841*1=282841<383600$ and $p=141421$

                                        • ...

                                        After all just remember to point the comma in place, where it should be, ie. after first number (it depends how many sections were there on the left side of our number), so you'll have:
                                        $$sqrt2approx 1.41421$$



                                        To obtain accuracy of 20 numbers after the comma, you should append 20 sections of 00 in the step 2. , ie.:




                                        02.00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00







                                        share|cite|improve this answer












                                        You can compute it manually using the algorithm:



                                        1. $p=0$, $r=0$, $i=0$

                                        2. Split the number into sections of two digits

                                        3. Take i'th section $n_i$, let $k=100t+n_i$

                                        4. Find the greatest number $x$, such that $$y=x(20p+x)leq k$$

                                        5. Assign $p=10 p + x$, $i=i+1$, if the accyracy of the result is not satisfied, then return to 3.

                                        Example:




                                        02.00 00 00 00 00




                                        • $n_0 = 2$, $k=2$, therefore for $x=1$: $y=1$ and $p=1$

                                        • $n_1=0$, $k=100$, so for $x=4$: $y=24*4=96<100$ and $p=14$

                                        • $n_2=0$, $k=400$, so for $x=1$, $y=281*1=281<400$ and $p=141$

                                        • $n_3=0$, $k=11900$, so for $x=4$, $y=2824*4=11296<11900$ and $p=1414$

                                        • $n_4=0$, $k=60400$, so for $x=2$, $y=28282*2=56564<60400$ and $p=14142$

                                        • $n_5=0$, $k=383600$, so for $x=1$, $y=282841*1=282841<383600$ and $p=141421$

                                        • ...

                                        After all just remember to point the comma in place, where it should be, ie. after first number (it depends how many sections were there on the left side of our number), so you'll have:
                                        $$sqrt2approx 1.41421$$



                                        To obtain accuracy of 20 numbers after the comma, you should append 20 sections of 00 in the step 2. , ie.:




                                        02.00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00








                                        share|cite|improve this answer












                                        share|cite|improve this answer



                                        share|cite|improve this answer










                                        answered 22 hours ago









                                        Jaroslaw Matlak

                                        3,948830




                                        3,948830




















                                            up vote
                                            0
                                            down vote













                                            Using the fact that $sin fracpi4 = fracsqrt22$, then we have to find $2 sin fracpi4$.



                                            We can approximate $sin x$ using the Taylor series to three terms:



                                            $$sin x = x - fracx^33! + fracx^55! + O(x^6),$$



                                            so we have:



                                            $$sin fracpi4 approx fracpi4 - frac(pi/4)^33! + frac(pi/4)^55! .$$



                                            If we approximate $pi$ as $frac227$, then we have $fracpi4 = frac1114$, then we have:



                                            $$sin fracpi4 approxfrac1114 - frac(11/14)^33! + frac(11/14)^55!,$$



                                            which when you multiply by $2$ to get $sqrt2$, gives $1.4147$, while the actual value is $1.4142$.



                                            If we expand the Taylor series to more terms, or improve the approximation of $pi$ (such as $frac355113$), then we can get to $20$ correct digits.






                                            share|cite|improve this answer
















                                            • 1




                                              Don’t you need pi to nearly 20 digits for this to work?
                                              – JoeTaxpayer
                                              9 hours ago














                                            up vote
                                            0
                                            down vote













                                            Using the fact that $sin fracpi4 = fracsqrt22$, then we have to find $2 sin fracpi4$.



                                            We can approximate $sin x$ using the Taylor series to three terms:



                                            $$sin x = x - fracx^33! + fracx^55! + O(x^6),$$



                                            so we have:



                                            $$sin fracpi4 approx fracpi4 - frac(pi/4)^33! + frac(pi/4)^55! .$$



                                            If we approximate $pi$ as $frac227$, then we have $fracpi4 = frac1114$, then we have:



                                            $$sin fracpi4 approxfrac1114 - frac(11/14)^33! + frac(11/14)^55!,$$



                                            which when you multiply by $2$ to get $sqrt2$, gives $1.4147$, while the actual value is $1.4142$.



                                            If we expand the Taylor series to more terms, or improve the approximation of $pi$ (such as $frac355113$), then we can get to $20$ correct digits.






                                            share|cite|improve this answer
















                                            • 1




                                              Don’t you need pi to nearly 20 digits for this to work?
                                              – JoeTaxpayer
                                              9 hours ago












                                            up vote
                                            0
                                            down vote










                                            up vote
                                            0
                                            down vote









                                            Using the fact that $sin fracpi4 = fracsqrt22$, then we have to find $2 sin fracpi4$.



                                            We can approximate $sin x$ using the Taylor series to three terms:



                                            $$sin x = x - fracx^33! + fracx^55! + O(x^6),$$



                                            so we have:



                                            $$sin fracpi4 approx fracpi4 - frac(pi/4)^33! + frac(pi/4)^55! .$$



                                            If we approximate $pi$ as $frac227$, then we have $fracpi4 = frac1114$, then we have:



                                            $$sin fracpi4 approxfrac1114 - frac(11/14)^33! + frac(11/14)^55!,$$



                                            which when you multiply by $2$ to get $sqrt2$, gives $1.4147$, while the actual value is $1.4142$.



                                            If we expand the Taylor series to more terms, or improve the approximation of $pi$ (such as $frac355113$), then we can get to $20$ correct digits.






                                            share|cite|improve this answer












                                            Using the fact that $sin fracpi4 = fracsqrt22$, then we have to find $2 sin fracpi4$.



                                            We can approximate $sin x$ using the Taylor series to three terms:



                                            $$sin x = x - fracx^33! + fracx^55! + O(x^6),$$



                                            so we have:



                                            $$sin fracpi4 approx fracpi4 - frac(pi/4)^33! + frac(pi/4)^55! .$$



                                            If we approximate $pi$ as $frac227$, then we have $fracpi4 = frac1114$, then we have:



                                            $$sin fracpi4 approxfrac1114 - frac(11/14)^33! + frac(11/14)^55!,$$



                                            which when you multiply by $2$ to get $sqrt2$, gives $1.4147$, while the actual value is $1.4142$.



                                            If we expand the Taylor series to more terms, or improve the approximation of $pi$ (such as $frac355113$), then we can get to $20$ correct digits.







                                            share|cite|improve this answer












                                            share|cite|improve this answer



                                            share|cite|improve this answer










                                            answered 22 hours ago









                                            Toby Mak

                                            2,8651925




                                            2,8651925







                                            • 1




                                              Don’t you need pi to nearly 20 digits for this to work?
                                              – JoeTaxpayer
                                              9 hours ago












                                            • 1




                                              Don’t you need pi to nearly 20 digits for this to work?
                                              – JoeTaxpayer
                                              9 hours ago







                                            1




                                            1




                                            Don’t you need pi to nearly 20 digits for this to work?
                                            – JoeTaxpayer
                                            9 hours ago




                                            Don’t you need pi to nearly 20 digits for this to work?
                                            – JoeTaxpayer
                                            9 hours ago










                                            up vote
                                            0
                                            down vote













                                            Let us start with an initial guess $x$ for the square root of $2$. Then add a correction term $y$. Write down $(x+y)^2 - 2 = 0$. Solve this equation for $y$ by expanding it up to third order in the difference $(2-x^2)$. This is a straightforward calculation. Combining all contributions, the result is simple and elegant:



                                            $$y = (x^4+12x^2+4)/(4x^3+8x)$$



                                            For a rational initial guess $x$ the result $y$ is also rational, but far more close to the desired value. For example if we take $x = 3/2$, then $y=577/408$, which differs from the square root of 2 by a factor 1.0000015.






                                            share|cite|improve this answer
























                                              up vote
                                              0
                                              down vote













                                              Let us start with an initial guess $x$ for the square root of $2$. Then add a correction term $y$. Write down $(x+y)^2 - 2 = 0$. Solve this equation for $y$ by expanding it up to third order in the difference $(2-x^2)$. This is a straightforward calculation. Combining all contributions, the result is simple and elegant:



                                              $$y = (x^4+12x^2+4)/(4x^3+8x)$$



                                              For a rational initial guess $x$ the result $y$ is also rational, but far more close to the desired value. For example if we take $x = 3/2$, then $y=577/408$, which differs from the square root of 2 by a factor 1.0000015.






                                              share|cite|improve this answer






















                                                up vote
                                                0
                                                down vote










                                                up vote
                                                0
                                                down vote









                                                Let us start with an initial guess $x$ for the square root of $2$. Then add a correction term $y$. Write down $(x+y)^2 - 2 = 0$. Solve this equation for $y$ by expanding it up to third order in the difference $(2-x^2)$. This is a straightforward calculation. Combining all contributions, the result is simple and elegant:



                                                $$y = (x^4+12x^2+4)/(4x^3+8x)$$



                                                For a rational initial guess $x$ the result $y$ is also rational, but far more close to the desired value. For example if we take $x = 3/2$, then $y=577/408$, which differs from the square root of 2 by a factor 1.0000015.






                                                share|cite|improve this answer












                                                Let us start with an initial guess $x$ for the square root of $2$. Then add a correction term $y$. Write down $(x+y)^2 - 2 = 0$. Solve this equation for $y$ by expanding it up to third order in the difference $(2-x^2)$. This is a straightforward calculation. Combining all contributions, the result is simple and elegant:



                                                $$y = (x^4+12x^2+4)/(4x^3+8x)$$



                                                For a rational initial guess $x$ the result $y$ is also rational, but far more close to the desired value. For example if we take $x = 3/2$, then $y=577/408$, which differs from the square root of 2 by a factor 1.0000015.







                                                share|cite|improve this answer












                                                share|cite|improve this answer



                                                share|cite|improve this answer










                                                answered 6 hours ago









                                                M. Wind

                                                1,874715




                                                1,874715




















                                                    up vote
                                                    0
                                                    down vote













                                                    Newton-Rhapson is a good idea because of the convergence rate. However, I am more of a fan of using Taylor's expansions here since it is super easy to derive on the go to give fairly ok estimates in quite a reasonable time. So, the way to go to find $sqrtx$ is to find first the closest integer which approximates $sqrtx$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                    $$ sqrtx approx a + (x-a^2)cdot frac12 a - (x-a^2)^2/2 cdot frac14 a^3 + cdots. $$
                                                    The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrtx$, then the error of a $n$th order approximation (i.e., going as far as $(x-a^2)^n/n! cdot f^(n)(a^2)$ in the approximation above) is given by $$ (x-a)^n+1/(n+1)! cdot f^(n+1)(xi)$$ for a certain $xi$ between $a^2$ and $x$. This can be estimated quite easily since this $f^(n+1)$ is monotone around $x$. Thus look at the boundaries of the domain of $xi$ and find the 'best' maximal value which you can calculate without a calculator.



                                                    Example for $x=2$. Apparently $1$ is the closest integer to $sqrt2$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                    $$sqrt2 approx 1 + (2-1)cdot frac12 - (2-1)^2/2cdot frac14 = 1 + 0.5 - 0.125 = 1.375 $$
                                                    and the absolute error is given by
                                                    $$ E=left|(2-1)^3/3!cdot frac38 cdot xi^2sqrtxiright| = frac116 cdot frac1$$
                                                    for a certain $xi$ between $1$ and $2$. Since this is a decreasing function on $(1,2)$. The maximum is attained at $1$ and hence the error is bounded by
                                                    $$ E leq frac116 $$
                                                    which seems to be a good estimate since $E = 0.039dots$ and $1/16 = 0.0625$.



                                                    Edit As some of you noted this method 'looks' more difficult than Newton-Rhapson and the convergence is slower. The last part is obviously true and I would answer this question with: How quick do you need it to be and do you want to calculate it in your head or do you have a computer? Do you need to have a quick guess which is approximately equal to the value of $sqrt2$ or do you need a precise estimate. If you don't have a computer but pen and paper, the best method is Newton-Rhapson.

                                                    I would argue that my method is better if you don't have pen and paper or a computer and you are asked to give an estimation of $sqrt10$ on the go (especially for $sqrtx$ with $x$ big, the Taylor approximation is better since the $sqrtbullet$ function becomes more linear as $x$ grows).

                                                    I agree that my method looks way more difficult but it isn't if you get more familiar with it. Also, this method is super quick in terms of calculation time in your head and if you practice a little with it, it becomes way easier. Also, this method works particularly nice for $sqrtx$ where $x$ differs one from a perfect square because then the $(x-a^2)^n$ term will always be one.

                                                    Let's look at an example here. Suppose you need to calculate $sqrt122$, then first order approximation of my method gives
                                                    $$ sqrt122 approx 11 + frac12cdot 11. $$
                                                    It took me less than one second to find this approximation and the second order approximation works almost as quick here. You just need to add $frac-18cdot 11^3$. Please note that the error of the first order approximation here is approximately equal to $10^-4$.

                                                    If you apply Newton-Rhapson here you get the same approximation after one step if you choose $x_0=11$. The only thing is that I always forget what the exact form is of Newton-Rhapson. So when I want to apply it, I have to think about it where I could have immediately applied Taylor but I would say that is just my particular preference.






                                                    share|cite|improve this answer


















                                                    • 2




                                                      I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                      – leftaroundabout
                                                      21 hours ago











                                                    • I would say it is less difficult since when you apply Newton-Rhapson you always have to find the exact algorithm and this method can be applied to find $sqrt2.243$ also quite quickly.
                                                      – Stan Tendijck
                                                      20 hours ago










                                                    • I agree with @leftaroundabout, but perhaps if you edit into your post an illustration of how this method could be used by hand to compute rad 2 to high accuracy, it would appear simpler. Right now, it looks much more difficult.
                                                      – Wildcard
                                                      17 hours ago






                                                    • 2




                                                      Taylor's converges much more slowly than Newton Raphson. Note the second order term starting with initial guess 1 is 1.4166.... already correct to two digits behind the decimal. You might get an additional correct digit at each step of the calculation heavy Taylor series. The accuracy doubles per step for Newton Raphson without the difficulty of calculating the Taylor coefficients. There might be ways to patch it up. There's an alternative series to the Taylor series for arctan that converges much faster than Taylor.
                                                      – TurlocTheRed
                                                      9 hours ago














                                                    up vote
                                                    0
                                                    down vote













                                                    Newton-Rhapson is a good idea because of the convergence rate. However, I am more of a fan of using Taylor's expansions here since it is super easy to derive on the go to give fairly ok estimates in quite a reasonable time. So, the way to go to find $sqrtx$ is to find first the closest integer which approximates $sqrtx$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                    $$ sqrtx approx a + (x-a^2)cdot frac12 a - (x-a^2)^2/2 cdot frac14 a^3 + cdots. $$
                                                    The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrtx$, then the error of a $n$th order approximation (i.e., going as far as $(x-a^2)^n/n! cdot f^(n)(a^2)$ in the approximation above) is given by $$ (x-a)^n+1/(n+1)! cdot f^(n+1)(xi)$$ for a certain $xi$ between $a^2$ and $x$. This can be estimated quite easily since this $f^(n+1)$ is monotone around $x$. Thus look at the boundaries of the domain of $xi$ and find the 'best' maximal value which you can calculate without a calculator.



                                                    Example for $x=2$. Apparently $1$ is the closest integer to $sqrt2$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                    $$sqrt2 approx 1 + (2-1)cdot frac12 - (2-1)^2/2cdot frac14 = 1 + 0.5 - 0.125 = 1.375 $$
                                                    and the absolute error is given by
                                                    $$ E=left|(2-1)^3/3!cdot frac38 cdot xi^2sqrtxiright| = frac116 cdot frac1$$
                                                    for a certain $xi$ between $1$ and $2$. Since this is a decreasing function on $(1,2)$. The maximum is attained at $1$ and hence the error is bounded by
                                                    $$ E leq frac116 $$
                                                    which seems to be a good estimate since $E = 0.039dots$ and $1/16 = 0.0625$.



                                                    Edit As some of you noted this method 'looks' more difficult than Newton-Rhapson and the convergence is slower. The last part is obviously true and I would answer this question with: How quick do you need it to be and do you want to calculate it in your head or do you have a computer? Do you need to have a quick guess which is approximately equal to the value of $sqrt2$ or do you need a precise estimate. If you don't have a computer but pen and paper, the best method is Newton-Rhapson.

                                                    I would argue that my method is better if you don't have pen and paper or a computer and you are asked to give an estimation of $sqrt10$ on the go (especially for $sqrtx$ with $x$ big, the Taylor approximation is better since the $sqrtbullet$ function becomes more linear as $x$ grows).

                                                    I agree that my method looks way more difficult but it isn't if you get more familiar with it. Also, this method is super quick in terms of calculation time in your head and if you practice a little with it, it becomes way easier. Also, this method works particularly nice for $sqrtx$ where $x$ differs one from a perfect square because then the $(x-a^2)^n$ term will always be one.

                                                    Let's look at an example here. Suppose you need to calculate $sqrt122$, then first order approximation of my method gives
                                                    $$ sqrt122 approx 11 + frac12cdot 11. $$
                                                    It took me less than one second to find this approximation and the second order approximation works almost as quick here. You just need to add $frac-18cdot 11^3$. Please note that the error of the first order approximation here is approximately equal to $10^-4$.

                                                    If you apply Newton-Rhapson here you get the same approximation after one step if you choose $x_0=11$. The only thing is that I always forget what the exact form is of Newton-Rhapson. So when I want to apply it, I have to think about it where I could have immediately applied Taylor but I would say that is just my particular preference.






                                                    share|cite|improve this answer


















                                                    • 2




                                                      I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                      – leftaroundabout
                                                      21 hours ago











                                                    • I would say it is less difficult since when you apply Newton-Rhapson you always have to find the exact algorithm and this method can be applied to find $sqrt2.243$ also quite quickly.
                                                      – Stan Tendijck
                                                      20 hours ago










                                                    • I agree with @leftaroundabout, but perhaps if you edit into your post an illustration of how this method could be used by hand to compute rad 2 to high accuracy, it would appear simpler. Right now, it looks much more difficult.
                                                      – Wildcard
                                                      17 hours ago






                                                    • 2




                                                      Taylor's converges much more slowly than Newton Raphson. Note the second order term starting with initial guess 1 is 1.4166.... already correct to two digits behind the decimal. You might get an additional correct digit at each step of the calculation heavy Taylor series. The accuracy doubles per step for Newton Raphson without the difficulty of calculating the Taylor coefficients. There might be ways to patch it up. There's an alternative series to the Taylor series for arctan that converges much faster than Taylor.
                                                      – TurlocTheRed
                                                      9 hours ago












                                                    up vote
                                                    0
                                                    down vote










                                                    up vote
                                                    0
                                                    down vote









                                                    Newton-Rhapson is a good idea because of the convergence rate. However, I am more of a fan of using Taylor's expansions here since it is super easy to derive on the go to give fairly ok estimates in quite a reasonable time. So, the way to go to find $sqrtx$ is to find first the closest integer which approximates $sqrtx$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                    $$ sqrtx approx a + (x-a^2)cdot frac12 a - (x-a^2)^2/2 cdot frac14 a^3 + cdots. $$
                                                    The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrtx$, then the error of a $n$th order approximation (i.e., going as far as $(x-a^2)^n/n! cdot f^(n)(a^2)$ in the approximation above) is given by $$ (x-a)^n+1/(n+1)! cdot f^(n+1)(xi)$$ for a certain $xi$ between $a^2$ and $x$. This can be estimated quite easily since this $f^(n+1)$ is monotone around $x$. Thus look at the boundaries of the domain of $xi$ and find the 'best' maximal value which you can calculate without a calculator.



                                                    Example for $x=2$. Apparently $1$ is the closest integer to $sqrt2$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                    $$sqrt2 approx 1 + (2-1)cdot frac12 - (2-1)^2/2cdot frac14 = 1 + 0.5 - 0.125 = 1.375 $$
                                                    and the absolute error is given by
                                                    $$ E=left|(2-1)^3/3!cdot frac38 cdot xi^2sqrtxiright| = frac116 cdot frac1$$
                                                    for a certain $xi$ between $1$ and $2$. Since this is a decreasing function on $(1,2)$. The maximum is attained at $1$ and hence the error is bounded by
                                                    $$ E leq frac116 $$
                                                    which seems to be a good estimate since $E = 0.039dots$ and $1/16 = 0.0625$.



                                                    Edit As some of you noted this method 'looks' more difficult than Newton-Rhapson and the convergence is slower. The last part is obviously true and I would answer this question with: How quick do you need it to be and do you want to calculate it in your head or do you have a computer? Do you need to have a quick guess which is approximately equal to the value of $sqrt2$ or do you need a precise estimate. If you don't have a computer but pen and paper, the best method is Newton-Rhapson.

                                                    I would argue that my method is better if you don't have pen and paper or a computer and you are asked to give an estimation of $sqrt10$ on the go (especially for $sqrtx$ with $x$ big, the Taylor approximation is better since the $sqrtbullet$ function becomes more linear as $x$ grows).

                                                    I agree that my method looks way more difficult but it isn't if you get more familiar with it. Also, this method is super quick in terms of calculation time in your head and if you practice a little with it, it becomes way easier. Also, this method works particularly nice for $sqrtx$ where $x$ differs one from a perfect square because then the $(x-a^2)^n$ term will always be one.

                                                    Let's look at an example here. Suppose you need to calculate $sqrt122$, then first order approximation of my method gives
                                                    $$ sqrt122 approx 11 + frac12cdot 11. $$
                                                    It took me less than one second to find this approximation and the second order approximation works almost as quick here. You just need to add $frac-18cdot 11^3$. Please note that the error of the first order approximation here is approximately equal to $10^-4$.

                                                    If you apply Newton-Rhapson here you get the same approximation after one step if you choose $x_0=11$. The only thing is that I always forget what the exact form is of Newton-Rhapson. So when I want to apply it, I have to think about it where I could have immediately applied Taylor but I would say that is just my particular preference.






                                                    share|cite|improve this answer














                                                    Newton-Rhapson is a good idea because of the convergence rate. However, I am more of a fan of using Taylor's expansions here since it is super easy to derive on the go to give fairly ok estimates in quite a reasonable time. So, the way to go to find $sqrtx$ is to find first the closest integer which approximates $sqrtx$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                    $$ sqrtx approx a + (x-a^2)cdot frac12 a - (x-a^2)^2/2 cdot frac14 a^3 + cdots. $$
                                                    The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrtx$, then the error of a $n$th order approximation (i.e., going as far as $(x-a^2)^n/n! cdot f^(n)(a^2)$ in the approximation above) is given by $$ (x-a)^n+1/(n+1)! cdot f^(n+1)(xi)$$ for a certain $xi$ between $a^2$ and $x$. This can be estimated quite easily since this $f^(n+1)$ is monotone around $x$. Thus look at the boundaries of the domain of $xi$ and find the 'best' maximal value which you can calculate without a calculator.



                                                    Example for $x=2$. Apparently $1$ is the closest integer to $sqrt2$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                    $$sqrt2 approx 1 + (2-1)cdot frac12 - (2-1)^2/2cdot frac14 = 1 + 0.5 - 0.125 = 1.375 $$
                                                    and the absolute error is given by
                                                    $$ E=left|(2-1)^3/3!cdot frac38 cdot xi^2sqrtxiright| = frac116 cdot frac1$$
                                                    for a certain $xi$ between $1$ and $2$. Since this is a decreasing function on $(1,2)$. The maximum is attained at $1$ and hence the error is bounded by
                                                    $$ E leq frac116 $$
                                                    which seems to be a good estimate since $E = 0.039dots$ and $1/16 = 0.0625$.



                                                    Edit As some of you noted this method 'looks' more difficult than Newton-Rhapson and the convergence is slower. The last part is obviously true and I would answer this question with: How quick do you need it to be and do you want to calculate it in your head or do you have a computer? Do you need to have a quick guess which is approximately equal to the value of $sqrt2$ or do you need a precise estimate. If you don't have a computer but pen and paper, the best method is Newton-Rhapson.

                                                    I would argue that my method is better if you don't have pen and paper or a computer and you are asked to give an estimation of $sqrt10$ on the go (especially for $sqrtx$ with $x$ big, the Taylor approximation is better since the $sqrtbullet$ function becomes more linear as $x$ grows).

                                                    I agree that my method looks way more difficult but it isn't if you get more familiar with it. Also, this method is super quick in terms of calculation time in your head and if you practice a little with it, it becomes way easier. Also, this method works particularly nice for $sqrtx$ where $x$ differs one from a perfect square because then the $(x-a^2)^n$ term will always be one.

                                                    Let's look at an example here. Suppose you need to calculate $sqrt122$, then first order approximation of my method gives
                                                    $$ sqrt122 approx 11 + frac12cdot 11. $$
                                                    It took me less than one second to find this approximation and the second order approximation works almost as quick here. You just need to add $frac-18cdot 11^3$. Please note that the error of the first order approximation here is approximately equal to $10^-4$.

                                                    If you apply Newton-Rhapson here you get the same approximation after one step if you choose $x_0=11$. The only thing is that I always forget what the exact form is of Newton-Rhapson. So when I want to apply it, I have to think about it where I could have immediately applied Taylor but I would say that is just my particular preference.







                                                    share|cite|improve this answer














                                                    share|cite|improve this answer



                                                    share|cite|improve this answer








                                                    edited 46 mins ago

























                                                    answered 23 hours ago









                                                    Stan Tendijck

                                                    1,301110




                                                    1,301110







                                                    • 2




                                                      I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                      – leftaroundabout
                                                      21 hours ago











                                                    • I would say it is less difficult since when you apply Newton-Rhapson you always have to find the exact algorithm and this method can be applied to find $sqrt2.243$ also quite quickly.
                                                      – Stan Tendijck
                                                      20 hours ago










                                                    • I agree with @leftaroundabout, but perhaps if you edit into your post an illustration of how this method could be used by hand to compute rad 2 to high accuracy, it would appear simpler. Right now, it looks much more difficult.
                                                      – Wildcard
                                                      17 hours ago






                                                    • 2




                                                      Taylor's converges much more slowly than Newton Raphson. Note the second order term starting with initial guess 1 is 1.4166.... already correct to two digits behind the decimal. You might get an additional correct digit at each step of the calculation heavy Taylor series. The accuracy doubles per step for Newton Raphson without the difficulty of calculating the Taylor coefficients. There might be ways to patch it up. There's an alternative series to the Taylor series for arctan that converges much faster than Taylor.
                                                      – TurlocTheRed
                                                      9 hours ago












                                                    • 2




                                                      I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                      – leftaroundabout
                                                      21 hours ago











                                                    • I would say it is less difficult since when you apply Newton-Rhapson you always have to find the exact algorithm and this method can be applied to find $sqrt2.243$ also quite quickly.
                                                      – Stan Tendijck
                                                      20 hours ago










                                                    • I agree with @leftaroundabout, but perhaps if you edit into your post an illustration of how this method could be used by hand to compute rad 2 to high accuracy, it would appear simpler. Right now, it looks much more difficult.
                                                      – Wildcard
                                                      17 hours ago






                                                    • 2




                                                      Taylor's converges much more slowly than Newton Raphson. Note the second order term starting with initial guess 1 is 1.4166.... already correct to two digits behind the decimal. You might get an additional correct digit at each step of the calculation heavy Taylor series. The accuracy doubles per step for Newton Raphson without the difficulty of calculating the Taylor coefficients. There might be ways to patch it up. There's an alternative series to the Taylor series for arctan that converges much faster than Taylor.
                                                      – TurlocTheRed
                                                      9 hours ago







                                                    2




                                                    2




                                                    I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                    – leftaroundabout
                                                    21 hours ago





                                                    I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                    – leftaroundabout
                                                    21 hours ago













                                                    I would say it is less difficult since when you apply Newton-Rhapson you always have to find the exact algorithm and this method can be applied to find $sqrt2.243$ also quite quickly.
                                                    – Stan Tendijck
                                                    20 hours ago




                                                    I would say it is less difficult since when you apply Newton-Rhapson you always have to find the exact algorithm and this method can be applied to find $sqrt2.243$ also quite quickly.
                                                    – Stan Tendijck
                                                    20 hours ago












                                                    I agree with @leftaroundabout, but perhaps if you edit into your post an illustration of how this method could be used by hand to compute rad 2 to high accuracy, it would appear simpler. Right now, it looks much more difficult.
                                                    – Wildcard
                                                    17 hours ago




                                                    I agree with @leftaroundabout, but perhaps if you edit into your post an illustration of how this method could be used by hand to compute rad 2 to high accuracy, it would appear simpler. Right now, it looks much more difficult.
                                                    – Wildcard
                                                    17 hours ago




                                                    2




                                                    2




                                                    Taylor's converges much more slowly than Newton Raphson. Note the second order term starting with initial guess 1 is 1.4166.... already correct to two digits behind the decimal. You might get an additional correct digit at each step of the calculation heavy Taylor series. The accuracy doubles per step for Newton Raphson without the difficulty of calculating the Taylor coefficients. There might be ways to patch it up. There's an alternative series to the Taylor series for arctan that converges much faster than Taylor.
                                                    – TurlocTheRed
                                                    9 hours ago




                                                    Taylor's converges much more slowly than Newton Raphson. Note the second order term starting with initial guess 1 is 1.4166.... already correct to two digits behind the decimal. You might get an additional correct digit at each step of the calculation heavy Taylor series. The accuracy doubles per step for Newton Raphson without the difficulty of calculating the Taylor coefficients. There might be ways to patch it up. There's an alternative series to the Taylor series for arctan that converges much faster than Taylor.
                                                    – TurlocTheRed
                                                    9 hours ago

















                                                     

                                                    draft saved


                                                    draft discarded















































                                                     


                                                    draft saved


                                                    draft discarded














                                                    StackExchange.ready(
                                                    function ()
                                                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2916718%2fcalculating-the-square-root-of-2%23new-answer', 'question_page');

                                                    );

                                                    Post as a guest













































































                                                    Comments

                                                    Popular posts from this blog

                                                    What does second last employer means? [closed]

                                                    Installing NextGIS Connect into QGIS 3?

                                                    One-line joke