Andrew Que Sites list Photos
Projects Contact
Main
   Yesterday I took my camera to the shop.  For a couple weeks now the shutter has been sticking.  After I take a shot, the mirror does not return.  If you physically force the mirror down the camera resets back to normal, but this requires taking the lens off after each shot and touching the mirror. 
   Happy 200,000 miles birthday Eve Liberty.  She rolled over today meaning I have placed more than 100,000 miles on her since November of 2009.

1 comment has been made.

From Stev

Chateau FryDoll, Beloit, WI

January 04, 2014 at 7:17 AM

Good to see the little lady chugging strong! I remember when you first got Eve after your old Beast of a truck was assassinated by that Republican Christian Fundamentalist Neo-con terrorist deer.
  Fresh bread.

1 comment has been made.

From Steve

Chateau FryDoll, Beloit, WI

January 04, 2014 at 7:19 AM

Nice weave with the bread. Reminds me of Jewish challah bread. I sure could have gone for some of your famous vegetable soup and bread today; just got hit full-force with a fucking cold.

November 30, 2013

Integer Square-Root

Over 10 years ago I was working on a DSP that did not having floating-point abilities, and I needed to preform a square root. I posted in comp.dsp to ask about an approach to this, and received a reply that implemented a very clever solution.

uint16_t sqrt32( uint32_t radicand )
{
  uint16_t root    = 0;
  uint16_t bitMask = 1U << 15;

  while ( bitMask )
  {
    uint32_t test = root + bitMask;
    if ( ( test * test ) <= radicand )
      root += bitMask;

    bitMask >>= 1;
  }

  return root;
}

Here we are taking the square root of a 32-bit unsigned integer. The result will always fit into 16-bits, thus why a 16-bit result is returned. Why is due to this relationship:

In this case, n = 32.

The loop is done with a while statement, but it is like a for loop counting down by dividing in integer halfs each loop. It will always loop 32 times, once for each bit. This scales to any integer size.

Here is where the clever part happens. The loop basically asks if setting the current bit will cause the square to be greater than the answer. If not, the bit is set, otherwise the bit is left clear. Why this is fast is because (unlike the square root) computing the square is easy—just a multiply.

With the DSP I was working with multiply instructions took the same amount of time as any other instruction—one of the reasons that gave DSPs an advantage over other processors. On some systems multiplication is costly, and if you are using fixed-point math chances are you are on such a system. For this, the code can be reworked to avoid having to do the multiplication.

uint16_t sqrt32( uint32_t radicand )
{
   enum { PRECESSION = 32 };

   uint16_t root        = 0;
   uint32_t rootSquared = 0;
   uint16_t mask        = 1U <<  ( PRECESSION / 2 - 1 );
   uint32_t maskSquared = 1UL << ( PRECESSION - 2 );

   int power;
   for ( power = PRECESSION / 2; power > 0--power )
   {
      uint32_t test = rootSquared + maskSquared + ( (uint32_t)root << power );

      if ( test <= radicand )
      {
        rootSquared = test;
        root += mask;
      }

      mask >>= 1;
      maskSquared >>= 2;
   }
}

Here the multiplication is avoided because we accumulate the square as part of the loop, using shifts rather than multiplication. It takes a few more operations, but will likely outrun the loop above if multiplication is an expensive operation.

This system works for fixed-point values too, but with low accuracy. Fixed-point number can be represented as such:

Where x is some real number, and f is the number of shifts. Ignoring the floor function, the fixed-point square root can be simplified:

What this means to the algorithm is that the fixed-point shift has changed after the square root has been taken. For example, if a Q16:16 number went into the square root function, a Q24:8 number would come out—and the upper 16 bits all zero. To get a number with the original fixed-point format a shift to the left of half the fractional shift is required. So for the Q16:16 number, a shift to the left of 8 is required after the square root has been taken.

The requirement for this finial shift also means the fractional precision is halved. A Q16:16 fixed-point number has 1/2 16 (≈0.000015) fractional precision, but after the square root it would only have 1/2 8 (≈0.0039). That's the loss of two decimal places.

Is this still useful today? Sure. Many embedded processors do not have hardware floating-point, and software floating-point is quite slow. For code where the square root is computed often, being able to use an integer or fixed-point square root can be a great performance boost.

1 comment has been made.

From Noah

December 04, 2013 at 1:53 AM

Binary numbers can do all sorts of interesting things - it's amazing how a complex operation like finding square roots can become a collection of simple tasks!

   Whatever it was from the darkness was approaching. The lights were now out except for a room just ahead. Cobwebs and dust covered everything. Through the dirty window she could see one person alone in the room. A single florescent bulb in the fixture above him provided all the illumination. The person had his back to the window, looking down, his hands folded in his lap. She knew him, or knew of him. Never anyone she really talked to as he was not at all popular.  At present, however, this person seemed her only hope.

   A picture of my victory today.  My task has been to synchronize clocks on two independent devices to a clock on the PC with as much precision as possible using NTP.  Writing a simple NTP client wasn't too complicated, but the question was would this be good enough to get the synchronization we wanted?  Measuring synchronization isn't an easy task when you want accuracy in fractions of a second.  Naturally this will involve an oscilloscope, but getting the software that uses a multitasking operating system to produce an output is a little tricky.  One can not simply stay in a tight loop and update the output because nothing else in the OS will get done.  A functional workaround is to run the tight loop for a single event, and then sleep for awhile so other tasks can run.  This has issues, but was functional enough to get my measurement.
   Rosa and Iggy.

1 comment has been made.

From Steve

Chateau FryDoll, Beloit, WI

December 19, 2013 at 7:32 AM

Holy balls, it's James Jr.! Haven't seen any pics of Iggy lately until now; man, there's no way James could ever possibly deny that boy! Looks just like him, red hair and all!
   We had our first snow of the season week or two ago, and it did accumulate some.  Today we had a real snowfall with over an inch of accumulation.  It's a little earlier than usual, but I'll take it!

1 comment has been made.

From Steve

Chateau FryDoll, Beloit, WI

December 19, 2013 at 7:35 AM

Boo, fuck snow! LOL, sorry old friend, you can have the snow. I still detest winter, especially the snow and the cold.