Каков самый быстрый способ найти целочисленный квадратный корень с использованием сдвигов бит?

Question

Я искал самый быстрый способ вычисления квадратного корня (целое число) числа (целое число). Я наткнулся на это решение в википедии, который находит квадратный корень числа (если его идеальный квадрат) или корень квадратный из его ближайшего нижнего полного квадрата (если данное число не является полным квадратом:

short isqrt(short num) { 
    short res = 0; 
    short bit = 1 << 14; // The second-to-top bit is set: 1L<<30 for long 
    // "bit" starts at the highest power of four <= the argument. 
    while (bit > num) 
     bit >>= 2; 
    while (bit != 0) { 
     if (num >= res + bit) { 
      num -= res + bit; 
      res = (res >> 1) + bit; 
     } 
     else 
      res >>= 1; 
     bit >>= 2; 
    } 
    return res; 
} 

Я пробовал много пробных прогонов, чтобы проследить алгоритм, но я, кажется, не понимаю часть внутри while(bit!=0). Может кто-нибудь объяснить эту часть мне?

Answer 1

Я также прорисовал несколько небольших примеров, и я думаю, . Насколько я понимаю, алгоритм строит ответ на одну двоичную цифру за раз, от наивысшего бита к младшему.

Пусть num_init - значение num в начале функции. Предположим, что на некоторой итерации мы имеем бит = 4^х, а число равно некоторому значению «num_curr» (быстрый взгляд показывает, что до тех пор, пока бит равен 0, он всегда равен 4). Тогда res имеет вид y * 2^(x + 1), где y^2 + num_curr = num_init, а y меньше фактического ответа, но в пределах 2^x.

Этот инвариант относительно значений num, res и bit будет ключевым. Как это делается в коде, что

while (bit != 0) { 
    .... 
} 

движется наш воображаемый указатель слева направо, и на каждом шаге мы определяем этот бит равен ли 0 или 1.

Переход к первой, если заявление , предположим, что наше воображаемое «застроенное» целое число равно y, и мы смотрим на бит 2^x. Тогда бит равен 1, если исходное значение num равно (y + 2^x)^2 = y^2 + y * 2^(x + 1) + 4^x. Другими словами, бит равен единице, если значение num в этой точке не меньше y * 2^(x + 1) + 4^x (так как мы имеем инвариант, что значение num упало на y^2) , Достаточно удобно res = y * 2^(x + 1) и бит = 4^x. После этого мы получим точку за

if (num >= res + bit) { 
    num -= res + bit; 
    res = (res >> 1) + bit; 
} 
else 
    res >>= 1; 

который добавляет 1 бит в нашем воображаемом месте, если это необходимо, затем обновляет разрешения и Num сохранить инвариант. Наконец

bit >>= 2; 

обновляет бит и перемещает все на один шаг.