快速整數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