Prev: Choosing Bi-port Ethernet Chip
Next: Loss of synchronisation: Are the chips reliable?
From: Paul Carpenter on 6 May 2008 15:05
"David Brown" <david.brown(a)hesbynett.removethisbit.no> wrote in message
news:d_ydnXqQPZd614fVnZ2dnUVZ8umdnZ2d(a)lyse.net...
> David T. Ashley wrote:
> > What is the best integer square root algorithm for a processor with MUL
and
> > DIV (integer multiplication and division) built-in?
> >
> > For one without MUL and DIV (or where the instructions operate on
shorter
> > operands than would be required to form the square in question)?
> >
> > Thanks for all ideas and thoughts.
> >
> > I will check TOACP, of course.
> >
> > The application is a low-cost microcontroller with a 3-axis
accelerometer.
> > To get the magnitude of the acceleration, we'd want to use
> > sqrt(x^2+y^2+z^2). The squaring operations are cheap (MUL). The
addition
> > is cheap (ADD, ADC). The square root extraction is what I'm not sure
how
> > best to do.
> >
> > The algorithm that comes to mind is just to do a binary search by
squaring
> > potential solutions and comparing them to the quantity whose square root
is
> > to be extracted.
> >
> > For example, if the sum of the squares is 16 bits or less, and since the
> > processor has a 8 x 8 = 16 MUL instruction, it should be possible to
iterate
> > to the solution in no more than 16 square/compare cycles.
> >
> > But maybe there is a better way?
> >
> > And it isn't clear what to do if the sum of the squares is a bit larger.
> >
> > Thanks for all.
> >
>
> First make sure you really need to find the square root. For many uses,
> you could just use the calculated square of the magnitude.

I am glad someone else said that. as often I look at algorithms and then
determine
what results are needed and if some of the final satges are actually needed!

Too often the mathematicians and straight coders are looking for the perfect
mousetrap where a sufficient one will do. By this I mean

Are our input or output ranges limited anyway
(for _most_ light reading applications negative light is not
possible!)

Do we need to process using the result in a way that a partial result
will
give the same relationship, i.e. could we just use the sum of
squares
or is the data being passed to a PC or higher computational device
better suited to do the intensive calculations.

What is out native (8/16/32/64bit) and software (emulated floating
point) ranges
and limitations on what we are doing.

How often are we doing this (once a day, down to millions a second)

How fast do we have to do this (closely associated with previous and
total system
and application
requirements)

How accurate is the response needed and implications of any inaccuracies
(e.g. image processing will calculating image position results to 10
decimal places
help us draw a circle on a fixed pixel array - integer).

--
Paul Carpenter | paul(a)pcserviceselectronics.co.uk
<http://www.pcserviceselectronics.co.uk/> PC Services
<http://www.pcserviceselectronics.co.uk/fonts/> Timing Diagram Font
<http://www.gnuh8.org.uk/> GNU H8 - compiler & Renesas H8/H8S/H8 Tiny
<http://www.badweb.org.uk/> For those web sites you hate


From: lowcost on 7 May 2008 10:27
Vladimir Vassilevsky ha scritto:
> How accurate do you want to be?

good question.

if you can tolerate +3 lsb or +7 % (that's better) accuracy, you can

convert polynomial to exponent (approx),
to halve exponent,
convert exponent to polynomial (approx).

none MUL_DIV: INC_DEC_SHIFT_ROT only.

best accuracy is at input values = 2^even.
worst accuracy is at input values = 2^odd.

regards
First  |  Prev  | 
Pages: 1 2
Prev: Choosing Bi-port Ethernet Chip
Next: Loss of synchronisation: Are the chips reliable?