2
\$\begingroup\$

I'm trying to make a 128-bit divider in Logisim using Logisim's built-in arithmetic library. How do I connect the dividers so that I can work with divisions of more than 32 bits?

What I have considered:

  1. Create the divider from logic gates (takes too long and would crash the simulation).
  2. Write my own divider library (I don't know Java or the Logisim source code that well and I'm still stuck with the original problem).
  3. Work with the dividers like I did the multipliers, but chain them in the reverse order (is that even plausible?).
  4. Write an application to generate the divider (the resulting circuit would crash the simulation).

I might be able to provide a screenshot of what I described for #3 with my multiplier if I need to clarify that point.

Edit: Here is what I've come up with so far based on the answer I got:

This circuit does not work!

\$\endgroup\$
4
  • 2
    \$\begingroup\$ You should read this article about division algorithms first: en.wikipedia.org/wiki/Division_algorithm Then think about how to implement such an algorithm for 128 bit operands in Logisim. But I don't believe using a library divider for 32 bit would help you. \$\endgroup\$
    – Uwe
    Commented Jan 10, 2017 at 10:39
  • \$\begingroup\$ It looks like I will need to forward the clock signal to the divider. \$\endgroup\$ Commented Jan 10, 2017 at 13:49
  • \$\begingroup\$ You could try to implement a clocked divider, calculating one bit at a time (= clock). \$\endgroup\$ Commented Aug 17, 2019 at 21:39
  • \$\begingroup\$ I've already come up with this solution and one that's similar. A [shift->subtract] operation per clock cycle or multiple [shift-subtract] operations per clock cycle. The number of these operations equals the bit width of the number with a counter to keep track of how many clock cycles are left. \$\endgroup\$ Commented Aug 29, 2019 at 17:42

1 Answer 1

1
\$\begingroup\$

When you want to build a 64 bit multiplier from 32 bit ones you can use the equation (a+b)*(c+d) = ac+bc+ad+bd You have four multiplications of 32 bit numbers for one 64 multiplication.

When you want to build a 64 bit divider from 32 bit ones the equation is (a+b)/(c+d) = a/(c+d) + b/(c+d) but this does not help much, you still have to divide 32 bits by 64 bits. You may try (a+b)/(c*d) = a/c/d + b/c/d but this is useful only if the divider may be split into two factors each smaller than 32 bits.

The properties of the division operation don't allow an expansion like that for multiplication.

\$\endgroup\$
3
  • \$\begingroup\$ I edited my question to include a circuit that I came up with based on your "a/c/d + b/c/d" answer. How do I hook up the remainers? \$\endgroup\$ Commented Jan 9, 2017 at 18:18
  • \$\begingroup\$ My "a/c/d + b/c/d" would not help you if the divider number is a prime number larger than 32 bits. Spliting the divider into c and d is not possible for prime numbers. You don't want a divider expansion that only works for some special numbers but not all possible numbers smaller than 128 bit. \$\endgroup\$
    – Uwe
    Commented Jan 10, 2017 at 10:14
  • \$\begingroup\$ A small example, we assume we have a divider for 4 bit numbers and want to build a 8 bit divider. We have to find a factorization of the divider number with two factors representable with 4 bits, but this is not possible for all prime numbers larger 15: 17, 19, 23, 29, 31, 37, 41, 43, 47, 53.. It is also not possible for all products with a factor being a prime larger than 15: 34, 38, 46, 58, 62, 74... and 51, 57, 69, 87... \$\endgroup\$
    – Uwe
    Commented Jan 10, 2017 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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