0

How well $\lfloor\sqrt{x}\rfloor + \dfrac{x-\lfloor \sqrt{x}\rfloor^2}{2\lfloor \sqrt{x}\rfloor}$ approximate $\sqrt{x}$ ?

After some searching, I found this interesting formula. It can be shown easily that for $x$ a square number this formula will always work.

I don't know how well it is actually approximating the square root. With a graph, this formula seems to fit quite well with the square root. Especially for very large values or very close to square numbers.

And also, when this formula create the worst approximation ?

Thanks for the help !

Jotadiolyne Dicci
  • 374
  • I cannot see a formula in your question. – vitamin d Jun 30 '21 at 18:54
  • Oh okay, i'm talking about this : $\lfloor\sqrt{x}\rfloor + \dfrac{x-\lfloor \sqrt{x}\rfloor^2}{2\lfloor \sqrt{x}\rfloor}$. – Jotadiolyne Dicci Jun 30 '21 at 18:57
  • 3
    This is the first iterate of Newton's method when the initial approximation is $\lfloor\sqrt x\rfloor$. The largest error occurs at the end of every unit interval. –  Jun 30 '21 at 18:59
  • This is not a formula (=a mathematical relationship or rule expressed in symbols.) Please be more precise. – vitamin d Jun 30 '21 at 19:00
  • @vitamind: I do see a formula, and it makes a lot of sense. –  Jun 30 '21 at 19:01
  • Sorry, I am french. I will use the same word in french. I am sorry. – Jotadiolyne Dicci Jun 30 '21 at 19:02
  • @YvesDaoust "How well $\lfloor\sqrt{x}\rfloor + \dfrac{x-\lfloor \sqrt{x}\rfloor^2}{2\lfloor \sqrt{x}\rfloor}$ approximate $\sqrt{x}$" is not a formula. It's a question. The expressions used are terms. Anyways, it is more or less clear what the OP is trying to ask, so (+1) to your comment. – vitamin d Jun 30 '21 at 19:03
  • @vitamind: $\lfloor\sqrt{x}\rfloor + \dfrac{x-\lfloor \sqrt{x}\rfloor^2}{2\lfloor \sqrt{x}\rfloor}$ is undisputably a formula. It is not an equation and it is an expression. –  Jun 30 '21 at 19:05
  • @YvesDaoust Oh, I see ! I didn't see it was linked with Newton's method. Thanks ! – Jotadiolyne Dicci Jun 30 '21 at 19:06
  • 1
    You might be interested in the approximation of $\sqrt{N}=\sqrt{a^2+b}\approx \left(a+\frac b{2a}\right)-\frac{\left(\frac b{2a}\right)^2}{2\left(a+\frac b{2a}\right)}$ I developped in this post https://math.stackexchange.com/a/2866233/399263 and which also is an application of one iteration of Newton's method but formulated slightly differently. – zwim Jun 30 '21 at 20:58
  • 1
    It's actually kind of crummy for $0<x<1$. Use a downward extrapolation from the ceiling value to get better results. – Oscar Lanzi Jun 30 '21 at 23:38

1 Answers1

2

Note, the formula only makes sense when $x\ge1$ (since $\lfloor\sqrt x\rfloor=0$ for $0\le x\lt1$). Now let $\lfloor\sqrt x\rfloor=\sqrt x-r$ with $0\le r\lt1$. Then

$$\begin{align} \lfloor\sqrt x\rfloor+{x-\lfloor\sqrt x\rfloor^2\over2\lfloor\sqrt x\rfloor} &=(\sqrt x-r)+{x-(\sqrt x-r)^2\over2(\sqrt x-r)}\\ &=(\sqrt x-r)+{2r\sqrt x-r^2\over2(\sqrt x-r)}\\ &=\sqrt x+{r^2\over2(\sqrt x-r)}\\ &=\sqrt x+{r^2\over2\lfloor\sqrt x\rfloor} \end{align}$$

So we see that the error term is always non-negative (i.e., the formula always somewhat overestimates the actual square root), and always less than $1/2$ (which it approaches as $x\to4^-$). It is quadratically small when $r\approx0$ (i.e., when $x$ is slightly larger than a square integer), and close to $1/(2\sqrt x)$ when $x$ is slightly less than a square integer, which itself is small when $x$ is large. As noted, the approximation is worst when $x$ is slightly smaller than $4$.

Barry Cipra
  • 79,832