Calculate fractional part of square root without taking square root Let's say I have a number $x>0$ and I need to calculate the fractional part of its square root:
$$f(x) = \sqrt x-\lfloor\sqrt x\rfloor$$
If I have $\lfloor\sqrt x\rfloor$ available, is there a way I can achieve (or approximate) this without having to calculate any other square roots? I would like to avoid square roots for performance reasons as they are usually a rather slow operation to calculate.
As an example of what I am thinking about, here is one option:
$$f(x)\approx\frac{x-\lfloor\sqrt x\rfloor^2}{(\lfloor\sqrt x\rfloor+1)^2-\lfloor\sqrt x\rfloor^2}$$
As $x$ gets large, this approximation becomes better and better (less than 1% error if $\sqrt x\ge40$), but for small $x$, it's quite terrible (unbounded error as $x$ goes to $0$).
Can I do better? Preferably an error of less than 1% for any $\sqrt x<10000$.
The holy grail would be to find a formula that doesn't need any division either.
Aside: 
In case anyone is interested why I need this: I'm trying to see if I can speed up Xiaolin Wu's anti-aliased circle drawing functions by calculating the needed variables incrementally (Bresenham-style)

After a bit more reading on Ted's Math World (first pointed out by @hatch22 in his answer), I came across a quite beautiful way to perform this calculation using the Pythagorean theorem:
Given some estimate $y$ of the square root (in the case here we have$\lfloor\sqrt{x}\rfloor$), if we let the hypotenuse of a right triangle be $x+y^2$ and one of its other two sides $x-y^2$, then the remaining side will have length $2y\sqrt{x}$, i.e. it will contain the desired answer.
The angle $\alpha$ formed by the side of interest and the hypotenuse can be calculated as:
$$\alpha=\sin^{-1}\frac{x-y^2}{x+y^2}\approx\frac{x-y^2}{x+y^2}$$
where the approximation is the first term of the Maclaurin Series for $\sin^{-1}$.
The side of interest can then be calculated from:
$$2y\sqrt{x}=(x+y^2)\cos\alpha\approx(x+y^2)\cos\frac{x-y^2}{x+y^2}\approx(x+y^2)\left(1-\frac{1}{2}\left(\frac{x-y^2}{x+y^2}\right)^2\right)$$
Where the second approximation are the first two terms of the Maclaurin Series for $\cos$.
From this, we can now get:
$$\sqrt{x}\approx\frac{x+y^2}{2y}\left(1-\frac{1}{2}\left(\frac{x-y^2}{x+y^2}\right)^2\right)=\frac{x^2+6xy^2+y^4}{4y(x+y^2)}$$
To get the fractional part of $\sqrt{x}$ in the range $0..255$, this can be optimized to:
$$y_{\,\text{square}}=y\times y$$
$$s=x+y_{\,\text{square}}$$
$$r=\frac{(s\times s\ll6) + (x\times y_{\,\text{square}}\ll8)}{s\times y}\,\,\&\,\,255$$
where $\ll$ signifies a bit-wise shift to the left (i.e. $\ll6$ and $\ll8$ are equivalent to $\times\,64$ and $\times\,256$ respectively) and $\&$ signifies a bit-wise and (i.e. $\&\,255$ is equivalent to $\%\,256$ where $\%$ stands for the modulus operator).
The amazing part is that despite the minimal Maclaurin Series used, if we can use the closer of $\lfloor\sqrt{x}\rfloor$ and $\lceil\sqrt{x}\rceil$ as the estimate $y$ (I have both available), the answer in the range $0..255$ is actually EXACT!!! for all values of $x\ge1$ that don't lead to an error due to overflow during the calculation (i.e. $x<134\,223\,232$ for 64-bit signed integers and $x<2\,071$ for 32-bit signed integers).
It is possible to expand the usable range of the approximation to $x<2\,147\,441\,941
$ for 64-bit signed integers and $x<41\,324$ for 32-bit signed integers by changing the formula to:
$$r=\left(\frac{s\ll6}{y} + \frac{x\times y\ll8}{s}\right)\,\&\,\,255$$
But due to the earlier rounding, this leads to a reduction in the accuracy such that the value is off by $1$ in many cases.
Now the problem: A little bit of benchmarking and reading indicates that on many processors a division operation is actually not much faster than a square root. So unless I can find a way to get rid of the division as well, this approach isn't actually going to help me much. :(
Update:
If an accuracy of $\pm 1$ is acceptable, the range can be increased significantly with this calculation:
$$k = \frac{(x + y \times y) \ll 5}{y}$$
$$r = \left(\left(k + \frac{x \ll 12}{k}\right)\ll 1\right)\,\&\,\,255$$
For 32-bit signed integers, this works for any $x<524\,288$, i.e. it breaks down as soon as $x \ll 12$ overflows. So, it can be used for circles up to radius 723 pixels. Note, that $y$ does not change on every step of the Bresenham algorithm, so $1/y$ can be pre-calculated and therefore does not add a full second division to the algorithm.
