Scott Dattalo <scott@DATTALO.COM> wrote:
> On Sat, 23 Aug 2003, CVT-SSS wrote:
> > local number, sqr_root, sqr_done, sqr_dif, sqr_nmbr
> > store 0 to  sqr_root, sqr_done, sqr_dif, sqr_nmbr
> > store 921 to number         /* max value from 1024 * 4.5 / 5.0
> > store 1 to sqr_dif
> > store number to sqr_root, sqr_done
> >
> > do while sqr_done > ( sqr_dif / 10 )
> >    sqr_nmbr = number / sqr_root
> >    sqr_done = sqr_root - sqr_nmbr
> >    sqr_root = ( sqr_root + sqr_nmbr ) / 2
> >    ? numero
> >    ? sqr_root
> >    ? sqr_done
> > enddo
>
> This algorithm is extraordinarily slow on a PIC. I wouldn't waste my time
> with it especially since there have been other algorithms posted that are
> faster and more importantly, working already.

I haven't really been paying attention to this thread so far, so pardon
me for jumping in. Here are two different integer square root routines
that use only shifts, adds and ors. These are given as C code, but hand
translation to assembly should be straightforward. Adjust as needed for
your actual word size.

uint16 SquareRoot (uint16 Number)
{
  uint16 Root;
  uint16 RootSquared;
  uint16 Mask;
  uint16 MaskSquared;
  uint16 Test;
  uint16 Power;

  Root = 0;
  RootSquared = 0;
  Mask = 1 << (Precision - 1);
  MaskSquared = 1L << ((Precision - 1) << 1);

  for (Power = Precision; Power > 0; --Power) {
    Test = RootSquared + MaskSquared + ((uint16)Root << Power);
    if (Test <= Number) {
      RootSquared = Test;
      Root |= Mask;
    }
    Mask >>= 1;
    MaskSquared >>= 2;
  }

  return Root;
}

uint32 sqrt (uint32 n)
{
  uint32 root = 0, bit, trial;
  bit = (n >= 0x10000) ? 1<<30 : 1<<14;
  do {
    trial = root + bit;
    if (n >= trial) {
      n -= trial;
      root = trial + bit;
    }
    root >>= 1;
    bit >>= 2;
  } while (bit);
  return root;
}

And here's a slower one that's even simpler:

int root (int x)
{
  int n;

  for (n=1; x>=n; n+=2) x -= n;
  return n>>1;
}

If you want a mathematical explanation of any of these, let me know.

-- Dave Tweed

--
http://www.piclist.com hint: To leave the PICList
mailto:piclist-unsubscribe-request@mitvma.mit.edu