问题描述
我要寻找一个快速的，只整数算法找到一个无符号整数的平方根（整数部分）。
在code必须在ARM的Thumb 2处理器的优异性能。这可能是汇编语言或C code。
I am looking for a fast, integer only algorithm to find the square root (integer part thereof) of an unsigned integer.The code must have excellent performance on ARM Thumb 2 processors. It could be assembly language or C code.
任何提示的欢迎。
推荐答案
Integer杰克·W·克伦肖的平方根可以作为另一个参考价值。
Integer Square Roots by Jack W. Crenshaw could be useful as another reference.
借助的有<一个href=\"http://web.archive.org/web/20080303101624/http://c.snippets.org/snip_lister.php?fname=isqrt.c\">integer平方根实现。一个超越只是整数结果，并计算应答的额外分数（定点）位。 （更新：。不幸的是，将C代码片段存档现已解散的我已经更新的链接指向页面的Web归档）
The C Snippets Archive also has an integer square root implementation. That one goes beyond just the integer result, and calculates extra fractional (fixed-point) bits of the answer. (Update: unfortunately, the C snippets archive is now defunct. I have updated the link to point to the web archive of the page.)
我定居在以下code。它本质上是由Wikipedia在平方根计算方法文章。但它已被更改为使用 stdint.h 类型 uint32_t的等严格地说，返回类型可以更改为 uint16_t 。
I settled on the following code. It's essentially from the Wikipedia article on square-root computing methods. But it has been changed to use stdint.h types uint32_t etc. Strictly speaking, the return type could be changed to uint16_t.
/**
* \brief Fast Square root algorithm
*
* Fractional parts of the answer are discarded. That is:
* - SquareRoot(3) --> 1
* - SquareRoot(4) --> 2
* - SquareRoot(5) --> 2
* - SquareRoot(8) --> 2
* - SquareRoot(9) --> 3
*
* \param[in] a_nInput - unsigned integer for which to find the square root
*
* \return Integer square root of the input value.
*/
uint32_t SquareRoot(uint32_t a_nInput)
{
uint32_t op = a_nInput;
uint32_t res = 0;
uint32_t one = 1uL << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type
// "one" starts at the highest power of four <= than the argument.
while (one > op)
{
one >>= 2;
}
while (one != 0)
{
if (op >= res + one)
{
op = op - (res + one);
res = res + 2 * one;
}
res >>= 1;
one >>= 2;
}
return res;
}
的好处，我发现，这是一个相当简单的修改可以返回四舍五入的答案。我发现这个有用的在一定的应用更高的精度。请注意，在这种情况下，返回类型必须是 uint32_t的，因为2的圆角方形根 - 1 2 。
The nice thing, I discovered, is that a fairly simple modification can return the "rounded" answer. I found this useful in a certain application for greater accuracy. Note that in this case, the return type must be uint32_t because the rounded square root of 2 - 1 is 2.
/**
* \brief Fast Square root algorithm, with rounding
*
* This does arithmetic rounding of the result. That is, if the real answer
* would have a fractional part of 0.5 or greater, the result is rounded up to
* the next integer.
* - SquareRootRounded(2) --> 1
* - SquareRootRounded(3) --> 2
* - SquareRootRounded(4) --> 2
* - SquareRootRounded(6) --> 2
* - SquareRootRounded(7) --> 3
* - SquareRootRounded(8) --> 3
* - SquareRootRounded(9) --> 3
*
* \param[in] a_nInput - unsigned integer for which to find the square root
*
* \return Integer square root of the input value.
*/
uint32_t SquareRootRounded(uint32_t a_nInput)
{
uint32_t op = a_nInput;
uint32_t res = 0;
uint32_t one = 1uL << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type
// "one" starts at the highest power of four <= than the argument.
while (one > op)
{
one >>= 2;
}
while (one != 0)
{
if (op >= res + one)
{
op = op - (res + one);
res = res + 2 * one;
}
res >>= 1;
one >>= 2;
}
/* Do arithmetic rounding to nearest integer */
if (op > res)
{
res++;
}
return res;
}
这篇关于寻找一个有效的整数平方根算法的ARM Thumb2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！