寻找一种高效的ARM Thumb2整数平方根算法
寻找一种高效的ARM Thumb2整数平方根算法
提问于 2009-07-09 03:29:28
我正在寻找一个快速，整数唯一的算法，以找到一个无符号整数的平方根(整数部分)。代码必须在ARM Thumb 2处理器上具有出色的性能。它可以是汇编语言或C代码。
欢迎任何提示。
回答 11
Stack Overflow用户
发布于 2009-07-08 19:35:02
一种常见的方法是一分为二。
hi = number
lo = 0
mid = ( hi + lo ) / 2
mid2 = mid*mid
while( lo < hi-1 and mid2 != number ) {
if( mid2 < number ) {
lo = mid
else
hi = mid
mid = ( hi + lo ) / 2
mid2 = mid*mid像这样的东西应该工作得相当好。它做log2(数字)测试，做log2(数字)乘法和除法。由于除数是除以2，因此可以用>>替换它。
终止条件可能不是正确的，因此一定要测试各种整数，以确保除以2不会在两个偶数值之间错误地振荡；它们之间的差异将超过1。
Stack Overflow用户
发布于 2009-08-27 20:54:19
它不是很快，但它很小很简单：
int isqrt(int n)
{
int b = 0;
while(n >= 0)
{
n = n - b;
b = b + 1;
n = n - b;
}
return b - 1;
}Stack Overflow用户
发布于 2012-04-26 17:45:13
我发现大多数算法都是基于简单的想法，但以一种比必要的方式更复杂的方式实现。我从这里得到了这个想法：http://ww1.microchip.com/downloads/en/AppNotes/91040a.pdf (由罗斯·M·福斯勒编写)，并把它变成了一个非常简短的C函数：
uint16_t int_sqrt32(uint32_t x)
{
uint16_t res=0;
uint16_t add= 0x8000;
int i;
for(i=0;i<16;i++)
{
uint16_t temp=res | add;
uint32_t g2=temp*temp;
if (x>=g2)
{
res=temp;
}
add>>=1;
}
return res;
}这在我的blackfin上编译为5个周期/位。我相信，如果使用for循环而不是while循环，编译后的代码通常会更快，并且可以获得确定性时间的额外好处(尽管这在一定程度上取决于编译器如何优化if语句)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1100090
复制相关文章
相似问题
腾讯云开发者
