Landing : Athabascau University
  • Blogs
  • Integer Square Root Algorithm

Integer Square Root Algorithm

Most Arduino platforms don't have a floating-point unit ("FPU") and limited-enough memory to avoid implementing it in software. Often enough, we need to calculate a square root. There are many algorithms floating around on the internet, and I've tried several and give the following one my endorsement:

uint32_t sqrt(uint32_t number)
{
if (number == 0)
return 0UL;
if (number < 3)
return 1UL;

uint32_t x = number;
uint32_t y = 1;
int32_t error = 1;
while (x - y > error)
{
x = (x + y + 1) / 2; // half-up rounding with integers
y = (number + x / 2) / x;
}
return x;
}

It's based on the Babylonian/Newtonian method, and I've tweaked it so that the answer is "half-up" rounded instead of the usual integer truncation (rounding towards zero). Feel free to change it to whatever integer data type you're using. It won't work for floats -- you'll have to remove the rounding tricks. The trick is "(numerator + denominator/2)/denominator". You can speed up the loop at the expense of accuracy by increasing the allowable error.

Yes, there are faster, better, algorithms, but this one is simple enough to understand intuitively, and as such can be more easily debugged.

Comments

These comments are moderated. Your comment will not be visible unless accepted by the content owner.

Only simple HTML formatting is allowed and any hyperlinks will be stripped away. If you need to include a URL then please simply type it so that users can copy and paste it if needed.

(Required)

(Required)