Looking for square root as a float from int and remainder?

Question

I'm looking right now at a specific square root algorithm that returns the integer part of the square root and the rest.

So for example: mysqrt(140) = 11*11 + 19 = integer 11, remainder 19

The question is, can I calculate the square root as a float, for example, the square root of 140 is ~ 11.8321 ....?

change comments

I am considering a fixed-point square root VHDL implementation that uses only binary operations such as left / right shift, addition and subtraction.

... will be sufficient.

EDIT 2 I really read this algorithm here: http://pioneer.netserv.chula.ac.th/~achatcha/Publications/0012.pdf

It seems that better accuracy could have been achieved by shifting the left radius by 2n. I'm not quite sure why this works? Can anyone explain me

Answer 1

 (11+x)^2 = 140 11^2 + 2*11*x + x^2 = 140 2*11*x + x^2 = 19 x^2 + 2*11*x - 19 = 0 

To solve this problem you need to do another sqrt:

 x = -11 + sqrt((2*11)^2 + 4 * 19) / 2 

Or for the final answer:

 11+x = sqrt((2*11)^2 + 4 * 19) / 2 

It is not faster than just doing

 sqrt(140) 

---

If you are looking for a quick approximation:

 x^2 + 2*11*x - 19 = 0 x = (19 - x^2)/(2*11) 

Guessing x = 0.5, gives

 x = 19/(2*11) - 0.5*0.5/(2*11) = 0.852272727 

You can reapply this to get more convenient approximations, but the Newton method is probably faster.

Answer 2

In response to:

It seems that better accuracy could have been achieved by shifting the left radius by 2n. I'm not quite sure why this works? Can anyone explain me

The document you linked refers to a left offset of 2n. The reason it works is because you are effectively moving by a multiple of 4, which is easy to insert into the square root.

 sqrt(K*2^2n) = sqrt(K)*sqrt(2^2n) = sqrt(K)*2^n 

So you just go to n bits and get the right answer. If you save these shifted bits as decimal parts, you will get your fractional answer.

Think about it in decimal terms by multiplying by 100 to the square root and dividing by 10 after.

So

 sqrt(2) = sqrt(200)/10 = 14/10 = 1.4 

Where sqrt (200) gives only an integer.

Answer 3

I'm not sure I understand your question. Do you want to know how to use sqrt function for float or how to write your own?

If this is the first, then your language will provide something (probably called sqrt ()). If this is the last, you need to find some kind of numerical resource. I would recommend GSL: http://www.gnu.org/software/gsl/