Determine the point where function output will go from positive to negative

Question

I have a function that is like:

f(x) = c - x^2 (c = some constant positive integer, x = +ve integer >= 0)

The output of this function, goes from positive to negative as x -> +infinity.

• Is there a way to directly figure out the x which produces last of the positive outputs before entering in the negative domain?

• Also, if I use an iterative method to locate such a point, how should I find the right increment to go with so that I can reach that value of x as quick as possible? Right now, I am initializing x = floor(sqrt(c) * 0.9) and using dumb +1 increments to x to reach the point where f(x) enters the negative range.

• An observation: f(x) seems to behave in a weird way for c > 10e40 (i.e. when we initiate x = floor(sqrt(c) * 0.9) it gives out a value way too far from the desired point) and you can imagine how long the +1 increment takes to get to the desired output with such large values of c.. ;-(.

Please help. thanks.

Answer 1

The mathematical answer is that given by Jasper Loy. The computational solution may be better done the following way in order to avoid the detour via floating point numbers and surprises caused by conversion. I assume that you have integer operations $+,-,\cdot,/$ available (where $/$ is integer division as usual in programming) that can deal with integers in the range $0,\ldots,c$. The following algorithm corresonds to Heron's method of computing square roots (assuming $c>2$ perhaps)

1. Let $r\leftarrow 2$
2. Let $s \leftarrow (r+c/r)/2$
3. If $s>r+1$ or $s<r-1$, let $r\leftarrow s$ and go back to step 2.
4. If $s\ge r$, then $r^2<c\le (r+1)^2$, hence we output $r$ and terminate
5. Now $s=r-1$, $s^2<c<r^2$, hence we output $s$ and terminate

Answer 2

If we solve the quadratic equation $c-x^2=0$ for a real number $x$, we get $x=\sqrt c$ or $x=-\sqrt c$. Since we are looking at the branch $x\ge 0$, the required solution is the largest integer not exceeding $\sqrt c$. For example, if $c=2$ then $\sqrt c=1.414\ldots$ and the solution would be $1$.