Register to reply 
Can you find the square root of n using only +, , :, x ? 
Share this thread: 
#1
Apr812, 10:14 AM

P: 137

Is it possible to find √n using only the times table and the 4 operations?



#2
Apr812, 10:21 AM

Emeritus
Sci Advisor
PF Gold
P: 4,500

Using only finitely many such operations, you cannot. For example taking the square root of two, after any such calculations you will be stuck with a rational number when you wanted an irrational one. You can calculate very good approximations though



#3
Apr812, 11:01 AM

P: 137

if n = x² , digits up to 6, : you can find (in most cases) the exact result using no tools, [likewise, you can find in all cases : [itex]\sqrt[3]{x³} [/itex] (9digit n), and [itex] \sqrt[5]{x^5}[/itex] (15digit n)] if n = x² , digits > 6, : you can still guess three digits and get x with a few operations, with a pocket calculator you can get any root in a few seconds. Can you believe that? 


#4
Apr812, 11:33 AM

P: 3,014

Can you find the square root of n using only +, , :, x ?
You can find the square root of a number a as the limit point of the following iterative procedure:
[tex] x_{n + 1} = \frac{1}{2} \, \left( x_n+ \frac{a}{x_n} \right) [/tex] However, as this is a limiting process, you can only get an exact result in the infinite limit [itex]n \rightarrow \infty[/itex]. The convergence is fast though, and you get a good approximate result in just several iterations. Actually, you will exhaust the number of digits on your calculator pretty fast. 


#5
Apr812, 12:13 PM

P: 137

That is the Babylonian method, according to wiki. Is there a general algorithm that does not use powers of the same order (k) of n = x^k ?
Cam you find[itex]\sqrt{403225}[/itex] using only logics, knowing that n= x²? 


#6
Apr812, 04:29 PM

P: 397

Why didn't you guys mention Taylor series? It's very easy to calculate the squareroot with a series:
(1+x)^n = 1 + n x + n(n1) x^2/2! + n(n1)(n2) x^3/3! + ... Substitute n with 1/2 and there you got the square root. Keep adding terms till you get the precision that satisfied you. That's actually how computers calculate squareroots. http://en.wikipedia.org/wiki/Taylor_series 


#7
Apr812, 04:33 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

For example, for many purposes, an algorithm to produce arbitrarily good approximations (e.g. the method in this post) counts as "finding" the number. 


#8
Apr812, 04:35 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091




#9
Apr812, 04:43 PM

Emeritus
Sci Advisor
PF Gold
P: 4,500

logics, if you just want the square root of something you know is an integer you can just use a binary search to find the square root without doing anything but multiplication a lot of times. For example to find the square root of 403225: 500^{2} = 250000 so we need a bigger number 750^{2} = 562500 so we need a smaller number. We try one in between these two: 625^{2} = 390625 so we need a number between 625 and 750 687^{2} = 471969 We need a number between 687 and 625 650^{2} = 422500 We need a number between 625 and 650: 637^{2} = 405769 We need a number between 625 and 635 etc, we find the square root is 635. This technique can also be used to find the square root of any number to whatever precision you want, for example if you want the square root of 403226, we know that it is larger than 635 and smaller than 636. So we try 635.5, and if the square is too large, 635.25, and if the square is too large 635.125, and eventually when the number squared is smaller than 403226 we have a bound for the square root (and at that point we can keep dividing the interval in half in order to get more precision) 


#10
Apr812, 04:51 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

Is it cheating to use the operation "<"?



#11
Apr812, 04:59 PM

P: 3,014




#12
Apr812, 05:18 PM

Emeritus
Sci Advisor
PF Gold
P: 4,500

It's a binary operation, which takes two inputs a<b and returns 1 if a is smaller than b, and 0 otherwise. Hurkyl was noting my tremendous reliance on it in my example despite it not being one of the permissible operations in the original post. I can't figure out a workaround either



#13
Apr812, 06:35 PM

P: 3,014




#14
Apr912, 12:11 AM

P: 137




#15
Apr912, 02:15 AM

HW Helper
P: 3,562

[itex]635^2=403,225[/itex] just for reference. So we're trying to find the answer of [itex]\sqrt{403,225}[/itex]. We know that since [itex]100^2<403,225<1000^2[/itex] then the answer will be a 3digit number that we will denote as ABC. To find the hundreds value, A, just realize that the first 2 digits of 403,225 are 40, and that is between 6^{2} and 7^{2} so A=6. For C, the last 2 digits are 25, so I'd guess that it would be 5. To find B  arguably the trickiest of all  I guess I'd flex my brain muscles by not pulling out a pen and paper and expanding (600+10B+5)^{2} in my mind, and scrapping all the values except the relevant ones that would be the biggest influence on the tenthousand's value in the answer. So [tex](600+10B+5)^2=(600+(10B+5))^2=600^2+1,200(10B+5)+(10B+5)^2[/tex] Clearly the influence would be that middle term [itex]1,200(10B+5)[/itex] So now let's do some simplifications. [itex]1,200(10B+5)>12,000B[/itex] and [itex]403,225360,000 \approx 40,000[/itex] and then [tex]3<\frac{40,000}{12,000}<4[/tex] and so I would make the logical guess that B=3. Thus, ABC = 635 


#16
Apr912, 03:24 AM

P: 137

But you must find something simpler if you want to solve the challenge in the twinthread about the cube root... (try to find x = [itex]\sqrt[3]{723³}[/itex]). If you do not wish to move on to that thread, here is a slightly tougher [but still easy] challenge: find x = [itex]\sqrt{277729}[/itex] 


#17
Apr912, 05:41 AM

HW Helper
P: 3,562

And obviously I'd have little luck extending it to the cube roots. 


#18
Apr912, 06:19 AM

Sci Advisor
P: 1,810

Do you "find" sqrt(2) by the operation sqrt?



Register to reply 
Related Discussions  
Find derivative of Square root (x + square root(x + x^(1/2))) Help!  Calculus & Beyond Homework  5  
Find the RootMeanSquare of the gas  Introductory Physics Homework  6  
How to find the square root...  General Math  9  
How to find Pressure and Root Mean Square Velocity  Introductory Physics Homework  14  
Find square root  Introductory Physics Homework  10 