| |
 |
|
|
Science Forum Index » Mathematics Forum » Integer Square Root Algorithm for Processor with MUL, DIV
Page 1 of 1
|
| Author |
Message |
| David T. Ashley |
 Posted: Thu May 01, 2008 12:06 pm |
|
|
|
Guest
|
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.
--
David T. Ashley (dta@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects) |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Sun Sep 07, 2008 8:14 pm
|
|