Блог

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

 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) . Кто-нибудь может объяснить мне эту часть?

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

Пусть «num_init» будет значением num в начале функции. Предположим, что на некоторой итерации у нас есть бит = 4 ^ x и это число равно некоторому значению «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.

Переходя к первому оператору if, предположим, что наше воображаемое «встроенное» целое число равно 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) и bit = 4 ^ x . Затем мы получаем точку позади

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

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

 bit >>= 2;
 

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

Я использую его, чтобы получить квадратный корень из числа uint_fast64_t в C :

 #include <stdint.h>

static inline uint_fast64_t square_root(uint_fast64_t n) {
    uint_fast64_t a = 0, b, c;
    for (b = 1ULL << 62; b;)
        c = a   b, n -= c amp;= -(n >= c), a = (a >> 1) | (c amp; b), b >>= 2;
    return a;
}