Finding Integer Square Roots using NN library

I am looking for a mo开发者_StackOverflow社区re efficient way of finding the Integer Square Root of a 128bit number... Need to use the NN Library one of the platforms I will use this on, has not enough memory for BigNum or 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);
}

---

Charles Ma already suggest to do a binary search, that would need just 64 iterations (takes log time, and the square root must be <=64 bit as the result would else not fit within 128 bit).

You can speed it up finding the first bit i set from your input, and then you know that the first bit set in your result must be i/2. So when doing your binary search you can limit your interval from i to i*2-1. This can reduce your number of iterations even more.

The binary search is really easy: you start with an interval, take the middle of it a check if the square of the middle element is your input. If so stop and output it as root, else depending wether it was to small or to big, repeat with new interval (old min, middle) or (middle, old max). (There are plenty full of sources about binary search, I think I dont need to elaborate here more about it)