Talk:Four bit adder: Difference between revisions
→I made a latch!: new section
(→I made a latch!: new section) |
|||
| (12 intermediate revisions by 6 users not shown) | |||
Line 161:
::Which I guess is the heart of my comment: What is the usefulness of a task that "simulates hardware"? I can see how RC can have tasks about bit-operations. I can kinda see how HW simulation might be kinda appropriate (in the sense of Verilog programming for FPGAs or ASICs; that's real programming with real languages) but in that case I'm not sure how valuable it is to require rather un-idiomatic layouts in the task descriptions. For example the shown layout of the 4-bit adder is squential (=naive) and I don't think this is how anybody doing real hardware would implement it. Imagine doing math on 64-bit numbers for a moment: after the <i>last</i> input bit has settled, your output bits are undefined (i.e. can be flipping from 0 to 1 and back a random number of times) for 65 times the delay introduced by a single full adder while you're slowly moving your carry bit from stage to stage. In other words: sequential carries maximize the execution time of the overall block. If you have that much time to waste, the you're almost always better off just running something on a ready-built processor rather than implementing your own hardware. So it is vaguely unclear to me what anybody is supposed to learn from this. [[User:Sgeier|Sgeier]] 19:12, 1 September 2010 (UTC)
:::I don't know quite how this is going to fit into RC in general yet, so I'm hoping that it can remain somewhat segregated away from the regular body of tasks by avoiding usage of, e.g. [[Template:Task]] and much of the regular infrastructure until things settle down and those interested in the hardware domain get a feel for how these tasks can/cannot tie in with the rest of the wiki. I haven't had time to monitor it, maintain separation and consider how things can tie back together later. My gut tells me that simulating hardware falls along similar lines to software implementations of programming languages and virtual machines, (See RCBF, RCSNUSP, RCH9Q+), and has analogous values and roles. (For whatever reasons, those tasks can expose complex practical consequence and behavior in their relevant languages.)
:::As for task descriptions forcing unidiomatic layouts and behaviors, and making unnecessary or incorrect assumptions about the problems they're trying to describe, people with the experience to recognize these things should generally work with the people who wrote the tasks to help them expand their understanding and improve the tasks they write in order to intersect the core idea/goal of the task writer with a broad cross-section of possible solutions without unnecessarily forcing unidiomatic code. --[[User:Short Circuit|Michael Mol]] 22:58, 1 September 2010 (UTC)
The idea as whole is enough large to be in the project category. Constructive blocks however are simple task of their own (task used in the general way, not as "RC task"); having a library of these blocks should then make it simpler (!) to realized the final project.
Line 242 ⟶ 244:
A quick note on how a logic simulator provides the illusion of parallelism needed to a typical logic circuit: a technique known as a "two list simulator". The "circuit" is represented by a set of objects that represent the components, and a second set the represent the wires (connectivity). Simulation proceeds in two phases: first, we tell each component to update its outputs based on the current value of its inputs. Next, we tell each wire to propagate the output of the upstream component to the input of the downstream component(s). While doing this, we note if any values actually change -- if none do then the current timestep is done (as an optimization, only those components whose inputs have changed are updated on each iteration). The term "two list simulation" comes the need to maintain these two sets of things to update: the components, and the wires..
(ps. Small world: I, too, used to work for Infineon -- 10 years ago when it was spun off from Siemens -- these days I'm at NVIDIA
--[[User:Davewhipp|DaveWhipp]])
==C++ code size==
Is the C++ example so large because it needs to be that large to fulfil the task? I don't think the example given shows C++ in a good light due to its extreme length. Maybe it was copied from existing code used for another purpose? --[[User:Paddy3118|Paddy3118]] 20:07, 30 September 2011 (UTC)
: Meh. The C++ code appears to be quite thorough and models the concept of physical devices pretty well. It's wordy, but that's C++. It actually can notice connection errors because everything exists as a device down to the input voltage sources. Compared to it, the C example is completely worthless as a "simulation", where you might have forgotten to put a voltage on one of the input pins and the program will merrily give you garbage output without noticing a thing. I suspect a lot of other languages also have this problem, which makes the task sort of much ado about nothing. It's very possible the C++ code can be shortened, but if it ends up like the C code, I'd prefer the way it is now, however much I hate long winded code. --[[User:Ledrug|Ledrug]] 21:42, 30 September 2011 (UTC)
:: But the task description does not even mention voltages, nor does it ask us to build up the gates on simulated silicon (or any other such model). Meanwhile, you can build four bit adders using optical or mechanical gates, where voltages are not a meaningful concept. So it's not far to describe this issue as a problem with the implementations in other languages. --[[User:Rdm|Rdm]] 22:27, 30 September 2011 (UTC)
::: Look, it's not my word: the C example called the inputs "pins" and the assignment statement "V", what was I supposed to infer? The desc does use the word "simulate", btw. I don't really care if you simulate a voltage or water pressure, the matter is task description does seem to want some reasonable simulation despite wasting a lot of effort talking about how one should use bit mask as input/output values. The C code along with some translated code did the task without a remotely systematic way of simulating a circuit (can you verify input pins are all with valid values? how much work is it change the code to do a 128 bit adder instead of 4?), it's ironic to call this a simulation. --[[User:Ledrug|Ledrug]] 23:23, 30 September 2011 (UTC)
::::Ok, and the task does say "chip" which would also imply electronics. But I would also draw a distinction between other languages in general (some of which have implementations where the 128 bit adder is trivial) and the C implementation in specific (which I have not studied). Still... if the task meant for physics to be simulated, instead of logic, I imagine it would have said something about the way physics was supposed to be simulated? --[[User:Rdm|Rdm]] 01:04, 1 October 2011 (UTC)
::I suspect the C++ (not the C) code, rather than being idiomatic, is "enterprise-y" the kind of code you get when people refuse to say no or the people in charge think "I might just need this" or "if I put this in, I can't be fired for leaving it out". There are several examples already existing that could be used to show what is expected from an answer. RC rarely requires any example of that size. It is just as unreasonable to have the C++ example as it would be to add a code golf solution. Simulations are supposed to reflect an ''appropriate'' abstraction of what is simulated. --[[User:Paddy3118|Paddy3118]] 10:26, 1 October 2011 (UTC)
::: Actually, the C++ code looks very idiomatic to me. Certainly not the most efficient, but it's very clear and readable in function. (Actually, frightfully so; I've never seen C++ code that clear) Also, an opinion on the code golf reference...Code golf is generally undesirable because it reduces clarity of code, and adds perverse incentives for example writers. --[[User:Short Circuit|Michael Mol]] 11:42, 1 October 2011 (UTC)
Could someone move the C++ code to a separate sub-page at least? That huge wad of code is over 16 pages long where the others are less than two pages! It is clearly [http://oxforddictionaries.com/definition/anomalous anomalous] in size.
(P.S. it would be instructive to know a little about how the code was written. Was it written for this RC task alone? Was a lot of the code generated by an IDE? ...) --[[User:Paddy3118|Paddy3118]] 04:59, 1 October 2011 (UTC)
: Concur on subpage, and done. I think it was very probably written for Rosetta Code; the usage of a namespace named 'rosetta' is good indicator. --[[User:Short Circuit|Michael Mol]] 11:42, 1 October 2011 (UTC)
== Clojure solution ==
I added a second Clojure solution to show what I think is more idiomatic Clojure code. Because Clojure does not have TCO (which unavailable in Java), it's generally not a good idea to write recursive code in the old Lisp style as done in the original solution ('''n-bit-adder''' function). If possible, you should use the special form '''recur''' in a tail-call position to avoid growing the stack. But most of the time, it's better to find a solution using '''reduce''' if you can.
The second solution shows a couple of interesting language features. First, it uses destructuring to simplify extracting multiple values out of a vector (see my '''full-adder''' function). Second, it uses '''reduce''' in '''nbit-adder''' which is a good thing for Clojure programmers to learn. Also, the pre-condition (''':pre''') is a nice way to check for errors. It can be turned off without having to change the source.
The choice of big endian or little endian is arbitrary, but I think big endian is easier to read. That requires a little extra fiddling with how the bits are fed to the reduce function, but also shows off the '''rseq''' function, which is constant-time reverse for vectors.
== I made a latch! ==
It wasn't my original goal. Instead my first step was a concurrent implementation a little more robust than MizardX's. That method probably would be sufficient to build a latch, but I wanted something more resistant to blocking and deadlocking. Anyway,
<pre>
=== RUN Test-4
--- PASS: Test-4 (0.01 seconds)
logic_test.go:17: power up
logic_test.go:20: S: 0 R: 0 Q: 1 NQ: 0
logic_test.go:22: pulling R = 1
logic_test.go:25: S: 0 R: 1 Q: 0 NQ: 1
logic_test.go:27: pulling R = 0
logic_test.go:30: S: 0 R: 0 Q: 0 NQ: 1
logic_test.go:32: pulling S = 1
logic_test.go:35: S: 1 R: 0 Q: 1 NQ: 0
logic_test.go:37: pulling S = 0
logic_test.go:40: S: 0 R: 0 Q: 1 NQ: 0
</pre>
The concurrency isn't very exotic, and could probably be coded pretty easily in most languages with any kind of concurrency support, but I'm not sure it's quite ready for another task. It still runs asyncronously, with no concept of simulation time, so you have to do the hokey thing of just sleeping for a bit to let it run. I have a vague idea of using a priority queue for simulation time. Maybe that will be next. —[[User:Sonia|Sonia]] 01:05, 9 July 2012 (UTC)
| |||