Вычисление целочисленного корня
От: ravik  
Дата: 10.02.21 13:37
Оценка: :)
Наткнулся на статью на Хабре, в которой автор из-за отсутствия под рукой софта (он программировал 12-разрядный контроллер), пустился во все тяжкие, чтобы заменить не хватающее ему взятие корня неким прикладным маневром. Заинтересовался и набросал решение взятия целочисленного корня из произвольной длины массива. Для иллюстрации здесь решение редуцировано до 32-битных значений (см. в скрытом тексте, описание алгоритма — в комментариях), чтобы сам алгоритм не затерялся в каше обработки пересечений границ блоков.

  Скрытый текст
void TestSQR(void)
{
    unsigned int pv = 14777;    //подкоренное значение
    unsigned int sqr = 0;        //извлеченный корень
    __asm
    {
        mov edx, pv;            //загружаем исходное значение
        xor edi, edi;            //в EDI будет накапливаться вычисляемый корень
        bsr ecx, edx;            //вычисляем позицию старшего значащего разряда (ПСЗР)
        jz QUIT;
        shr ecx, 1;
        mov edi, 1;
        shl edi, cl;            //получаем установленный старший бит корня
        shl edi, cl;            //
        sub edx, edi;            //эти 3 команды сокращают цикл на 2 итерации
        shr edi, cl;            //
        mov ch, cl;
START:  bsr eax, edx;            //вычисляем ПСЗР уменьшающегося с каждым шагом цикла pv
        jz QUIT;                //pv обнулился - значит, корень извлекся нацело
        mov cl, al;
        sub cl, ch;
        jz QUIT;                //без этой строки алгоритм ошибается на корне из 2 и 3
        jc QUIT;
        dec cl;
        jz LAST_BIT;            //если остаток pv >= 2 * sqr + 1, то добавляем к sqr 1
        dec cl;                    //в CL вычислен индекс разряда корня, в который надо добавить 1
        mov eax, 1;                
        shl eax, cl;            //в итерации до возврата к метке START
        mov ebx, edi;            //происходит вычитание из текущего значения pv
        shl ebx, cl;            //вычисленного на лету значения 2 * sqr + 1 
        sub edx, ebx;            //и смещенного в правильную по отношению к pv позицию.
        lea ebx, [edi+eax];        //Вместо умножения на 2 производится 2 вычитания:
        mov edi, ebx;            //сначала без добавленной единицы в правильный разряд,
        shl ebx, cl;            //затем уже вместе с ней
        sub edx, ebx;
        jmp START;
LAST_BIT:                        //проверка, что остаток не превышает 2 * sqr + 1
        lea ebx, [edi*2];
        cmp edx, ebx;
        jbe QUIT;
        inc ebx;
        sub edx, ebx;
        inc edi;
QUIT:
        mov sqr, edi;
        mov pv, edx;
    }
    WCHAR sz[256];
    wsprintf(sz, L"корень: %d\nостаток: %d\n", sqr, pv);
    ::OutputDebugString(sz);
    return;
}


Но возник вопрос разбирающимся в матобеспечении. Взаправдашний алгоритм вычисления квадратного корня программным способом, например, в матбиблиотеках, — примерно похож?! Я до сего момента довольствовался пионерским методом усреднения множителей, знаю еще метод цепных дробей... А вот вышеприведенного велосипеда — не встречал... Удовлетворите любопытство, плж!
Отредактировано 12.02.2021 5:56 ravik . Предыдущая версия . Еще …
Отредактировано 10.02.2021 14:02 ravik . Предыдущая версия .
Отредактировано 10.02.2021 13:53 ravik . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.