Нахождение целочисленных квадратных корней с использованием библиотеки 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

Чарльз Ма уже предлагает выполнить бинарный поиск, который потребует всего 64 итерации (занимает время журнала, а квадратный корень должен быть <= 64 бит, так как результат не укладывается в 128 бит). </p>

Вы можете ускорить его, найдя первый бит i, установленный на вашем входе, и тогда вы узнаете, что первый бит, установленный в вашем результате, должен быть i/2. Поэтому при выполнении бинарного поиска вы можете ограничить интервал от i до i*2-1. Это может еще больше сократить количество ваших итераций.

Бинарный поиск действительно прост: вы начинаете с интервала, проверяете в середине его, является ли квадрат среднего элемента вашим вводом. Если это так, остановите и выведите его как root, иначе, в зависимости от того, было ли оно маленьким или большим, повторите с новым интервалом (старый минимум, средний) или (средний, старый максимум) . (Существует множество источников о бинарном поиске, я думаю, мне не нужно подробно здесь рассказывать об этом)