c - 使用 NN 库求整数平方根

Question

我正在寻找一种更有效的方法来查找 128 位数字的整数平方根...需要使用 NN 库，我将在其上使用它的平台之一，没有足够的内存用于 BigNum 或 MPZ

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);
}

Answer 1

Charles Ma 已经建议进行二分搜索，这只需要 64 次迭代(需要对数时间，并且平方根必须 <=64 位，否则结果不适合 128 位)。

您可以加快查找输入中设置的第一个位 i 的速度，然后您就知道结果中设置的第一个位必须是 i/2。因此，在进行二分搜索时，您可以将间隔限制在 i 到 i*2-1 之间。这可以进一步减少迭代次数。

二分查找非常简单:从一个区间开始，在中间检查中间元素的平方是否是您的输入。如果是这样，则停止并将其输出为 root，否则根据它是小还是大，以新间隔 (旧最小值，中) 或 (中，旧最大值) 重复>。 (关于二分搜索的资料有很多，我想我不需要在这里详细说明)