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)
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)
Last edited by Mathsniper; 12-15-2006 at 09:44 AM.
take sqrt, convert to int and check that the res*res == orig
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
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
Callou collei we'll code the way
Of prime numbers and pings!
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?Originally Posted by coder8137
Callou collei we'll code the way
Of prime numbers and pings!
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.Isn't this step equivalent to the original problem?
Last edited by coder8137; 12-15-2006 at 10:07 PM.
