Division | Logical Redstone #14
ฝัง
- เผยแพร่เมื่อ 13 มิ.ย. 2024
- !!! Check out the NEW AND IMPROVED logical redstone series here! • Logical Redstone Reloaded !!!
In this episode, I cover binary division, providing a full tutorial for a combinational and sequential design.
Patreon: / mattbatwings
Discord: / discord
My socials: linktr.ee/mattbatwings
My texture pack: modrinth.com/resourcepack/mat...
World Download: (JAVA 1.17.1) www.planetminecraft.com/proje...
-------------------------
Want to get more involved in the logical redstone community?
Learn Logical Redstone! • Logical Redstone Reloaded
Open Redstone Engineers (ORE): openredstone.org/
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!
Music: • the background MUSIC f... - เกม
Check out the NEW AND IMPROVED logical redstone series here! th-cam.com/play/PL5LiOvrbVo8keeEWRZVaHfprU4zQTCsV4.html
The highest level of understanding is to be able to teach.
second reply
How does binary division and multiplication really work? (In both Two's complement and floating point numbers) I just can't seem to find an answer.
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
That is so wholesome that my heart just melted.
Wow
Did he though?
"The five knocking on the twos door and saying: ' *How many times can I fit inside you?* '"
😂
sus
i watched the video too
💯💯💀
1:16 “how many times can I fit inside of you”
-mattbatwings
Division is very interesting, I was waiting for this after the multiplication video.
1:15 geez man buy me a drink first
01:14 he didnt think about what he said...
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.
It is likely that there is some identity for x / (1/y) that I'm missing which might be able to work with this algorithm without computing 1/y , e.g. xy = (x + y) / (1/x + 1/y) (for real x and real y), or x / (a / y) = (x/a) (1/y), which can be reconfigured to multiply or divide. If you already have some fraction, nevertheless the algorithm will still work in principle on the same hardware, but now with x mod y for y less than 1 which can be computed using a slightly modified identity of the modular reduction function so that only the result needs a bit shift after shifting either x or y before computing the difference. For some modular identities, you can check the Wikipedia page, as well as Dr. Jones' tutorial on modulus without division here: homepage.divms.uiowa.edu/~jones/bcd/mod.shtml
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
You want to talk about modular reciprocals? The result looks nothing like traditional division, but then again, 2's complement looks almost nothing like traditional negative numbers, so is that really a problem?
The easiest way to find modular reciprocals is actually just Newton's method: 0 = 1/x - a; xₙ₊₁ = xₙ - (1/x - a)/(-1/x²) = xₙ + xₙ²(1/xₙ - a) = xₙ(1 + xₙ(1 - axₙ)/xₙ) = xₙ(2 - axₙ). The real magic? When dealing with modular arithmetic, Newton's method doesn't approach the answer slowly; it approaches it _fast!_ More specifically, every iteration _doubles the number of accurate bits!_
Now we just need a good first guess... Well, I can't prove it myself, but here's one: 3a xor 2, or rather, add a to a shifted copy of itself and then invert bit 1. How accurate is this guess? _5 bits!_ (No, I can't explain it.) That's only _one_ iteration for a result accurate to 8 bits! Add another multiplier to the output and you can now losslessly and reversibly divide by any odd 8-bit integer. Dividing by even integers requires shifting both inputs until the denominator is odd, which isn't very hard in its own right. This means that the full division is only lossless if the numerator is divisible by a larger power of 2 than the denominator.
Oh, and when the remainder of traditional division is 0, then the modular division matches it perfectly! (provided you do the right kind of shifting.)
I really love your tutorials, the tutorials are very clear and I learn a lot from them.
Please continue making them!
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!
I am sure, he is better then Mumbo Jumbo
loved the video man, learning how to divide for my own computer
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!
Thank You for that video! You’ve got an enormous knowledge about that kind of stuff!
I was waiting for this!! Thank you so much bro!
I LOVE THIS VIDEO! Just rethink the knocking on the door part. Lmao 🤣
Thanks Matt I needed to perform modulos and now with this its easy: just take the reminder and your modulo is the divisor.
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.
well timed I just stared leaning division, amazing love you're videos!!!!
another one from our boyyye Mattbatwings. sweet
Absolutely great Vid!!! Love it! perfectly explained. Now I can create a division circuit by my own without any help!
loving this series... I know I'm late lol. But it's as clear and smooth an explanation, as any I know of. I'm learning a lot of things, the why of the things I've known how to do for years.
Would love to see a chapter on flipflops of various kinds... the shift register to store the answer here was useful. There's a lot I still don't know...
Good work Keep em coming
eeee
Nice to see this! I just learned how to do binary division and I was wondering how you would actually implement it in hardware.
This machine is super awesome!
Oh wow I didn't know about the freeze command or stepping by certain amount of ticks. I used to suck at timing my circuits, maybe next time I redstone I can use this to get a bit better!
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
I am also from Germany and I was really confused until I saw your comment
@@Wasserkleber yeah same in France we use
a | b
|-----
|
|
I do a different looking division at school, but cool vid!
so clear & good ty
I have never clicked faster
Loved it.
LOVE IT! I'VE BUILDT EVERYTHING YOU COVERED CAN WE GET AN ALU SOON?
It is really clear
this helps a-lot
Therefore we've finally got an answer to the question 1/0, it's 255 !
1:15 ayo WHAT
This video taught me long division before school did
lol
i'm really curious to see if someone could find a way to work redstone computing in their resumé/interviewing for some computing jobs... it seems silly but if you think about it you do need a fairly deep understanding of computing to make minecraft computers, but the hard part would probably be trying not to look like a weirdo to your employer lol
Hi matt, can you please tell me what software you used to make your pfp? Thanks in advance :)
i stole it from google images and changed the hue
@@mattbatwings lol
@@mattbatwingsXD
Um Is this series continued or not? BTW I love this series I learned a lot thx :)
Could you do some form of binary search?
i.e. Try to subtract 8×5, then try to subtract 4×5, then 2×5, and then 1×5?
This seems like it would be much faster and would only require shifting bits left and right.
Is it possible to get a world download with everything made so far?
@@the_czech I meant a single world with all of the devices made in every Logical Redstone video thus far
so a decimal system divider could work by putting the decimal input into an encoder which encodes it into binary then put that into the input of the divider and then put the output back into a decoder to convert it to decimal?
Is there a way you could link to where you got the design for the combinational divider?
You use a 3x3 font for binary and 5 high 3 wide font for decimal/hex.
Do you have an build which can do division with fractions and not give out the rest?
After this tutorial I can say that I can make a minecraft calculator
I thought there would be a more efficient algorithm for division but apparently people still use the basic long division method. Is it because there really is no better algorithm or is it just because we're talking the basics? Thanks
i havent spent any time researching or designing a different alg because this way has sufficied for me, so i don’t know for sure, but i would assume there’s way better ways. i would suggest joining the ORE discord and asking them what division alg is the best
It depends on the amount of significance you want to have your answer.
Long division is perfect when you want to have a quick rough answer. It is also the most compact algorithm.
If you want an easy way to do it quicker, you should subtract numbers in parallel, but this is way less compact.
If you are dividing by small numbers, it is worth having a small look-up table, to have the reciprocate ready.
does the first divider support cases like a < b (the answer should be < 1)
How is this guy teaching division better than my teacher?😂
After you divided by zero the circuit sends ones, that's the proof why anything divided by zero is infinity :D
33:21 this is why the calculator keeps blowing up when attemping division.
I just got it that you can just shift left the remainder the amount of lower than 1 bits you have (if you have 1/2, 1/4 and 1/8 bits, you shift 3 times if you have 1/2 and 1/4 bits you shift 2 times, etc.), and then divide it by the dividant, it will give off the 1/2, 1/4, 1/8 and 1/16 in order (0100 = .25; 1000 = .5, etc.), and the remainder is what isn't possible to divide with such little amount of bits (trying to divide 2 by 5 would give result 0110 remainder 1)
yay
For anyone wondering, yes it is basically modulo
I have waited more than 3 months for this vid
no matter what i put into the sequential divider I built, I always only get 7 as the answer with 0 remainder. Does anyone know what might cause this?
Next:Squareroot
1:15 ayo🗿
division :o first hehe
Can you make it for the bedrock version?
Hey man, challenge for you: build a Redstone version of the chip featured in Veritasium's new video lol
You mean analog = signal strenght?
Chad: Build a NOR Gate to check if B is 0. As simple as that in order to blow the entire thing up. 😅
Me: Builds a detection circuit which detects for 0 and then just displays "Error" on screen.
I'm like a chad and not like a chad at the same time
how to convert the remainder into decimal format?
if I want to make the combinational into an 8 bit, do I need 16 bit adders?
yeah, im working on one rn, 16 bit CCA adders are a bit complex, you get 2 and the top highest comparator that has the 2 slab towers running into it, the block its going into you put a torch / block / redstone then you put 2 blocks by that redstone dust 1 block 3 blocks above the comparator and on the opposite end, you put another block / on the block above the comparator you put a torch that feeds into the carry in, and the other torch goes into the bottom of the top XOR gate at the end
really complex in text but also really simple once you make it
รอตั้งนาน
I've done some digging on continuing the conditional subtraction by adding a redix point (decimal point) and carrying on through another subtractor, and another. (And I practiced it on paper ... 3.66666 etc is 11.101010101 etc.. but I can't work out where to stop or how to round. After just 5 digits after the point. .10101... Its 3.65625 which just isn't accurate.
Just thinking.. couldn't you (hypothetically) run the sequential divider for longer and have a bigger serial shift register to continue with the .5 .25 .125 bits as many bits as you would like?
Might take some time to calculate, and create a Binary to BCD decoder for all those fraction digits... But on the plus side, I've learnt how to do a serial bus from a shift register. 😎
@@coastermad13 The easiest way to get accurate decimals is to multiply the dividend by for example 100 before dividing, this way you get two decimal accuracy.
Hello, is there way to make both designs 16 bit?
expand them vertically, im fairly sure everything in this series can be expanded like this
Helpppp😢😢😢😢😢
Here's my problems to this build
I exactly almost copy all the step only the colour i didn't copy but the answer doesn't match up, sometimes it resulted to 6 lamp lit and the lit doesn't lit 1 but 2 every tick so when the answer is 1 it lit 2
Also the remainder doesn't work, instead it show the exact number of the green num(left side i forgot it)
when i do 25 ÷ 5 the answer is 5 which iis good but the remainder litt up the exact number just like the one on left side(25)
Additionally,after i tried the 25 ÷ 5 i tried to 25 ÷ 4 but the answer different.😢😢😢😢
If i download my Minecraft on Chrome/google what my Minecraft is? Is it bedrock or PE
(Im on mobile)
😢😢😢😢😢😢😢plsss help me😢😢😢😢😢😢😢
You should make a video of logicalredstone where you explain while making it so people could build this also dont use world edit
I am curious about the notation you used to show division in the first part of the video. Is that really the way it was told to you at school?. It’s weird to me because I was taught a convention where the divider was put on the left and the divisor on the right. Then the result was obtained below the divisor, not above the dividend, etc. So what country were you taught it like this, and which other countries use that same convention?
6:07 Who noticed "no nothing"
this operation isn't really called Division but Modulo
33:07 if a human divides something by zero, he gets infinity, all ones is just the highest number a computer can get, so thats kinda accurate
well, even dividing by zero makes sense since lim n->0 1/n = infinity
so you are saying that 1 / 0 = -1 in twos compliment
Ummm. This is not how we did division in our school. So I don't understand anything :(
Is there a way to make a machine that finds the HCF and LCM of two numbers? If yes could u please make a tutorial
yoo
For anyone wondering, any positive real number divided by 0 is ♾️, and negative real number divided by 0 is -♾️. 0 divided by 0 is any number between -♾️ and ♾️.
so ♾times 0 is any positive real number? if so, lets say ♾ times 0 = 1, and ♾ times 0 = 2, so 1 = 2?
@@7MinutozRapsLetras When I say, "any real positive/negative number, I essentially mean positive/negative 'null'". "Null" is a valueless value like infinity, that lies between 0 and infinity. Otherwise, your logic checks out, and we end up with the true and false statement of 1 = 2.
@@johnmillerpere_grin6371 oh ok
1st
I can't watch it now since I'm in school
Legends noticed that at 6:11 there was something wrong…
Audio broken? Also first
No wait mine was broken
First
My school told me not to put 0 on the leftmost part of the quotient.
FiRSt, actually 9th but who’s counting 🤷♀️
What about 0/ any number
it's zero
lol, three firsts. thats a little wack. I’m 4th ig lol.
im 41st
out of context 1:16
make cubic root
how is 1011-111 = 100
1011 = 11 in binary and 111 = 7 in binary and 100 = 4 in binary. So 11 - 7 = 4
12:54 technically, the carry out is not the normal sign bit, however it will always be the inverse of the sign, which is why it works!
The sign bit is the top/leftmost bit, and is 1 when negative.
If the result is positive, let’s say in 4 - 1, or:
00000100 + 11111111
You get the following
Result: 00000011 (3)
Carry out: 1
The carry out (1) is the opposite of the sign bit (0), because the way we do subtraction is by adding a number so big that it rolls over.
When the answer is negative, for example 2 - 3, or:
00000010 + 11111101
You get
Result: 11111111 (-1)
Carry out: 0
The number is still negative, and didn’t roll over to the carry.
Therefor, the carry will always be the opposite of the sign bit of the result, and we can use it as the sign bit just simply by inverting it :)
1:01 American thinks everyone in the world writes this the same way
Other than that great video, good job
Hoi dude
hello dude
Maf
so 1/0 = 11111111.... -> infinity
any number / 0 is infinite
unless its negative
Why did the Thumbnail chamge
1:13 Im sorry, but that is just an objectively worse way of thinking about it.
xD true
You kept the pretty version of the CCA-Adder from us for 5 whole episodes! AHH!!!
I wonder if I could modify some of the other designes as well... just for the sake of looking sleek. (⌐▨_▨)