If i'm following your pseudocode correctly: one has no way of knowing which bit contains the most significant 1 in the divisor. Thus, one cannot just place the divisor in the correct position for comparison/subtraction. This is where the left shifting shift register comes in as described by immibis's steps 1-3. The other steps 4-6 are actually identical to your description.
Well, you could use a left-shifting register to align the number, before copying it into a right-shifting register. But that seems like it'd be bigger than a bidirectional register.
A bi-directional shift register? Hmm...that's an interesting challenge. Once such a device is created, a computer could be programmed to do long-division like this.
Another useful component (in general) would be a simple and fast circuit that could check "greater than" without having to use a subtractor.
If you had a redstone computer, it could already be programmed to do division. You probably mean a computer could be made to do long-division in hardware?
A simple test for "greater than" (pseudocode):
(where A(x) and B(x) are the x'th bit in numbers A and :cool.gif:
(where && is binary AND, ! is binary NOT and == is equal)
for each bit b, starting from the MSB:
if A(:cool.gif: && !B(:cool.gif:, set output to "A > B" and stop
if !A(:cool.gif: && B(:cool.gif:, set output to "A < B" and stop
otherwise, continue to the next bit.
set output to "A == B" and stop
(where A(x) and B(x) are the x'th bit in numbers A and :cool.gif:
(where && is binary AND, ! is binary NOT and == is equal)
for each bit b, starting from the MSB:
if A(:cool.gif: && !B(:cool.gif:, set output to "A > B" and stop
if !A(:cool.gif: && B(:cool.gif:, set output to "A < B" and stop
otherwise, continue to the next bit.
set output to "A == B" and stop
Hmm...so no way of doing it other than comparing the bits one by one? I think I might be able to do a time-sensitive implementation of that with repeaters.
Hey, I've got a problem which has been bugging me for a while, how to turn an 8 bit input into an output for three seven segment displays.
the largest number i need to display is 225 which is the output of my 4-bit multiplier (15x15)
can anyone help?
If you're looking to make something that will display "15x15=255" in decimal, then I'm afraid you're rather out of luck. Converting from Binary to Decimal is no trivial task; it will be virtually impossible to make a static circuit that can do the job without it being ridiculously huge. Unless you do all of your calculations in decimal from the get-go, I'm afraid you're going to have to make do with "FxF=E1".
You COULD however try using your "division" circuit to make the conversion from Binary to decimal though. Unfortunatley it still can't be done in just one pass.
Hans Lemurson's Thread of Links:http://www.minecraftforum.net/topic/371610-hans-lemursons-thread-of-links/
Look here to find links to my inventions, creations, and my Youtube channel featuring Amazing Creations of Mine (Redstone engineering FTW!!!) and charming Music-Videos about clones. I also made "Minecraft in Minecraft" (2D platformer/building game). I'm currently trying to make a computer.
Hmm, if I were to multiplex a binary output (12 bit) into a pulse signal, and attach it to a decade counter...
That would do nothing, right?
I mean unless I manage to make something like a 256 pulse generator on one input that's not going to work.
However.
Using multiple decade counters and probably some fewer pulse generators in place of mux, it could be possible to easily convert from binary to decimal.
For example the eighth place signal, 256 (on/off) could be attached to three pulse generators, a double pulse, a quintuple pulse, and a sextuple pulse. The respective pulses from each tens place would go to respective decade counters.
Honestly there are only even digits in the ones place of the binary place values, (and also one) so one would only need to build not as many pulse generators.
I wouldn't risk trying to make the design using only 9, however; and gates and timing with that probably won't work, at least to my understanding. (Haven't really thought it out though)
Pulse Generator Digits needed using this theory to 16bit:
It is very big and three of the gates aren't needed, and of course there are better ways to divide, but it essentially works on the principal of right shifting.
In the case of the picture, 8 goes in and gets shifted twice to the right to make 2. The dividing factor is the A input into the full adder while one bit of the number to be divided is the B input. The carry out is that one bit shifted to the right.
oh and it also does decimal places (0.25, 0.5 and 0.75) out of the final carry out on each row.
hope you find a use for the decoder, I made a very simple and compact 3 bit decoder which takes about 10x10x5 blocks and more than half of that is the bus.
That sounds like it can only divide by powers of two...
Hans Lemurson's Thread of Links:http://www.minecraftforum.net/topic/371610-hans-lemursons-thread-of-links/
Look here to find links to my inventions, creations, and my Youtube channel featuring Amazing Creations of Mine (Redstone engineering FTW!!!) and charming Music-Videos about clones. I also made "Minecraft in Minecraft" (2D platformer/building game). I'm currently trying to make a computer.
No apologies needed, my note there is a bit lazy of me. The clock gets attached to the label C. Where label C is is a pulse generator, the circuit of which has been separated from the main bulk of the device by 1 block. This is where some adjustment must be made to the clock's pulse width.
also have any of you come across this decoder which I think is unique to my own design?
it decodes 2 bit decimal to binary in one unit:
00 = 0
01 = 1
10 = 2
11 = 3
I like this decoder; it is very compact. However, it has a flaw:
It is only so compact because it skimps on the fourth output line. A normal 2-bit decoder has four output lines, one of which is always lit up (even 00 results in one output being lit up).
This is because you generally want a specific target mechanism to activate based on the result of your decoding. I.e. you have four registers, and a 2-bit memory address. One register is always active. In fact, there can be no such thing as a state where there is no register active, because your computation result would evaporate into thin air instead of being stored.
So in the case of your design, you'd need an additional three-way NOT gate behind the outputs that generates a high fourth signal if (and only if) all three outputs are low. But because you also want to use the three outputs on their own as well, you need to branch them, which requires dirt bridges.
And when you're done building that, it'll consume more space than a more traditional 2bit decoder with four native outputs.
The Meaning of Life, the Universe, and Everything.
Join Date:
5/4/2011
Posts:
237
Member Details
Very nice, Simnik :biggrin.gif:
Another, totally different question though:
I have a circuit that adjusts one of its inputs based on one of the outputs. This of course will result in special cases where the circuit updates itself, and by that update, invalidates the update just made, thus reverting (and later re-triggering) it. An endless loop.
Are there tricks I can use to help guide such a circuit into a state of stability?
You could use redstone repeaters to delay the input to during the execution so it doesn't interfere, or you could use a monostable circuit to limit the rate at which the circuit responds to inputs, thereby excluding the changes it itself creates.
I have a circuit that adjusts one of its inputs based on one of the outputs. This of course will result in special cases where the circuit updates itself, and by that update, invalidates the update just made, thus reverting (and later re-triggering) it. An endless loop.
Are there tricks I can use to help guide such a circuit into a state of stability?
Try using an AND gate to control when the output feeds back into the input. A zero in the AND gate will hold the circuit steady, and flashing a 1 will let it go through 1 update cycle.
Output AND Control --> Input
Rollback Post to RevisionRollBack
Hans Lemurson's Thread of Links:http://www.minecraftforum.net/topic/371610-hans-lemursons-thread-of-links/
Look here to find links to my inventions, creations, and my Youtube channel featuring Amazing Creations of Mine (Redstone engineering FTW!!!) and charming Music-Videos about clones. I also made "Minecraft in Minecraft" (2D platformer/building game). I'm currently trying to make a computer.
The Meaning of Life, the Universe, and Everything.
Join Date:
5/4/2011
Posts:
237
Member Details
Hmmm... the AND gate is easier to build, for now. If you want, you can now toy with my latest modification to Simnik's adder-subtracter design. As usual, my goal was "input generic binary with sign flag, output generic binary with sign flag, invest as little logic as possible". And this time, it worked fully and completely!
...Unfortunately the circuit tends to fall into an infinite feedback loop now and then. That's what my previous question was about. :tongue.gif:
Notes:
'T' switch, "Toggle feedback loop": Must be 1 for normal operation. However, if the circuit oscillates, set to 0 for a bit to let it calm down.
'M' switch, "set computation Mode": 0 = subtraction, 1 = addition
'F' output, "sign/buffer Flag": In subtract mode, designates presence or absence of a minus sign. In addition mode, it's a buffer overflow (9nth digit).
Enjoy, if anyone still cares at this point :biggrin.gif:
If there is a minus, is F 1 or 0? And other question: why is it always on if I subtract? 14-7=7 and F is 1, reversed, 7-14=-7 and F is 1. Or is it me being dumb?
F is supposed to light up in only one case: When the result is negative. In other words:
0000 0111, F=0 ---> Result is 7
0000 0111, F=1 ---> Result is -7
The minor side effect of my construction is that you get the result "0 - 0 = -0", i.e. if no input is given and the mechanism is in subtraction mode, the flag is lit up. But since -0 == 0, mathematically there isn't anything wrong with it.
However you are completely right, the flag DOES light up in some cases when it shouldn't. I tested several use cases that worked fine, but it's like writing an essay: you can't spot your own typos...
I made a boo-boo with the carry-out. It shouldn't be connected to the F-line. It should only go into the feedback loop. I tweaked it and gave it a few quick tests, and it seems to behave properly now... but, as before, the only real way to test is to have someone else try to break it :biggrin.gif:
If you change the upper left corner to look like the screenshot, does it work for you?
Well, I made an if-else small schematic, that can be used to redirect output, so you can apply X functions (or gates) when the lever is on (true) and Y functions (or gates) when the lever is off (false)...
There are 2 levels on the schematic, the top one, that says "true or false" and the middle one, that combines (compares) the if/else so it redirects the input data (in the example, an loop/counter) to the correct place.
Schematic (only 1 level):
The Meaning of Life, the Universe, and Everything.
Join Date:
5/4/2011
Posts:
237
Member Details
I'm not sure what it is that you are trying to do, but it seems to me that you have one input, and want to be able to send that input one of two different ways depending on a lever.
In that case, why not simply employ two trusty AND gates and a NOT? There are several different possible shapes for AND gates, so you can pick the design that fits most comfortably in your existing mechanism.
Fun fact: this assembly works the other way too. Simply split up the input into two separate lines, and instead combine the two outputs into a single one. Voila, you have a mechanism that lets you choose which of two possible inputs you want on one single output. I am using that in my calculator, for example, to be able to send data from different sources (user input, memory, last result etc.) into the adders. Cramming 24 AND-gates in front of 8 full adders was an interesting project... :smile.gif:
The Meaning of Life, the Universe, and Everything.
Join Date:
5/4/2011
Posts:
237
Member Details
Not if you want to pass both low and high signals through. Using only a NOT gate will cause the second output to be always high when it is active. That might be enough for some applications, but for others you might want the option for the second output to be low even as the first is deactivated.
No way to use the output, really.
It's painful.
And any way of making the 7447 chip? The one with the ripple blank i/o?
YOUR BACK... you have missed so much...there are plans of us geting a redstone sub-forum...
Well, you could use a left-shifting register to align the number, before copying it into a right-shifting register. But that seems like it'd be bigger than a bidirectional register.
If you had a redstone computer, it could already be programmed to do division. You probably mean a computer could be made to do long-division in hardware?
A simple test for "greater than" (pseudocode):
Hmm...so no way of doing it other than comparing the bits one by one? I think I might be able to do a time-sensitive implementation of that with repeaters.
I invented a super-compact XOR gate which enabled me to create a multi-function logic gate (does AND, OR, NAND, and NOR) and a 2-wide full adder.
But I suppose you'll be all demanding and want pictures and schematics of them rather than just taking my word for it.
If you're looking to make something that will display "15x15=255" in decimal, then I'm afraid you're rather out of luck. Converting from Binary to Decimal is no trivial task; it will be virtually impossible to make a static circuit that can do the job without it being ridiculously huge. Unless you do all of your calculations in decimal from the get-go, I'm afraid you're going to have to make do with "FxF=E1".
You COULD however try using your "division" circuit to make the conversion from Binary to decimal though. Unfortunatley it still can't be done in just one pass.
Look here to find links to my inventions, creations, and my Youtube channel featuring Amazing Creations of Mine (Redstone engineering FTW!!!) and charming Music-Videos about clones. I also made "Minecraft in Minecraft" (2D platformer/building game). I'm currently trying to make a computer.
I'm sorry for being so noob, but where do i put in this clock that you are talking about?
That would do nothing, right?
I mean unless I manage to make something like a 256 pulse generator on one input that's not going to work.
However.
Using multiple decade counters and probably some fewer pulse generators in place of mux, it could be possible to easily convert from binary to decimal.
For example the eighth place signal, 256 (on/off) could be attached to three pulse generators, a double pulse, a quintuple pulse, and a sextuple pulse. The respective pulses from each tens place would go to respective decade counters.
Honestly there are only even digits in the ones place of the binary place values, (and also one) so one would only need to build not as many pulse generators.
I wouldn't risk trying to make the design using only 9, however; and gates and timing with that probably won't work, at least to my understanding. (Haven't really thought it out though)
Pulse Generator Digits needed using this theory to 16bit:
That sounds like it can only divide by powers of two...
That would explain the full-adders. A + A = ShiftLeft(A)
In different news, I just made a thread and video about my "Multi-Funtion Logic Gate": http://www.minecraftforum.net/topic/371707-hans-lemursons-multi-function-logic-gate/
And here's the video for your convenience:
Look here to find links to my inventions, creations, and my Youtube channel featuring Amazing Creations of Mine (Redstone engineering FTW!!!) and charming Music-Videos about clones. I also made "Minecraft in Minecraft" (2D platformer/building game). I'm currently trying to make a computer.
If you could, it would help.
I like this decoder; it is very compact. However, it has a flaw:
It is only so compact because it skimps on the fourth output line. A normal 2-bit decoder has four output lines, one of which is always lit up (even 00 results in one output being lit up).
This is because you generally want a specific target mechanism to activate based on the result of your decoding. I.e. you have four registers, and a 2-bit memory address. One register is always active. In fact, there can be no such thing as a state where there is no register active, because your computation result would evaporate into thin air instead of being stored.
So in the case of your design, you'd need an additional three-way NOT gate behind the outputs that generates a high fourth signal if (and only if) all three outputs are low. But because you also want to use the three outputs on their own as well, you need to branch them, which requires dirt bridges.
And when you're done building that, it'll consume more space than a more traditional 2bit decoder with four native outputs.
Do you think you can adapt your design?
Another, totally different question though:
I have a circuit that adjusts one of its inputs based on one of the outputs. This of course will result in special cases where the circuit updates itself, and by that update, invalidates the update just made, thus reverting (and later re-triggering) it. An endless loop.
Are there tricks I can use to help guide such a circuit into a state of stability?
Try using an AND gate to control when the output feeds back into the input. A zero in the AND gate will hold the circuit steady, and flashing a 1 will let it go through 1 update cycle.
Output AND Control --> Input
Look here to find links to my inventions, creations, and my Youtube channel featuring Amazing Creations of Mine (Redstone engineering FTW!!!) and charming Music-Videos about clones. I also made "Minecraft in Minecraft" (2D platformer/building game). I'm currently trying to make a computer.
...Unfortunately the circuit tends to fall into an infinite feedback loop now and then. That's what my previous question was about. :tongue.gif:
Schematic: download here
Notes:
'T' switch, "Toggle feedback loop": Must be 1 for normal operation. However, if the circuit oscillates, set to 0 for a bit to let it calm down.
'M' switch, "set computation Mode": 0 = subtraction, 1 = addition
'F' output, "sign/buffer Flag": In subtract mode, designates presence or absence of a minus sign. In addition mode, it's a buffer overflow (9nth digit).
Enjoy, if anyone still cares at this point :biggrin.gif:
F is supposed to light up in only one case: When the result is negative. In other words:
0000 0111, F=0 ---> Result is 7
0000 0111, F=1 ---> Result is -7
The minor side effect of my construction is that you get the result "0 - 0 = -0", i.e. if no input is given and the mechanism is in subtraction mode, the flag is lit up. But since -0 == 0, mathematically there isn't anything wrong with it.
However you are completely right, the flag DOES light up in some cases when it shouldn't. I tested several use cases that worked fine, but it's like writing an essay: you can't spot your own typos...
I made a boo-boo with the carry-out. It shouldn't be connected to the F-line. It should only go into the feedback loop. I tweaked it and gave it a few quick tests, and it seems to behave properly now... but, as before, the only real way to test is to have someone else try to break it :biggrin.gif:
If you change the upper left corner to look like the screenshot, does it work for you?
There are 2 levels on the schematic, the top one, that says "true or false" and the middle one, that combines (compares) the if/else so it redirects the input data (in the example, an loop/counter) to the correct place.
Schematic (only 1 level):
In that case, why not simply employ two trusty AND gates and a NOT? There are several different possible shapes for AND gates, so you can pick the design that fits most comfortably in your existing mechanism.
Fun fact: this assembly works the other way too. Simply split up the input into two separate lines, and instead combine the two outputs into a single one. Voila, you have a mechanism that lets you choose which of two possible inputs you want on one single output. I am using that in my calculator, for example, to be able to send data from different sources (user input, memory, last result etc.) into the adders. Cramming 24 AND-gates in front of 8 full adders was an interesting project... :smile.gif: