使用NN庫查找整數平方根

我正在尋找一種更有效的方式來查找128位數的整數平方根... 需要使用NN庫我將使用此平臺的其中一個平臺，還沒有足夠的內存來BIGNUM或MPZ使用NN庫查找整數平方根

void NN_SquareRoot(NN_DIGIT *output, NN_DIGIT *input, int digits) 
{ 
NN_DIGIT divisor[NS*2], Temp[NS*2], Temp2[NS*2], Temp3[NS*2]; 
int t; 
int i; 
int g; 
unsigned char temp3[16]; 
NN_AssignZero(Temp2,NS); 
for(t=0;t<digits;t++){ 
for(i=0;i<=255;i++){ 
temp3[t]=i; 
NN_AssignZero(Temp,NS); 
NN_Decode(Temp,16,temp3,NS/2); 
NN_Mult(Temp2,Temp,Temp,NS/2); 
if(NN_Cmp(input,Temp2,digits)==-1){ 
    if(i!=0)temp3[t]=i-1; 
    if(t<digits)break; 
    t++; 
    i=0; 
} 

    } 
} 
NN_Copy(output,Temp,NS); 
}

來源

2011-08-21 Phillip

您可以進行二分搜索，128個數字應該不超過64次迭代。 –

你有沒有例子？ – Phillip

查爾斯·馬已經建議做一個二進制搜索，這將只需要64次迭代（需要登錄時間，平方根必須< = 64位的結果將別的不適合128位）。

您可以加速找到從您的輸入中設置的第一位i，然後您知道結果中設置的第一位必須是i/2。因此，在進行二進制搜索時，您可以將時間間隔從i限制爲i*2-1。這可以減少您的迭代次數。

二分法搜索非常簡單：您從一個區間開始，如果中間元素的平方是您的輸入，請在中間進行檢查。如果這樣停止並輸出它作爲根，否則取決於它是小還是大，以新的間隔（舊分，中）或（中，舊最大）重複。（關於二進制搜索，有很多豐富的資源，我想我不需要在此詳細說明）

來源

2011-08-21 19:51:30 flolo

使用NN庫查找整數平方根

回答

相關問題