Вычисление квадратного корня 8-битного двоичного числа

Я искал способ вычислить квадратный корень данного 8-битного числа, используя только цифровую комбинацию или последовательную логику. Это возможно?

Одним из способов может быть использование таблицы поиска, поскольку я вообще не рассматриваю дробные части (поэтому ), но должен быть лучший способ, чем этот. Кто-то может указать мне на это?$\sqrt{10} \simeq 3$

Таблицы поиска были упомянуты в комментариях. Есть два подхода.

Быстрое
создание таблицы длиной 256 байт, с каждым следующим значением квадратный корень из соответствующего индекса. Это быстро, поскольку вы используете аргумент в качестве индекса для прямого доступа к нужному значению. Недостаток в том, что ему нужна длинная таблица с множеством повторяющихся значений.

Compact
Как уже говорилось, 8-разрядное целое число может иметь значения только от 0 до 255, а соответствующие квадратные корни - от 0 до 16 (округлены). Построить таблицу из 16 записей (начиная с нуля) с n-й записью - максимальное значение для аргумента, для которого квадратный корень равен n. Таблица будет выглядеть так:

 0  
 2  
 6  
12  
20
etc.

Вы проходите через таблицу и останавливаетесь, когда встречаете значение, большее или равное вашему аргументу. Пример: квадратный корень из 18

set index to 0
value[0] = 0, is less than 18, go to the next entry  
value[1] = 2, is less than 18, go to the next entry  
value[2] = 6, is less than 18, go to the next entry  
value[3] = 12, is less than 18, go to the next entry
value[4] = 20, is greater than or equal to 18, so sqrt(18) = 4

В то время как таблица быстрого просмотра имеет фиксированное время выполнения (только один поиск), здесь время выполнения больше для аргументов с более высокими значениями.

Для обоих методов следует, что, выбирая разные значения для таблицы, вы можете выбрать округленное или усеченное значение для квадратного корня.

Работая в 8 битах, вы в основном ограничены целочисленными решениями. Если вам нужен квадратный корень из X, самое близкое, что вы можете получить, это наибольшее целое число, квадрат которого меньше или равен X. Например, для sqrt (50) вы получите 7, так как 8 * 8 будет больше, чем 50.

Итак, вот хитрость для этого: посчитайте, сколько нечетных чисел, начиная с 1, вы можете вычесть из X. Вы можете сделать это с помощью логики следующим образом: 8-битный регистр R1 содержит рабочее значение, 7-битный счетчик R2 содержит (большую часть) нечетное число, а 4-битный счетчик R3 содержит результат. При сбросе R1 загружается со значением X, R2 сбрасывается в ноль, а R3 сбрасывается в ноль. 8-разрядная схема вычитания подается на R1 для входа «A», а значение R2 в сочетании с LSB фиксируется на «1» (через подтягивание) для входа «B». Вычитатель выдает 8-разрядную разность AB и бит заимствования. На каждом такте, если бит заимствования сброшен, R1 загружается с выходом вычитателя, R2 увеличивается, а R3 увеличивается. Если бит заимствования установлен, R1 не загружается, а R2, R3 не увеличиваются, b / c результат теперь готов в R3.

АЛЬТЕРНАТИВЫ

Есть только 16 возможных выходных значений, поэтому ответом является четырехбитное число. По сути, у вас есть четыре однобитных функции из 8 входных битов. Теперь я не могу нарисовать 8-мерную карту Карно, но в принципе вы можете просто создать комбинаторную схему для каждого бита ответа. Возьмите выходы этих четырех комбинаторных схем вместе и интерпретируйте их как четырехбитный ответ. Вуаля. Нет часов, нет регистров, достаточно просто NAND и NOR.

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

unsigned char sqrt(unsigned char num)
{
    unsigned char op  = num;
    unsigned char res = 0;
    unsigned char one = 0x40;

    while (one > op)
        one >>= 2;

    while (one != 0)
    {
        if (op >= res + one)
        {
            op -= res + one;
            res = (res >> 1) + one;
        }
        else
        {
            res >>= 1;
        }

        one >>= 2;
    }
    return res;
}

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

$2^8$

    A =     a
     or     b;

    B =     a and     b
     or not b and     c
     or not b and     d;

    C =     a and     b and     c
     or     a and     b and     d
     or     a and not b and not c and not d
     or     a and not c and not d and     e
     or     a and not c and not d and     f
     or not a and     c and     d
     or not a and     c and     e
     or not a and     c and     f
     or not a and not b and not d and     e
     or not a and not b and not d and     f;

     D =     a and     b and     c and     e
     or     a and     b and     c and     f
     or     a and     c and     d
     or     a and not b and not c and not d
     or     a and not b and not d and     e and     f
     or     a and not b and not d and     e and     g
     or     a and not b and not d and     e and     h
     or     a and not c and not d and not e and not f
     or     b and     c and not d and not e and not f and     g
     or     b and     c and not d and not e and not f and     h
     or not a and     b and not c and     d and     e
     or not a and     b and not c and     d and     f
     or not a and     b and not c and     d and     g
     or not a and     b and not c and     d and     h
     or not a and     c and not d and not e and not f
     or not a and     d and     e and     f
     or not a and     d and     e and     g
     or not a and     d and     e and     h
     or not a and not b and     c and not e and not f and     g
     or not a and not b and     c and not e and not f and     h
     or not a and not b and not c and     e and     f
     or not b and     c and     d and     e
     or not b and     c and     d and     f
     or not b and not c and not d and not f and     g
     or not b and not c and not d and not f and     h;