Re: Fixed Point Square Root Improvements?

From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 11/25/04 

Date: Thu, 25 Nov 2004 11:16:21 +0000 (UTC)

spamtrap@crayne.org (Chris Williams) writes:

> I will be working with an embedded system with no FPU and need to be
> able to find the square root of a 16.16 fixed point integer.
>
> My current design is using a lookup table where the index is the root
> (with two decimal bits) of the value pointed to (with four decimal
> bits.) This doesn't cover every possible value, so I do a search for
> the nearest value that is contained in the array.
>
> Building the table:
>
> sqrtTable[0x400];
> for (L = 0; L < 0x400; L++) {
> sqrtTable[L] = (L * L);
> }
>
> (Actually I write the results out to a file for direct compilation in)

I trust that the recorded values are actually root of the value
being pointed to and not the square, as the above indicates.
 
 
> And my current function is as such:
>
> __inline unsigned int fsqrt(unsigned int value) { //square root
> function which works on a 16/16 fixed point integer
[SNIP - binary chop]
> }
>
> The C version appears to work about 2.2 times slower than C's sqrt()
> on a float and the assembly at about 1.5.
> Was just wondering if anyone had any recommendations? I am relatively
> pleased to have gotten that close to the standard library, but
> certainly wouldn't complain if I could get more speed and/or more
> decimal bits with a different approach.

Use Newton-Raphson.
It's easiest to find 1/sqrt(x), and then post-multiply that by x.

Phil 

-- 
... one Marine noticed one of the prisoners was still breathing. A Marine 
can be heard saying on the pool footage provided to Reuters Television: 
"He's fucking faking he's dead. He faking he's fucking dead."
"The Marine then raises his rifle and fires into the man's head. 
The pictures are too graphic for us to broadcast," Sites said.