Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is the following:

Is there a polytime non-numerical algorithm for computing square root of perfect square integers?

The more elementary the algorithm is, the better!


EDIT: This is probably the most silly question I ever asked (I hope!). As pointed out by picakhu, since the input integer $n$ is perfect square, we can simply do a binary search to find the number whose square equals to $n$.

share|improve this question
1  
What's a non-numerical algorithm? And by "computing", do you mean "iteratively approximating by rational numbers"? If not, what do you mean? –  joriki Apr 21 '11 at 4:51
4  
No idea if this is relevant, but you could do a binary search –  picakhu Apr 21 '11 at 4:53
    
Did you peruse the results of Googling "fast integer square root"? –  Bill Dubuque Apr 21 '11 at 4:57
1  
@Joriki: Numerical are algorithms that use numerical approximation (as opposed to general symbolic manipulations). So I prefer symbolic manipulation. But picakhu's answer sounds right! That's clever! It's a shame that I didn't think of that. Picakhu, could you please make it an answer? –  Dai Apr 21 '11 at 4:57
    
I can imagine an $O(\sqrt n)$ time algorithm -- checking every number from 0 until you reach one that squares to your number. –  Justin L. Apr 21 '11 at 4:57

1 Answer 1

up vote 6 down vote accepted

The following should suffice, from Cohen: A course in computational algebraic number theory. enter image description here enter image description here

share|improve this answer
    
I thought of some "computer algebra" algorithms like this myself. But when the given integer is perfect square, I think binary search will work! –  Dai Apr 21 '11 at 5:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.