Obliczanie pierwiastka kwadratowego z 8-bitowej liczby binarnej

Szukałem sposobu na obliczenie pierwiastka kwadratowego z danej liczby 8-bitowej przy użyciu tylko kombinacji cyfrowej lub logiki sekwencyjnej. Czy to jest możliwe?

Jednym ze sposobów może być użycie tabeli przeglądowej, ponieważ w ogóle nie rozważam części ułamkowych (więc ), ale musi być lepszy sposób niż ten. Czy ktoś może mi to wskazać?$\sqrt{10} \simeq 3$

Tabele odnośników zostały wspomniane w komentarzach. Istnieją dwa podejścia.

Szybko
Utwórz tabelę o długości 256 bajtów, z każdą kolejną wartością pierwiastek kwadratowy z odpowiedniego indeksu. Jest to szybkie, ponieważ używasz argumentu jako indeksu, aby uzyskać bezpośredni dostęp do właściwej wartości. Wadą jest to, że potrzebuje długiej tabeli z dużą ilością zduplikowanych wartości.

Kompaktowy
Jak powiedziano, 8-bitowa liczba całkowita może mieć tylko wartości od 0 do 255, a odpowiednie pierwiastki kwadratowe mają wartości od 0 do 16 (zaokrąglone). Skonstruuj tablicę 16 pozycji (od zera) z n-tym wpisem maksymalną wartością argumentu, dla którego pierwiastek kwadratowy wynosi n. Tabela wyglądałaby następująco:

 0  
 2  
 6  
12  
20
etc.

Przechodzisz przez stół i zatrzymujesz się, gdy napotykasz wartość większą lub równą argumentowi. Przykład: pierwiastek kwadratowy z 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

Podczas gdy tabela szybkiego wyszukiwania ma ustalony czas wykonania (tylko jedno wyszukiwanie), tutaj czas wykonania jest dłuższy dla argumentów o wyższej wartości.

W przypadku obu metod, wybierając różne wartości dla tabeli, możesz wybrać pomiędzy zaokrągloną lub skróconą wartością pierwiastka kwadratowego.

Pracując w 8 bitach, jesteś zasadniczo ograniczony do rozwiązań całkowitych. Jeśli potrzebujesz pierwiastka kwadratowego z X, najbliższą możliwą wartością jest największa liczba całkowita, której kwadrat jest mniejszy lub równy X. Na przykład dla sqrt (50) dostaniesz 7, ponieważ 8 * 8 byłoby więcej niż 50

Oto sztuczka polegająca na tym: policz, ile liczb nieparzystych, zaczynając od 1, możesz odjąć od X. Możesz to zrobić za pomocą logiki: 8-bitowy rejestr R1 przechowuje wartość roboczą, 7-bitowy licznik R2 przechowuje (większość) liczbę nieparzystą, a 4-bitowy licznik R3 przechowuje wynik. Przy resecie R1 jest ładowany wartością X, R2 jest zerowane do zera, a R3 jest zerowane. 8-bitowy obwód odejmujący jest zasilany R1 dla wejścia „A”, a wartość R2 połączona z LSB ustalonym na „1” (poprzez podciąganie) dla wejścia „B”. Subtraktor wyprowadza 8-bitową różnicę AB i bit pożyczony. Przy każdym zegarze, jeśli bit pożyczony jest czysty, R1 jest ładowane wyjściem subtraktora, R2 jest zwiększane, a R3 jest zwiększane. Jeśli bit pożyczki jest ustawiony, R1 nie jest ładowany, a R2, R3 nie są zwiększane, b / c wynik jest teraz gotowy w R3.

ALTERNATYWNIE

Istnieje tylko 16 możliwych wartości wyjściowych, więc odpowiedź jest czterobitową liczbą. Zasadniczo masz cztery funkcje jednobitowe z 8 bitów wejściowych. Nie mogę teraz narysować 8-wymiarowej mapy Karnaugh, ale w zasadzie dla każdego fragmentu odpowiedzi można po prostu wymyślić kombinatoryczny obwód. Połącz wyjścia tych czterech obwodów kombinatorycznych i zinterpretuj je jako czterobitową odpowiedź. Voila Żadnych zegarów, żadnych rejestrów, wystarczy garść NAND i NOR.

Nie wiem, czy to jakaś pomoc, ale istnieje genialnie prosty sposób na obliczenie pierwiastka kwadratowego:

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;
}

Nie wiem wiele o tym, co można i czego nie można zrobić w logice sekwencyjnej, ale ponieważ ten algorytm kończy się w zaledwie 4 pętlach, możesz być w stanie zaimplementować go w 4 etapach.

$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;