is there any efficent method to do it? for example,
Code:5
false
7
false
9
true
49
true
2553604
true
(the input data less than 2^32)
Printable View
is there any efficent method to do it? for example,
Code:5
false
7
false
9
true
49
true
2553604
true
(the input data less than 2^32)
take sqrt, convert to int and check that the res*res == orig
E.g.: 841
1) Split number into sets of 2 digits 08|41
2) Let a = sqrt so far (init: a = 0)
2) Let b = remainder = 08
3) Solve for c in d=c(20a + c) such that d<=b
.: c = 2 d=4
.: a = 2
4) b - d = 08 - 4 = 04
5) Restart at 2) using b= 04*100+41 = 441
3) .:c=9 d=441
.:a=29
4) b-d = 441-441 = 0
5) Done. This is a perfect square since no remainder and we haven't gone into decimals yet
There is an efficient way to do this, yes.
Newton's Method (Heron's Method?) works for integers when calculating square roots. It finds the square root in what appears to be log(n) time
Find sqrt of 64
Starting guess: 64.
f(n) = (n + 64/n)/2
f(64) = (64 + 64/64)/2 = 32
f(32) = (32 + 64/32)/2 = 17
f(17) = (17 + 64/17)/2 = 10
f(10) = (10 + 64/10)/2 = 8
f(8) = (8 + 64/8)/2 = 8 STOP
Does 8*8 = 64? Yes. 64 is a square.
There's just one tiny infinite loop to be worried about. Try finding the square root of 99, using a guess of "10" to see the loop.
1. Use a number you know to be greater than the correct value as the first guess for this algorithm. Notice how my first guess was "64", which is guaranteed to be greater than or equal to sqrt(64).
2. If at any point in the algorithm, f(n) > n, then quit there.
http://mathforum.org/library/drmath/view/52609.html
I haven't the time to carefully go over this... but this is solving for c, given the square of c. Isn't this step equivalent to the original problem?Quote:
Originally Posted by coder8137
It's similar, the important point is that b should always be < 10000. (EDIT: Not true for calculating sqrt of large numbers, when further into the calculation, since a will get bigger and bigger.) Also, just in case you didn't notice, the formula is looking for the biggest integer c. Usually solved with a few guesses. It's designed for large numbers or can calculate actual square roots to with decimal places easily. Also, it's probably one of the few methods you can use in your head to find the sqrt of non-perfect squares.Quote:
Isn't this step equivalent to the original problem?