3
$\begingroup$

I was recently working with functions of the form $$N - \sqrt{\frac{N}{x}}\cdot\left\lfloor \frac{N}{\sqrt{N/x}}\right\rfloor + \sqrt{\frac{N}{x}} - \left\lfloor \sqrt{\frac{N}{x}}\right\rfloor$$ where $N$ is positive integer.

Almost any graphing calculator I used was unable to find the zeroes of the function mentioned above and I concluded that it probably was not possible to numerically locate the roots. I recently was working with an application called Desmos calculator which strangely enough was able to locate the zeroes of this function (and almost instantaneously at that). When I emailed the team they told me they were using a form of bisection but I am unclear exactly how to implement bisection to locate roots of this function. I would be very glad if someone here could explain how the implementation would be done (i.e. how to select anchor points, etc...). Would it also be possible to utilize Newton's method or some Householder Method on this curve for fast convergence?

I have attached images of the function below. The Red functions show the graph with $N = 2813$. And Blue functions show the graph with $N = 6$. The zeroes are displayed for red as $1.5$ and $0.66666$. The zeroes are displayed for blue as $3.345$ and $0.299$.

enter image description here enter image description here enter image description here enter image description here

To graph the functions yourself, go to https://www.desmos.com/calculator and there you can substitute the expression

N - (N/x)^(1/2)*floor(N/((N/x)^(1/2))) + (N/x)^(1/2) - floor((N/x)^(1/2))

with $N = 6$, and $2813$.

My main problem with bisection is that if one looks at the graphs they notice that they are impossible to bisect (all values are positive) and also using Newton's fails. So I suppose that any root finding algorithm that actually works for this would be also appreciated.

  • 1
    Welcome to math.SE! To make your questions more readable, you can format the math using the tutorial [here](http://meta.math.stackexchange.com/questions/5020/tex-latex-mathjax-basic-tutorial-and-quick-reference).2012-12-31
  • 0
    Can you attach the images you are referring to on a public site that allows you to post pictures and others can peruse? I updated your formula with better formatting, but please check it as it was long, so make sure I didn't hose it? Regards2012-12-31
  • 0
    You can use http://imgur.com/ to upload the graphs. Add the URLs of the images and someone will edit them into the question.2012-12-31
  • 0
    As for the actual question, I think one would have to specially handle the points at which the floor functions have discontinuities. It looks like the Desmos calculator misses a zero at $x=6$ when $N=6$. In fact I'd guess the zeros are precisely at those points where the arguments of both floor functions are integers.2012-12-31
  • 0
    I used imgur to upload the files. They can be viewed at this link: http://imgur.com/a/r9zMu2013-01-01

1 Answers 1

3

$$\begin{align} f(x) &= N - \sqrt\frac Nx\cdot\left\lfloor\sqrt{Nx}\right\rfloor + \sqrt{\frac Nx} - \left\lfloor\sqrt\frac Nx\right\rfloor \\ &\ge N - \sqrt\frac Nx\cdot\sqrt{Nx} + \sqrt\frac Nx - \sqrt\frac Nx \\ &= 0, \end{align}$$ with equality holding if and only if $\sqrt{Nx}$ and $\sqrt{Nx^{-1}}$ are both integers.

The necessary and sufficient conditions on $x$ can be characterized in terms of in terms of the prime factorization of $N$. Let the prime factorization be $N = p_1^{n_1} p_2^{n_2} \cdots p_k^{n_k}$. Now $x$ must be rational, and it cannot contain any prime other than these $p_i$ as a factor in its reduced form, otherwise one of $Nx$ and $Nx^{-1}$ would not be an integer. So it is of the form $x = p_1^{m_1} p_2^{m_2} \cdots p_k^{m_k}$, where the $m_k$ are integers. Then $Nx = p_1^{n_1+m_1} p_2^{n_2+m_2} \cdots p_k^{n_k+m_k}$ is a square integer if and only if $m_i \equiv n_i \pmod 2$ and $m_i \ge -n_i$. Similarly, $Nx^{-1}$ is a square integer if and only if $m_i \equiv n_i \pmod 2$ and $m_i \le n_i$. That means $m_i \in \{-n_i, -n_i+2, \ldots, n_i-2, n_i\}$, and that's all there is to it.

For example, when $N=6$, we have $N = 2^1 3^1$, and there are four zeroes for $x$, namely $2^{-1}3^{-1} = \frac16$, $2^1 3^{-1} = \frac23$, $2^{-1}3^1 = \frac32$, and $2^1 3^1 = 6$.

  • 0
    I guess I didn't answer the question of how to *numerically* find the roots of the function at all. But then, at the zeroes the function does not equal either of its one-sided limits, so numerical methods are almost certainly useless.2013-01-01
  • 0
    Thank you for your quick response! So basically I was wondering for large N where we don't have the prime factorizations known our best bet is to just attack the zeroes using a numerical method of some type. The strange thing is that the application Desmos Calculator was able to find these zeroes numerically even for large N such as 2813 and 15871. I would really like to know what method they used. So I emailed and was told it was a form of bisection. How it is being used is still a mystery to me. Perhaps you could share some insight on how to use bisection on this class of function?2013-01-01
  • 0
    Oh yea and I think I should clarify by stating that I am only interested in the solutions not equal to 1/N and N (which are the trivial solutions due to 1 being a square number). All others are of interest to me but being I don't know the prime factorizations all the time I end up resorting to numerical methods2013-01-01
  • 0
    I uploaded the aforementioned images at this link: http://imgur.com/a/r9zMu2013-01-01
  • 0
    Wow, they really did find the zeroes at $29/97$ and $97/29$. That is pretty amazing to me. Anyhow, just saying "a form of bisection" isn't much to go on, so I have no idea. My guess is still that they're explicitly finding the points ($m^2/N$ and $N/m^2$ for $m\in\mathbb N$) at which the floor function has jumps, and computing the values exactly there. You could email them again and ask them for more details; any sort of technical information would be better than having me speculate wildly about it.2013-01-01
  • 1
    Note that the numbers you mention aren't really that big. A very simple factorization algorithm will easily give the prime factors. Other than that, treating the function piecewise, which requires finding all the discontinuities anyway, is the only straightforward approach I see.2013-01-01