我正在寻找一些用于平方根计算的算法并找到了这个源文件。我想尝试复制它,因为它看起来很简单,但我无法将它与一些已知的算法(牛顿,巴比伦......)联系起来。能告诉我名字吗?
int sqrt(int num) {
int op = num;
int res = 0;
int one = 1 << 30; // The second-to-top bit is set: 1L<<30 for long
// "one" starts at the highest power of four <= the argument.
while (one > op)
one >>= 2;
while (one != 0) {
if (op >= res + one) {
op -= res + one;
res += 2 * one;
}
res >>= 1;
one >>= 2;
}
return res;
}
最佳答案
如@Eugene Sh.引用文献,这是计算平方根的经典“逐位”方法。在 base 10 中学到的小学时就教过这些东西。
OP 的代码也无法选择数字。 sqrt(1073741824) --> -1
而不是预期的 32768。1073741824 == 0x40000000
。此外,它未能满足大多数(全部?)的值(value)以及更大的值(value)。当然OP的sqrt(some_negative)
也是一个问题。
候选替代方案:也 here
unsigned isqrt(unsigned num) {
unsigned res = 0;
// The second-to-top bit is set: 1 << 30 for 32 bits
// Needs work to run on unusual platforms where `unsigned` has padding or odd bit width.
unsigned bit = 1u << (sizeof(num) * CHAR_BIT - 2);
// "bit" starts at the highest power of four <= the argument.
while (bit > num) {
bit >>= 2;
}
while (bit > 0) {
if (num >= res + bit) {
num -= res + bit;
res = (res >> 1) + bit; // Key difference between this and OP's code
} else {
res >>= 1;
}
bit >>= 2;
}
return res;
}
可移植性更新。需要 4 的最大幂。
#include <limits.h>
// greatest power of 4 <= a power-of-2 minus 1
#define POW4_LE_POW2M1(n) ( ((n)/2 + 1) >> ((n)%3==0) )
unsigned bit = POW4_LE_POW2M1(UINT_MAX);
关于c - 网上找到的平方根源代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45148893/