快整数平方根近似
我目前正在寻找一个非常快的整数平方根逼近，其中floor(sqrt(x)) <= veryFastIntegerSquareRoot(x) <= x
平方根例程用于计算素数，如果只检查低于或等于sqrt(x)是否为x的除数，则该常数会显着加快。
我目前拥有的是维基百科的这个功能，调整了一点点以使用64位整数。
因为我没有其他功能可以与之比较（或者更确切地说，功能对于我的目的来说太精确了，而且可能需要更多时间，而不是比实际结果更高）。
Loopfree / jumpfree（well：差不多;-) Newton-Raphson：
/* static will allow inlining */
static unsigned usqrt4(unsigned val) {
unsigned a, b;
if (val < 2) return val; /* avoid div/0 */
a = 1255; /* starting point is relatively unimportant */
b = val / a; a = (a+b) /2;
b = val / a; a = (a+b) /2;
b = val / a; a = (a+b) /2;
b = val / a; a = (a+b) /2;
return a;
}
对于64位整数，您将需要更多的步骤（我的猜测：6）
在现代PC硬件上，使用浮点运算比使用任何类型的快速整数数学计算n平方根可能更快。
但是请注意，它可能根本不需要：您可以改变候选人的方格，并在广场超过n的值时停止。 无论如何，主要的操作是分工：
#define PBITS32 ((1<<2) | (1<<3) | (1<<5) | (1<<7) | (1<<11) | (1<<13) |
(1UL<<17) | (1UL<<19) | (1UL<<23) | (1UL<<29) | (1UL<<31))
int isprime(unsigned int n) {
if (n < 32)
return (PBITS32 >> n) & 1;
if ((n & 1) == 0)
return 0;
for (unsigned int p = 3; p * p <= n; p += 2) {
if (n % p == 0)
return 0;
}
return 1;
}
这个版本可以更快，因为DIV是缓慢的，对于小数字（Val <20k），此版本将错误降低到5％以下。 测试ARM M0（没有DIV硬件加速）
static uint32_t usqrt4_6(uint32_t val) {
uint32_t a, b;
if (val < 2) return val; /* avoid div/0 */
a = 1255; /* starting point is relatively unimportant */
b = val / a; a = (a + b)>>1;
b = val / a; a = (a + b)>>1;
b = val / a; a = (a + b)>>1;
b = val / a; a = (a + b)>>1;
if (val < 20000) {
b = val / a; a = (a + b)>>1; // < 17% error Max
b = val / a; a = (a + b)>>1; // < 5% error Max
}
return a;
}