快速整数sqrt上限近似

Question

这是一个关于我的作业，特别是关于NASM的问题。

我正在写一个算法来查找数字的最小整数。 （大于1）

在伪代码可以概括为：

if(n%2==0) 
    return 2; 
for(i=3; i <= n/2; i+=2) 
    if(n%i==0) 
     return i; 
return n; 

该方案是仅比为大量的要求稍微慢一些。 （n> 1 000 000 000）

最明显的（对我来说）改进将取代n/2与sqrt(n)。然而，我不应该知道如何使用浮点数，并且通过牛顿的方法找到整数sqrt似乎过分。 （因为我实际上并不需要知道确切的值，虽然我没有测试它，但我会想象找到isqrt递归地/迭代地会很慢）

所以我想知道，是否有快速算法的一些功能，如sqrt(n) < f(n) < n/2。 “快”我的意思是最好是恒定的时间，由f(n) < n/2我的意思是大大减少大n。

一些我正在考虑的选项有：

• 检查，为i <= min(sqrt(2^32), n/2)，其中sqrt(2^32) = 2^16是一个常数。

• 用i <= n/2替换i <= (2^p)，其中p = ⌈log_2(n)/2⌉什么的。 （p是n最显著位的一半的位置）

Answer 1

在我的⌈log_2(n)/2⌉版本结算结束。由于sqrt(n) = 2^(log_2(n)/2)。所以对于有需要的人来说，这是我的解决方案sqrt(n)上限近似值为O(1)。整个算法是O(sqrt(n))（我认为）。

mov esi,ebx  ;ebx = N 
shr esi,1  ;esi = N/2 
cmovnc esi,2 ;if no remainder RETURN 2 
jnc RETURN 
mov edi,2  ;edi is max counter 
bsr eax,ebx  ;eax is most significant set bit of ebx (log_2(eax)) 
shr eax,1  ;eax/=2 
mov cl,al 
shl edi,cl  ;max counter is 2^(log_2(N)/2 + 1) >= sqrt(N) 
mov esi,1  ;default answer is 1 
mov ecx,3  ;start counter is 3 
START: 
mov edx,0 
mov eax,ebx 
div ecx   ;divide N by counter 
test edx,edx ;if no remainder RETURN counter 
cmovz esi,ecx 
jz RETURN 
add ecx,2  ;else counter += 2 
cmp ecx,edi 
jb START  ;if counter <= max counter try agian with new divisor 
RETURN: 
       ;the answer is in (esi) 

P.S.如果你想知道为什么我不检查i*i <= N。它实际上比这个版本慢很多。在循环内部添加一个mul不应该太慢，所以我怀疑它会在每次迭代中打破分支预测算法。 cmp ecx,edi正在比较一个计数器和一个常数，因此可以预测在大多数时间，cmp 'ecx*ecx',ebx将比较计数器的平方，这对处理器来说可能不是那么明显。

Answer 2

更换I与I * I：

if (n % 2 == 0) 
    return 2; 
for (int i = 3; i * i <= n; i += 2) 
    if (n % i == 0) 
     return i; 
return n