14
\$\begingroup\$

I was looking for a way to calculate the square root of a given 8-bit number using only digital combination or sequential logic. Is that possible?

One way may be to just use a look up table since I'm not considering fractional parts at all (so \$ \sqrt{10} \simeq 3\$) but there has to be a better way than this. Can someone point me to that?

\$\endgroup\$
  • 4
    \$\begingroup\$ I would use a simple lookup table with ranges. Min number and max for each output and you just check. \$\endgroup\$ – Kortuk Apr 4 '12 at 21:43
  • 6
    \$\begingroup\$ A lookup seems pretty simple. After all, there are only 16 possible answers for the square root of a 8 bit number. \$\endgroup\$ – Olin Lathrop Apr 4 '12 at 21:46
  • 3
    \$\begingroup\$ hmm.. the only answers are 0000 to 1111; only inputs 64 or greater will have the topmost bit set in the answer, so that's just an OR of the top two bits of the input. Now you only have three functions of 8 bits to reduce .. \$\endgroup\$ – JustJeff Apr 5 '12 at 2:29
9
\$\begingroup\$

Lookup tables have been mentioned in comments. There are two approaches.

Fast
Create a 256 bytes long table, with every next value the square root of the corresponding index. This is fast since you use the argument as index to access the right value directly. Drawback is that it needs a long table, with lots of duplicate values.

Compact
As said, an 8-bit integer can only have values 0 through 255, and the corresponding square roots are 0 through 16 (rounded). Construct a 16 entry table (zero-based) with the n-th entry the maximum value for the argument for which the square root is n. Table would look like this:

 0  
 2  
 6  
12  
20
etc.

You walk through the table and stop when you encounter a value greater than or equal to your argument. Example: square root of 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

While the fast lookup table has a fixed execution time (just one lookup), here the execution time is longer for higher value arguments.

For both methods goes that, by choosing different values for the table, you can select between a rounded or a truncated value for the square root.

\$\endgroup\$
  • 2
    \$\begingroup\$ If you turn that table upside down you'll need less iterations on average \$\endgroup\$ – Federico Russo Apr 5 '12 at 12:05
  • \$\begingroup\$ A binary search on the shorter table can speed up the algoritm on average. You start half way through the lookup table (position 8) then you decide if the value found is too high or too low and you go either 4 places up or 4 down. Repeat until done. \$\endgroup\$ – jippie Sep 19 '13 at 5:49
7
\$\begingroup\$

Working in 8 bits, you're basically constrained to integer solutions. If you need the square root of X, the closest you can get is the largest integer whose square is less than or equal to X. For example, for sqrt(50) you'd get 7, since 8*8 would be more than 50.

So here's a trick for doing that: count how many odd numbers, starting with 1, you can subtract from X. You could do it with logic like so: an 8-bit register R1 holds the working value, a 7-bit counter R2 holds (most of) the odd number, and a 4-bit counter R3 holds the result. At reset, R1 is loaded with the value of X, R2 is cleared to zero, and R3 is cleared to zero. An 8-bit subtractor circuit is fed R1 for the 'A' input, and the value of R2 combined with an LSB fixed at '1' (via pull-up) for the 'B' input. The subtractor outputs an 8-bit difference A-B and a borrow bit. At each clock, if the borrow bit is clear, R1 is loaded with the subtractor output, R2 is incremented, and R3 is incremented. If the borrow bit is set, R1 is not loaded and R2, R3 are not incremented, b/c the result is now ready in R3.

ALTERNATIVELY

There are only 16 possible output values, so the answer is a four bit number. Essentially, you have four single-bit functions of the 8 input bits. Now, I can't draw an 8-dimensional Karnaugh map, but in principle you could just come up with a combinatorial circuit for each bit of the answer. Take the outputs of those four combinatorial circuits together and interpret them as the four bit answer. Voila. No clocks, no registers, just a bunch of NAND and NOR would suffice.

\$\endgroup\$
  • \$\begingroup\$ I've been mulling this all night. The 8's bit in the output is clearly a function of the two most significant input bits. Similarly, I think the 4's bit in the output is likely a function of only the top 4 input bits: 00x1, 001x, 1xx1, and 11x1 seem to set it. Will verify this later. \$\endgroup\$ – JustJeff Apr 5 '12 at 10:42
  • 1
    \$\begingroup\$ If you're doing this in an FPGA, you could just throw it in to a big case statement and let the synthesis tool do all the work. On the one hand it's kind of like doing a big look-up table in distributed RAM (used as ROM); on the other hand the tool should find optimizations like you mention in your comment. \$\endgroup\$ – The Photon Apr 5 '12 at 15:40
5
\$\begingroup\$

I don't know if this is any help, but there's an ingeniously simple way to calculate a square root:

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

I don't know much about what can and can't be done in sequential logic, but since this algorithm finishes in just 4 loops, you might be able to implement it in 4 stages.

\$\endgroup\$
4
\$\begingroup\$

I ran the truth tables for the integer square root from 0-255 through a Quine-McCluskey logic minimizer. The integer square root can be done with just combinatorial logic, but even for such a relatively small input size of \$2^8\$ possible values, the answer isn't for the faint of heart. The following is ordered from MSB A to LSB D of the output, in terms of abcdefgh as inputs, MSB to LSB:

    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;
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, what software does that? Does it work for arbitrarily large dimensions? How would you derive the minimal number of gates to actually build it from those SOP forms? It looks like at this point a cpld or better would definitely be the most practical way to build it. \$\endgroup\$ – captncraig Apr 6 '12 at 5:33
  • \$\begingroup\$ @CMP Sorry for the delay in my reply. I used the program available here: home.roadrunner.com/~ssolver which can accept truth tables - I used a simple Python script to generate a truth table for each of the integer square root digits. Those SOPs above actually are in their minimal form, to the limits of ability of the algorithms the program uses to minimize them. \$\endgroup\$ – Bitrex Apr 7 '12 at 21:25
  • 1
    \$\begingroup\$ @CMP As you say, it would be crazy to implement the integer square root this way, as one could either use a lookup table, or code up one of the algorithms for the integer square root and let your HDL language of choice synthesize it. \$\endgroup\$ – Bitrex Apr 7 '12 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.