cancel
Showing results for 
Search instead for 
Did you mean: 

Fast SQRT function

fakhfakh2
Associate II
Posted on December 03, 2012 at 09:32

Hello,

I'm looking for a very fast SQRT.c function (32bit Int to 16bit Int) that works on STM32f100. I already have one but it's slow. 

thank you,

#sqrt-stm32f100 #integer-square-root
4 REPLIES 4
frankmeyer9
Associate II
Posted on December 03, 2012 at 10:08

Piecewise linear interpolation in a precalculated table.

That's the way most integer fft algorithms doing it with sin/cos.

John F.
Senior
Posted on December 03, 2012 at 12:05

Google ''Crenshaw Integer Square Root'' or buy Jack Crenshaw's book.

jpeacock2399
Associate II
Posted on December 03, 2012 at 15:56

/** 
* @brief Integer square root for RMS 
* @param sqrtAvg (sum(x squared) / count) 
* @retval approximate square root 
* 
* Approximate integer square root, used for RMS calculations. 
*/ 
static unsigned int sqrtI( unsigned long sqrtArg ) 
{ 
unsigned int answer, x; 
unsigned long temp; 
if ( sqrtArg == 0 ) return 0; // undefined result 
if ( sqrtArg == 1 ) return 1; // identity 
answer = 0; // integer square root 
for( x=0x8000; x>0; x=x>>1 ) 
{ // 16 bit shift 
answer |= x; // possible bit in root 
temp = __builtin_muluu(answer, answer); // fast unsigned multiply 
if (temp == sqrtArg) break; // exact, found it 
if (temp > sqrtArg) answer ^= x; // too large, reverse bit 
} 
return answer; // approximate root 
} 

Here's a simple bitwise successive approximation routine I use in motor controllers. It depends on a relatively fast multiply. The muluu routine is a PIC33 DSP hardware instruction for unsigned multiply. On average theiterations to derive a sqrt is log2 of the number, assuming an even distribution. Jack Peacock
zzdz2
Associate II
Posted on December 03, 2012 at 16:16

LUT and one or two Newton iterations may be accurate enough and fast.