I wasn't at school when we were learning this, and I've forgot how to calculate a square root on paper using a formula?
Can anyone please help me? What is the formula?
I need this to write an algorithm for my college assignment home work. Thanks!
[Math] the mathematical formula for Square Root
arithmetic
Related Solutions
You can use the identity $(x+c)^2 = x^2 + 2xc + c^2$ to arrive at a "long-division" like method. Let me show you how it is done for 3838 before giving the algorithm.
- Start with 3838
- Write the digits in groups of 2, so write 3838 as 38,38.
- For the "highest placed group of 2", find the biggest square number less than it. In this case, $6^2 = 36 < 38 < 49 = 7^2$. So you write down 6, and subtract 36 from the first group. You then get
- 2,38 = 38,38 - 36,00.
- Take the 6 you wrote down before, multiply it by 20 (so you get 120). Now find the largest multiple of $6\times 20$ that is less than 238. You'll see that it is 1. So you write down 1 (so your number is now 61). Subtract from 238 120 to get 118.
- Subtract from 118 the number $1 = 1^2$ to get 117. Now add two more digits to it (to form 117.00). Take 61, multiply it by 20, you get 1220. Find the largest multiple of 1220 less than 11700, which would be $1220 \times 9 = 10980$. So write down 9, and your number is 61.9, and subtract from 11700 the number 10980 to get 720. Subtract from 720 the number $9^2 = 81$ to get 639.
So you've arrived at, at this point, $3838 = (61.9)^2 + 6.39$. And you can continue the process indefinitely.
How does this work? Given a number $A$, you want to find its square root in base-10 representation. Suppose your square root looks like $$ a_{100}a_{10}a_1.a_{0.1}a_{0.0.1}\ldots $$ when expanded as a string of digits. Then you find the biggest $a_{100}$ such that $$ (a_{100}\times 100)^2 \leq A $$ (similar to how you do long division). Then to make solve for the next digit, you use that $$ (a_{100} \times 100 + a_{10}\times 10)^2 \leq A $$ (since you are truncating the decimal expansion, which makes the number smaller). So you solve for the best $a_{10}$ such that $$ (a_{100})^2\times 100^2 + \left[ 20 \times (a_{100}\times a_{10}) + (a_{10})^2\right] \times 100 + \leq A $$ The above expression shows why in the first step you want to group the digits in twos: in some sense we are thinking of $A$ as in base-100, the "square" of base-10.
At every step you use the identity $(x+c)^2 = x^2 + 2xc + c^2$ to compute the next digit correction to the square root.
Another method, as the Babylonians did it, was recently detailed by John Baez at his blog, which uses the "equality case" of the arithmetic-mean-geometric-mean inequality to power the iteration.
If by "formula", Nirbhay (the former engineer featured in the article) means "closed form formula", then the answer is obviously not; because the answers would all have to be rational, whereas e.g the cube root of 2 is not. However, if by "formula" Nirbhay means "algorithm which computes the digits in sequence, which converges on the answer and terminates in the case of integers and other terminating fractions which are perfect cubes", then the answer is yes, if you allow either simple multiplications, or perform it in base 2. (Of course, you can reduce multiplication to addition if you like, but beyond small integers or shifting numbers by place values, that feels like cheating.)
No innovation is required; it's a simple modification of the digit-by-digit algorithm for computing square roots. The intuition behind this algorithm is that at each point, you are trying to get better and better approximations to X by constructing rational numbers Y1, Y2, Y3, ... having more and more digits, whose cubes approximate X from below. We chip away at the error between X and the cubes of these approximations by trying to "complete the cube". Each new digit of X that we consider allows us to try to chip away more of the difference between Yj ³ and X, by defining Yj+1 = Yj + δ for a suitable increment δ; we then determine the error involved in the new approximation by computing Yj+1³ = Yj ³ + 3δYj ² + 3δ²Yj + δ³. The trick is how to do this with simple arithmetic operations; but it's not too difficult.
I demonstrate the algorithm in binary, because that's the base where it would be easiest in practise to compute the cube roots. The generalization to arbitrary bases (e.g. decimal) is an exercise for the reader. To simplify the presentation, we may assume without loss of generality that the number X whose cube-root we compute is less than 8. We may repeatedly divide by 8 until this is the case; when we have obtained the square root, simply multiply the answer the same number of times by 2. This is just observing that $\sqrt[3]{8^{-n} \cdot X\;} = 2^{-n} \cdot \sqrt[3]{X\;}$, and allows me to emphasize that the algorithm works just as well for fractions as for integers. Because of how the algorithm works, it looks somewhat as though it's starting with a number in octal, and obtaining a root in binary (for square roots it looks like it produces a binary root from a number in quartal); but of course we can represent the base 8 "digits" by groups of three binary digits.
Let X = x0 + x1/81 + x2/82 + ... , where each xj ranges from 0 to 7. We compute binary digits yj representing Y = y0 + y1/21 + y2/22 + ... such that Y3 = X, as follows.
If x0 = 0, set y0 = 0; otherwise, set y0 = 1. Let R := x0 − y0.
Set A = B = C = y0 .
Set j = 1, and repeat the following until the desired number of digits is obtained (or until R = 0 and only if all the remaining digits xj , xj+1 , ... are also zero):
Set D = 8R + xj , and consider the largest binary digit yj such that $$ D \;\;\geqslant\;\; y_j^3 + 6Ay_j^2 + 12By_j + 8C.$$ Of course, we're working with binary digits; all the powers of yj are either zero or one. So what we're really testing is whether or not $$ D \;\;\geqslant\;\; 1 + 2A + 4A + 4B + 8B + 8C,$$ where multiplication by 2, 4, and 8 can be realized by shifting integers one, two, or three places (tacking on zeros). If the inequality above holds, set yj = 1; otherwise set yj = 0.
The integer A will actually be the number whose binary representation is the bit-sequence y0 y1 ... yj−1 in order; B is equal to A², and C is equal to A³. To maintain this invariant for the next iteration j, we compute new values A', B', and C' as updated values. For A, we define $$ A' = 2A + y_j \;. $$ For B', we take advantage of the fact that we have B and A: $$\begin{align*} B' &= (A')^2 = (2A + y_j)^2 = 4A^2 + 4Ay_j + y_j^2 \\&= 4B + 4Ay_j + y_j^2 \;. \end{align*}$$ Similarly, for C': $$\begin{align*} C' &= (A')^3 = (2A + y_j)^2 = 8A^3 + 12A^2y_j + 6Ay_j^2 + y_j^3 \\&= 8C + 8By_j + 4By_j + 4Ay_j^2 + 2Ay_j^2 + y_j^3 \;. \end{align*}$$ Again, multiplications by zero, one, or powers of two are trivial inbinary representation. We then update A := A', B := B', and C := C'.
We update R, which is meant to represent the error of C as an approximation to the integer formed by the first j digits (in octal) of X: we set $$ R' = \bigl(8R + x_j\bigr) - C' = D - C' \;,$$ and then set R := R'.
If ever we obtain R = 0 and with all of the remaining digits of X equal to zero, we stop (with an exact solution).
In fact, it is not very difficult to modify this algorithm to obtain a procedure for extracting fourth roots, fifth roots, or nth roots for any constant n (though the number of parameters you have to carry around with you, and the sizes of the additions you have to carry out, will grow as you work harder and harder to avoid explicitly performing any multiplications).
Best Answer
Let $ a \geq 0 $. If you want to find $ \sqrt{a} $, use the following iteration: \begin{align} x_{0} &:= a. \\ x_{n+1} &:= \frac{1}{2} \left( x_{n} + \frac{a}{x_{n}} \right). \end{align} Then $ \displaystyle \lim_{n \rightarrow \infty} x_{n} = \sqrt{a} $. This is an example of the Newton-Raphson method, applied to the function $ f(x) = x^{2} - a $. This particular iteration exhibits quadratic convergence, which means that the number of correct digits about doubles in size with each successive step. Hence, on an ordinary scientific calculator, one can obtain a good approximation after just a few steps.