Calculating the square root of 2












24












$begingroup$


Since $sqrt{2}$ 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 $sqrt{2}$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



begin{align}
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
end{align}



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











$endgroup$








  • 4




    $begingroup$
    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.
    $endgroup$
    – Gibbs
    Sep 14 '18 at 12:14






  • 2




    $begingroup$
    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    $endgroup$
    – lhf
    Sep 14 '18 at 12:17










  • $begingroup$
    @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    $endgroup$
    – MMJM
    Sep 14 '18 at 12:21






  • 2




    $begingroup$
    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.
    $endgroup$
    – user202729
    Sep 14 '18 at 15:22






  • 1




    $begingroup$
    @Gibbs Please don't post answers as comments.
    $endgroup$
    – David Richerby
    Sep 14 '18 at 18:44
















24












$begingroup$


Since $sqrt{2}$ 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 $sqrt{2}$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



begin{align}
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
end{align}



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











$endgroup$








  • 4




    $begingroup$
    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.
    $endgroup$
    – Gibbs
    Sep 14 '18 at 12:14






  • 2




    $begingroup$
    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    $endgroup$
    – lhf
    Sep 14 '18 at 12:17










  • $begingroup$
    @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    $endgroup$
    – MMJM
    Sep 14 '18 at 12:21






  • 2




    $begingroup$
    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.
    $endgroup$
    – user202729
    Sep 14 '18 at 15:22






  • 1




    $begingroup$
    @Gibbs Please don't post answers as comments.
    $endgroup$
    – David Richerby
    Sep 14 '18 at 18:44














24












24








24


9



$begingroup$


Since $sqrt{2}$ 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 $sqrt{2}$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



begin{align}
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
end{align}



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











$endgroup$




Since $sqrt{2}$ 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 $sqrt{2}$ by calculating iteratively so that it would not go to 3 so fast. It looks like this:



begin{align}
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
end{align}



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 Sep 15 '18 at 11:36









amWhy

1




1










asked Sep 14 '18 at 12:10









MMJMMMJM

3351111




3351111








  • 4




    $begingroup$
    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.
    $endgroup$
    – Gibbs
    Sep 14 '18 at 12:14






  • 2




    $begingroup$
    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    $endgroup$
    – lhf
    Sep 14 '18 at 12:17










  • $begingroup$
    @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    $endgroup$
    – MMJM
    Sep 14 '18 at 12:21






  • 2




    $begingroup$
    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.
    $endgroup$
    – user202729
    Sep 14 '18 at 15:22






  • 1




    $begingroup$
    @Gibbs Please don't post answers as comments.
    $endgroup$
    – David Richerby
    Sep 14 '18 at 18:44














  • 4




    $begingroup$
    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.
    $endgroup$
    – Gibbs
    Sep 14 '18 at 12:14






  • 2




    $begingroup$
    See en.wikipedia.org/wiki/Methods_of_computing_square_roots
    $endgroup$
    – lhf
    Sep 14 '18 at 12:17










  • $begingroup$
    @Gibbs I tried that so far. But the reason is that it takes more time to compute it.
    $endgroup$
    – MMJM
    Sep 14 '18 at 12:21






  • 2




    $begingroup$
    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.
    $endgroup$
    – user202729
    Sep 14 '18 at 15:22






  • 1




    $begingroup$
    @Gibbs Please don't post answers as comments.
    $endgroup$
    – David Richerby
    Sep 14 '18 at 18:44








4




4




$begingroup$
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.
$endgroup$
– Gibbs
Sep 14 '18 at 12:14




$begingroup$
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.
$endgroup$
– Gibbs
Sep 14 '18 at 12:14




2




2




$begingroup$
See en.wikipedia.org/wiki/Methods_of_computing_square_roots
$endgroup$
– lhf
Sep 14 '18 at 12:17




$begingroup$
See en.wikipedia.org/wiki/Methods_of_computing_square_roots
$endgroup$
– lhf
Sep 14 '18 at 12:17












$begingroup$
@Gibbs I tried that so far. But the reason is that it takes more time to compute it.
$endgroup$
– MMJM
Sep 14 '18 at 12:21




$begingroup$
@Gibbs I tried that so far. But the reason is that it takes more time to compute it.
$endgroup$
– MMJM
Sep 14 '18 at 12:21




2




2




$begingroup$
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.
$endgroup$
– user202729
Sep 14 '18 at 15:22




$begingroup$
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.
$endgroup$
– user202729
Sep 14 '18 at 15:22




1




1




$begingroup$
@Gibbs Please don't post answers as comments.
$endgroup$
– David Richerby
Sep 14 '18 at 18:44




$begingroup$
@Gibbs Please don't post answers as comments.
$endgroup$
– David Richerby
Sep 14 '18 at 18:44










16 Answers
16






active

oldest

votes


















42












$begingroup$

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 $ynesqrt{x}$ then $y,,x/y$ will be on opposite sides of $sqrt{x}$, and we could try averaging them. So try $y_0=1,,y_{n+1}=frac{1}{2}(y_n+frac{x}{y_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











$endgroup$









  • 14




    $begingroup$
    Definitely one of the fastest methods: $$ y_0 = 1.color{tan}{0};\ y_1 = 1.color{tan}{5};\ y_2 = 1.41color{tan}{666666666666666666666666666...};\ y_3 = 1.41421color{tan}{568627450980392156862745...};\ y_4 = 1.41421356237color{tan}{468991062629557889...};\ y_5 = 1.41421356237309504880168color{tan}{962350...};\ cdots $$
    $endgroup$
    – Oleg567
    Sep 14 '18 at 12:26








  • 6




    $begingroup$
    @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.
    $endgroup$
    – J.G.
    Sep 14 '18 at 12:30






  • 2




    $begingroup$
    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.
    $endgroup$
    – Vasya
    Sep 14 '18 at 12:32






  • 3




    $begingroup$
    Love the intuitive explanation for it!
    $endgroup$
    – dbx
    Sep 14 '18 at 12:52






  • 1




    $begingroup$
    @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.
    $endgroup$
    – J.G.
    Sep 14 '18 at 22:04



















19












$begingroup$

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



begin{array}{lcl}
2&big( &color{red}1.414,2dots \[1ex]
1,00&& 24times color{red}4=96<100\
-96,&& 25times5=125>100\[1ex]
phantom{-0}4,00&&281timescolor{red}1<400\
;:-2,81&&282times2>400\[1ex]
phantom{-0}119,00&&2824timescolor{red}4<11900\
phantom{0}{-}112,96&&2825times5>11900 \[1ex]
phantom{00;}604,00&&28282timescolor{red}2 < 60400 \
&&28283times3> 60400
end{array}
&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 d{10}Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
    begin{align}
    Bigl(n+frac d{10}Bigr)^2le a&iff frac{2n}{10}d+frac{d^2}{100}<a -n^2\
    &iff (10times 2n+d)times dle (a-n^2)times 100
    end{align}
    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











$endgroup$









  • 4




    $begingroup$
    Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
    $endgroup$
    – goblin
    Sep 15 '18 at 1:57












  • $begingroup$
    @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
    $endgroup$
    – shoover
    Sep 15 '18 at 5:21










  • $begingroup$
    @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.
    $endgroup$
    – Bernard
    Sep 15 '18 at 9:24










  • $begingroup$
    @Bernard, thanks.
    $endgroup$
    – goblin
    Sep 15 '18 at 9:39










  • $begingroup$
    @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.
    $endgroup$
    – Paul Evans
    Sep 15 '18 at 9:41





















7












$begingroup$

The number $sqrt{2}$ 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 $sqrt{2}$.






share|cite|improve this answer









$endgroup$









  • 4




    $begingroup$
    I don't see how this qualifies as an answer. It is just a general statement.
    $endgroup$
    – M. Wind
    Sep 16 '18 at 5:29



















6












$begingroup$

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 $sqrt{N}$.



In the particular case $N=2$, we have:
$$ sqrt{2} = 1 + frac{1}{2 + frac{1}{2 + frac{1}{2 + ddots}}}. $$
(This follows from the fact that if $x = sqrt{2}-1$, then $x = sqrt{2}-1 = frac{1}{sqrt{2}+1} = frac{1}{2+x}$.)



Now, from this we can calculate subsequent rational approximations to $sqrt{2}$:



$$
begin{matrix}
& & 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
end{matrix} $$
So, for example $frac{99}{70} approx 1.4142857$ whereas $sqrt{2} 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 sqrt{2} = pm frac{1}{a + b sqrt{2}}$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt{2} approx pmfrac{1}{2a}$ which implies $frac{a}{b} - sqrt{2} approx pmfrac{1}{2ab} approx pmfrac{1}{a^2sqrt{2}}$.)






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
    $endgroup$
    – goblin
    Sep 15 '18 at 2:00










  • $begingroup$
    Once you see the first few rational approximations it's easy to guess and prove the recursion for $p/q$, namely, $p_n = p_{n-1} + 2q_{n-1}$, $q_n = p_{n-1} + q_{n-1}$..See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Pell%27s_equation
    $endgroup$
    – Ethan Bolker
    Sep 15 '18 at 13:13



















5












$begingroup$

Okay, I searched through the answers, but none seems to mention this one: long quadratic root calculation.



From the name it is obvious that it resembles long division, like this:



$$
begin{align}
sqrt{2.00;00;00;00;..}
end{align}
$$



Notice how they are grouped into tuples. Now estimate the first digit, namely $1$:



$$
begin{align}
&~~~1.\
1&sqrt{2.00;00;00;00;..}\
&~~~1\
&~~~overline{1,00}
end{align}
$$



We calculate $1times1=1$, write it down, and calculate the "remainder", just like divisions. Notice that we append 2 digits behind instead of 1.



Next, double the number on the top, and write it on the left of $1,00$:



$$
begin{align}
&~~~1.;*\
1&sqrt{2.00;00;00;00;..}\
&~~~1\
2*&,,|overline{1,00}
end{align}
$$



Now we estimate the next digit, *. It is written both on the top and to the left. Of course, we know that it is 4, so:



$$
begin{align}
&~~~1.;4;;;*\
1&sqrt{2.00;00;00;00;..}\
&~~~1\
24&,,|overline{1,00}\
&,,|,,,,96\
&2overline{8{*}|,4,00}
end{align}
$$



We double the numbers on the top again to get $28*$, and repeat the process:



$$
begin{align}
&~~~1.;4;;;1\
1&sqrt{2.00;00;00;00;..}\
&~~~1\
24&,,|overline{1,00}\
&,,|,,,,96\
&2overline{8{1}|,4,00}\
&,,,,,,,,,|,2,81
end{align}
$$



I found a picture, but not of $sqrt{2}$:



sqrt(7)



This is extremely inefficient for computers, but great for manual calculation. After all, we don't do multiplication through fast Fourier transforms!



Also, this method is developed in ancient China.






share|cite|improve this answer









$endgroup$





















    4












    $begingroup$

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



    Let $mathbf M=begin{bmatrix} 1 & p \ 1 & 1 end{bmatrix}$ and $mathbf q=begin{pmatrix} x \ y end{pmatrix}$
    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











    $endgroup$





















      1












      $begingroup$

      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 + frac{a}{ sqrt b + y_n}$



      $y_{n+1}$ converges to $sqrt N$.






      share|cite|improve this answer











      $endgroup$





















        1












        $begingroup$

        In this answer, there is a method using continued fraction approximations for $sqrt2$ and the generating function for the central binomial coefficients to get some very quickly convergent series for $sqrt2$. For example,
        $$
        sqrt2=frac75sum_{k=0}^inftybinom{2k}{k}frac1{200^k}tag1
        $$
        and
        $$
        sqrt2=frac{239}{169}sum_{k=0}^inftybinom{2k}{k}frac1{228488^k}tag2
        $$





        For example, summing to $k=4$ in $(2)$ gives
        $$
        sqrt2=1.414213562373095048801688
        $$
        which is accurate to $23$ places.






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          (+) This method could be used to calculate millions of $sqrt{2}$ digits (especially when notice that the series has rational terms, and apply en.wikipedia.org/wiki/Binary_splitting technique).
          $endgroup$
          – Oleg567
          Sep 24 '18 at 4:44










        • $begingroup$
          Good description of the elementary school method. You are not likely to succeed unless you do at least one square root every day. After age 75, you have to do more than one every day. That is why there are calculators.
          $endgroup$
          – richard1941
          Sep 24 '18 at 23:53



















        1












        $begingroup$

        Binary search for it.



        Since $1 < 2 < 4$, we must have $sqrt{1} < sqrt{2} < sqrt{4}$, so $sqrt{2} in (1,2)$. Now repeatedly: find the midpoint, $m$, of the current interval, $(a,b)$, square $m$ and compare with $2$, and if $2 = m^2$ declare that $m = sqrt{2}$, or if $2 < m^2$, make the new interval $(a,m)$, otherwise make the new interval $(m,b)$. This process halves the size of the interval on each step. Since $log_2(10^{-20}) = -66.438dots$, after 67 doublings, the error in taking any value from the interval is $<10^{-20}$ (but, if the interval straddles a digit change, you may have to perform additional steps to find out on which side of the change is $sqrt{2}$).



        This process is shown in the table below. Each decimal number is computed to $21$ digits and has trailing zeroes stripped. If there are still $21$ digits, a space is inserted between the $20^text{th}$ and $21^text{st}$.



        begin{align}
        text{step} && text{interval} && m && m^2 \
        1 && (1., 2.) && 1.5 && 2<2.25 \
        2 && (1., 1.5) && 1.25 && 1.5625<2 \
        3 && (1.25, 1.5) && 1.375 && 1.890625<2 \
        4 && (1.375, 1.5) && 1.4375 && 2<2.06640625 \
        5 && (1.375, 1.4375) && 1.40625 && 1.9775390625<2 \
        6 && (1.40625, 1.4375) && 1.421875 && 2<2.021728515625 \
        7 && (1.40625, 1.421875) && 1.4140625 && 1.99957275390625<2 \
        8 && (1.4140625, 1.421875) && 1.41796875 && 2<2.0106353759765625 \
        9 && (1.4140625, 1.41796875) && 1.416015625 && 2<2.005100250244140625
        \
        10 && (1.4140625, 1.416015625) && 1.4150390625 &&
        2<2.00233554840087890625 \
        11 && (1.4140625, 1.4150390625) && 1.41455078125 &&
        2<2.00095391273498535156 3 \
        12 && (1.4140625, 1.41455078125) && 1.414306640625 &&
        2<2.00026327371597290039 \
        13 && (1.4140625, 1.414306640625) && 1.4141845703125 &&
        1.99991799890995025634 8<2 \
        14 && (1.4141845703125, 1.414306640625) && 1.41424560546875 &&
        2<2.00009063258767127990 7 \
        15 && (1.4141845703125, 1.41424560546875) && 1.414215087890625 &&
        2<2.00000431481748819351 2 \
        16 && (1.4141845703125, 1.414215087890625) && 1.4141998291015625 &&
        1.99996115663088858127 6<2 \
        17 && (1.4141998291015625, 1.414215087890625) && 1.41420745849609375 &&
        1.99998273566598072648<2 \
        18 && (1.41420745849609375, 1.414215087890625) &&
        1.414211273193359375 && 1.99999352522718254476 8<2 \
        19 && (1.414211273193359375, 1.414215087890625) &&
        1.4142131805419921875 && 1.99999892001869739033 3<2 \
        20 && (1.4142131805419921875, 1.414215087890625) &&
        1.41421413421630859375 && 2<2.00000161741718329722
        end{align}begin{align}
        21 && (1.4142131805419921875, 1.41421413421630859375) &&
        1.41421365737915039062 5 && 2<2.00000026871771297010 1 \
        22 && (1.4142131805419921875, 1.41421365737915039062 5) &&
        1.41421341896057128906 2 && 1.99999959436814833679 8<2 \
        23 && (1.41421341896057128906 2, 1.41421365737915039062 5) &&
        1.41421353816986083984 4 && 1.99999993154291644259 5<2 \
        24 && (1.41421353816986083984 4, 1.41421365737915039062 5) &&
        1.41421359777450561523 4 && 2<2.00000010013031115363 4 \
        25 && (1.41421353816986083984 4, 1.41421359777450561523 4) &&
        1.41421356797218322753 9 && 2<2.00000001583661290993 6 \
        26 && (1.41421353816986083984 4, 1.41421356797218322753 9) &&
        1.41421355307102203369 1 && 1.99999997368976445422 1<2 \
        27 && (1.41421355307102203369 1, 1.41421356797218322753 9) &&
        1.41421356052160263061 5 && 1.99999999476318862656 8<2 \
        28 && (1.41421356052160263061 5, 1.41421356797218322753 9) &&
        1.41421356424689292907 7 && 2<2.00000000529990075437 4 \
        29 && (1.41421356052160263061 5, 1.41421356424689292907 7) &&
        1.41421356238424777984 6 && 2<2.00000000003154468700 1 \
        30 && (1.41421356052160263061 5, 1.41421356238424777984 6) &&
        1.41421356145292520523 && 1.99999999739736665591 7<2 \
        31 && (1.41421356145292520523, 1.41421356238424777984 6) &&
        1.41421356191858649253 8 && 1.99999999871445567124 2<2 \
        32 && (1.41421356191858649253 8, 1.41421356238424777984 6) &&
        1.41421356215141713619 2 && 1.99999999937300017906 8<2 \
        33 && (1.41421356215141713619 2, 1.41421356238424777984 6) &&
        1.41421356226783245801 9 && 1.99999999970227243302 1<2 \
        34 && (1.41421356226783245801 9, 1.41421356238424777984 6) &&
        1.41421356232604011893 3 && 1.99999999986690856000 8<2 \
        35 && (1.41421356232604011893 3, 1.41421356238424777984 6) &&
        1.41421356235514394938 9 && 1.99999999994922662350 4<2
        end{align}begin{align}
        36 && (1.41421356235514394938 9, 1.41421356238424777984 6) &&
        1.41421356236969586461 8 && 1.99999999999038565525 2<2 \
        37 && (1.41421356236969586461 8, 1.41421356238424777984 6) &&
        1.41421356237697182223 2 && 2<2.00000000001096517112 7 \
        38 && (1.41421356236969586461 8, 1.41421356237697182223 2) &&
        1.41421356237333384342 5 && 2<2.00000000000067541319 0 \
        39 && (1.41421356236969586461 8, 1.41421356237333384342 5) &&
        1.41421356237151485402 1 && 1.99999999999553053422 1<2 \
        40 && (1.41421356237151485402 1, 1.41421356237333384342 5) &&
        1.41421356237242434872 3 && 1.99999999999810297370 5<2 \
        41 && (1.41421356237242434872 3, 1.41421356237333384342 5) &&
        1.41421356237287909607 4 && 1.99999999999938919344 7<2 \
        42 && (1.41421356237287909607 4, 1.41421356237333384342 5) &&
        1.41421356237310646974 9 && 2<2.00000000000003230331 9 \
        43 && (1.41421356237287909607 4, 1.41421356237310646974 9) &&
        1.41421356237299278291 2 && 1.99999999999971074838 3<2 \
        44 && (1.41421356237299278291 2, 1.41421356237310646974 9) &&
        1.41421356237304962633 && 1.99999999999987152585<2 \
        45 && (1.41421356237304962633, 1.41421356237310646974 9) &&
        1.41421356237307804804 && 1.99999999999995191458 5<2 \
        46 && (1.41421356237307804804, 1.41421356237310646974 9) &&
        1.41421356237309225889 5 && 1.99999999999999210895 2<2 \
        47 && (1.41421356237309225889 5, 1.41421356237310646974 9) &&
        1.41421356237309936432 2 && 2<2.00000000000001220613 5 \
        48 && (1.41421356237309225889 5, 1.41421356237309936432 2) &&
        1.41421356237309581160 8 && 2<2.00000000000000215754 3 \
        49 && (1.41421356237309225889 5, 1.41421356237309581160 8) &&
        1.41421356237309403525 2 && 1.99999999999999713324 7<2 \
        50 && (1.41421356237309403525 2, 1.41421356237309581160 8) &&
        1.41421356237309492343 && 1.99999999999999964539 5<2 \
        51 && (1.41421356237309492343, 1.41421356237309581160 8) &&
        1.41421356237309536751 9 && 2<2.00000000000000090146 9 \
        52 && (1.41421356237309492343, 1.41421356237309536751 9) &&
        1.41421356237309514547 5 && 2<2.00000000000000027343 2 \
        53 && (1.41421356237309492343, 1.41421356237309514547 5) &&
        1.41421356237309503445 2 && 1.99999999999999995941 4<2 \
        54 && (1.41421356237309503445 2, 1.41421356237309514547 5) &&
        1.41421356237309508996 3 && 2<2.00000000000000011642 3 \
        55 && (1.41421356237309503445 2, 1.41421356237309508996 3) &&
        1.41421356237309506220 8 && 2<2.00000000000000003791 8 \
        56 && (1.41421356237309503445 2, 1.41421356237309506220 8) &&
        1.41421356237309504833 && 1.99999999999999999866 6<2 \
        57 && (1.41421356237309504833, 1.41421356237309506220 8) &&
        1.41421356237309505526 9 && 2<2.00000000000000001829 2 \
        58 && (1.41421356237309504833, 1.41421356237309505526 9) &&
        1.41421356237309505180 0 && 2<2.00000000000000000847 9 \
        59 && (1.41421356237309504833, 1.41421356237309505180 0) &&
        1.41421356237309505006 5 && 2<2.00000000000000000357 3 \
        60 && (1.41421356237309504833, 1.41421356237309505006 5) &&
        1.41421356237309504919 7 && 2<2.00000000000000000111 9 \
        61 && (1.41421356237309504833, 1.41421356237309504919 7) &&
        1.41421356237309504876 4 && 1.99999999999999999989 3<2 \
        62 && (1.41421356237309504876 4, 1.41421356237309504919 7) &&
        1.41421356237309504898 && 2<2.00000000000000000050 6 \
        63 && (1.41421356237309504876 4, 1.41421356237309504898) &&
        1.41421356237309504887 2 && 2<2.00000000000000000019 9 \
        64 && (1.41421356237309504876 4, 1.41421356237309504887 2) &&
        1.41421356237309504881 8 && 2<2.00000000000000000004 6 \
        65 && (1.41421356237309504876 4, 1.41421356237309504881 8) &&
        1.41421356237309504879 && 1.99999999999999999996 9<2 \
        66 && (1.41421356237309504879, 1.41421356237309504881 8) &&
        1.41421356237309504880 4 && 2<2.00000000000000000000 8 \
        67 && (1.41421356237309504879, 1.41421356237309504880 4) &&
        1.41421356237309504879 8 && 1.99999999999999999998 9<2 \
        68 && (1.41421356237309504879 8, 1.41421356237309504880 4) &&
        1.41421356237309504880 1 && 1.99999999999999999999 8<2 \
        69 && (1.41421356237309504880 1, 1.41421356237309504880 4) &&
        1.41421356237309504880 3 && 2<2.00000000000000000000 3
        end{align}






        share|cite|improve this answer









        $endgroup$





















          1












          $begingroup$

          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 elegant:



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



          For a rational initial guess $x$ the result $(x + y)$ is also rational, but much closer to the desired value.



          For example if we take $x = 3/2$, then $(x +y)=577/408$, which differs from the square root of 2 by a factor 1.0000015. If we start with $x = 7/5$, the result is $19601/13860$, which differs from the square of root of $2$ by a factor $1.0000000013$






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Please show what happens with 140/99. I find the error to be 1.2 10^-18 on my WP-34s iPhone emulator in double precision mode (good to at least 30 digits). If you recycle 577/408, you get an error 9.0 10^-25. That meets to goal of 20 digits. Recycling 19601/13860 gives an error of absolute zero (on the calculator).
            $endgroup$
            – richard1941
            Dec 21 '18 at 17:50










          • $begingroup$
            Thanks! The initial values $99/70$ and $140/99$ both result in $768398401/543339720$.
            $endgroup$
            – M. Wind
            Dec 23 '18 at 19:39





















          0












          $begingroup$

          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:
          $$sqrt{2}approx 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









          $endgroup$





















            0












            $begingroup$

            Using the fact that $sin frac{pi}{4} = frac{sqrt{2}}{2}$, then we have to find $2 sin frac{pi}{4}$.



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



            $$sin x = x - frac{x^3}{3!} + frac{x^5}{5!} + O(x^6),$$



            so we have:



            $$sin frac{pi}{4} approx frac{pi}{4} - frac{(pi/4)^3}{3!} + frac{(pi/4)^5}{5!} .$$



            If we approximate $pi$ as $frac{22}{7}$, then we have $frac{pi}{4} = frac{11}{14}$, then we have:



            $$sin frac{pi}{4} approxfrac{11}{14} - frac{(11/14)^3}{3!} + frac{(11/14)^5}{5!},$$



            which when you multiply by $2$ to get $sqrt{2}$, 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 $frac{355}{113}$), then we can get to $20$ correct digits.






            share|cite|improve this answer









            $endgroup$









            • 1




              $begingroup$
              Don’t you need pi to nearly 20 digits for this to work?
              $endgroup$
              – JoeTaxpayer
              Sep 15 '18 at 2:10



















            0












            $begingroup$

            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 $sqrt{x}$ is to find first the closest integer which approximates $sqrt{x}$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
            $$ sqrt{x} approx a + (x-a^2)cdot frac{1}{2 a} - (x-a^2)^2/2 cdot frac{1}{4 a^3} + cdots. $$
            The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrt{x}$, 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 $sqrt{2}$ and thus we will take $a=1$. Then, let's take a second order approximation
            $$sqrt{2} approx 1 + (2-1)cdot frac{1}{2} - (2-1)^2/2cdot frac{1}{4} = 1 + 0.5 - 0.125 = 1.375 $$
            and the absolute error is given by
            $$ E=left|(2-1)^3/3!cdot frac{3}{8 cdot xi^2sqrt{xi}}right| = frac{1}{16} cdot frac{1}{|xi^2sqrt{xi}|}$$
            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 frac{1}{16} $$
            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 $sqrt{2}$ 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 $sqrt{10}$ on the go (especially for $sqrt{x}$ with $x$ big, the Taylor approximation is better since the $sqrt{bullet}$ 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 $sqrt{x}$ 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 $sqrt{122}$, then first order approximation of my method gives
            $$ sqrt{122} approx 11 + frac{1}{2cdot 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{-1}{8cdot 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











            $endgroup$









            • 2




              $begingroup$
              I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
              $endgroup$
              – leftaroundabout
              Sep 14 '18 at 14:48












            • $begingroup$
              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 $sqrt{2.243}$ also quite quickly.
              $endgroup$
              – Stan Tendijck
              Sep 14 '18 at 15:38










            • $begingroup$
              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.
              $endgroup$
              – Wildcard
              Sep 14 '18 at 18:17






            • 3




              $begingroup$
              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.
              $endgroup$
              – TurlocTheRed
              Sep 15 '18 at 2:09



















            0












            $begingroup$

            I came up with an interesting, but terribly inefficient method.



            Consider the sequence {$x_n$}: $1,frac{1}{2},frac{1}{2},frac{1}{3},frac{1}{3},frac{1}{3},frac{1}{4},frac{1}{4},frac{1}{4},frac{1}{4}$, ...



            Suppose you want k digits of the square root of 2. Then add up the first $100^k$ terms and then divide the sum by $10^k$.






            share|cite|improve this answer









            $endgroup$





















              0












              $begingroup$

              I know an easy way to calculate the binary digits of $sqrt{2}$. Take the ordered pair (1, 2) $1^2$ is less than 2 and $2^2$ is more than 2. Calculate the square of the average $1.5^2$ in base 2. The square of the average is just the average of the squares minus $frac{1}{4}$. The result expressed in binary is 10.01 so the first binary digit after the decimal is 0. Take the next ordered pair to be (1, 1.5) and calculate the square of its average which is the average of its squares minus $frac{1}{16}$. The result expressed in binary is 1.1001 so the next binary digit is 1.






              share|cite|improve this answer









              $endgroup$





















                0












                $begingroup$

                Towers' bisection method above is similar to your own approach, but more efficient. Another method that is not as good as binary search, but is better than your own method, is to increment the last digit in bigger steps. I would try incrementing by 3. The worst case is that you reach the correct digit in 5 steps instead of 9.



                My favorite method for mental approximation is to find the next lowest square, determine the error, and add to its square root the error divided by double the guess. For sqrt(200), the lowest square is 196. The error is 4, so my mental estimate is 14 + 4/14 = 14.142857...



                I apologize for off-topic, but note that square roots can be used to calculate logarithms by a process similar to bisection. I suspect that is how it was done in the late 16th century, as they did not yet have calculus. In our times, there are extremely accurate formulas for logarithm that still require square roots. This exercise should make you appreciate the power of a square root button on a calculator, even if you have no "scientific" functions.






                share|cite|improve this answer









                $endgroup$












                  protected by cactus314 Sep 30 '18 at 16:59



                  Thank you for your interest in this question.
                  Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



                  Would you like to answer one of these unanswered questions instead?














                  16 Answers
                  16






                  active

                  oldest

                  votes








                  16 Answers
                  16






                  active

                  oldest

                  votes









                  active

                  oldest

                  votes






                  active

                  oldest

                  votes









                  42












                  $begingroup$

                  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 $ynesqrt{x}$ then $y,,x/y$ will be on opposite sides of $sqrt{x}$, and we could try averaging them. So try $y_0=1,,y_{n+1}=frac{1}{2}(y_n+frac{x}{y_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











                  $endgroup$









                  • 14




                    $begingroup$
                    Definitely one of the fastest methods: $$ y_0 = 1.color{tan}{0};\ y_1 = 1.color{tan}{5};\ y_2 = 1.41color{tan}{666666666666666666666666666...};\ y_3 = 1.41421color{tan}{568627450980392156862745...};\ y_4 = 1.41421356237color{tan}{468991062629557889...};\ y_5 = 1.41421356237309504880168color{tan}{962350...};\ cdots $$
                    $endgroup$
                    – Oleg567
                    Sep 14 '18 at 12:26








                  • 6




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 12:30






                  • 2




                    $begingroup$
                    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.
                    $endgroup$
                    – Vasya
                    Sep 14 '18 at 12:32






                  • 3




                    $begingroup$
                    Love the intuitive explanation for it!
                    $endgroup$
                    – dbx
                    Sep 14 '18 at 12:52






                  • 1




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 22:04
















                  42












                  $begingroup$

                  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 $ynesqrt{x}$ then $y,,x/y$ will be on opposite sides of $sqrt{x}$, and we could try averaging them. So try $y_0=1,,y_{n+1}=frac{1}{2}(y_n+frac{x}{y_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











                  $endgroup$









                  • 14




                    $begingroup$
                    Definitely one of the fastest methods: $$ y_0 = 1.color{tan}{0};\ y_1 = 1.color{tan}{5};\ y_2 = 1.41color{tan}{666666666666666666666666666...};\ y_3 = 1.41421color{tan}{568627450980392156862745...};\ y_4 = 1.41421356237color{tan}{468991062629557889...};\ y_5 = 1.41421356237309504880168color{tan}{962350...};\ cdots $$
                    $endgroup$
                    – Oleg567
                    Sep 14 '18 at 12:26








                  • 6




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 12:30






                  • 2




                    $begingroup$
                    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.
                    $endgroup$
                    – Vasya
                    Sep 14 '18 at 12:32






                  • 3




                    $begingroup$
                    Love the intuitive explanation for it!
                    $endgroup$
                    – dbx
                    Sep 14 '18 at 12:52






                  • 1




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 22:04














                  42












                  42








                  42





                  $begingroup$

                  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 $ynesqrt{x}$ then $y,,x/y$ will be on opposite sides of $sqrt{x}$, and we could try averaging them. So try $y_0=1,,y_{n+1}=frac{1}{2}(y_n+frac{x}{y_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











                  $endgroup$



                  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 $ynesqrt{x}$ then $y,,x/y$ will be on opposite sides of $sqrt{x}$, and we could try averaging them. So try $y_0=1,,y_{n+1}=frac{1}{2}(y_n+frac{x}{y_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








                  edited Dec 19 '18 at 9:44









                  Björn Friedrich

                  2,67961831




                  2,67961831










                  answered Sep 14 '18 at 12:17









                  J.G.J.G.

                  28.2k22844




                  28.2k22844








                  • 14




                    $begingroup$
                    Definitely one of the fastest methods: $$ y_0 = 1.color{tan}{0};\ y_1 = 1.color{tan}{5};\ y_2 = 1.41color{tan}{666666666666666666666666666...};\ y_3 = 1.41421color{tan}{568627450980392156862745...};\ y_4 = 1.41421356237color{tan}{468991062629557889...};\ y_5 = 1.41421356237309504880168color{tan}{962350...};\ cdots $$
                    $endgroup$
                    – Oleg567
                    Sep 14 '18 at 12:26








                  • 6




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 12:30






                  • 2




                    $begingroup$
                    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.
                    $endgroup$
                    – Vasya
                    Sep 14 '18 at 12:32






                  • 3




                    $begingroup$
                    Love the intuitive explanation for it!
                    $endgroup$
                    – dbx
                    Sep 14 '18 at 12:52






                  • 1




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 22:04














                  • 14




                    $begingroup$
                    Definitely one of the fastest methods: $$ y_0 = 1.color{tan}{0};\ y_1 = 1.color{tan}{5};\ y_2 = 1.41color{tan}{666666666666666666666666666...};\ y_3 = 1.41421color{tan}{568627450980392156862745...};\ y_4 = 1.41421356237color{tan}{468991062629557889...};\ y_5 = 1.41421356237309504880168color{tan}{962350...};\ cdots $$
                    $endgroup$
                    – Oleg567
                    Sep 14 '18 at 12:26








                  • 6




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 12:30






                  • 2




                    $begingroup$
                    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.
                    $endgroup$
                    – Vasya
                    Sep 14 '18 at 12:32






                  • 3




                    $begingroup$
                    Love the intuitive explanation for it!
                    $endgroup$
                    – dbx
                    Sep 14 '18 at 12:52






                  • 1




                    $begingroup$
                    @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.
                    $endgroup$
                    – J.G.
                    Sep 14 '18 at 22:04








                  14




                  14




                  $begingroup$
                  Definitely one of the fastest methods: $$ y_0 = 1.color{tan}{0};\ y_1 = 1.color{tan}{5};\ y_2 = 1.41color{tan}{666666666666666666666666666...};\ y_3 = 1.41421color{tan}{568627450980392156862745...};\ y_4 = 1.41421356237color{tan}{468991062629557889...};\ y_5 = 1.41421356237309504880168color{tan}{962350...};\ cdots $$
                  $endgroup$
                  – Oleg567
                  Sep 14 '18 at 12:26






                  $begingroup$
                  Definitely one of the fastest methods: $$ y_0 = 1.color{tan}{0};\ y_1 = 1.color{tan}{5};\ y_2 = 1.41color{tan}{666666666666666666666666666...};\ y_3 = 1.41421color{tan}{568627450980392156862745...};\ y_4 = 1.41421356237color{tan}{468991062629557889...};\ y_5 = 1.41421356237309504880168color{tan}{962350...};\ cdots $$
                  $endgroup$
                  – Oleg567
                  Sep 14 '18 at 12:26






                  6




                  6




                  $begingroup$
                  @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.
                  $endgroup$
                  – J.G.
                  Sep 14 '18 at 12:30




                  $begingroup$
                  @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.
                  $endgroup$
                  – J.G.
                  Sep 14 '18 at 12:30




                  2




                  2




                  $begingroup$
                  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.
                  $endgroup$
                  – Vasya
                  Sep 14 '18 at 12:32




                  $begingroup$
                  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.
                  $endgroup$
                  – Vasya
                  Sep 14 '18 at 12:32




                  3




                  3




                  $begingroup$
                  Love the intuitive explanation for it!
                  $endgroup$
                  – dbx
                  Sep 14 '18 at 12:52




                  $begingroup$
                  Love the intuitive explanation for it!
                  $endgroup$
                  – dbx
                  Sep 14 '18 at 12:52




                  1




                  1




                  $begingroup$
                  @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.
                  $endgroup$
                  – J.G.
                  Sep 14 '18 at 22:04




                  $begingroup$
                  @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.
                  $endgroup$
                  – J.G.
                  Sep 14 '18 at 22:04











                  19












                  $begingroup$

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



                  begin{array}{lcl}
                  2&big( &color{red}1.414,2dots \[1ex]
                  1,00&& 24times color{red}4=96<100\
                  -96,&& 25times5=125>100\[1ex]
                  phantom{-0}4,00&&281timescolor{red}1<400\
                  ;:-2,81&&282times2>400\[1ex]
                  phantom{-0}119,00&&2824timescolor{red}4<11900\
                  phantom{0}{-}112,96&&2825times5>11900 \[1ex]
                  phantom{00;}604,00&&28282timescolor{red}2 < 60400 \
                  &&28283times3> 60400
                  end{array}
                  &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 d{10}Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
                    begin{align}
                    Bigl(n+frac d{10}Bigr)^2le a&iff frac{2n}{10}d+frac{d^2}{100}<a -n^2\
                    &iff (10times 2n+d)times dle (a-n^2)times 100
                    end{align}
                    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











                  $endgroup$









                  • 4




                    $begingroup$
                    Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 1:57












                  • $begingroup$
                    @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
                    $endgroup$
                    – shoover
                    Sep 15 '18 at 5:21










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Bernard
                    Sep 15 '18 at 9:24










                  • $begingroup$
                    @Bernard, thanks.
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 9:39










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Paul Evans
                    Sep 15 '18 at 9:41


















                  19












                  $begingroup$

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



                  begin{array}{lcl}
                  2&big( &color{red}1.414,2dots \[1ex]
                  1,00&& 24times color{red}4=96<100\
                  -96,&& 25times5=125>100\[1ex]
                  phantom{-0}4,00&&281timescolor{red}1<400\
                  ;:-2,81&&282times2>400\[1ex]
                  phantom{-0}119,00&&2824timescolor{red}4<11900\
                  phantom{0}{-}112,96&&2825times5>11900 \[1ex]
                  phantom{00;}604,00&&28282timescolor{red}2 < 60400 \
                  &&28283times3> 60400
                  end{array}
                  &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 d{10}Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
                    begin{align}
                    Bigl(n+frac d{10}Bigr)^2le a&iff frac{2n}{10}d+frac{d^2}{100}<a -n^2\
                    &iff (10times 2n+d)times dle (a-n^2)times 100
                    end{align}
                    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











                  $endgroup$









                  • 4




                    $begingroup$
                    Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 1:57












                  • $begingroup$
                    @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
                    $endgroup$
                    – shoover
                    Sep 15 '18 at 5:21










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Bernard
                    Sep 15 '18 at 9:24










                  • $begingroup$
                    @Bernard, thanks.
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 9:39










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Paul Evans
                    Sep 15 '18 at 9:41
















                  19












                  19








                  19





                  $begingroup$

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



                  begin{array}{lcl}
                  2&big( &color{red}1.414,2dots \[1ex]
                  1,00&& 24times color{red}4=96<100\
                  -96,&& 25times5=125>100\[1ex]
                  phantom{-0}4,00&&281timescolor{red}1<400\
                  ;:-2,81&&282times2>400\[1ex]
                  phantom{-0}119,00&&2824timescolor{red}4<11900\
                  phantom{0}{-}112,96&&2825times5>11900 \[1ex]
                  phantom{00;}604,00&&28282timescolor{red}2 < 60400 \
                  &&28283times3> 60400
                  end{array}
                  &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 d{10}Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
                    begin{align}
                    Bigl(n+frac d{10}Bigr)^2le a&iff frac{2n}{10}d+frac{d^2}{100}<a -n^2\
                    &iff (10times 2n+d)times dle (a-n^2)times 100
                    end{align}
                    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











                  $endgroup$



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



                  begin{array}{lcl}
                  2&big( &color{red}1.414,2dots \[1ex]
                  1,00&& 24times color{red}4=96<100\
                  -96,&& 25times5=125>100\[1ex]
                  phantom{-0}4,00&&281timescolor{red}1<400\
                  ;:-2,81&&282times2>400\[1ex]
                  phantom{-0}119,00&&2824timescolor{red}4<11900\
                  phantom{0}{-}112,96&&2825times5>11900 \[1ex]
                  phantom{00;}604,00&&28282timescolor{red}2 < 60400 \
                  &&28283times3> 60400
                  end{array}
                  &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 d{10}Bigr)^2le a$. We'll transform this inequality into a more easy-to-use test:
                    begin{align}
                    Bigl(n+frac d{10}Bigr)^2le a&iff frac{2n}{10}d+frac{d^2}{100}<a -n^2\
                    &iff (10times 2n+d)times dle (a-n^2)times 100
                    end{align}
                    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 Sep 15 '18 at 9:43

























                  answered Sep 14 '18 at 12:55









                  BernardBernard

                  122k740116




                  122k740116








                  • 4




                    $begingroup$
                    Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 1:57












                  • $begingroup$
                    @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
                    $endgroup$
                    – shoover
                    Sep 15 '18 at 5:21










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Bernard
                    Sep 15 '18 at 9:24










                  • $begingroup$
                    @Bernard, thanks.
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 9:39










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Paul Evans
                    Sep 15 '18 at 9:41
















                  • 4




                    $begingroup$
                    Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 1:57












                  • $begingroup$
                    @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
                    $endgroup$
                    – shoover
                    Sep 15 '18 at 5:21










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Bernard
                    Sep 15 '18 at 9:24










                  • $begingroup$
                    @Bernard, thanks.
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 9:39










                  • $begingroup$
                    @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.
                    $endgroup$
                    – Paul Evans
                    Sep 15 '18 at 9:41










                  4




                  4




                  $begingroup$
                  Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
                  $endgroup$
                  – goblin
                  Sep 15 '18 at 1:57






                  $begingroup$
                  Looks interesting, can you talk us through it a bit? I don't really get it. e.g. where does 100 come from?
                  $endgroup$
                  – goblin
                  Sep 15 '18 at 1:57














                  $begingroup$
                  @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
                  $endgroup$
                  – shoover
                  Sep 15 '18 at 5:21




                  $begingroup$
                  @goblin, There are some references for this method at math.stackexchange.com/a/538055/117057 and math.stackexchange.com/q/376365/117057
                  $endgroup$
                  – shoover
                  Sep 15 '18 at 5:21












                  $begingroup$
                  @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.
                  $endgroup$
                  – Bernard
                  Sep 15 '18 at 9:24




                  $begingroup$
                  @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.
                  $endgroup$
                  – Bernard
                  Sep 15 '18 at 9:24












                  $begingroup$
                  @Bernard, thanks.
                  $endgroup$
                  – goblin
                  Sep 15 '18 at 9:39




                  $begingroup$
                  @Bernard, thanks.
                  $endgroup$
                  – goblin
                  Sep 15 '18 at 9:39












                  $begingroup$
                  @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.
                  $endgroup$
                  – Paul Evans
                  Sep 15 '18 at 9:41






                  $begingroup$
                  @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.
                  $endgroup$
                  – Paul Evans
                  Sep 15 '18 at 9:41













                  7












                  $begingroup$

                  The number $sqrt{2}$ 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 $sqrt{2}$.






                  share|cite|improve this answer









                  $endgroup$









                  • 4




                    $begingroup$
                    I don't see how this qualifies as an answer. It is just a general statement.
                    $endgroup$
                    – M. Wind
                    Sep 16 '18 at 5:29
















                  7












                  $begingroup$

                  The number $sqrt{2}$ 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 $sqrt{2}$.






                  share|cite|improve this answer









                  $endgroup$









                  • 4




                    $begingroup$
                    I don't see how this qualifies as an answer. It is just a general statement.
                    $endgroup$
                    – M. Wind
                    Sep 16 '18 at 5:29














                  7












                  7








                  7





                  $begingroup$

                  The number $sqrt{2}$ 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 $sqrt{2}$.






                  share|cite|improve this answer









                  $endgroup$



                  The number $sqrt{2}$ 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 $sqrt{2}$.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Sep 14 '18 at 12:13









                  5xum5xum

                  91.3k394161




                  91.3k394161








                  • 4




                    $begingroup$
                    I don't see how this qualifies as an answer. It is just a general statement.
                    $endgroup$
                    – M. Wind
                    Sep 16 '18 at 5:29














                  • 4




                    $begingroup$
                    I don't see how this qualifies as an answer. It is just a general statement.
                    $endgroup$
                    – M. Wind
                    Sep 16 '18 at 5:29








                  4




                  4




                  $begingroup$
                  I don't see how this qualifies as an answer. It is just a general statement.
                  $endgroup$
                  – M. Wind
                  Sep 16 '18 at 5:29




                  $begingroup$
                  I don't see how this qualifies as an answer. It is just a general statement.
                  $endgroup$
                  – M. Wind
                  Sep 16 '18 at 5:29











                  6












                  $begingroup$

                  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 $sqrt{N}$.



                  In the particular case $N=2$, we have:
                  $$ sqrt{2} = 1 + frac{1}{2 + frac{1}{2 + frac{1}{2 + ddots}}}. $$
                  (This follows from the fact that if $x = sqrt{2}-1$, then $x = sqrt{2}-1 = frac{1}{sqrt{2}+1} = frac{1}{2+x}$.)



                  Now, from this we can calculate subsequent rational approximations to $sqrt{2}$:



                  $$
                  begin{matrix}
                  & & 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
                  end{matrix} $$
                  So, for example $frac{99}{70} approx 1.4142857$ whereas $sqrt{2} 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 sqrt{2} = pm frac{1}{a + b sqrt{2}}$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt{2} approx pmfrac{1}{2a}$ which implies $frac{a}{b} - sqrt{2} approx pmfrac{1}{2ab} approx pmfrac{1}{a^2sqrt{2}}$.)






                  share|cite|improve this answer









                  $endgroup$









                  • 2




                    $begingroup$
                    Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 2:00










                  • $begingroup$
                    Once you see the first few rational approximations it's easy to guess and prove the recursion for $p/q$, namely, $p_n = p_{n-1} + 2q_{n-1}$, $q_n = p_{n-1} + q_{n-1}$..See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Pell%27s_equation
                    $endgroup$
                    – Ethan Bolker
                    Sep 15 '18 at 13:13
















                  6












                  $begingroup$

                  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 $sqrt{N}$.



                  In the particular case $N=2$, we have:
                  $$ sqrt{2} = 1 + frac{1}{2 + frac{1}{2 + frac{1}{2 + ddots}}}. $$
                  (This follows from the fact that if $x = sqrt{2}-1$, then $x = sqrt{2}-1 = frac{1}{sqrt{2}+1} = frac{1}{2+x}$.)



                  Now, from this we can calculate subsequent rational approximations to $sqrt{2}$:



                  $$
                  begin{matrix}
                  & & 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
                  end{matrix} $$
                  So, for example $frac{99}{70} approx 1.4142857$ whereas $sqrt{2} 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 sqrt{2} = pm frac{1}{a + b sqrt{2}}$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt{2} approx pmfrac{1}{2a}$ which implies $frac{a}{b} - sqrt{2} approx pmfrac{1}{2ab} approx pmfrac{1}{a^2sqrt{2}}$.)






                  share|cite|improve this answer









                  $endgroup$









                  • 2




                    $begingroup$
                    Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 2:00










                  • $begingroup$
                    Once you see the first few rational approximations it's easy to guess and prove the recursion for $p/q$, namely, $p_n = p_{n-1} + 2q_{n-1}$, $q_n = p_{n-1} + q_{n-1}$..See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Pell%27s_equation
                    $endgroup$
                    – Ethan Bolker
                    Sep 15 '18 at 13:13














                  6












                  6








                  6





                  $begingroup$

                  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 $sqrt{N}$.



                  In the particular case $N=2$, we have:
                  $$ sqrt{2} = 1 + frac{1}{2 + frac{1}{2 + frac{1}{2 + ddots}}}. $$
                  (This follows from the fact that if $x = sqrt{2}-1$, then $x = sqrt{2}-1 = frac{1}{sqrt{2}+1} = frac{1}{2+x}$.)



                  Now, from this we can calculate subsequent rational approximations to $sqrt{2}$:



                  $$
                  begin{matrix}
                  & & 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
                  end{matrix} $$
                  So, for example $frac{99}{70} approx 1.4142857$ whereas $sqrt{2} 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 sqrt{2} = pm frac{1}{a + b sqrt{2}}$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt{2} approx pmfrac{1}{2a}$ which implies $frac{a}{b} - sqrt{2} approx pmfrac{1}{2ab} approx pmfrac{1}{a^2sqrt{2}}$.)






                  share|cite|improve this answer









                  $endgroup$



                  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 $sqrt{N}$.



                  In the particular case $N=2$, we have:
                  $$ sqrt{2} = 1 + frac{1}{2 + frac{1}{2 + frac{1}{2 + ddots}}}. $$
                  (This follows from the fact that if $x = sqrt{2}-1$, then $x = sqrt{2}-1 = frac{1}{sqrt{2}+1} = frac{1}{2+x}$.)



                  Now, from this we can calculate subsequent rational approximations to $sqrt{2}$:



                  $$
                  begin{matrix}
                  & & 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
                  end{matrix} $$
                  So, for example $frac{99}{70} approx 1.4142857$ whereas $sqrt{2} 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 sqrt{2} = pm frac{1}{a + b sqrt{2}}$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - bsqrt{2} approx pmfrac{1}{2a}$ which implies $frac{a}{b} - sqrt{2} approx pmfrac{1}{2ab} approx pmfrac{1}{a^2sqrt{2}}$.)







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Sep 14 '18 at 22:43









                  Daniel ScheplerDaniel Schepler

                  8,9591620




                  8,9591620








                  • 2




                    $begingroup$
                    Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 2:00










                  • $begingroup$
                    Once you see the first few rational approximations it's easy to guess and prove the recursion for $p/q$, namely, $p_n = p_{n-1} + 2q_{n-1}$, $q_n = p_{n-1} + q_{n-1}$..See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Pell%27s_equation
                    $endgroup$
                    – Ethan Bolker
                    Sep 15 '18 at 13:13














                  • 2




                    $begingroup$
                    Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                    $endgroup$
                    – goblin
                    Sep 15 '18 at 2:00










                  • $begingroup$
                    Once you see the first few rational approximations it's easy to guess and prove the recursion for $p/q$, namely, $p_n = p_{n-1} + 2q_{n-1}$, $q_n = p_{n-1} + q_{n-1}$..See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Pell%27s_equation
                    $endgroup$
                    – Ethan Bolker
                    Sep 15 '18 at 13:13








                  2




                  2




                  $begingroup$
                  Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                  $endgroup$
                  – goblin
                  Sep 15 '18 at 2:00




                  $begingroup$
                  Is there somewhere I can read more about this, especially the connection between continued fractions and Pell's equation?
                  $endgroup$
                  – goblin
                  Sep 15 '18 at 2:00












                  $begingroup$
                  Once you see the first few rational approximations it's easy to guess and prove the recursion for $p/q$, namely, $p_n = p_{n-1} + 2q_{n-1}$, $q_n = p_{n-1} + q_{n-1}$..See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Pell%27s_equation
                  $endgroup$
                  – Ethan Bolker
                  Sep 15 '18 at 13:13




                  $begingroup$
                  Once you see the first few rational approximations it's easy to guess and prove the recursion for $p/q$, namely, $p_n = p_{n-1} + 2q_{n-1}$, $q_n = p_{n-1} + q_{n-1}$..See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Pell%27s_equation
                  $endgroup$
                  – Ethan Bolker
                  Sep 15 '18 at 13:13











                  5












                  $begingroup$

                  Okay, I searched through the answers, but none seems to mention this one: long quadratic root calculation.



                  From the name it is obvious that it resembles long division, like this:



                  $$
                  begin{align}
                  sqrt{2.00;00;00;00;..}
                  end{align}
                  $$



                  Notice how they are grouped into tuples. Now estimate the first digit, namely $1$:



                  $$
                  begin{align}
                  &~~~1.\
                  1&sqrt{2.00;00;00;00;..}\
                  &~~~1\
                  &~~~overline{1,00}
                  end{align}
                  $$



                  We calculate $1times1=1$, write it down, and calculate the "remainder", just like divisions. Notice that we append 2 digits behind instead of 1.



                  Next, double the number on the top, and write it on the left of $1,00$:



                  $$
                  begin{align}
                  &~~~1.;*\
                  1&sqrt{2.00;00;00;00;..}\
                  &~~~1\
                  2*&,,|overline{1,00}
                  end{align}
                  $$



                  Now we estimate the next digit, *. It is written both on the top and to the left. Of course, we know that it is 4, so:



                  $$
                  begin{align}
                  &~~~1.;4;;;*\
                  1&sqrt{2.00;00;00;00;..}\
                  &~~~1\
                  24&,,|overline{1,00}\
                  &,,|,,,,96\
                  &2overline{8{*}|,4,00}
                  end{align}
                  $$



                  We double the numbers on the top again to get $28*$, and repeat the process:



                  $$
                  begin{align}
                  &~~~1.;4;;;1\
                  1&sqrt{2.00;00;00;00;..}\
                  &~~~1\
                  24&,,|overline{1,00}\
                  &,,|,,,,96\
                  &2overline{8{1}|,4,00}\
                  &,,,,,,,,,|,2,81
                  end{align}
                  $$



                  I found a picture, but not of $sqrt{2}$:



                  sqrt(7)



                  This is extremely inefficient for computers, but great for manual calculation. After all, we don't do multiplication through fast Fourier transforms!



                  Also, this method is developed in ancient China.






                  share|cite|improve this answer









                  $endgroup$


















                    5












                    $begingroup$

                    Okay, I searched through the answers, but none seems to mention this one: long quadratic root calculation.



                    From the name it is obvious that it resembles long division, like this:



                    $$
                    begin{align}
                    sqrt{2.00;00;00;00;..}
                    end{align}
                    $$



                    Notice how they are grouped into tuples. Now estimate the first digit, namely $1$:



                    $$
                    begin{align}
                    &~~~1.\
                    1&sqrt{2.00;00;00;00;..}\
                    &~~~1\
                    &~~~overline{1,00}
                    end{align}
                    $$



                    We calculate $1times1=1$, write it down, and calculate the "remainder", just like divisions. Notice that we append 2 digits behind instead of 1.



                    Next, double the number on the top, and write it on the left of $1,00$:



                    $$
                    begin{align}
                    &~~~1.;*\
                    1&sqrt{2.00;00;00;00;..}\
                    &~~~1\
                    2*&,,|overline{1,00}
                    end{align}
                    $$



                    Now we estimate the next digit, *. It is written both on the top and to the left. Of course, we know that it is 4, so:



                    $$
                    begin{align}
                    &~~~1.;4;;;*\
                    1&sqrt{2.00;00;00;00;..}\
                    &~~~1\
                    24&,,|overline{1,00}\
                    &,,|,,,,96\
                    &2overline{8{*}|,4,00}
                    end{align}
                    $$



                    We double the numbers on the top again to get $28*$, and repeat the process:



                    $$
                    begin{align}
                    &~~~1.;4;;;1\
                    1&sqrt{2.00;00;00;00;..}\
                    &~~~1\
                    24&,,|overline{1,00}\
                    &,,|,,,,96\
                    &2overline{8{1}|,4,00}\
                    &,,,,,,,,,|,2,81
                    end{align}
                    $$



                    I found a picture, but not of $sqrt{2}$:



                    sqrt(7)



                    This is extremely inefficient for computers, but great for manual calculation. After all, we don't do multiplication through fast Fourier transforms!



                    Also, this method is developed in ancient China.






                    share|cite|improve this answer









                    $endgroup$
















                      5












                      5








                      5





                      $begingroup$

                      Okay, I searched through the answers, but none seems to mention this one: long quadratic root calculation.



                      From the name it is obvious that it resembles long division, like this:



                      $$
                      begin{align}
                      sqrt{2.00;00;00;00;..}
                      end{align}
                      $$



                      Notice how they are grouped into tuples. Now estimate the first digit, namely $1$:



                      $$
                      begin{align}
                      &~~~1.\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      &~~~overline{1,00}
                      end{align}
                      $$



                      We calculate $1times1=1$, write it down, and calculate the "remainder", just like divisions. Notice that we append 2 digits behind instead of 1.



                      Next, double the number on the top, and write it on the left of $1,00$:



                      $$
                      begin{align}
                      &~~~1.;*\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      2*&,,|overline{1,00}
                      end{align}
                      $$



                      Now we estimate the next digit, *. It is written both on the top and to the left. Of course, we know that it is 4, so:



                      $$
                      begin{align}
                      &~~~1.;4;;;*\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      24&,,|overline{1,00}\
                      &,,|,,,,96\
                      &2overline{8{*}|,4,00}
                      end{align}
                      $$



                      We double the numbers on the top again to get $28*$, and repeat the process:



                      $$
                      begin{align}
                      &~~~1.;4;;;1\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      24&,,|overline{1,00}\
                      &,,|,,,,96\
                      &2overline{8{1}|,4,00}\
                      &,,,,,,,,,|,2,81
                      end{align}
                      $$



                      I found a picture, but not of $sqrt{2}$:



                      sqrt(7)



                      This is extremely inefficient for computers, but great for manual calculation. After all, we don't do multiplication through fast Fourier transforms!



                      Also, this method is developed in ancient China.






                      share|cite|improve this answer









                      $endgroup$



                      Okay, I searched through the answers, but none seems to mention this one: long quadratic root calculation.



                      From the name it is obvious that it resembles long division, like this:



                      $$
                      begin{align}
                      sqrt{2.00;00;00;00;..}
                      end{align}
                      $$



                      Notice how they are grouped into tuples. Now estimate the first digit, namely $1$:



                      $$
                      begin{align}
                      &~~~1.\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      &~~~overline{1,00}
                      end{align}
                      $$



                      We calculate $1times1=1$, write it down, and calculate the "remainder", just like divisions. Notice that we append 2 digits behind instead of 1.



                      Next, double the number on the top, and write it on the left of $1,00$:



                      $$
                      begin{align}
                      &~~~1.;*\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      2*&,,|overline{1,00}
                      end{align}
                      $$



                      Now we estimate the next digit, *. It is written both on the top and to the left. Of course, we know that it is 4, so:



                      $$
                      begin{align}
                      &~~~1.;4;;;*\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      24&,,|overline{1,00}\
                      &,,|,,,,96\
                      &2overline{8{*}|,4,00}
                      end{align}
                      $$



                      We double the numbers on the top again to get $28*$, and repeat the process:



                      $$
                      begin{align}
                      &~~~1.;4;;;1\
                      1&sqrt{2.00;00;00;00;..}\
                      &~~~1\
                      24&,,|overline{1,00}\
                      &,,|,,,,96\
                      &2overline{8{1}|,4,00}\
                      &,,,,,,,,,|,2,81
                      end{align}
                      $$



                      I found a picture, but not of $sqrt{2}$:



                      sqrt(7)



                      This is extremely inefficient for computers, but great for manual calculation. After all, we don't do multiplication through fast Fourier transforms!



                      Also, this method is developed in ancient China.







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Sep 17 '18 at 7:44









                      TreborTrebor

                      81013




                      81013























                          4












                          $begingroup$

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



                          Let $mathbf M=begin{bmatrix} 1 & p \ 1 & 1 end{bmatrix}$ and $mathbf q=begin{pmatrix} x \ y end{pmatrix}$
                          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











                          $endgroup$


















                            4












                            $begingroup$

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



                            Let $mathbf M=begin{bmatrix} 1 & p \ 1 & 1 end{bmatrix}$ and $mathbf q=begin{pmatrix} x \ y end{pmatrix}$
                            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











                            $endgroup$
















                              4












                              4








                              4





                              $begingroup$

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



                              Let $mathbf M=begin{bmatrix} 1 & p \ 1 & 1 end{bmatrix}$ and $mathbf q=begin{pmatrix} x \ y end{pmatrix}$
                              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











                              $endgroup$



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



                              Let $mathbf M=begin{bmatrix} 1 & p \ 1 & 1 end{bmatrix}$ and $mathbf q=begin{pmatrix} x \ y end{pmatrix}$
                              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 Sep 15 '18 at 3:29









                              Tyberius

                              7342724




                              7342724










                              answered Sep 15 '18 at 1:52









                              TurlocTheRedTurlocTheRed

                              916311




                              916311























                                  1












                                  $begingroup$

                                  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 + frac{a}{ sqrt b + y_n}$



                                  $y_{n+1}$ converges to $sqrt N$.






                                  share|cite|improve this answer











                                  $endgroup$


















                                    1












                                    $begingroup$

                                    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 + frac{a}{ sqrt b + y_n}$



                                    $y_{n+1}$ converges to $sqrt N$.






                                    share|cite|improve this answer











                                    $endgroup$
















                                      1












                                      1








                                      1





                                      $begingroup$

                                      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 + frac{a}{ sqrt b + y_n}$



                                      $y_{n+1}$ converges to $sqrt N$.






                                      share|cite|improve this answer











                                      $endgroup$



                                      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 + frac{a}{ 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 Sep 14 '18 at 22:33









                                      asky

                                      1418




                                      1418










                                      answered Sep 14 '18 at 20:35









                                      TurlocTheRedTurlocTheRed

                                      916311




                                      916311























                                          1












                                          $begingroup$

                                          In this answer, there is a method using continued fraction approximations for $sqrt2$ and the generating function for the central binomial coefficients to get some very quickly convergent series for $sqrt2$. For example,
                                          $$
                                          sqrt2=frac75sum_{k=0}^inftybinom{2k}{k}frac1{200^k}tag1
                                          $$
                                          and
                                          $$
                                          sqrt2=frac{239}{169}sum_{k=0}^inftybinom{2k}{k}frac1{228488^k}tag2
                                          $$





                                          For example, summing to $k=4$ in $(2)$ gives
                                          $$
                                          sqrt2=1.414213562373095048801688
                                          $$
                                          which is accurate to $23$ places.






                                          share|cite|improve this answer











                                          $endgroup$













                                          • $begingroup$
                                            (+) This method could be used to calculate millions of $sqrt{2}$ digits (especially when notice that the series has rational terms, and apply en.wikipedia.org/wiki/Binary_splitting technique).
                                            $endgroup$
                                            – Oleg567
                                            Sep 24 '18 at 4:44










                                          • $begingroup$
                                            Good description of the elementary school method. You are not likely to succeed unless you do at least one square root every day. After age 75, you have to do more than one every day. That is why there are calculators.
                                            $endgroup$
                                            – richard1941
                                            Sep 24 '18 at 23:53
















                                          1












                                          $begingroup$

                                          In this answer, there is a method using continued fraction approximations for $sqrt2$ and the generating function for the central binomial coefficients to get some very quickly convergent series for $sqrt2$. For example,
                                          $$
                                          sqrt2=frac75sum_{k=0}^inftybinom{2k}{k}frac1{200^k}tag1
                                          $$
                                          and
                                          $$
                                          sqrt2=frac{239}{169}sum_{k=0}^inftybinom{2k}{k}frac1{228488^k}tag2
                                          $$





                                          For example, summing to $k=4$ in $(2)$ gives
                                          $$
                                          sqrt2=1.414213562373095048801688
                                          $$
                                          which is accurate to $23$ places.






                                          share|cite|improve this answer











                                          $endgroup$













                                          • $begingroup$
                                            (+) This method could be used to calculate millions of $sqrt{2}$ digits (especially when notice that the series has rational terms, and apply en.wikipedia.org/wiki/Binary_splitting technique).
                                            $endgroup$
                                            – Oleg567
                                            Sep 24 '18 at 4:44










                                          • $begingroup$
                                            Good description of the elementary school method. You are not likely to succeed unless you do at least one square root every day. After age 75, you have to do more than one every day. That is why there are calculators.
                                            $endgroup$
                                            – richard1941
                                            Sep 24 '18 at 23:53














                                          1












                                          1








                                          1





                                          $begingroup$

                                          In this answer, there is a method using continued fraction approximations for $sqrt2$ and the generating function for the central binomial coefficients to get some very quickly convergent series for $sqrt2$. For example,
                                          $$
                                          sqrt2=frac75sum_{k=0}^inftybinom{2k}{k}frac1{200^k}tag1
                                          $$
                                          and
                                          $$
                                          sqrt2=frac{239}{169}sum_{k=0}^inftybinom{2k}{k}frac1{228488^k}tag2
                                          $$





                                          For example, summing to $k=4$ in $(2)$ gives
                                          $$
                                          sqrt2=1.414213562373095048801688
                                          $$
                                          which is accurate to $23$ places.






                                          share|cite|improve this answer











                                          $endgroup$



                                          In this answer, there is a method using continued fraction approximations for $sqrt2$ and the generating function for the central binomial coefficients to get some very quickly convergent series for $sqrt2$. For example,
                                          $$
                                          sqrt2=frac75sum_{k=0}^inftybinom{2k}{k}frac1{200^k}tag1
                                          $$
                                          and
                                          $$
                                          sqrt2=frac{239}{169}sum_{k=0}^inftybinom{2k}{k}frac1{228488^k}tag2
                                          $$





                                          For example, summing to $k=4$ in $(2)$ gives
                                          $$
                                          sqrt2=1.414213562373095048801688
                                          $$
                                          which is accurate to $23$ places.







                                          share|cite|improve this answer














                                          share|cite|improve this answer



                                          share|cite|improve this answer








                                          edited Sep 15 '18 at 23:39

























                                          answered Sep 15 '18 at 13:50









                                          robjohnrobjohn

                                          268k27308634




                                          268k27308634












                                          • $begingroup$
                                            (+) This method could be used to calculate millions of $sqrt{2}$ digits (especially when notice that the series has rational terms, and apply en.wikipedia.org/wiki/Binary_splitting technique).
                                            $endgroup$
                                            – Oleg567
                                            Sep 24 '18 at 4:44










                                          • $begingroup$
                                            Good description of the elementary school method. You are not likely to succeed unless you do at least one square root every day. After age 75, you have to do more than one every day. That is why there are calculators.
                                            $endgroup$
                                            – richard1941
                                            Sep 24 '18 at 23:53


















                                          • $begingroup$
                                            (+) This method could be used to calculate millions of $sqrt{2}$ digits (especially when notice that the series has rational terms, and apply en.wikipedia.org/wiki/Binary_splitting technique).
                                            $endgroup$
                                            – Oleg567
                                            Sep 24 '18 at 4:44










                                          • $begingroup$
                                            Good description of the elementary school method. You are not likely to succeed unless you do at least one square root every day. After age 75, you have to do more than one every day. That is why there are calculators.
                                            $endgroup$
                                            – richard1941
                                            Sep 24 '18 at 23:53
















                                          $begingroup$
                                          (+) This method could be used to calculate millions of $sqrt{2}$ digits (especially when notice that the series has rational terms, and apply en.wikipedia.org/wiki/Binary_splitting technique).
                                          $endgroup$
                                          – Oleg567
                                          Sep 24 '18 at 4:44




                                          $begingroup$
                                          (+) This method could be used to calculate millions of $sqrt{2}$ digits (especially when notice that the series has rational terms, and apply en.wikipedia.org/wiki/Binary_splitting technique).
                                          $endgroup$
                                          – Oleg567
                                          Sep 24 '18 at 4:44












                                          $begingroup$
                                          Good description of the elementary school method. You are not likely to succeed unless you do at least one square root every day. After age 75, you have to do more than one every day. That is why there are calculators.
                                          $endgroup$
                                          – richard1941
                                          Sep 24 '18 at 23:53




                                          $begingroup$
                                          Good description of the elementary school method. You are not likely to succeed unless you do at least one square root every day. After age 75, you have to do more than one every day. That is why there are calculators.
                                          $endgroup$
                                          – richard1941
                                          Sep 24 '18 at 23:53











                                          1












                                          $begingroup$

                                          Binary search for it.



                                          Since $1 < 2 < 4$, we must have $sqrt{1} < sqrt{2} < sqrt{4}$, so $sqrt{2} in (1,2)$. Now repeatedly: find the midpoint, $m$, of the current interval, $(a,b)$, square $m$ and compare with $2$, and if $2 = m^2$ declare that $m = sqrt{2}$, or if $2 < m^2$, make the new interval $(a,m)$, otherwise make the new interval $(m,b)$. This process halves the size of the interval on each step. Since $log_2(10^{-20}) = -66.438dots$, after 67 doublings, the error in taking any value from the interval is $<10^{-20}$ (but, if the interval straddles a digit change, you may have to perform additional steps to find out on which side of the change is $sqrt{2}$).



                                          This process is shown in the table below. Each decimal number is computed to $21$ digits and has trailing zeroes stripped. If there are still $21$ digits, a space is inserted between the $20^text{th}$ and $21^text{st}$.



                                          begin{align}
                                          text{step} && text{interval} && m && m^2 \
                                          1 && (1., 2.) && 1.5 && 2<2.25 \
                                          2 && (1., 1.5) && 1.25 && 1.5625<2 \
                                          3 && (1.25, 1.5) && 1.375 && 1.890625<2 \
                                          4 && (1.375, 1.5) && 1.4375 && 2<2.06640625 \
                                          5 && (1.375, 1.4375) && 1.40625 && 1.9775390625<2 \
                                          6 && (1.40625, 1.4375) && 1.421875 && 2<2.021728515625 \
                                          7 && (1.40625, 1.421875) && 1.4140625 && 1.99957275390625<2 \
                                          8 && (1.4140625, 1.421875) && 1.41796875 && 2<2.0106353759765625 \
                                          9 && (1.4140625, 1.41796875) && 1.416015625 && 2<2.005100250244140625
                                          \
                                          10 && (1.4140625, 1.416015625) && 1.4150390625 &&
                                          2<2.00233554840087890625 \
                                          11 && (1.4140625, 1.4150390625) && 1.41455078125 &&
                                          2<2.00095391273498535156 3 \
                                          12 && (1.4140625, 1.41455078125) && 1.414306640625 &&
                                          2<2.00026327371597290039 \
                                          13 && (1.4140625, 1.414306640625) && 1.4141845703125 &&
                                          1.99991799890995025634 8<2 \
                                          14 && (1.4141845703125, 1.414306640625) && 1.41424560546875 &&
                                          2<2.00009063258767127990 7 \
                                          15 && (1.4141845703125, 1.41424560546875) && 1.414215087890625 &&
                                          2<2.00000431481748819351 2 \
                                          16 && (1.4141845703125, 1.414215087890625) && 1.4141998291015625 &&
                                          1.99996115663088858127 6<2 \
                                          17 && (1.4141998291015625, 1.414215087890625) && 1.41420745849609375 &&
                                          1.99998273566598072648<2 \
                                          18 && (1.41420745849609375, 1.414215087890625) &&
                                          1.414211273193359375 && 1.99999352522718254476 8<2 \
                                          19 && (1.414211273193359375, 1.414215087890625) &&
                                          1.4142131805419921875 && 1.99999892001869739033 3<2 \
                                          20 && (1.4142131805419921875, 1.414215087890625) &&
                                          1.41421413421630859375 && 2<2.00000161741718329722
                                          end{align}begin{align}
                                          21 && (1.4142131805419921875, 1.41421413421630859375) &&
                                          1.41421365737915039062 5 && 2<2.00000026871771297010 1 \
                                          22 && (1.4142131805419921875, 1.41421365737915039062 5) &&
                                          1.41421341896057128906 2 && 1.99999959436814833679 8<2 \
                                          23 && (1.41421341896057128906 2, 1.41421365737915039062 5) &&
                                          1.41421353816986083984 4 && 1.99999993154291644259 5<2 \
                                          24 && (1.41421353816986083984 4, 1.41421365737915039062 5) &&
                                          1.41421359777450561523 4 && 2<2.00000010013031115363 4 \
                                          25 && (1.41421353816986083984 4, 1.41421359777450561523 4) &&
                                          1.41421356797218322753 9 && 2<2.00000001583661290993 6 \
                                          26 && (1.41421353816986083984 4, 1.41421356797218322753 9) &&
                                          1.41421355307102203369 1 && 1.99999997368976445422 1<2 \
                                          27 && (1.41421355307102203369 1, 1.41421356797218322753 9) &&
                                          1.41421356052160263061 5 && 1.99999999476318862656 8<2 \
                                          28 && (1.41421356052160263061 5, 1.41421356797218322753 9) &&
                                          1.41421356424689292907 7 && 2<2.00000000529990075437 4 \
                                          29 && (1.41421356052160263061 5, 1.41421356424689292907 7) &&
                                          1.41421356238424777984 6 && 2<2.00000000003154468700 1 \
                                          30 && (1.41421356052160263061 5, 1.41421356238424777984 6) &&
                                          1.41421356145292520523 && 1.99999999739736665591 7<2 \
                                          31 && (1.41421356145292520523, 1.41421356238424777984 6) &&
                                          1.41421356191858649253 8 && 1.99999999871445567124 2<2 \
                                          32 && (1.41421356191858649253 8, 1.41421356238424777984 6) &&
                                          1.41421356215141713619 2 && 1.99999999937300017906 8<2 \
                                          33 && (1.41421356215141713619 2, 1.41421356238424777984 6) &&
                                          1.41421356226783245801 9 && 1.99999999970227243302 1<2 \
                                          34 && (1.41421356226783245801 9, 1.41421356238424777984 6) &&
                                          1.41421356232604011893 3 && 1.99999999986690856000 8<2 \
                                          35 && (1.41421356232604011893 3, 1.41421356238424777984 6) &&
                                          1.41421356235514394938 9 && 1.99999999994922662350 4<2
                                          end{align}begin{align}
                                          36 && (1.41421356235514394938 9, 1.41421356238424777984 6) &&
                                          1.41421356236969586461 8 && 1.99999999999038565525 2<2 \
                                          37 && (1.41421356236969586461 8, 1.41421356238424777984 6) &&
                                          1.41421356237697182223 2 && 2<2.00000000001096517112 7 \
                                          38 && (1.41421356236969586461 8, 1.41421356237697182223 2) &&
                                          1.41421356237333384342 5 && 2<2.00000000000067541319 0 \
                                          39 && (1.41421356236969586461 8, 1.41421356237333384342 5) &&
                                          1.41421356237151485402 1 && 1.99999999999553053422 1<2 \
                                          40 && (1.41421356237151485402 1, 1.41421356237333384342 5) &&
                                          1.41421356237242434872 3 && 1.99999999999810297370 5<2 \
                                          41 && (1.41421356237242434872 3, 1.41421356237333384342 5) &&
                                          1.41421356237287909607 4 && 1.99999999999938919344 7<2 \
                                          42 && (1.41421356237287909607 4, 1.41421356237333384342 5) &&
                                          1.41421356237310646974 9 && 2<2.00000000000003230331 9 \
                                          43 && (1.41421356237287909607 4, 1.41421356237310646974 9) &&
                                          1.41421356237299278291 2 && 1.99999999999971074838 3<2 \
                                          44 && (1.41421356237299278291 2, 1.41421356237310646974 9) &&
                                          1.41421356237304962633 && 1.99999999999987152585<2 \
                                          45 && (1.41421356237304962633, 1.41421356237310646974 9) &&
                                          1.41421356237307804804 && 1.99999999999995191458 5<2 \
                                          46 && (1.41421356237307804804, 1.41421356237310646974 9) &&
                                          1.41421356237309225889 5 && 1.99999999999999210895 2<2 \
                                          47 && (1.41421356237309225889 5, 1.41421356237310646974 9) &&
                                          1.41421356237309936432 2 && 2<2.00000000000001220613 5 \
                                          48 && (1.41421356237309225889 5, 1.41421356237309936432 2) &&
                                          1.41421356237309581160 8 && 2<2.00000000000000215754 3 \
                                          49 && (1.41421356237309225889 5, 1.41421356237309581160 8) &&
                                          1.41421356237309403525 2 && 1.99999999999999713324 7<2 \
                                          50 && (1.41421356237309403525 2, 1.41421356237309581160 8) &&
                                          1.41421356237309492343 && 1.99999999999999964539 5<2 \
                                          51 && (1.41421356237309492343, 1.41421356237309581160 8) &&
                                          1.41421356237309536751 9 && 2<2.00000000000000090146 9 \
                                          52 && (1.41421356237309492343, 1.41421356237309536751 9) &&
                                          1.41421356237309514547 5 && 2<2.00000000000000027343 2 \
                                          53 && (1.41421356237309492343, 1.41421356237309514547 5) &&
                                          1.41421356237309503445 2 && 1.99999999999999995941 4<2 \
                                          54 && (1.41421356237309503445 2, 1.41421356237309514547 5) &&
                                          1.41421356237309508996 3 && 2<2.00000000000000011642 3 \
                                          55 && (1.41421356237309503445 2, 1.41421356237309508996 3) &&
                                          1.41421356237309506220 8 && 2<2.00000000000000003791 8 \
                                          56 && (1.41421356237309503445 2, 1.41421356237309506220 8) &&
                                          1.41421356237309504833 && 1.99999999999999999866 6<2 \
                                          57 && (1.41421356237309504833, 1.41421356237309506220 8) &&
                                          1.41421356237309505526 9 && 2<2.00000000000000001829 2 \
                                          58 && (1.41421356237309504833, 1.41421356237309505526 9) &&
                                          1.41421356237309505180 0 && 2<2.00000000000000000847 9 \
                                          59 && (1.41421356237309504833, 1.41421356237309505180 0) &&
                                          1.41421356237309505006 5 && 2<2.00000000000000000357 3 \
                                          60 && (1.41421356237309504833, 1.41421356237309505006 5) &&
                                          1.41421356237309504919 7 && 2<2.00000000000000000111 9 \
                                          61 && (1.41421356237309504833, 1.41421356237309504919 7) &&
                                          1.41421356237309504876 4 && 1.99999999999999999989 3<2 \
                                          62 && (1.41421356237309504876 4, 1.41421356237309504919 7) &&
                                          1.41421356237309504898 && 2<2.00000000000000000050 6 \
                                          63 && (1.41421356237309504876 4, 1.41421356237309504898) &&
                                          1.41421356237309504887 2 && 2<2.00000000000000000019 9 \
                                          64 && (1.41421356237309504876 4, 1.41421356237309504887 2) &&
                                          1.41421356237309504881 8 && 2<2.00000000000000000004 6 \
                                          65 && (1.41421356237309504876 4, 1.41421356237309504881 8) &&
                                          1.41421356237309504879 && 1.99999999999999999996 9<2 \
                                          66 && (1.41421356237309504879, 1.41421356237309504881 8) &&
                                          1.41421356237309504880 4 && 2<2.00000000000000000000 8 \
                                          67 && (1.41421356237309504879, 1.41421356237309504880 4) &&
                                          1.41421356237309504879 8 && 1.99999999999999999998 9<2 \
                                          68 && (1.41421356237309504879 8, 1.41421356237309504880 4) &&
                                          1.41421356237309504880 1 && 1.99999999999999999999 8<2 \
                                          69 && (1.41421356237309504880 1, 1.41421356237309504880 4) &&
                                          1.41421356237309504880 3 && 2<2.00000000000000000000 3
                                          end{align}






                                          share|cite|improve this answer









                                          $endgroup$


















                                            1












                                            $begingroup$

                                            Binary search for it.



                                            Since $1 < 2 < 4$, we must have $sqrt{1} < sqrt{2} < sqrt{4}$, so $sqrt{2} in (1,2)$. Now repeatedly: find the midpoint, $m$, of the current interval, $(a,b)$, square $m$ and compare with $2$, and if $2 = m^2$ declare that $m = sqrt{2}$, or if $2 < m^2$, make the new interval $(a,m)$, otherwise make the new interval $(m,b)$. This process halves the size of the interval on each step. Since $log_2(10^{-20}) = -66.438dots$, after 67 doublings, the error in taking any value from the interval is $<10^{-20}$ (but, if the interval straddles a digit change, you may have to perform additional steps to find out on which side of the change is $sqrt{2}$).



                                            This process is shown in the table below. Each decimal number is computed to $21$ digits and has trailing zeroes stripped. If there are still $21$ digits, a space is inserted between the $20^text{th}$ and $21^text{st}$.



                                            begin{align}
                                            text{step} && text{interval} && m && m^2 \
                                            1 && (1., 2.) && 1.5 && 2<2.25 \
                                            2 && (1., 1.5) && 1.25 && 1.5625<2 \
                                            3 && (1.25, 1.5) && 1.375 && 1.890625<2 \
                                            4 && (1.375, 1.5) && 1.4375 && 2<2.06640625 \
                                            5 && (1.375, 1.4375) && 1.40625 && 1.9775390625<2 \
                                            6 && (1.40625, 1.4375) && 1.421875 && 2<2.021728515625 \
                                            7 && (1.40625, 1.421875) && 1.4140625 && 1.99957275390625<2 \
                                            8 && (1.4140625, 1.421875) && 1.41796875 && 2<2.0106353759765625 \
                                            9 && (1.4140625, 1.41796875) && 1.416015625 && 2<2.005100250244140625
                                            \
                                            10 && (1.4140625, 1.416015625) && 1.4150390625 &&
                                            2<2.00233554840087890625 \
                                            11 && (1.4140625, 1.4150390625) && 1.41455078125 &&
                                            2<2.00095391273498535156 3 \
                                            12 && (1.4140625, 1.41455078125) && 1.414306640625 &&
                                            2<2.00026327371597290039 \
                                            13 && (1.4140625, 1.414306640625) && 1.4141845703125 &&
                                            1.99991799890995025634 8<2 \
                                            14 && (1.4141845703125, 1.414306640625) && 1.41424560546875 &&
                                            2<2.00009063258767127990 7 \
                                            15 && (1.4141845703125, 1.41424560546875) && 1.414215087890625 &&
                                            2<2.00000431481748819351 2 \
                                            16 && (1.4141845703125, 1.414215087890625) && 1.4141998291015625 &&
                                            1.99996115663088858127 6<2 \
                                            17 && (1.4141998291015625, 1.414215087890625) && 1.41420745849609375 &&
                                            1.99998273566598072648<2 \
                                            18 && (1.41420745849609375, 1.414215087890625) &&
                                            1.414211273193359375 && 1.99999352522718254476 8<2 \
                                            19 && (1.414211273193359375, 1.414215087890625) &&
                                            1.4142131805419921875 && 1.99999892001869739033 3<2 \
                                            20 && (1.4142131805419921875, 1.414215087890625) &&
                                            1.41421413421630859375 && 2<2.00000161741718329722
                                            end{align}begin{align}
                                            21 && (1.4142131805419921875, 1.41421413421630859375) &&
                                            1.41421365737915039062 5 && 2<2.00000026871771297010 1 \
                                            22 && (1.4142131805419921875, 1.41421365737915039062 5) &&
                                            1.41421341896057128906 2 && 1.99999959436814833679 8<2 \
                                            23 && (1.41421341896057128906 2, 1.41421365737915039062 5) &&
                                            1.41421353816986083984 4 && 1.99999993154291644259 5<2 \
                                            24 && (1.41421353816986083984 4, 1.41421365737915039062 5) &&
                                            1.41421359777450561523 4 && 2<2.00000010013031115363 4 \
                                            25 && (1.41421353816986083984 4, 1.41421359777450561523 4) &&
                                            1.41421356797218322753 9 && 2<2.00000001583661290993 6 \
                                            26 && (1.41421353816986083984 4, 1.41421356797218322753 9) &&
                                            1.41421355307102203369 1 && 1.99999997368976445422 1<2 \
                                            27 && (1.41421355307102203369 1, 1.41421356797218322753 9) &&
                                            1.41421356052160263061 5 && 1.99999999476318862656 8<2 \
                                            28 && (1.41421356052160263061 5, 1.41421356797218322753 9) &&
                                            1.41421356424689292907 7 && 2<2.00000000529990075437 4 \
                                            29 && (1.41421356052160263061 5, 1.41421356424689292907 7) &&
                                            1.41421356238424777984 6 && 2<2.00000000003154468700 1 \
                                            30 && (1.41421356052160263061 5, 1.41421356238424777984 6) &&
                                            1.41421356145292520523 && 1.99999999739736665591 7<2 \
                                            31 && (1.41421356145292520523, 1.41421356238424777984 6) &&
                                            1.41421356191858649253 8 && 1.99999999871445567124 2<2 \
                                            32 && (1.41421356191858649253 8, 1.41421356238424777984 6) &&
                                            1.41421356215141713619 2 && 1.99999999937300017906 8<2 \
                                            33 && (1.41421356215141713619 2, 1.41421356238424777984 6) &&
                                            1.41421356226783245801 9 && 1.99999999970227243302 1<2 \
                                            34 && (1.41421356226783245801 9, 1.41421356238424777984 6) &&
                                            1.41421356232604011893 3 && 1.99999999986690856000 8<2 \
                                            35 && (1.41421356232604011893 3, 1.41421356238424777984 6) &&
                                            1.41421356235514394938 9 && 1.99999999994922662350 4<2
                                            end{align}begin{align}
                                            36 && (1.41421356235514394938 9, 1.41421356238424777984 6) &&
                                            1.41421356236969586461 8 && 1.99999999999038565525 2<2 \
                                            37 && (1.41421356236969586461 8, 1.41421356238424777984 6) &&
                                            1.41421356237697182223 2 && 2<2.00000000001096517112 7 \
                                            38 && (1.41421356236969586461 8, 1.41421356237697182223 2) &&
                                            1.41421356237333384342 5 && 2<2.00000000000067541319 0 \
                                            39 && (1.41421356236969586461 8, 1.41421356237333384342 5) &&
                                            1.41421356237151485402 1 && 1.99999999999553053422 1<2 \
                                            40 && (1.41421356237151485402 1, 1.41421356237333384342 5) &&
                                            1.41421356237242434872 3 && 1.99999999999810297370 5<2 \
                                            41 && (1.41421356237242434872 3, 1.41421356237333384342 5) &&
                                            1.41421356237287909607 4 && 1.99999999999938919344 7<2 \
                                            42 && (1.41421356237287909607 4, 1.41421356237333384342 5) &&
                                            1.41421356237310646974 9 && 2<2.00000000000003230331 9 \
                                            43 && (1.41421356237287909607 4, 1.41421356237310646974 9) &&
                                            1.41421356237299278291 2 && 1.99999999999971074838 3<2 \
                                            44 && (1.41421356237299278291 2, 1.41421356237310646974 9) &&
                                            1.41421356237304962633 && 1.99999999999987152585<2 \
                                            45 && (1.41421356237304962633, 1.41421356237310646974 9) &&
                                            1.41421356237307804804 && 1.99999999999995191458 5<2 \
                                            46 && (1.41421356237307804804, 1.41421356237310646974 9) &&
                                            1.41421356237309225889 5 && 1.99999999999999210895 2<2 \
                                            47 && (1.41421356237309225889 5, 1.41421356237310646974 9) &&
                                            1.41421356237309936432 2 && 2<2.00000000000001220613 5 \
                                            48 && (1.41421356237309225889 5, 1.41421356237309936432 2) &&
                                            1.41421356237309581160 8 && 2<2.00000000000000215754 3 \
                                            49 && (1.41421356237309225889 5, 1.41421356237309581160 8) &&
                                            1.41421356237309403525 2 && 1.99999999999999713324 7<2 \
                                            50 && (1.41421356237309403525 2, 1.41421356237309581160 8) &&
                                            1.41421356237309492343 && 1.99999999999999964539 5<2 \
                                            51 && (1.41421356237309492343, 1.41421356237309581160 8) &&
                                            1.41421356237309536751 9 && 2<2.00000000000000090146 9 \
                                            52 && (1.41421356237309492343, 1.41421356237309536751 9) &&
                                            1.41421356237309514547 5 && 2<2.00000000000000027343 2 \
                                            53 && (1.41421356237309492343, 1.41421356237309514547 5) &&
                                            1.41421356237309503445 2 && 1.99999999999999995941 4<2 \
                                            54 && (1.41421356237309503445 2, 1.41421356237309514547 5) &&
                                            1.41421356237309508996 3 && 2<2.00000000000000011642 3 \
                                            55 && (1.41421356237309503445 2, 1.41421356237309508996 3) &&
                                            1.41421356237309506220 8 && 2<2.00000000000000003791 8 \
                                            56 && (1.41421356237309503445 2, 1.41421356237309506220 8) &&
                                            1.41421356237309504833 && 1.99999999999999999866 6<2 \
                                            57 && (1.41421356237309504833, 1.41421356237309506220 8) &&
                                            1.41421356237309505526 9 && 2<2.00000000000000001829 2 \
                                            58 && (1.41421356237309504833, 1.41421356237309505526 9) &&
                                            1.41421356237309505180 0 && 2<2.00000000000000000847 9 \
                                            59 && (1.41421356237309504833, 1.41421356237309505180 0) &&
                                            1.41421356237309505006 5 && 2<2.00000000000000000357 3 \
                                            60 && (1.41421356237309504833, 1.41421356237309505006 5) &&
                                            1.41421356237309504919 7 && 2<2.00000000000000000111 9 \
                                            61 && (1.41421356237309504833, 1.41421356237309504919 7) &&
                                            1.41421356237309504876 4 && 1.99999999999999999989 3<2 \
                                            62 && (1.41421356237309504876 4, 1.41421356237309504919 7) &&
                                            1.41421356237309504898 && 2<2.00000000000000000050 6 \
                                            63 && (1.41421356237309504876 4, 1.41421356237309504898) &&
                                            1.41421356237309504887 2 && 2<2.00000000000000000019 9 \
                                            64 && (1.41421356237309504876 4, 1.41421356237309504887 2) &&
                                            1.41421356237309504881 8 && 2<2.00000000000000000004 6 \
                                            65 && (1.41421356237309504876 4, 1.41421356237309504881 8) &&
                                            1.41421356237309504879 && 1.99999999999999999996 9<2 \
                                            66 && (1.41421356237309504879, 1.41421356237309504881 8) &&
                                            1.41421356237309504880 4 && 2<2.00000000000000000000 8 \
                                            67 && (1.41421356237309504879, 1.41421356237309504880 4) &&
                                            1.41421356237309504879 8 && 1.99999999999999999998 9<2 \
                                            68 && (1.41421356237309504879 8, 1.41421356237309504880 4) &&
                                            1.41421356237309504880 1 && 1.99999999999999999999 8<2 \
                                            69 && (1.41421356237309504880 1, 1.41421356237309504880 4) &&
                                            1.41421356237309504880 3 && 2<2.00000000000000000000 3
                                            end{align}






                                            share|cite|improve this answer









                                            $endgroup$
















                                              1












                                              1








                                              1





                                              $begingroup$

                                              Binary search for it.



                                              Since $1 < 2 < 4$, we must have $sqrt{1} < sqrt{2} < sqrt{4}$, so $sqrt{2} in (1,2)$. Now repeatedly: find the midpoint, $m$, of the current interval, $(a,b)$, square $m$ and compare with $2$, and if $2 = m^2$ declare that $m = sqrt{2}$, or if $2 < m^2$, make the new interval $(a,m)$, otherwise make the new interval $(m,b)$. This process halves the size of the interval on each step. Since $log_2(10^{-20}) = -66.438dots$, after 67 doublings, the error in taking any value from the interval is $<10^{-20}$ (but, if the interval straddles a digit change, you may have to perform additional steps to find out on which side of the change is $sqrt{2}$).



                                              This process is shown in the table below. Each decimal number is computed to $21$ digits and has trailing zeroes stripped. If there are still $21$ digits, a space is inserted between the $20^text{th}$ and $21^text{st}$.



                                              begin{align}
                                              text{step} && text{interval} && m && m^2 \
                                              1 && (1., 2.) && 1.5 && 2<2.25 \
                                              2 && (1., 1.5) && 1.25 && 1.5625<2 \
                                              3 && (1.25, 1.5) && 1.375 && 1.890625<2 \
                                              4 && (1.375, 1.5) && 1.4375 && 2<2.06640625 \
                                              5 && (1.375, 1.4375) && 1.40625 && 1.9775390625<2 \
                                              6 && (1.40625, 1.4375) && 1.421875 && 2<2.021728515625 \
                                              7 && (1.40625, 1.421875) && 1.4140625 && 1.99957275390625<2 \
                                              8 && (1.4140625, 1.421875) && 1.41796875 && 2<2.0106353759765625 \
                                              9 && (1.4140625, 1.41796875) && 1.416015625 && 2<2.005100250244140625
                                              \
                                              10 && (1.4140625, 1.416015625) && 1.4150390625 &&
                                              2<2.00233554840087890625 \
                                              11 && (1.4140625, 1.4150390625) && 1.41455078125 &&
                                              2<2.00095391273498535156 3 \
                                              12 && (1.4140625, 1.41455078125) && 1.414306640625 &&
                                              2<2.00026327371597290039 \
                                              13 && (1.4140625, 1.414306640625) && 1.4141845703125 &&
                                              1.99991799890995025634 8<2 \
                                              14 && (1.4141845703125, 1.414306640625) && 1.41424560546875 &&
                                              2<2.00009063258767127990 7 \
                                              15 && (1.4141845703125, 1.41424560546875) && 1.414215087890625 &&
                                              2<2.00000431481748819351 2 \
                                              16 && (1.4141845703125, 1.414215087890625) && 1.4141998291015625 &&
                                              1.99996115663088858127 6<2 \
                                              17 && (1.4141998291015625, 1.414215087890625) && 1.41420745849609375 &&
                                              1.99998273566598072648<2 \
                                              18 && (1.41420745849609375, 1.414215087890625) &&
                                              1.414211273193359375 && 1.99999352522718254476 8<2 \
                                              19 && (1.414211273193359375, 1.414215087890625) &&
                                              1.4142131805419921875 && 1.99999892001869739033 3<2 \
                                              20 && (1.4142131805419921875, 1.414215087890625) &&
                                              1.41421413421630859375 && 2<2.00000161741718329722
                                              end{align}begin{align}
                                              21 && (1.4142131805419921875, 1.41421413421630859375) &&
                                              1.41421365737915039062 5 && 2<2.00000026871771297010 1 \
                                              22 && (1.4142131805419921875, 1.41421365737915039062 5) &&
                                              1.41421341896057128906 2 && 1.99999959436814833679 8<2 \
                                              23 && (1.41421341896057128906 2, 1.41421365737915039062 5) &&
                                              1.41421353816986083984 4 && 1.99999993154291644259 5<2 \
                                              24 && (1.41421353816986083984 4, 1.41421365737915039062 5) &&
                                              1.41421359777450561523 4 && 2<2.00000010013031115363 4 \
                                              25 && (1.41421353816986083984 4, 1.41421359777450561523 4) &&
                                              1.41421356797218322753 9 && 2<2.00000001583661290993 6 \
                                              26 && (1.41421353816986083984 4, 1.41421356797218322753 9) &&
                                              1.41421355307102203369 1 && 1.99999997368976445422 1<2 \
                                              27 && (1.41421355307102203369 1, 1.41421356797218322753 9) &&
                                              1.41421356052160263061 5 && 1.99999999476318862656 8<2 \
                                              28 && (1.41421356052160263061 5, 1.41421356797218322753 9) &&
                                              1.41421356424689292907 7 && 2<2.00000000529990075437 4 \
                                              29 && (1.41421356052160263061 5, 1.41421356424689292907 7) &&
                                              1.41421356238424777984 6 && 2<2.00000000003154468700 1 \
                                              30 && (1.41421356052160263061 5, 1.41421356238424777984 6) &&
                                              1.41421356145292520523 && 1.99999999739736665591 7<2 \
                                              31 && (1.41421356145292520523, 1.41421356238424777984 6) &&
                                              1.41421356191858649253 8 && 1.99999999871445567124 2<2 \
                                              32 && (1.41421356191858649253 8, 1.41421356238424777984 6) &&
                                              1.41421356215141713619 2 && 1.99999999937300017906 8<2 \
                                              33 && (1.41421356215141713619 2, 1.41421356238424777984 6) &&
                                              1.41421356226783245801 9 && 1.99999999970227243302 1<2 \
                                              34 && (1.41421356226783245801 9, 1.41421356238424777984 6) &&
                                              1.41421356232604011893 3 && 1.99999999986690856000 8<2 \
                                              35 && (1.41421356232604011893 3, 1.41421356238424777984 6) &&
                                              1.41421356235514394938 9 && 1.99999999994922662350 4<2
                                              end{align}begin{align}
                                              36 && (1.41421356235514394938 9, 1.41421356238424777984 6) &&
                                              1.41421356236969586461 8 && 1.99999999999038565525 2<2 \
                                              37 && (1.41421356236969586461 8, 1.41421356238424777984 6) &&
                                              1.41421356237697182223 2 && 2<2.00000000001096517112 7 \
                                              38 && (1.41421356236969586461 8, 1.41421356237697182223 2) &&
                                              1.41421356237333384342 5 && 2<2.00000000000067541319 0 \
                                              39 && (1.41421356236969586461 8, 1.41421356237333384342 5) &&
                                              1.41421356237151485402 1 && 1.99999999999553053422 1<2 \
                                              40 && (1.41421356237151485402 1, 1.41421356237333384342 5) &&
                                              1.41421356237242434872 3 && 1.99999999999810297370 5<2 \
                                              41 && (1.41421356237242434872 3, 1.41421356237333384342 5) &&
                                              1.41421356237287909607 4 && 1.99999999999938919344 7<2 \
                                              42 && (1.41421356237287909607 4, 1.41421356237333384342 5) &&
                                              1.41421356237310646974 9 && 2<2.00000000000003230331 9 \
                                              43 && (1.41421356237287909607 4, 1.41421356237310646974 9) &&
                                              1.41421356237299278291 2 && 1.99999999999971074838 3<2 \
                                              44 && (1.41421356237299278291 2, 1.41421356237310646974 9) &&
                                              1.41421356237304962633 && 1.99999999999987152585<2 \
                                              45 && (1.41421356237304962633, 1.41421356237310646974 9) &&
                                              1.41421356237307804804 && 1.99999999999995191458 5<2 \
                                              46 && (1.41421356237307804804, 1.41421356237310646974 9) &&
                                              1.41421356237309225889 5 && 1.99999999999999210895 2<2 \
                                              47 && (1.41421356237309225889 5, 1.41421356237310646974 9) &&
                                              1.41421356237309936432 2 && 2<2.00000000000001220613 5 \
                                              48 && (1.41421356237309225889 5, 1.41421356237309936432 2) &&
                                              1.41421356237309581160 8 && 2<2.00000000000000215754 3 \
                                              49 && (1.41421356237309225889 5, 1.41421356237309581160 8) &&
                                              1.41421356237309403525 2 && 1.99999999999999713324 7<2 \
                                              50 && (1.41421356237309403525 2, 1.41421356237309581160 8) &&
                                              1.41421356237309492343 && 1.99999999999999964539 5<2 \
                                              51 && (1.41421356237309492343, 1.41421356237309581160 8) &&
                                              1.41421356237309536751 9 && 2<2.00000000000000090146 9 \
                                              52 && (1.41421356237309492343, 1.41421356237309536751 9) &&
                                              1.41421356237309514547 5 && 2<2.00000000000000027343 2 \
                                              53 && (1.41421356237309492343, 1.41421356237309514547 5) &&
                                              1.41421356237309503445 2 && 1.99999999999999995941 4<2 \
                                              54 && (1.41421356237309503445 2, 1.41421356237309514547 5) &&
                                              1.41421356237309508996 3 && 2<2.00000000000000011642 3 \
                                              55 && (1.41421356237309503445 2, 1.41421356237309508996 3) &&
                                              1.41421356237309506220 8 && 2<2.00000000000000003791 8 \
                                              56 && (1.41421356237309503445 2, 1.41421356237309506220 8) &&
                                              1.41421356237309504833 && 1.99999999999999999866 6<2 \
                                              57 && (1.41421356237309504833, 1.41421356237309506220 8) &&
                                              1.41421356237309505526 9 && 2<2.00000000000000001829 2 \
                                              58 && (1.41421356237309504833, 1.41421356237309505526 9) &&
                                              1.41421356237309505180 0 && 2<2.00000000000000000847 9 \
                                              59 && (1.41421356237309504833, 1.41421356237309505180 0) &&
                                              1.41421356237309505006 5 && 2<2.00000000000000000357 3 \
                                              60 && (1.41421356237309504833, 1.41421356237309505006 5) &&
                                              1.41421356237309504919 7 && 2<2.00000000000000000111 9 \
                                              61 && (1.41421356237309504833, 1.41421356237309504919 7) &&
                                              1.41421356237309504876 4 && 1.99999999999999999989 3<2 \
                                              62 && (1.41421356237309504876 4, 1.41421356237309504919 7) &&
                                              1.41421356237309504898 && 2<2.00000000000000000050 6 \
                                              63 && (1.41421356237309504876 4, 1.41421356237309504898) &&
                                              1.41421356237309504887 2 && 2<2.00000000000000000019 9 \
                                              64 && (1.41421356237309504876 4, 1.41421356237309504887 2) &&
                                              1.41421356237309504881 8 && 2<2.00000000000000000004 6 \
                                              65 && (1.41421356237309504876 4, 1.41421356237309504881 8) &&
                                              1.41421356237309504879 && 1.99999999999999999996 9<2 \
                                              66 && (1.41421356237309504879, 1.41421356237309504881 8) &&
                                              1.41421356237309504880 4 && 2<2.00000000000000000000 8 \
                                              67 && (1.41421356237309504879, 1.41421356237309504880 4) &&
                                              1.41421356237309504879 8 && 1.99999999999999999998 9<2 \
                                              68 && (1.41421356237309504879 8, 1.41421356237309504880 4) &&
                                              1.41421356237309504880 1 && 1.99999999999999999999 8<2 \
                                              69 && (1.41421356237309504880 1, 1.41421356237309504880 4) &&
                                              1.41421356237309504880 3 && 2<2.00000000000000000000 3
                                              end{align}






                                              share|cite|improve this answer









                                              $endgroup$



                                              Binary search for it.



                                              Since $1 < 2 < 4$, we must have $sqrt{1} < sqrt{2} < sqrt{4}$, so $sqrt{2} in (1,2)$. Now repeatedly: find the midpoint, $m$, of the current interval, $(a,b)$, square $m$ and compare with $2$, and if $2 = m^2$ declare that $m = sqrt{2}$, or if $2 < m^2$, make the new interval $(a,m)$, otherwise make the new interval $(m,b)$. This process halves the size of the interval on each step. Since $log_2(10^{-20}) = -66.438dots$, after 67 doublings, the error in taking any value from the interval is $<10^{-20}$ (but, if the interval straddles a digit change, you may have to perform additional steps to find out on which side of the change is $sqrt{2}$).



                                              This process is shown in the table below. Each decimal number is computed to $21$ digits and has trailing zeroes stripped. If there are still $21$ digits, a space is inserted between the $20^text{th}$ and $21^text{st}$.



                                              begin{align}
                                              text{step} && text{interval} && m && m^2 \
                                              1 && (1., 2.) && 1.5 && 2<2.25 \
                                              2 && (1., 1.5) && 1.25 && 1.5625<2 \
                                              3 && (1.25, 1.5) && 1.375 && 1.890625<2 \
                                              4 && (1.375, 1.5) && 1.4375 && 2<2.06640625 \
                                              5 && (1.375, 1.4375) && 1.40625 && 1.9775390625<2 \
                                              6 && (1.40625, 1.4375) && 1.421875 && 2<2.021728515625 \
                                              7 && (1.40625, 1.421875) && 1.4140625 && 1.99957275390625<2 \
                                              8 && (1.4140625, 1.421875) && 1.41796875 && 2<2.0106353759765625 \
                                              9 && (1.4140625, 1.41796875) && 1.416015625 && 2<2.005100250244140625
                                              \
                                              10 && (1.4140625, 1.416015625) && 1.4150390625 &&
                                              2<2.00233554840087890625 \
                                              11 && (1.4140625, 1.4150390625) && 1.41455078125 &&
                                              2<2.00095391273498535156 3 \
                                              12 && (1.4140625, 1.41455078125) && 1.414306640625 &&
                                              2<2.00026327371597290039 \
                                              13 && (1.4140625, 1.414306640625) && 1.4141845703125 &&
                                              1.99991799890995025634 8<2 \
                                              14 && (1.4141845703125, 1.414306640625) && 1.41424560546875 &&
                                              2<2.00009063258767127990 7 \
                                              15 && (1.4141845703125, 1.41424560546875) && 1.414215087890625 &&
                                              2<2.00000431481748819351 2 \
                                              16 && (1.4141845703125, 1.414215087890625) && 1.4141998291015625 &&
                                              1.99996115663088858127 6<2 \
                                              17 && (1.4141998291015625, 1.414215087890625) && 1.41420745849609375 &&
                                              1.99998273566598072648<2 \
                                              18 && (1.41420745849609375, 1.414215087890625) &&
                                              1.414211273193359375 && 1.99999352522718254476 8<2 \
                                              19 && (1.414211273193359375, 1.414215087890625) &&
                                              1.4142131805419921875 && 1.99999892001869739033 3<2 \
                                              20 && (1.4142131805419921875, 1.414215087890625) &&
                                              1.41421413421630859375 && 2<2.00000161741718329722
                                              end{align}begin{align}
                                              21 && (1.4142131805419921875, 1.41421413421630859375) &&
                                              1.41421365737915039062 5 && 2<2.00000026871771297010 1 \
                                              22 && (1.4142131805419921875, 1.41421365737915039062 5) &&
                                              1.41421341896057128906 2 && 1.99999959436814833679 8<2 \
                                              23 && (1.41421341896057128906 2, 1.41421365737915039062 5) &&
                                              1.41421353816986083984 4 && 1.99999993154291644259 5<2 \
                                              24 && (1.41421353816986083984 4, 1.41421365737915039062 5) &&
                                              1.41421359777450561523 4 && 2<2.00000010013031115363 4 \
                                              25 && (1.41421353816986083984 4, 1.41421359777450561523 4) &&
                                              1.41421356797218322753 9 && 2<2.00000001583661290993 6 \
                                              26 && (1.41421353816986083984 4, 1.41421356797218322753 9) &&
                                              1.41421355307102203369 1 && 1.99999997368976445422 1<2 \
                                              27 && (1.41421355307102203369 1, 1.41421356797218322753 9) &&
                                              1.41421356052160263061 5 && 1.99999999476318862656 8<2 \
                                              28 && (1.41421356052160263061 5, 1.41421356797218322753 9) &&
                                              1.41421356424689292907 7 && 2<2.00000000529990075437 4 \
                                              29 && (1.41421356052160263061 5, 1.41421356424689292907 7) &&
                                              1.41421356238424777984 6 && 2<2.00000000003154468700 1 \
                                              30 && (1.41421356052160263061 5, 1.41421356238424777984 6) &&
                                              1.41421356145292520523 && 1.99999999739736665591 7<2 \
                                              31 && (1.41421356145292520523, 1.41421356238424777984 6) &&
                                              1.41421356191858649253 8 && 1.99999999871445567124 2<2 \
                                              32 && (1.41421356191858649253 8, 1.41421356238424777984 6) &&
                                              1.41421356215141713619 2 && 1.99999999937300017906 8<2 \
                                              33 && (1.41421356215141713619 2, 1.41421356238424777984 6) &&
                                              1.41421356226783245801 9 && 1.99999999970227243302 1<2 \
                                              34 && (1.41421356226783245801 9, 1.41421356238424777984 6) &&
                                              1.41421356232604011893 3 && 1.99999999986690856000 8<2 \
                                              35 && (1.41421356232604011893 3, 1.41421356238424777984 6) &&
                                              1.41421356235514394938 9 && 1.99999999994922662350 4<2
                                              end{align}begin{align}
                                              36 && (1.41421356235514394938 9, 1.41421356238424777984 6) &&
                                              1.41421356236969586461 8 && 1.99999999999038565525 2<2 \
                                              37 && (1.41421356236969586461 8, 1.41421356238424777984 6) &&
                                              1.41421356237697182223 2 && 2<2.00000000001096517112 7 \
                                              38 && (1.41421356236969586461 8, 1.41421356237697182223 2) &&
                                              1.41421356237333384342 5 && 2<2.00000000000067541319 0 \
                                              39 && (1.41421356236969586461 8, 1.41421356237333384342 5) &&
                                              1.41421356237151485402 1 && 1.99999999999553053422 1<2 \
                                              40 && (1.41421356237151485402 1, 1.41421356237333384342 5) &&
                                              1.41421356237242434872 3 && 1.99999999999810297370 5<2 \
                                              41 && (1.41421356237242434872 3, 1.41421356237333384342 5) &&
                                              1.41421356237287909607 4 && 1.99999999999938919344 7<2 \
                                              42 && (1.41421356237287909607 4, 1.41421356237333384342 5) &&
                                              1.41421356237310646974 9 && 2<2.00000000000003230331 9 \
                                              43 && (1.41421356237287909607 4, 1.41421356237310646974 9) &&
                                              1.41421356237299278291 2 && 1.99999999999971074838 3<2 \
                                              44 && (1.41421356237299278291 2, 1.41421356237310646974 9) &&
                                              1.41421356237304962633 && 1.99999999999987152585<2 \
                                              45 && (1.41421356237304962633, 1.41421356237310646974 9) &&
                                              1.41421356237307804804 && 1.99999999999995191458 5<2 \
                                              46 && (1.41421356237307804804, 1.41421356237310646974 9) &&
                                              1.41421356237309225889 5 && 1.99999999999999210895 2<2 \
                                              47 && (1.41421356237309225889 5, 1.41421356237310646974 9) &&
                                              1.41421356237309936432 2 && 2<2.00000000000001220613 5 \
                                              48 && (1.41421356237309225889 5, 1.41421356237309936432 2) &&
                                              1.41421356237309581160 8 && 2<2.00000000000000215754 3 \
                                              49 && (1.41421356237309225889 5, 1.41421356237309581160 8) &&
                                              1.41421356237309403525 2 && 1.99999999999999713324 7<2 \
                                              50 && (1.41421356237309403525 2, 1.41421356237309581160 8) &&
                                              1.41421356237309492343 && 1.99999999999999964539 5<2 \
                                              51 && (1.41421356237309492343, 1.41421356237309581160 8) &&
                                              1.41421356237309536751 9 && 2<2.00000000000000090146 9 \
                                              52 && (1.41421356237309492343, 1.41421356237309536751 9) &&
                                              1.41421356237309514547 5 && 2<2.00000000000000027343 2 \
                                              53 && (1.41421356237309492343, 1.41421356237309514547 5) &&
                                              1.41421356237309503445 2 && 1.99999999999999995941 4<2 \
                                              54 && (1.41421356237309503445 2, 1.41421356237309514547 5) &&
                                              1.41421356237309508996 3 && 2<2.00000000000000011642 3 \
                                              55 && (1.41421356237309503445 2, 1.41421356237309508996 3) &&
                                              1.41421356237309506220 8 && 2<2.00000000000000003791 8 \
                                              56 && (1.41421356237309503445 2, 1.41421356237309506220 8) &&
                                              1.41421356237309504833 && 1.99999999999999999866 6<2 \
                                              57 && (1.41421356237309504833, 1.41421356237309506220 8) &&
                                              1.41421356237309505526 9 && 2<2.00000000000000001829 2 \
                                              58 && (1.41421356237309504833, 1.41421356237309505526 9) &&
                                              1.41421356237309505180 0 && 2<2.00000000000000000847 9 \
                                              59 && (1.41421356237309504833, 1.41421356237309505180 0) &&
                                              1.41421356237309505006 5 && 2<2.00000000000000000357 3 \
                                              60 && (1.41421356237309504833, 1.41421356237309505006 5) &&
                                              1.41421356237309504919 7 && 2<2.00000000000000000111 9 \
                                              61 && (1.41421356237309504833, 1.41421356237309504919 7) &&
                                              1.41421356237309504876 4 && 1.99999999999999999989 3<2 \
                                              62 && (1.41421356237309504876 4, 1.41421356237309504919 7) &&
                                              1.41421356237309504898 && 2<2.00000000000000000050 6 \
                                              63 && (1.41421356237309504876 4, 1.41421356237309504898) &&
                                              1.41421356237309504887 2 && 2<2.00000000000000000019 9 \
                                              64 && (1.41421356237309504876 4, 1.41421356237309504887 2) &&
                                              1.41421356237309504881 8 && 2<2.00000000000000000004 6 \
                                              65 && (1.41421356237309504876 4, 1.41421356237309504881 8) &&
                                              1.41421356237309504879 && 1.99999999999999999996 9<2 \
                                              66 && (1.41421356237309504879, 1.41421356237309504881 8) &&
                                              1.41421356237309504880 4 && 2<2.00000000000000000000 8 \
                                              67 && (1.41421356237309504879, 1.41421356237309504880 4) &&
                                              1.41421356237309504879 8 && 1.99999999999999999998 9<2 \
                                              68 && (1.41421356237309504879 8, 1.41421356237309504880 4) &&
                                              1.41421356237309504880 1 && 1.99999999999999999999 8<2 \
                                              69 && (1.41421356237309504880 1, 1.41421356237309504880 4) &&
                                              1.41421356237309504880 3 && 2<2.00000000000000000000 3
                                              end{align}







                                              share|cite|improve this answer












                                              share|cite|improve this answer



                                              share|cite|improve this answer










                                              answered Sep 16 '18 at 5:59









                                              Eric TowersEric Towers

                                              32.8k22370




                                              32.8k22370























                                                  1












                                                  $begingroup$

                                                  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 elegant:



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



                                                  For a rational initial guess $x$ the result $(x + y)$ is also rational, but much closer to the desired value.



                                                  For example if we take $x = 3/2$, then $(x +y)=577/408$, which differs from the square root of 2 by a factor 1.0000015. If we start with $x = 7/5$, the result is $19601/13860$, which differs from the square of root of $2$ by a factor $1.0000000013$






                                                  share|cite|improve this answer











                                                  $endgroup$













                                                  • $begingroup$
                                                    Please show what happens with 140/99. I find the error to be 1.2 10^-18 on my WP-34s iPhone emulator in double precision mode (good to at least 30 digits). If you recycle 577/408, you get an error 9.0 10^-25. That meets to goal of 20 digits. Recycling 19601/13860 gives an error of absolute zero (on the calculator).
                                                    $endgroup$
                                                    – richard1941
                                                    Dec 21 '18 at 17:50










                                                  • $begingroup$
                                                    Thanks! The initial values $99/70$ and $140/99$ both result in $768398401/543339720$.
                                                    $endgroup$
                                                    – M. Wind
                                                    Dec 23 '18 at 19:39


















                                                  1












                                                  $begingroup$

                                                  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 elegant:



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



                                                  For a rational initial guess $x$ the result $(x + y)$ is also rational, but much closer to the desired value.



                                                  For example if we take $x = 3/2$, then $(x +y)=577/408$, which differs from the square root of 2 by a factor 1.0000015. If we start with $x = 7/5$, the result is $19601/13860$, which differs from the square of root of $2$ by a factor $1.0000000013$






                                                  share|cite|improve this answer











                                                  $endgroup$













                                                  • $begingroup$
                                                    Please show what happens with 140/99. I find the error to be 1.2 10^-18 on my WP-34s iPhone emulator in double precision mode (good to at least 30 digits). If you recycle 577/408, you get an error 9.0 10^-25. That meets to goal of 20 digits. Recycling 19601/13860 gives an error of absolute zero (on the calculator).
                                                    $endgroup$
                                                    – richard1941
                                                    Dec 21 '18 at 17:50










                                                  • $begingroup$
                                                    Thanks! The initial values $99/70$ and $140/99$ both result in $768398401/543339720$.
                                                    $endgroup$
                                                    – M. Wind
                                                    Dec 23 '18 at 19:39
















                                                  1












                                                  1








                                                  1





                                                  $begingroup$

                                                  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 elegant:



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



                                                  For a rational initial guess $x$ the result $(x + y)$ is also rational, but much closer to the desired value.



                                                  For example if we take $x = 3/2$, then $(x +y)=577/408$, which differs from the square root of 2 by a factor 1.0000015. If we start with $x = 7/5$, the result is $19601/13860$, which differs from the square of root of $2$ by a factor $1.0000000013$






                                                  share|cite|improve this answer











                                                  $endgroup$



                                                  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 elegant:



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



                                                  For a rational initial guess $x$ the result $(x + y)$ is also rational, but much closer to the desired value.



                                                  For example if we take $x = 3/2$, then $(x +y)=577/408$, which differs from the square root of 2 by a factor 1.0000015. If we start with $x = 7/5$, the result is $19601/13860$, which differs from the square of root of $2$ by a factor $1.0000000013$







                                                  share|cite|improve this answer














                                                  share|cite|improve this answer



                                                  share|cite|improve this answer








                                                  edited Sep 16 '18 at 16:42

























                                                  answered Sep 15 '18 at 5:36









                                                  M. WindM. Wind

                                                  2,093715




                                                  2,093715












                                                  • $begingroup$
                                                    Please show what happens with 140/99. I find the error to be 1.2 10^-18 on my WP-34s iPhone emulator in double precision mode (good to at least 30 digits). If you recycle 577/408, you get an error 9.0 10^-25. That meets to goal of 20 digits. Recycling 19601/13860 gives an error of absolute zero (on the calculator).
                                                    $endgroup$
                                                    – richard1941
                                                    Dec 21 '18 at 17:50










                                                  • $begingroup$
                                                    Thanks! The initial values $99/70$ and $140/99$ both result in $768398401/543339720$.
                                                    $endgroup$
                                                    – M. Wind
                                                    Dec 23 '18 at 19:39




















                                                  • $begingroup$
                                                    Please show what happens with 140/99. I find the error to be 1.2 10^-18 on my WP-34s iPhone emulator in double precision mode (good to at least 30 digits). If you recycle 577/408, you get an error 9.0 10^-25. That meets to goal of 20 digits. Recycling 19601/13860 gives an error of absolute zero (on the calculator).
                                                    $endgroup$
                                                    – richard1941
                                                    Dec 21 '18 at 17:50










                                                  • $begingroup$
                                                    Thanks! The initial values $99/70$ and $140/99$ both result in $768398401/543339720$.
                                                    $endgroup$
                                                    – M. Wind
                                                    Dec 23 '18 at 19:39


















                                                  $begingroup$
                                                  Please show what happens with 140/99. I find the error to be 1.2 10^-18 on my WP-34s iPhone emulator in double precision mode (good to at least 30 digits). If you recycle 577/408, you get an error 9.0 10^-25. That meets to goal of 20 digits. Recycling 19601/13860 gives an error of absolute zero (on the calculator).
                                                  $endgroup$
                                                  – richard1941
                                                  Dec 21 '18 at 17:50




                                                  $begingroup$
                                                  Please show what happens with 140/99. I find the error to be 1.2 10^-18 on my WP-34s iPhone emulator in double precision mode (good to at least 30 digits). If you recycle 577/408, you get an error 9.0 10^-25. That meets to goal of 20 digits. Recycling 19601/13860 gives an error of absolute zero (on the calculator).
                                                  $endgroup$
                                                  – richard1941
                                                  Dec 21 '18 at 17:50












                                                  $begingroup$
                                                  Thanks! The initial values $99/70$ and $140/99$ both result in $768398401/543339720$.
                                                  $endgroup$
                                                  – M. Wind
                                                  Dec 23 '18 at 19:39






                                                  $begingroup$
                                                  Thanks! The initial values $99/70$ and $140/99$ both result in $768398401/543339720$.
                                                  $endgroup$
                                                  – M. Wind
                                                  Dec 23 '18 at 19:39













                                                  0












                                                  $begingroup$

                                                  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:
                                                  $$sqrt{2}approx 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









                                                  $endgroup$


















                                                    0












                                                    $begingroup$

                                                    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:
                                                    $$sqrt{2}approx 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









                                                    $endgroup$
















                                                      0












                                                      0








                                                      0





                                                      $begingroup$

                                                      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:
                                                      $$sqrt{2}approx 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









                                                      $endgroup$



                                                      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:
                                                      $$sqrt{2}approx 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 Sep 14 '18 at 13:05









                                                      Jaroslaw MatlakJaroslaw Matlak

                                                      4,181930




                                                      4,181930























                                                          0












                                                          $begingroup$

                                                          Using the fact that $sin frac{pi}{4} = frac{sqrt{2}}{2}$, then we have to find $2 sin frac{pi}{4}$.



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



                                                          $$sin x = x - frac{x^3}{3!} + frac{x^5}{5!} + O(x^6),$$



                                                          so we have:



                                                          $$sin frac{pi}{4} approx frac{pi}{4} - frac{(pi/4)^3}{3!} + frac{(pi/4)^5}{5!} .$$



                                                          If we approximate $pi$ as $frac{22}{7}$, then we have $frac{pi}{4} = frac{11}{14}$, then we have:



                                                          $$sin frac{pi}{4} approxfrac{11}{14} - frac{(11/14)^3}{3!} + frac{(11/14)^5}{5!},$$



                                                          which when you multiply by $2$ to get $sqrt{2}$, 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 $frac{355}{113}$), then we can get to $20$ correct digits.






                                                          share|cite|improve this answer









                                                          $endgroup$









                                                          • 1




                                                            $begingroup$
                                                            Don’t you need pi to nearly 20 digits for this to work?
                                                            $endgroup$
                                                            – JoeTaxpayer
                                                            Sep 15 '18 at 2:10
















                                                          0












                                                          $begingroup$

                                                          Using the fact that $sin frac{pi}{4} = frac{sqrt{2}}{2}$, then we have to find $2 sin frac{pi}{4}$.



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



                                                          $$sin x = x - frac{x^3}{3!} + frac{x^5}{5!} + O(x^6),$$



                                                          so we have:



                                                          $$sin frac{pi}{4} approx frac{pi}{4} - frac{(pi/4)^3}{3!} + frac{(pi/4)^5}{5!} .$$



                                                          If we approximate $pi$ as $frac{22}{7}$, then we have $frac{pi}{4} = frac{11}{14}$, then we have:



                                                          $$sin frac{pi}{4} approxfrac{11}{14} - frac{(11/14)^3}{3!} + frac{(11/14)^5}{5!},$$



                                                          which when you multiply by $2$ to get $sqrt{2}$, 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 $frac{355}{113}$), then we can get to $20$ correct digits.






                                                          share|cite|improve this answer









                                                          $endgroup$









                                                          • 1




                                                            $begingroup$
                                                            Don’t you need pi to nearly 20 digits for this to work?
                                                            $endgroup$
                                                            – JoeTaxpayer
                                                            Sep 15 '18 at 2:10














                                                          0












                                                          0








                                                          0





                                                          $begingroup$

                                                          Using the fact that $sin frac{pi}{4} = frac{sqrt{2}}{2}$, then we have to find $2 sin frac{pi}{4}$.



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



                                                          $$sin x = x - frac{x^3}{3!} + frac{x^5}{5!} + O(x^6),$$



                                                          so we have:



                                                          $$sin frac{pi}{4} approx frac{pi}{4} - frac{(pi/4)^3}{3!} + frac{(pi/4)^5}{5!} .$$



                                                          If we approximate $pi$ as $frac{22}{7}$, then we have $frac{pi}{4} = frac{11}{14}$, then we have:



                                                          $$sin frac{pi}{4} approxfrac{11}{14} - frac{(11/14)^3}{3!} + frac{(11/14)^5}{5!},$$



                                                          which when you multiply by $2$ to get $sqrt{2}$, 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 $frac{355}{113}$), then we can get to $20$ correct digits.






                                                          share|cite|improve this answer









                                                          $endgroup$



                                                          Using the fact that $sin frac{pi}{4} = frac{sqrt{2}}{2}$, then we have to find $2 sin frac{pi}{4}$.



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



                                                          $$sin x = x - frac{x^3}{3!} + frac{x^5}{5!} + O(x^6),$$



                                                          so we have:



                                                          $$sin frac{pi}{4} approx frac{pi}{4} - frac{(pi/4)^3}{3!} + frac{(pi/4)^5}{5!} .$$



                                                          If we approximate $pi$ as $frac{22}{7}$, then we have $frac{pi}{4} = frac{11}{14}$, then we have:



                                                          $$sin frac{pi}{4} approxfrac{11}{14} - frac{(11/14)^3}{3!} + frac{(11/14)^5}{5!},$$



                                                          which when you multiply by $2$ to get $sqrt{2}$, 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 $frac{355}{113}$), then we can get to $20$ correct digits.







                                                          share|cite|improve this answer












                                                          share|cite|improve this answer



                                                          share|cite|improve this answer










                                                          answered Sep 14 '18 at 13:49









                                                          Toby MakToby Mak

                                                          3,52311128




                                                          3,52311128








                                                          • 1




                                                            $begingroup$
                                                            Don’t you need pi to nearly 20 digits for this to work?
                                                            $endgroup$
                                                            – JoeTaxpayer
                                                            Sep 15 '18 at 2:10














                                                          • 1




                                                            $begingroup$
                                                            Don’t you need pi to nearly 20 digits for this to work?
                                                            $endgroup$
                                                            – JoeTaxpayer
                                                            Sep 15 '18 at 2:10








                                                          1




                                                          1




                                                          $begingroup$
                                                          Don’t you need pi to nearly 20 digits for this to work?
                                                          $endgroup$
                                                          – JoeTaxpayer
                                                          Sep 15 '18 at 2:10




                                                          $begingroup$
                                                          Don’t you need pi to nearly 20 digits for this to work?
                                                          $endgroup$
                                                          – JoeTaxpayer
                                                          Sep 15 '18 at 2:10











                                                          0












                                                          $begingroup$

                                                          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 $sqrt{x}$ is to find first the closest integer which approximates $sqrt{x}$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                          $$ sqrt{x} approx a + (x-a^2)cdot frac{1}{2 a} - (x-a^2)^2/2 cdot frac{1}{4 a^3} + cdots. $$
                                                          The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrt{x}$, 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 $sqrt{2}$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                          $$sqrt{2} approx 1 + (2-1)cdot frac{1}{2} - (2-1)^2/2cdot frac{1}{4} = 1 + 0.5 - 0.125 = 1.375 $$
                                                          and the absolute error is given by
                                                          $$ E=left|(2-1)^3/3!cdot frac{3}{8 cdot xi^2sqrt{xi}}right| = frac{1}{16} cdot frac{1}{|xi^2sqrt{xi}|}$$
                                                          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 frac{1}{16} $$
                                                          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 $sqrt{2}$ 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 $sqrt{10}$ on the go (especially for $sqrt{x}$ with $x$ big, the Taylor approximation is better since the $sqrt{bullet}$ 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 $sqrt{x}$ 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 $sqrt{122}$, then first order approximation of my method gives
                                                          $$ sqrt{122} approx 11 + frac{1}{2cdot 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{-1}{8cdot 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











                                                          $endgroup$









                                                          • 2




                                                            $begingroup$
                                                            I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                            $endgroup$
                                                            – leftaroundabout
                                                            Sep 14 '18 at 14:48












                                                          • $begingroup$
                                                            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 $sqrt{2.243}$ also quite quickly.
                                                            $endgroup$
                                                            – Stan Tendijck
                                                            Sep 14 '18 at 15:38










                                                          • $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – Wildcard
                                                            Sep 14 '18 at 18:17






                                                          • 3




                                                            $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – TurlocTheRed
                                                            Sep 15 '18 at 2:09
















                                                          0












                                                          $begingroup$

                                                          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 $sqrt{x}$ is to find first the closest integer which approximates $sqrt{x}$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                          $$ sqrt{x} approx a + (x-a^2)cdot frac{1}{2 a} - (x-a^2)^2/2 cdot frac{1}{4 a^3} + cdots. $$
                                                          The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrt{x}$, 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 $sqrt{2}$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                          $$sqrt{2} approx 1 + (2-1)cdot frac{1}{2} - (2-1)^2/2cdot frac{1}{4} = 1 + 0.5 - 0.125 = 1.375 $$
                                                          and the absolute error is given by
                                                          $$ E=left|(2-1)^3/3!cdot frac{3}{8 cdot xi^2sqrt{xi}}right| = frac{1}{16} cdot frac{1}{|xi^2sqrt{xi}|}$$
                                                          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 frac{1}{16} $$
                                                          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 $sqrt{2}$ 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 $sqrt{10}$ on the go (especially for $sqrt{x}$ with $x$ big, the Taylor approximation is better since the $sqrt{bullet}$ 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 $sqrt{x}$ 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 $sqrt{122}$, then first order approximation of my method gives
                                                          $$ sqrt{122} approx 11 + frac{1}{2cdot 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{-1}{8cdot 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











                                                          $endgroup$









                                                          • 2




                                                            $begingroup$
                                                            I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                            $endgroup$
                                                            – leftaroundabout
                                                            Sep 14 '18 at 14:48












                                                          • $begingroup$
                                                            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 $sqrt{2.243}$ also quite quickly.
                                                            $endgroup$
                                                            – Stan Tendijck
                                                            Sep 14 '18 at 15:38










                                                          • $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – Wildcard
                                                            Sep 14 '18 at 18:17






                                                          • 3




                                                            $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – TurlocTheRed
                                                            Sep 15 '18 at 2:09














                                                          0












                                                          0








                                                          0





                                                          $begingroup$

                                                          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 $sqrt{x}$ is to find first the closest integer which approximates $sqrt{x}$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                          $$ sqrt{x} approx a + (x-a^2)cdot frac{1}{2 a} - (x-a^2)^2/2 cdot frac{1}{4 a^3} + cdots. $$
                                                          The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrt{x}$, 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 $sqrt{2}$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                          $$sqrt{2} approx 1 + (2-1)cdot frac{1}{2} - (2-1)^2/2cdot frac{1}{4} = 1 + 0.5 - 0.125 = 1.375 $$
                                                          and the absolute error is given by
                                                          $$ E=left|(2-1)^3/3!cdot frac{3}{8 cdot xi^2sqrt{xi}}right| = frac{1}{16} cdot frac{1}{|xi^2sqrt{xi}|}$$
                                                          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 frac{1}{16} $$
                                                          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 $sqrt{2}$ 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 $sqrt{10}$ on the go (especially for $sqrt{x}$ with $x$ big, the Taylor approximation is better since the $sqrt{bullet}$ 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 $sqrt{x}$ 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 $sqrt{122}$, then first order approximation of my method gives
                                                          $$ sqrt{122} approx 11 + frac{1}{2cdot 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{-1}{8cdot 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











                                                          $endgroup$



                                                          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 $sqrt{x}$ is to find first the closest integer which approximates $sqrt{x}$ and call this $a$, then apply Taylor to $a^2$. Then Taylor says
                                                          $$ sqrt{x} approx a + (x-a^2)cdot frac{1}{2 a} - (x-a^2)^2/2 cdot frac{1}{4 a^3} + cdots. $$
                                                          The thing that is nice here is that you also get bounds on the error you make. So, denote $f(x) = sqrt{x}$, 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 $sqrt{2}$ and thus we will take $a=1$. Then, let's take a second order approximation
                                                          $$sqrt{2} approx 1 + (2-1)cdot frac{1}{2} - (2-1)^2/2cdot frac{1}{4} = 1 + 0.5 - 0.125 = 1.375 $$
                                                          and the absolute error is given by
                                                          $$ E=left|(2-1)^3/3!cdot frac{3}{8 cdot xi^2sqrt{xi}}right| = frac{1}{16} cdot frac{1}{|xi^2sqrt{xi}|}$$
                                                          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 frac{1}{16} $$
                                                          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 $sqrt{2}$ 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 $sqrt{10}$ on the go (especially for $sqrt{x}$ with $x$ big, the Taylor approximation is better since the $sqrt{bullet}$ 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 $sqrt{x}$ 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 $sqrt{122}$, then first order approximation of my method gives
                                                          $$ sqrt{122} approx 11 + frac{1}{2cdot 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{-1}{8cdot 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 Sep 15 '18 at 11:09

























                                                          answered Sep 14 '18 at 12:39









                                                          Stan TendijckStan Tendijck

                                                          2,028414




                                                          2,028414








                                                          • 2




                                                            $begingroup$
                                                            I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                            $endgroup$
                                                            – leftaroundabout
                                                            Sep 14 '18 at 14:48












                                                          • $begingroup$
                                                            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 $sqrt{2.243}$ also quite quickly.
                                                            $endgroup$
                                                            – Stan Tendijck
                                                            Sep 14 '18 at 15:38










                                                          • $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – Wildcard
                                                            Sep 14 '18 at 18:17






                                                          • 3




                                                            $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – TurlocTheRed
                                                            Sep 15 '18 at 2:09














                                                          • 2




                                                            $begingroup$
                                                            I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                            $endgroup$
                                                            – leftaroundabout
                                                            Sep 14 '18 at 14:48












                                                          • $begingroup$
                                                            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 $sqrt{2.243}$ also quite quickly.
                                                            $endgroup$
                                                            – Stan Tendijck
                                                            Sep 14 '18 at 15:38










                                                          • $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – Wildcard
                                                            Sep 14 '18 at 18:17






                                                          • 3




                                                            $begingroup$
                                                            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.
                                                            $endgroup$
                                                            – TurlocTheRed
                                                            Sep 15 '18 at 2:09








                                                          2




                                                          2




                                                          $begingroup$
                                                          I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                          $endgroup$
                                                          – leftaroundabout
                                                          Sep 14 '18 at 14:48






                                                          $begingroup$
                                                          I'd say this is more difficult, less precise, and not as generally applicable as Newton-Raphson.
                                                          $endgroup$
                                                          – leftaroundabout
                                                          Sep 14 '18 at 14:48














                                                          $begingroup$
                                                          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 $sqrt{2.243}$ also quite quickly.
                                                          $endgroup$
                                                          – Stan Tendijck
                                                          Sep 14 '18 at 15:38




                                                          $begingroup$
                                                          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 $sqrt{2.243}$ also quite quickly.
                                                          $endgroup$
                                                          – Stan Tendijck
                                                          Sep 14 '18 at 15:38












                                                          $begingroup$
                                                          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.
                                                          $endgroup$
                                                          – Wildcard
                                                          Sep 14 '18 at 18:17




                                                          $begingroup$
                                                          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.
                                                          $endgroup$
                                                          – Wildcard
                                                          Sep 14 '18 at 18:17




                                                          3




                                                          3




                                                          $begingroup$
                                                          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.
                                                          $endgroup$
                                                          – TurlocTheRed
                                                          Sep 15 '18 at 2:09




                                                          $begingroup$
                                                          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.
                                                          $endgroup$
                                                          – TurlocTheRed
                                                          Sep 15 '18 at 2:09











                                                          0












                                                          $begingroup$

                                                          I came up with an interesting, but terribly inefficient method.



                                                          Consider the sequence {$x_n$}: $1,frac{1}{2},frac{1}{2},frac{1}{3},frac{1}{3},frac{1}{3},frac{1}{4},frac{1}{4},frac{1}{4},frac{1}{4}$, ...



                                                          Suppose you want k digits of the square root of 2. Then add up the first $100^k$ terms and then divide the sum by $10^k$.






                                                          share|cite|improve this answer









                                                          $endgroup$


















                                                            0












                                                            $begingroup$

                                                            I came up with an interesting, but terribly inefficient method.



                                                            Consider the sequence {$x_n$}: $1,frac{1}{2},frac{1}{2},frac{1}{3},frac{1}{3},frac{1}{3},frac{1}{4},frac{1}{4},frac{1}{4},frac{1}{4}$, ...



                                                            Suppose you want k digits of the square root of 2. Then add up the first $100^k$ terms and then divide the sum by $10^k$.






                                                            share|cite|improve this answer









                                                            $endgroup$
















                                                              0












                                                              0








                                                              0





                                                              $begingroup$

                                                              I came up with an interesting, but terribly inefficient method.



                                                              Consider the sequence {$x_n$}: $1,frac{1}{2},frac{1}{2},frac{1}{3},frac{1}{3},frac{1}{3},frac{1}{4},frac{1}{4},frac{1}{4},frac{1}{4}$, ...



                                                              Suppose you want k digits of the square root of 2. Then add up the first $100^k$ terms and then divide the sum by $10^k$.






                                                              share|cite|improve this answer









                                                              $endgroup$



                                                              I came up with an interesting, but terribly inefficient method.



                                                              Consider the sequence {$x_n$}: $1,frac{1}{2},frac{1}{2},frac{1}{3},frac{1}{3},frac{1}{3},frac{1}{4},frac{1}{4},frac{1}{4},frac{1}{4}$, ...



                                                              Suppose you want k digits of the square root of 2. Then add up the first $100^k$ terms and then divide the sum by $10^k$.







                                                              share|cite|improve this answer












                                                              share|cite|improve this answer



                                                              share|cite|improve this answer










                                                              answered Sep 28 '18 at 1:09









                                                              TurlocTheRedTurlocTheRed

                                                              916311




                                                              916311























                                                                  0












                                                                  $begingroup$

                                                                  I know an easy way to calculate the binary digits of $sqrt{2}$. Take the ordered pair (1, 2) $1^2$ is less than 2 and $2^2$ is more than 2. Calculate the square of the average $1.5^2$ in base 2. The square of the average is just the average of the squares minus $frac{1}{4}$. The result expressed in binary is 10.01 so the first binary digit after the decimal is 0. Take the next ordered pair to be (1, 1.5) and calculate the square of its average which is the average of its squares minus $frac{1}{16}$. The result expressed in binary is 1.1001 so the next binary digit is 1.






                                                                  share|cite|improve this answer









                                                                  $endgroup$


















                                                                    0












                                                                    $begingroup$

                                                                    I know an easy way to calculate the binary digits of $sqrt{2}$. Take the ordered pair (1, 2) $1^2$ is less than 2 and $2^2$ is more than 2. Calculate the square of the average $1.5^2$ in base 2. The square of the average is just the average of the squares minus $frac{1}{4}$. The result expressed in binary is 10.01 so the first binary digit after the decimal is 0. Take the next ordered pair to be (1, 1.5) and calculate the square of its average which is the average of its squares minus $frac{1}{16}$. The result expressed in binary is 1.1001 so the next binary digit is 1.






                                                                    share|cite|improve this answer









                                                                    $endgroup$
















                                                                      0












                                                                      0








                                                                      0





                                                                      $begingroup$

                                                                      I know an easy way to calculate the binary digits of $sqrt{2}$. Take the ordered pair (1, 2) $1^2$ is less than 2 and $2^2$ is more than 2. Calculate the square of the average $1.5^2$ in base 2. The square of the average is just the average of the squares minus $frac{1}{4}$. The result expressed in binary is 10.01 so the first binary digit after the decimal is 0. Take the next ordered pair to be (1, 1.5) and calculate the square of its average which is the average of its squares minus $frac{1}{16}$. The result expressed in binary is 1.1001 so the next binary digit is 1.






                                                                      share|cite|improve this answer









                                                                      $endgroup$



                                                                      I know an easy way to calculate the binary digits of $sqrt{2}$. Take the ordered pair (1, 2) $1^2$ is less than 2 and $2^2$ is more than 2. Calculate the square of the average $1.5^2$ in base 2. The square of the average is just the average of the squares minus $frac{1}{4}$. The result expressed in binary is 10.01 so the first binary digit after the decimal is 0. Take the next ordered pair to be (1, 1.5) and calculate the square of its average which is the average of its squares minus $frac{1}{16}$. The result expressed in binary is 1.1001 so the next binary digit is 1.







                                                                      share|cite|improve this answer












                                                                      share|cite|improve this answer



                                                                      share|cite|improve this answer










                                                                      answered Oct 24 '18 at 3:56









                                                                      TimothyTimothy

                                                                      315214




                                                                      315214























                                                                          0












                                                                          $begingroup$

                                                                          Towers' bisection method above is similar to your own approach, but more efficient. Another method that is not as good as binary search, but is better than your own method, is to increment the last digit in bigger steps. I would try incrementing by 3. The worst case is that you reach the correct digit in 5 steps instead of 9.



                                                                          My favorite method for mental approximation is to find the next lowest square, determine the error, and add to its square root the error divided by double the guess. For sqrt(200), the lowest square is 196. The error is 4, so my mental estimate is 14 + 4/14 = 14.142857...



                                                                          I apologize for off-topic, but note that square roots can be used to calculate logarithms by a process similar to bisection. I suspect that is how it was done in the late 16th century, as they did not yet have calculus. In our times, there are extremely accurate formulas for logarithm that still require square roots. This exercise should make you appreciate the power of a square root button on a calculator, even if you have no "scientific" functions.






                                                                          share|cite|improve this answer









                                                                          $endgroup$


















                                                                            0












                                                                            $begingroup$

                                                                            Towers' bisection method above is similar to your own approach, but more efficient. Another method that is not as good as binary search, but is better than your own method, is to increment the last digit in bigger steps. I would try incrementing by 3. The worst case is that you reach the correct digit in 5 steps instead of 9.



                                                                            My favorite method for mental approximation is to find the next lowest square, determine the error, and add to its square root the error divided by double the guess. For sqrt(200), the lowest square is 196. The error is 4, so my mental estimate is 14 + 4/14 = 14.142857...



                                                                            I apologize for off-topic, but note that square roots can be used to calculate logarithms by a process similar to bisection. I suspect that is how it was done in the late 16th century, as they did not yet have calculus. In our times, there are extremely accurate formulas for logarithm that still require square roots. This exercise should make you appreciate the power of a square root button on a calculator, even if you have no "scientific" functions.






                                                                            share|cite|improve this answer









                                                                            $endgroup$
















                                                                              0












                                                                              0








                                                                              0





                                                                              $begingroup$

                                                                              Towers' bisection method above is similar to your own approach, but more efficient. Another method that is not as good as binary search, but is better than your own method, is to increment the last digit in bigger steps. I would try incrementing by 3. The worst case is that you reach the correct digit in 5 steps instead of 9.



                                                                              My favorite method for mental approximation is to find the next lowest square, determine the error, and add to its square root the error divided by double the guess. For sqrt(200), the lowest square is 196. The error is 4, so my mental estimate is 14 + 4/14 = 14.142857...



                                                                              I apologize for off-topic, but note that square roots can be used to calculate logarithms by a process similar to bisection. I suspect that is how it was done in the late 16th century, as they did not yet have calculus. In our times, there are extremely accurate formulas for logarithm that still require square roots. This exercise should make you appreciate the power of a square root button on a calculator, even if you have no "scientific" functions.






                                                                              share|cite|improve this answer









                                                                              $endgroup$



                                                                              Towers' bisection method above is similar to your own approach, but more efficient. Another method that is not as good as binary search, but is better than your own method, is to increment the last digit in bigger steps. I would try incrementing by 3. The worst case is that you reach the correct digit in 5 steps instead of 9.



                                                                              My favorite method for mental approximation is to find the next lowest square, determine the error, and add to its square root the error divided by double the guess. For sqrt(200), the lowest square is 196. The error is 4, so my mental estimate is 14 + 4/14 = 14.142857...



                                                                              I apologize for off-topic, but note that square roots can be used to calculate logarithms by a process similar to bisection. I suspect that is how it was done in the late 16th century, as they did not yet have calculus. In our times, there are extremely accurate formulas for logarithm that still require square roots. This exercise should make you appreciate the power of a square root button on a calculator, even if you have no "scientific" functions.







                                                                              share|cite|improve this answer












                                                                              share|cite|improve this answer



                                                                              share|cite|improve this answer










                                                                              answered Dec 21 '18 at 17:26









                                                                              richard1941richard1941

                                                                              51729




                                                                              51729

















                                                                                  protected by cactus314 Sep 30 '18 at 16:59



                                                                                  Thank you for your interest in this question.
                                                                                  Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



                                                                                  Would you like to answer one of these unanswered questions instead?



                                                                                  Popular posts from this blog

                                                                                  Probability when a professor distributes a quiz and homework assignment to a class of n students.

                                                                                  Aardman Animations

                                                                                  Are they similar matrix