Division | Logical Redstone #14

In this episode, I cover binary division, providing a full tutorial for a combinational and sequential design.

-------------------------

Want to get more involved in the logical redstone community?

0:00 Intro
1:00 Division on Paper
5:16 The Conditional Subtractor
8:16 Building a Conditional Subtractor
14:20 Building a Combinational Divider
20:14 Building a Sequential Divider
33:01 Dividing by zero?
33:43 Subscribe!

[MalinaBoy]

I used redstone as an additional material for explanation in my course work on discrete mathematics, and my teacher, an eighty-year-old doctor of physical and mathematical sciences, was delighted to say that he also wanted to try this

[spagta]

"The five knocking on the twos door and saying: ' *How many times can I fit inside you?* '"

[XDTheEmoticon]

1:16 “how many times can I fit inside of you”

-mattbatwings

[choonyongtan]

Division is very interesting, I was waiting for this after the multiplication video.

[deru]

I really love your tutorials, the tutorials are very clear and I learn a lot from them.
Please continue making them!

[Creepy-Wolf]

For the people that want fractions: for the combinational: Make it longer, more conditional subtractors, for the sequential: just make the shift register longer and the timer too so it pushes it up like 16 times (that makes it 16 bit)

[andrewporter]

There is a geometric way to look at division. I also would like to see you make a video combining subtraction and division into one, compact circuit as there's a better division algorithm you can use which can use multiplier circuitry as it as division is just modular multiplication.

Geometrically, the product of two numbers A and B is C. The simplest shape that represents this is the rectangle of width A and height B. Multiplication asks what the area of said rectangle is given width A and height B; Division asks what the length of one side is given the area and one side length.

You can compute rational approximations of arbitrary reciprocals in binary using modular left shifts, aka `2x (mod y)` for some quotient x/y. This algorithm computes the Euclidean quotient with integer and fraction parts simultaneously using integer arithmetic (where the fraction part is the numerator of a fraction over y).

Suppose we wish to compute 1/3 to 64-bit precision, then a valid 64-bit approximation is 2**(-64) (2**64 / 3), or equivalently, 2**64 (2**(-64) / 3). For an arbitrary quotient x / y, we can exploit the latter fact to reduce x to the range [1, 2] and repeatedly multiply both integer and fraction parts by 2 with the fraction part modulo y. This is a simple O(n) shift and add operation; however, with modular exponentiation by squaring, it instead becomes an O(M(n) log n) algorithm.

How does this algorithm look in action for 1/3?
Legend: integer_part + fraction_part_numerator
1. (0 + 1/3) * 2 = 0 + 2/3 [meaning we have 2/3 now]
2. (0 + 2/3) * 2 = 0 + 4/3 = 1 + 1/3 [4 (mod 3) is congruent to 1]
3. (1 + 1/3) * 2 = 2^1 + 2^1 / 3
4. (2^1 + 2^1 / 3) * 2 = 2^2 + 2^2 / 3 = 2^2 + (1 + 1/3) = 2^2 + 2^0 + 2^0 / 3
5. (2^2 + 2^0 + 2^0 / 3) * 2 = 2^3 + 2^1 + 2^1 / 3
...
N. floor(2^N / 3) + reduce(2^N | mod 3) [where the reduce function computes the equivalence class of 2^N with a codomain of [0, 3). One such valid formula for computing modular reduction x mod y is x - y floor(x/y). ]

Now of course you could just compute the reciprocal of y and divide that result by x to multiply x by y, but this is where it's faster to just make a long multiplier within a device whose mode of operation can be reconfigured and even repurposed for bulk addition where the final result has at most twice the number of bits as the size of a single input. This is what I meant when I said a single device that can compute subtracts and divides since you can do addition and multiplication using their respective inverse operations and vice versa.


If I find said algorithm/identity, I will edit this question. I'm sure it won't be too long from now; I just simply haven't thought about it yet for long enough.

Alternatively, you can trivialize all of this by generalizing double dabble to convert from one base to another while still encoded in binary, allowing addition, subtraction, multiplication, and division to all have similarly trivial costs. If you want to exploit native base two carries in hardware, encode each digit as the distance to the power of two which each digit is associated with, e.g. if base 3 requires two bits to encode a digit, then encode a digit d_i as d_i + (2**2 - 1 - 3), or more generally, for base k: 2**2 - 1 - k + d_i. So, for the sum of 22_3 + 11_3, we get 11 11_2 + 01 01_2 (this operand is not encoded as above) = 01 01 00_2 or 110_3 which is indeed correct.

Edit:
So I actually found a better O(n log n) algorithm for both mul and div, namely by converting to the base of y, so for example, if you want to compute either a product or quotient xy or x/y respectively, then you can convert to base y and then mul/div is a trivial digit shift. For arbitrary precision arithmetic, that can remain constant time by simply evaluating at that digit offset when converting to/from some other base, so it can be a symbolic representation.

As it turns out, you can convert from any one base into another in O(log n) base conversion steps with n proportional to the input size. I won't detail the whole algorithm here as it gets somewhat technical (if you know how, you can pretty easily figure it out yourself from what I put here).

Suppose we wish to compute the quotient x/3, then we must convert x to base 3. To do this in O(log n) steps, we successively convert to higher bases as a product of our native base, b, and our target base, 3, as some base (b**n * 3). We can trivially compute the greatest n as a solution to b**n * 3 <= x (simply solve for n here), and then the representation of x in base (b**n * 3) will be of the form 1:(x - b**n *3). From here, it is quite simple to see that this has an equivalent improper representation in base 3 as (b**n) plus some other digit. Conversion to a proper base 3 representation will only take O(log n) steps, but you need to be able to add in any base is the only catch using your native hardware.

[yourlocalprogramer]

01:14 he didnt think about what he said...

[martin]

What an amazing tutorial! I've been doing hardware design (FPGAs) for over two years now and I never saw such a good explanation for binary division!

[ben]

I love that you're teaching kids math through minecraft! And I love the way it gives people an explanation for why math works, not just telling people how to do it!

[raxyen]

Thank You for that video! You’ve got an enormous knowledge about that kind of stuff!

[greenwhisper]

Thanks Matt I needed to perform modulos and now with this its easy: just take the reminder and your modulo is the divisor.

[SpuNix-offr]

I was waiting for this!! Thank you so much bro!

[frostyusername]

another one from our boyyye Mattbatwings. sweet

[thecossackfromukraine]

I do a different looking division at school, but cool vid!

[turnrp]

I LOVE THIS VIDEO! Just rethink the knocking on the door part. Lmao 🤣

[fyrewire]

loved the video man, learning how to divide for my own computer

[zhabiboss]

I am sure, he is better then Mumbo Jumbo

[Luca-gbog]

It’s interesting to see how learned division in school. I’m from Germany and we have a different way of writing it down where the wasn’t any confusion of which to divide by wich. And this technique worked with fractions also, however I think your will work too but you just stopped because you want the remainder

[Player]

Yes another Vid, I was waiting for this for a while, but it didn't come, so obviously the day after I finish mine, you upload.