0
$\begingroup$

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?

  • 1
    See this [question](http://stackoverflow.com/q/9114874/866022) and [answer](http://stackoverflow.com/a/9115166/866022)2012-02-07

3 Answers 3

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.

  • 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.2012-02-14
2

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!

  • 0
    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!2012-02-07
0

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.

  • 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](http://en.wikipedia.org/wiki/Methods_of_computing_square_roots), specialized to a small range of numbers.2013-04-23