1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $f$ does not behave weirdly for $c>10^{40}$. Are you using floating point math on a computer perhaps? $\endgroup$ – Hagen von Eitzen Aug 27 '18 at 6:15
  • $\begingroup$ I am using standard C/Python interface to do the calculations of sqrt..can this be the reason? $\endgroup$ – khan Aug 27 '18 at 6:17
2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Very interesting indeed. A question though: Is this method more expensive than computational square root? $\endgroup$ – khan Aug 27 '18 at 6:42
  • 2
    $\begingroup$ @khan For questions of performance, a computing group may be better but first consider whether you prefer: the correct answer slowly or the wrong answer quickly. $\endgroup$ – badjohn Aug 27 '18 at 8:26
  • $\begingroup$ That is right. I agree. $\endgroup$ – khan Aug 27 '18 at 13:48
  • $\begingroup$ @Hagen von Eitzen what do you suggest about figuring out the right increment to x, to reach the desired point, if we choose to go with an iterative approach? $\endgroup$ – khan Aug 27 '18 at 16:40
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ That is sqrt(c) - 1? $\endgroup$ – khan Aug 27 '18 at 6:26
  • $\begingroup$ @khan - No it is not "sqrt(c) - 1". It is "floor(sqrt(c))" where floor() returns the next lower integer value of the argument. In some computer languages you can use "int(sqrt(c))" to achieve the same result but some languages will round up of the fractional part of the argument is greater than or equal to 0.5. $\endgroup$ – Michael Karas Aug 27 '18 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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