Archive for April, 2007

Crest factor, Square roots & neat algorithms

Saturday, April 21st, 2007 Nigel Jones

I’ve been programming microcontrollers for about 25 years now – and can count on one hand the number of times I’ve needed to compute the square root of an integer. This curious drought came to an end recently when I needed to compute the Crest Factor of the line voltage being used to power a product I was designing. (For the uninitiated / rusty out there, Crest Factor is the ratio of the Peak : RMS of a waveform. For example, A sine wave has a CF of 1.414, whereas a square wave has a CF of 1.000).

Why, you might ask, do I need to compute the CF? Well, the product uses triacs to control a number of AC loads. If the system is inadvertently powered from a square wave inverter, or just a really lousy generator, then the triacs will not self-commutate – and I could never turn off the loads. Thus to prevent this unfortunate scenario, I need to know how good (i.e. sinusoidal) the line voltage is. The CF is a direct figure of merit that allows me to make this decision.

Evidently, the computation of CF requires one to compute an RMS voltage, which in turn requires one to calculate the square root of a number. For various reasons, I need to compute the CF on a mains cycle by cycle basis – and I’m using a 7.37 MHz ATmega CPU. Thus, the computational efficiency of the algorithm is important.

Now IAR has a nifty little algorithm that computes an approximate square root. See http://supp.iar.com/Support/?note=18180&from=search+result

However, this gets blown away by the algorithm described by Crenshaw in his wonderful book: Math Toolkit for Real-Time Programming, CMP Books. ISBN 1-929629-09-5.

The code in his book is for computing the square root of a 32 bit unsigned integer. I adapted it to give the square root of a 16 bit integer. Here’s the code:

static inline uint8_t friden_sqrt16(uint16_t val)
{
 uint16_t rem = 0;
 uint16_t root = 0;
 uint8_t i;

 for(i = 0; i < 8; i++)
 {
  root <<= 1;
  rem = ((rem << 2) + (val >> 14));
  val <<= 2;
  root++;
  if (root <= rem)
  {
   rem -=root;
   root++;
  }
  else
  {
   root--;
  }
 }
 return (uint8_t)(root >> 1);
}

This will compute the exact square root of a 16 bit integer in about 268 clock cycles on an AVR – i.e. in about 33 microseconds on an 8 MHz AVR processor.

To Crenshaw’s point – don’t just blindly use the code, but endeavor to understand how it works. Only then will you see it for what it truly is – a work of art. Thanks Jack.

Home