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.

How can I find the first perfect square from the function: f(n)=An²+Bn+C? B and C are given. A,B,C and n are always integer numbers, and A is always 1. The problem is to find n.

Example: A=1, B=2182, C=3248

The answer for the first perfect square is n=16, because sqrt(f(16))=196.

My algorithm increments n and tests if the square root is a integer number.

This algorithm is very slow when B or C is large, because it takes n calculations to find the answer.

Is there a faster way to do this calculation? Is there a simple formula that can produce an answer?

share|improve this question
    
Before proceeding with the calculation, you could do a remainder check, using modular arithmetic! –  user21436 Feb 7 '12 at 4:21
1  
See this question and answer –  Jim Feb 7 '12 at 4:24

3 Answers 3

First let's do the case where $B=2b$ is even.

$x^2=n^2+2bn+c=(n+b)^2+c-b^2$, $c-b^2=x^2-(n+b)^2=(x-n-b)(x+n+b)$. Factor $c-b^2$; if $c-b^2=de$ with $d\le e$ of the same parity then let $x-n-b=d,x+n+b=e$ so $n=(e-d)/2-b$.

So, the method is to compute $c-b^2$, write it as a product $de$ of two numbers both even or both odd, and then the formula gives you $n$. You want $n$ as small as possible, take $d,e$ so $(e-d)/2-b$ is small.

If $B$ is odd then first multiply by 4: $4x^2=4n^2+4Bn+4C=(2n+B)^2+4C-B^2$ and proceed as above.

share|improve this answer
    
Gerry, i din´t undestand how you method works, can you give me an example? In your description n=(e-d)/2-b the variables e and d also depends of x and n. –  user1185049 Feb 10 '12 at 20:53
    
Have you tried working through an example yourself? Say, the one you give, with $B=2182$ and $C=c=3248$? Let me know if you get stuck. $e$ and $d$ only depend on $b$ and $c$ and on which way you choose to factor $c-b^2$, if you have a choice. –  Gerry Myerson Feb 11 '12 at 5:48
    
Yes i tried this. But your solution makes the problem more complicated because [c-b^2] is a multiple of two number d and e. OK!! But you know that to find this numbers is necessary to divide the number [c-b^2] prime by prime utill the rest of division to be zero. –  user1185049 Feb 13 '12 at 21:26
1  
"More complicated" than what? $b=1091$, $c=3248$, $c-b^2=-1187033=-(911)(1303)$ so we can take $d=911$, $e=-1303$, or $d=-911$, $e=1303$, or $d=1303$, $e=-911$, or $d=-1303$, $e=911$. Presumably we want $n\gt0$, so we need $e\gt d$. Taking $d=-911$, $e=1303$ gives $n=(1303+911)/2-1091=16$, and we're done ($d=-1303$, $e=911$ clearly gives the same answer). Now it may be that factoring 1187033 takes more time than testing $n=1,2,\dots,16$. But if the smallest answer had been $n=1600$, the method involving factorization would have been faster. And you can't know in advance. –  Gerry Myerson Feb 14 '12 at 0:04

Given the values of $B$ and $C$, calculate their residues $\mod 4$. And, a necessary but not sufficient condition for $f(n)$ to be a perfect square is $f(n) \equiv \{1,0\} \mod 4$. So, using this fact, choose those congruent classes $\mod 4$ that will give you perfect squares instead of running the algorithm for all numbers.

There might be better ways, but this is the best I can think of.

Warning.

This simplification may not eliminate some congruent classes in all cases, whence your algorithm will not be improved!

share|improve this answer
1  
"if and only if"? $f(n)\equiv0\pmod4$ is certainly not enough to imply that $f(n)$ is a perfect square. –  Gerry Myerson Feb 7 '12 at 4:31
    
Ah! Sorry! I was hurrying up to my class only to find that my class has been postponed! But that cannot be an excuse here! –  user21436 Feb 7 '12 at 4:33

This is my way of finding square roots larger than 100. Take 1089 for example. You first find the closest number (without going over) that has a square root divisible by 10. That would be 900; 30x30. The tens digit is a 3. Next subtract that number leaving me with 189. Now take the square root of 900. Take the 10s digit, multiply from 20, and add 1. That would be 61. Subtract that number from 189; 128. Now subtract 63, 65, 67, etc until you reach 0. Including 61, count the amount of numbers that you subtracted that is the units digit. For this problem it would be 189-61-63-65=0, so the units is 3. Your final answer is √1089.

share|improve this answer
1  
But OP is not trying to find the square root of a number known to be a square, he is trying to check numbers that may be square. Your approach is a modification of the digit-by-digit method of computing square roots, specialized to a small range of numbers. –  Ross Millikan Apr 23 '13 at 22:00

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.