获得sqrt(n)整数部分的最快方法？
我们知道，如果n不是一个完美的正方形，那么sqrt(n)就不是一个整数。因为我只需要整数部分，所以我觉得调用sqrt(n)不会那么快，因为它也需要时间来计算小数部分。
所以我的问题是，
我们能不能只得到sqrt(n)的整数部分而不计算sqrt(n)的实际值？算法应该比sqrt(n) (在<math.h>或<cmath>中定义)更快吗？
如果可能，您也可以在asm块中编写代码。
回答 7
Stack Overflow用户
发布于 2011-03-14 17:17:13
编辑:这个答案很愚蠢--使用(int) sqrt(i)
在使用适当的设置(-march=native -m64 -O3)进行性能分析之后，上述操作的速度要快得多。
好吧，这是一个有点老的问题，但是“最快”的答案还没有给出。最快的(我认为)是二进制平方根算法，在this Embedded.com article中有详细的解释。
它基本上可以归结为：
unsigned short isqrt(unsigned long a) {
unsigned long rem = 0;
int root = 0;
int i;
for (i = 0; i < 16; i++) {
root <<= 1;
rem <<= 2;
rem += a >> 30;
a <<= 2;
if (root < rem) {
root++;
rem -= root;
root++;
}
}
return (unsigned short) (root >> 1);
}在我的机器(Q6600，Ubuntu10.10)上，我通过取数字1-100000000的平方根来进行分析。使用iqsrt(i)需要2750ms。使用(unsigned short) sqrt((float) i)花费了3600ms。这是使用g++ -O3完成的。使用-ffast-math编译选项，时间分别为2100ms和3100ms。注意，这甚至不需要使用一行汇编程序，所以它可能仍然会更快。
上面的代码既适用于C语言，也适用于C++，只需稍作语法更改即可。
在有限范围内工作得更好的是二进制搜索。在我的机器上，这使上面的版本超出了4倍。不幸的是，它的范围非常有限：
#include <stdint.h>
const uint16_t squares[] = {
0, 1, 4, 9,
16, 25, 36, 49,
64, 81, 100, 121,
144, 169, 196, 225,
256, 289, 324, 361,
400, 441, 484, 529,
576, 625, 676, 729,
784, 841, 900, 961,
1024, 1089, 1156, 1225,
1296, 1369, 1444, 1521,
1600, 1681, 1764, 1849,
1936, 2025, 2116, 2209,
2304, 2401, 2500, 2601,
2704, 2809, 2916, 3025,
3136, 3249, 3364, 3481,
3600, 3721, 3844, 3969,
4096, 4225, 4356, 4489,
4624, 4761, 4900, 5041,
5184, 5329, 5476, 5625,
5776, 5929, 6084, 6241,
6400, 6561, 6724, 6889,
7056, 7225, 7396, 7569,
7744, 7921, 8100, 8281,
8464, 8649, 8836, 9025,
9216, 9409, 9604, 9801,
10000, 10201, 10404, 10609,
10816, 11025, 11236, 11449,
11664, 11881, 12100, 12321,
12544, 12769, 12996, 13225,
13456, 13689, 13924, 14161,
14400, 14641, 14884, 15129,
15376, 15625, 15876, 16129,
16384, 16641, 16900, 17161,
17424, 17689, 17956, 18225,
18496, 18769, 19044, 19321,
19600, 19881, 20164, 20449,
20736, 21025, 21316, 21609,
21904, 22201, 22500, 22801,
23104, 23409, 23716, 24025,
24336, 24649, 24964, 25281,
25600, 25921, 26244, 26569,
26896, 27225, 27556, 27889,
28224, 28561, 28900, 29241,
29584, 29929, 30276, 30625,
30976, 31329, 31684, 32041,
32400, 32761, 33124, 33489,
33856, 34225, 34596, 34969,
35344, 35721, 36100, 36481,
36864, 37249, 37636, 38025,
38416, 38809, 39204, 39601,
40000, 40401, 40804, 41209,
41616, 42025, 42436, 42849,
43264, 43681, 44100, 44521,
44944, 45369, 45796, 46225,
46656, 47089, 47524, 47961,
48400, 48841, 49284, 49729,
50176, 50625, 51076, 51529,
51984, 52441, 52900, 53361,
53824, 54289, 54756, 55225,
55696, 56169, 56644, 57121,
57600, 58081, 58564, 59049,
59536, 60025, 60516, 61009,
61504, 62001, 62500, 63001,
63504, 64009, 64516, 65025
};
inline int isqrt(uint16_t x) {
const uint16_t *p = squares;
if (p[128] <= x) p += 128;
if (p[ 64] <= x) p += 64;
if (p[ 32] <= x) p += 32;
if (p[ 16] <= x) p += 16;
if (p[ 8] <= x) p += 8;
if (p[ 4] <= x) p += 4;
if (p[ 2] <= x) p += 2;
if (p[ 1] <= x) p += 1;
return p - squares;
}32位版本可在此处下载：https://gist.github.com/3481770
Stack Overflow用户
发布于 2015-03-11 08:42:51
如果你不介意近似值，我拼凑的这个整型sqrt函数怎么样？
int sqrti(int x)
{
union { float f; int x; } v;
// convert to float
v.f = (float)x;
// fast aprox sqrt
// assumes float is in IEEE 754 single precision format
// assumes int is 32 bits
// b = exponent bias
// m = number of mantissa bits
v.x -= 1 << 23; // subtract 2^m
v.x >>= 1; // divide by 2
v.x += 1 << 29; // add ((b + 1) / 2) * 2^m
// convert to int
return (int)v.f;
}它使用这篇Wikipedia文章中描述的算法。在我的机器上，它几乎是sqrt的两倍:)
Stack Overflow用户
发布于 2012-08-27 01:55:31
要执行整数sqrt，您可以使用这种特殊化的newton方法：
Def isqrt(N):
a = 1
b = N
while |a-b| > 1
b = N / a
a = (a + b) / 2
return a基本上，对于任何x，sqrt都在(x…N/x)，所以我们只在每次循环时将该间隔一分为二，以获得新的猜测。有点像二进制搜索，但它的收敛速度必须更快。
它收敛于O(loglog(N))，这是非常快的。它也完全不使用浮点数，它也可以很好地处理任意精度的整数。
https://stackoverflow.com/questions/4930307
复制相似问题
腾讯云开发者
