I think ROM is easier than actually calculating it because there are tables for binary fractions
ROM's always an option, the only problem is how quickly its required size balloons with the number of digits. A 256 entry table for 8 bits of fractions is do-able, but is getting fairly big. 12 bits of fractions this way is completely unfeasible. Then again, I can't imagine making anything that would need to use 12 bits of fractions.
In other news, the algorithm I was attempting doesn't quite work. It looks like I'll have to go with Approach 1: Use separate algorithms to convert the digits for the bits to the Left and Right of the decimal point. My failure had been in applying both algorithms to both halves, which only works in special cases.
Can you download your knowledge and e-mail it to me?
Sadly the knowledge stays stuck in my head most of the time.
In algorithm news, I've made a bit of progress in working with fractional digits. I'm using a combination of the two methods I proposed in the previous post.
The critical thing to note is: the Reverse-Algorithm to undo the 1.6x error is not the inverse of the Bin->BCD function. The Bin-to-BCD function works on the left-end of digits as they get shifted left, but the Reverse-Algorithm works on the right-end of the digits as they get shifted right.
A Warning: I'm just in preliminary testing of this and so I'm not 100% sure that this will work for all cases. So far I've converted 3.C into 3.75 successfully, but I'm not sure how it will deal with larger numbers with more digits.
Using a fixed-point format for fractional numbers, you can't simply run the whole thing through a Bin->BCD conversion algorithm and get the right answer, since a 1-digit shift in Hex represents a 16x increase in value whereas only a 10x increase in decimal.
(I will use Hex and Dec for numbers in examples since they both use 4-bit digit groupings)
For example, if you started with D.6 (13.375) and naively ran it through a BinToBCD algorithm as D6 (214) and then put a decimal point in front of the first digit, you'd end up with 21.4. That is not the correct answer. It is in fact 1.6x the true answer of 13.375 (13.4 or 13.3 would be acceptable).
Proceeding in a naive fashion like this will give you a compounding 1.6x value error for ever fractional digit you use. Clearly a method must be used that takes this into account.
I have two ideas: - One is to split the number in half at the decimal point and do a "Forwards" version of the algorithm on the leftmost portion and a "Reverse" version on the right-half. However, this involves splitting apart the number which makes things a wee bit complicated.
- The other, which I think will be more effective requires some knowledge of what exactly the Bin-To-BCD algorithm is DOING. It can be described as a HEX-to-BCD algorithm, since every 4 shifting steps, it has modified the apparent value of the number to 1.6x what it was before. Consider the hex value of 100. 4 steps through the algorithm gives you 160, and 4 more steps gives you 256. However since the naive approach yielded a result that was already 1.6x the correct answer, you'll want to use the inverse of the algorithm to correct this.
I haven't thought this through fully, but I believe that if you run the number through the algorithm forwards, and then the inverse for the number of fractional digits it contains (since the naive first step creates the problem by shifting in a different base) then you should be able to get the right answer.
However, this would suggest that a number that is all fractional digits like the one you first brought up (0.555... in Hex) would require 0 runs through the algorithm (number of inverses = number of steps which is a cancellation) which obviously can't be right.
More thought on this will be required. It might even be a good idea for me to search the web for answers from people who have already figured this out rather than trying to re-invent the wheel.
Back on topic, does anyone have any ideas how I can fix the worst problem with my calculator - lag? The decoders for multiplication are massive - those four skyscraper-sized buildings in the back of the last photo - and with 2655 torches, lag horrifically for ~30s when passed a signal.
You did multiplication with lookup-tables? Does RedPower let you make read-only-memory that's more compact than normal, or did you do it the normal way (rows of torches over wire)?
A critique: I'll be prefectly honest that I thought a 4-bit Calculator made in RedPower would be a lot smaller than this. It's true that multiplication and division are no trivial task, but this is the only slightly smaller than the size (in terms of land area) I would expect from a vanilla 4-bit Calculator with the same features (if made by an RDF pro).
How did you organize the different functions in the Calculator? I see what looks like a bunch of Read-Only memory. Are all the answers stored in advance, or am I grossly misreading this? I would think that you would at least have done addition/subtraction with Logic (which you may have, I just can't see it well from the pictures given).
So this would be used to figure out how to write programs for your CPU without having to wait through ~4 seconds per instruction? A tool to make sure your code is good before you feed it to your (presumably flawless) machine?
I was playing some survival with my friends, and I went out on a mission to fetch wolves. Doggies for all!!! That was the plan anyways. However, once I got the wolves back and started a breeding program, I quickly realized that I didn't know how to give wolves to anybody else!
My friends could feed injured wolves, but couldn't get them to mate after they were at full health, and all new puppies were loyal to me. One friend tried a bone on a wolf which produced hearts but didn't seem to change who it followed.
To any players more knowledgeable about SMP than I: Is there any way to give wolves to your friends?
Let X be the horizontal position (left to right) and H be the vertical position (bottom to top).
Data is stored in horizontal rows designated by the Height value. $H = data for the row you are on, $(H+1) = data for row above you.
Horizontal position X is used to select which position in the row is being looked at. X and H by themselves are the current position values. $(H)[X] refers to the block-state of the current position.
Here is how the "Move Right" function works: If $(H)[X+1] == 0, X += 1
Translation: If the block to the right of your current position is empty, shift position to the right.
I stored the X and H values in "One hot" format, meaning that if you were on the bottom row and on the 3rd block from the left:
H = 10000000
X = 00100000
Changing position to be + or - the current was accomplished by just shifting the bits. To determine the value of a certain block, H is used to select a single register in the RAM, and then that value gets ANDed with X. If the result is a 1, then position-changes are blocked and the cursor/player remains in place. That is how collision detection works.
Oh, so you're ALHJ1997. I'm watching your videos on this and I'll have some critiques.
1.) You should probably use some better RAM. The RAM you're using is going to have problematic access-times. I should really get around to making a video about state-of-the-art RAM technologies. Making good RAM is a big impediment for many people's projects.
2.) I think you might have some trouble implementing the commands, since movement is based on conditional shifting, not an automatic change in position. It does a "hypthetical" shift to the new position, sees if that square is empty, and only saves the new position if it's empty. Using the shifter you have you'll be able to move around just fine, but I don't think you'll be able to implement collision-detection.
Have you thought about adding a pipeline if the speed buggers you? That's what I'm doing for mine: Simple 3 step pipeline and I should be able to achieve clock speeds of around 0.66Hz without instant wire.
Unfortunately, pipelining is a bit of a nightmare to program with since you have to keep track of a whole host of new data hazards. However, if you think you can handle it and get a goodly speed boost, then by all means do it!
I won't be making any architectural changes to this CPU for the simple reason that it's my FIRST CPU. I'm learning right now and I want to have a full understanding of all the difficulties faced with a "normal" CPU before I start fiddling around with anything fancy like pipelining or new mechanics like instant-wire.
I think everyone would like to see what it can do with instantwire The best bet would probably be to finish what you're doing normally, and then make a copy of it and start messing around with instantwire. For just BUSing, it shouldn't be that hard.
I'll have to make a decision about whether my next CPU will be instant-based or not. I think I might go for a hybrid system with instant-bussing but conventional logic.
I have a feeling that like me, you like to synchronise all your things. This is most likely the cause of your pistons dropping blocks. Do not synchronise inputs connected to a piston, for example, the insta carry piston in an adder. Something over 3 ticks is best, but if you know the piston isn't powered by a torch then 2 can suffice. The other way would be to put a 2 tick repeater infront of every piston. I prefer the former becuase in come circumstances you can distribute the asynchronicity around without slowing it down or strategically place it in routes that are slower anyway.
I haven't carefully studied what the exact causes of the various block-dropping errors are, but fortunately none of the "Instant-Carry" pistons have been affected. I've added insulating delays on all the control-bits and "pulse-hardened" some pistons where it wouldn't slow down the system and so far it SEEMS to be working ok, but again, further testing will be needed.
I don't really know what you mean by "synchronicity" since none of the gates are on a clock and I made no specific effort to keep delays uniform. What are you referring to, and how would this lead to additional block-dropping behaviors?
Also note that a Carry-In can often result in a chain-reaction where it produces a Cout that makes another adder produce a Cout and so on rippling down the line. That's how 0111 + 0001 = 1000
0
ROM's always an option, the only problem is how quickly its required size balloons with the number of digits. A 256 entry table for 8 bits of fractions is do-able, but is getting fairly big. 12 bits of fractions this way is completely unfeasible. Then again, I can't imagine making anything that would need to use 12 bits of fractions.
In other news, the algorithm I was attempting doesn't quite work. It looks like I'll have to go with Approach 1: Use separate algorithms to convert the digits for the bits to the Left and Right of the decimal point. My failure had been in applying both algorithms to both halves, which only works in special cases.
0
Sadly the knowledge stays stuck in my head most of the time.
In algorithm news, I've made a bit of progress in working with fractional digits. I'm using a combination of the two methods I proposed in the previous post.
The critical thing to note is: the Reverse-Algorithm to undo the 1.6x error is not the inverse of the Bin->BCD function. The Bin-to-BCD function works on the left-end of digits as they get shifted left, but the Reverse-Algorithm works on the right-end of the digits as they get shifted right.
A Warning: I'm just in preliminary testing of this and so I'm not 100% sure that this will work for all cases. So far I've converted 3.C into 3.75 successfully, but I'm not sure how it will deal with larger numbers with more digits.
0
Using a fixed-point format for fractional numbers, you can't simply run the whole thing through a Bin->BCD conversion algorithm and get the right answer, since a 1-digit shift in Hex represents a 16x increase in value whereas only a 10x increase in decimal.
(I will use Hex and Dec for numbers in examples since they both use 4-bit digit groupings)
For example, if you started with D.6 (13.375) and naively ran it through a BinToBCD algorithm as D6 (214) and then put a decimal point in front of the first digit, you'd end up with 21.4. That is not the correct answer. It is in fact 1.6x the true answer of 13.375 (13.4 or 13.3 would be acceptable).
Proceeding in a naive fashion like this will give you a compounding 1.6x value error for ever fractional digit you use. Clearly a method must be used that takes this into account.
I have two ideas:
- One is to split the number in half at the decimal point and do a "Forwards" version of the algorithm on the leftmost portion and a "Reverse" version on the right-half. However, this involves splitting apart the number which makes things a wee bit complicated.
- The other, which I think will be more effective requires some knowledge of what exactly the Bin-To-BCD algorithm is DOING. It can be described as a HEX-to-BCD algorithm, since every 4 shifting steps, it has modified the apparent value of the number to 1.6x what it was before. Consider the hex value of 100. 4 steps through the algorithm gives you 160, and 4 more steps gives you 256. However since the naive approach yielded a result that was already 1.6x the correct answer, you'll want to use the inverse of the algorithm to correct this.
I haven't thought this through fully, but I believe that if you run the number through the algorithm forwards, and then the inverse for the number of fractional digits it contains (since the naive first step creates the problem by shifting in a different base) then you should be able to get the right answer.
However, this would suggest that a number that is all fractional digits like the one you first brought up (0.555... in Hex) would require 0 runs through the algorithm (number of inverses = number of steps which is a cancellation) which obviously can't be right.
More thought on this will be required. It might even be a good idea for me to search the web for answers from people who have already figured this out rather than trying to re-invent the wheel.
0
To be RAM, you must have memory cells that share the same Input and Output lines.
0
You did multiplication with lookup-tables? Does RedPower let you make read-only-memory that's more compact than normal, or did you do it the normal way (rows of torches over wire)?
A critique: I'll be prefectly honest that I thought a 4-bit Calculator made in RedPower would be a lot smaller than this. It's true that multiplication and division are no trivial task, but this is the only slightly smaller than the size (in terms of land area) I would expect from a vanilla 4-bit Calculator with the same features (if made by an RDF pro).
How did you organize the different functions in the Calculator? I see what looks like a bunch of Read-Only memory. Are all the answers stored in advance, or am I grossly misreading this? I would think that you would at least have done addition/subtraction with Logic (which you may have, I just can't see it well from the pictures given).
0
0
0
0
My friends could feed injured wolves, but couldn't get them to mate after they were at full health, and all new puppies were loyal to me. One friend tried a bone on a wolf which produced hearts but didn't seem to change who it followed.
To any players more knowledgeable about SMP than I: Is there any way to give wolves to your friends?
0
Data is stored in horizontal rows designated by the Height value. $H = data for the row you are on, $(H+1) = data for row above you.
Horizontal position X is used to select which position in the row is being looked at. X and H by themselves are the current position values. $(H)[X] refers to the block-state of the current position.
Here is how the "Move Right" function works:
If $(H)[X+1] == 0, X += 1
Translation: If the block to the right of your current position is empty, shift position to the right.
I stored the X and H values in "One hot" format, meaning that if you were on the bottom row and on the 3rd block from the left:
H = 10000000
X = 00100000
Changing position to be + or - the current was accomplished by just shifting the bits. To determine the value of a certain block, H is used to select a single register in the RAM, and then that value gets ANDed with X. If the result is a 1, then position-changes are blocked and the cursor/player remains in place. That is how collision detection works.
0
1.) You should probably use some better RAM. The RAM you're using is going to have problematic access-times. I should really get around to making a video about state-of-the-art RAM technologies. Making good RAM is a big impediment for many people's projects.
2.) I think you might have some trouble implementing the commands, since movement is based on conditional shifting, not an automatic change in position. It does a "hypthetical" shift to the new position, sees if that square is empty, and only saves the new position if it's empty. Using the shifter you have you'll be able to move around just fine, but I don't think you'll be able to implement collision-detection.
0
I'm having to do a lot of studying for an algorithms class so don't expect anything impressive on the CPU for at least another week.
0
Unfortunately, pipelining is a bit of a nightmare to program with since you have to keep track of a whole host of new data hazards. However, if you think you can handle it and get a goodly speed boost, then by all means do it!
I won't be making any architectural changes to this CPU for the simple reason that it's my FIRST CPU. I'm learning right now and I want to have a full understanding of all the difficulties faced with a "normal" CPU before I start fiddling around with anything fancy like pipelining or new mechanics like instant-wire.
I'll have to make a decision about whether my next CPU will be instant-based or not. I think I might go for a hybrid system with instant-bussing but conventional logic.
I haven't carefully studied what the exact causes of the various block-dropping errors are, but fortunately none of the "Instant-Carry" pistons have been affected. I've added insulating delays on all the control-bits and "pulse-hardened" some pistons where it wouldn't slow down the system and so far it SEEMS to be working ok, but again, further testing will be needed.
I don't really know what you mean by "synchronicity" since none of the gates are on a clock and I made no specific effort to keep delays uniform. What are you referring to, and how would this lead to additional block-dropping behaviors?
0
According to Brotep's explanation though, what I described would actually be a D-Latch, not a flip-flop. Learn something new every day.
1