Ok, so I've been looking around at how to do multiplication here, but up until this point, most of the circuits I've seen have been either bulky, complex, or both. They focus on either "peasant" multiplication, or a series of adders chained together. I was looking for something a bit simpler, and after talking it over with an electrical engineer (I got lucky, my dad is one), I wanted to try a shift/add multiplier. And I haven't tested its full capabilities yet, but I got it working on the first try, which says something about its simplicity.
First off, technical definition, according to Wikipedia:
Shift and add
Most computers use a "shift and add" algorithm for multiplying small integers. Both base 2 long multiplication and base 2 peasant multiplication reduce to this same algorithm.
In base 2, multiplying by the single digit of the multiplier reduces to a simple series of logical AND operations. Each partial product is added to a running sum as soon as each partial product is computed. Most currently available microprocessors implement this or other similar algorithms (such as Booth encoding) for various integer and floating-point sizes in hardware multipliers or in microcode.
On currently available processors, a bit-wise shift instruction is faster than a multiply instruction and can be used to multiply (shift left) and divide (shift right) by powers of two. Multiplication by a constant and division by a constant can be implemented using a sequence of shifts and adds or subtracts. For example, there are several ways to multiply by 10 using only bit-shift and addition.
((x << 2) + x) << 1 # Here x*10 => x*[(2^2+1)*2]
(x << 3) + (x << 1) # Here x*10 => x*[(2^3+2)]
In some cases such sequences of shifts and adds or subtracts will outperform hardware multipliers and especially dividers. A division by a number of the form 2n or often can be converted to such a short sequence.
These types of sequences have to always be used for computers that do not have a "multiply" instruction,[5] and can also be used by extension to floating point numbers if one replaces the shifts with computation of 2*x as x+x, as these are logically equivalent.
A bit complex, but what it comes down to is you plug an adder into a shift register, and then shift the data over, with each shift giving you an (exponentially) higher output. It's more limited on possible outputs, but this could be changed by some kind of hybrid mix in with existing multiplication solution. I haven't done the logic on that bit yet, but that's the next step I'm going to try and work on.
Example:
1st shift (into the system) = Input x 1
2nd = Input x 2
3rd = Input x 4
4th = Input x 8
...and so on, I think you get the idea.
For my proof-of-concept, I decided to use a 3 bit adder, into a 6 bit shift register. Credits for the shift register design go to nikobroo, who put it up on Youtube, where I found it, and the adder design is from the Minecraft Wiki Advanced Redstone Circuits page. I'm using a pulse limiter to preclude any possibility of the input overloading the circuit (may not be necessary, once again, I haven't done the math yet). A couple downsides are that the current design requires one shift to place the actual data INTO the shift register, a toggle for each and every shift you want, and having to manually reset the circuit by toggling the data out through the end of the shift register.
One thought that I just had is that this could have more possible outputs if you use 2 or more sets of inputs from the adder.
Hope this makes sense. Any thoughts?
And sorry for the links and the pictures not being embedded, the board won't let me use the [img] tags for some reason.
If I've helped in any way, or made some sort of constructive comment, there's a little green plus sign in the bottom right corner of the post. Click it to let me know!
Ok, so I've been looking around at how to do multiplication here, but up until this point, most of the circuits I've seen have been either bulky, complex, or both. They focus on either "peasant" multiplication, or a series of adders chained together. I was looking for something a bit simpler, and after talking it over with an electrical engineer (I got lucky, my dad is one), I wanted to try a shift/add multiplier. And I haven't tested its full capabilities yet, but I got it working on the first try, which says something about its simplicity.
First off, technical definition, according to Wikipedia:
A bit complex, but what it comes down to is you plug an adder into a shift register, and then shift the data over, with each shift giving you an (exponentially) higher output. It's more limited on possible outputs, but this could be changed by some kind of hybrid mix in with existing multiplication solution. I haven't done the logic on that bit yet, but that's the next step I'm going to try and work on.
Example:
1st shift (into the system) = Input x 1
2nd = Input x 2
3rd = Input x 4
4th = Input x 8
...and so on, I think you get the idea.
For my proof-of-concept, I decided to use a 3 bit adder, into a 6 bit shift register. Credits for the shift register design go to nikobroo, who put it up on Youtube, where I found it, and the adder design is from the Minecraft Wiki Advanced Redstone Circuits page. I'm using a pulse limiter to preclude any possibility of the input overloading the circuit (may not be necessary, once again, I haven't done the math yet). A couple downsides are that the current design requires one shift to place the actual data INTO the shift register, a toggle for each and every shift you want, and having to manually reset the circuit by toggling the data out through the end of the shift register.
One thought that I just had is that this could have more possible outputs if you use 2 or more sets of inputs from the adder.
Hope this makes sense. Any thoughts?
And sorry for the links and the pictures not being embedded, the board won't let me use the [img] tags for some reason.
Your idea is definably worthwhile to experiment on, I like your way of thinking. However your shift register looks like nikobroo 's which is not a bad thing because if you came up with that yourself then you have the right idea of how a shift register works.
Here is my simpe Paint application in Minecraft.
Above is my old 2011 project that I liked, I don't play that much minecraft anymore but I occasionally help out on the Redstone forum. Hope my answers can be of help, let me know if I am unclear, and a +REP would be nice for me.
Your idea is definably worthwhile to experiment on, I like your way of thinking. However your shift register looks like nikobroo 's which is not a bad thing because if you came up with that yourself then you have the right idea of how a shift register works.
Yeah, that's where I got the shift register design in the first place, I guess I didn't mention it very clearly, but it's there. Credit is due where credit is due. I was looking for a nice simple one that I could chain together. For a PoC, it does the job rather nicely, I think, but obviously it can be optimized quite a bit. I'm gonna crunch some numbers and see if I can't put together what this particular 3 bit to 6 bit can put out. I'm gonna start with single set input though, double sets could get confusing, and quick.
EDIT: This 3 to 6 bit version has a total of 25 outputs, not removing any redundant outputs. I'll calculate them and run the numbers out for ya, and from there I should be able to pull some kind of equation to pull the outputs easily or show the number of possible different outputs.
Also, small brainwave. Don't know if it'll work, but you could change the multiplication values to a tradition 1, 2, 3, 4, 5, etc. by using a unary adder to decode the output. While that would make it less useful for higher numbers, as you'd have to expand somehow in order to reach greater numbers, it could make it a much more versatile design.
EDIT 2: Numbers for those who are interested:
The numbers 7, 6, 5, and 4 can each shift 3 times total, 3 and 2 can go up to 4 times, and 1 can make the shift 5 times. There are 8 redundant outputs, making it a total of 17 outputs for 25 combinations (not including zero).
The possible numbers are: 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 20, 24, 18, 32, 40, 48, and 56 with what I've already got up and running, not using the shift register's ability to take two full data sets. This could actually also be used as a slightly more complicated, but I think more compact way of adding up in higher bit ranges, by feeding the inputs into a shift register from a simple 3 or 4 bit adder, and using the shift register as the sum outputs.
EDIT 3: Just crunched a few more numbers, and if you took the 5 minutes necessary to make it a 4 bit adder into an 8 bit shift register, your total (redundancy check not done yet) number of outputs/input combinations jumps to a whopping 71 possibilities, and some of those numbers start getting quite high, and it starts filling in the lower register quite nicely too.
If I've helped in any way, or made some sort of constructive comment, there's a little green plus sign in the bottom right corner of the post. Click it to let me know!
Pics:
[IMG]http://i.imgur.com/Vo1w0.jpg[/IMG]
[IMG]http://i.imgur.com/xoLPM.jpg[/IMG]
[IMG]http://i.imgur.com/dRqs9.jpg[/IMG]
[IMG]http://i.imgur.com/xy1jA.jpg[/IMG]
First off, technical definition, according to Wikipedia:
A bit complex, but what it comes down to is you plug an adder into a shift register, and then shift the data over, with each shift giving you an (exponentially) higher output. It's more limited on possible outputs, but this could be changed by some kind of hybrid mix in with existing multiplication solution. I haven't done the logic on that bit yet, but that's the next step I'm going to try and work on.
Example:
1st shift (into the system) = Input x 1
2nd = Input x 2
3rd = Input x 4
4th = Input x 8
...and so on, I think you get the idea.
For my proof-of-concept, I decided to use a 3 bit adder, into a 6 bit shift register. Credits for the shift register design go to nikobroo, who put it up on Youtube, where I found it, and the adder design is from the Minecraft Wiki Advanced Redstone Circuits page. I'm using a pulse limiter to preclude any possibility of the input overloading the circuit (may not be necessary, once again, I haven't done the math yet). A couple downsides are that the current design requires one shift to place the actual data INTO the shift register, a toggle for each and every shift you want, and having to manually reset the circuit by toggling the data out through the end of the shift register.
One thought that I just had is that this could have more possible outputs if you use 2 or more sets of inputs from the adder.
Hope this makes sense. Any thoughts?
And sorry for the links and the pictures not being embedded, the board won't let me use the [img] tags for some reason.
EDIT: Pics problem fixed.
Your idea is definably worthwhile to experiment on, I like your way of thinking. However your shift register looks like nikobroo 's which is not a bad thing because if you came up with that yourself then you have the right idea of how a shift register works.
Above is my old 2011 project that I liked, I don't play that much minecraft anymore but I occasionally help out on the Redstone forum. Hope my answers can be of help, let me know if I am unclear, and a +REP would be nice for me.
Yeah, that's where I got the shift register design in the first place, I guess I didn't mention it very clearly, but it's there. Credit is due where credit is due. I was looking for a nice simple one that I could chain together. For a PoC, it does the job rather nicely, I think, but obviously it can be optimized quite a bit. I'm gonna crunch some numbers and see if I can't put together what this particular 3 bit to 6 bit can put out. I'm gonna start with single set input though, double sets could get confusing, and quick.
EDIT: This 3 to 6 bit version has a total of 25 outputs, not removing any redundant outputs. I'll calculate them and run the numbers out for ya, and from there I should be able to pull some kind of equation to pull the outputs easily or show the number of possible different outputs.
Also, small brainwave. Don't know if it'll work, but you could change the multiplication values to a tradition 1, 2, 3, 4, 5, etc. by using a unary adder to decode the output. While that would make it less useful for higher numbers, as you'd have to expand somehow in order to reach greater numbers, it could make it a much more versatile design.
EDIT 2: Numbers for those who are interested:
The numbers 7, 6, 5, and 4 can each shift 3 times total, 3 and 2 can go up to 4 times, and 1 can make the shift 5 times. There are 8 redundant outputs, making it a total of 17 outputs for 25 combinations (not including zero).
The possible numbers are: 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 20, 24, 18, 32, 40, 48, and 56 with what I've already got up and running, not using the shift register's ability to take two full data sets. This could actually also be used as a slightly more complicated, but I think more compact way of adding up in higher bit ranges, by feeding the inputs into a shift register from a simple 3 or 4 bit adder, and using the shift register as the sum outputs.
EDIT 3: Just crunched a few more numbers, and if you took the 5 minutes necessary to make it a 4 bit adder into an 8 bit shift register, your total (redundancy check not done yet) number of outputs/input combinations jumps to a whopping 71 possibilities, and some of those numbers start getting quite high, and it starts filling in the lower register quite nicely too.