Talk:Four bit adder: Difference between revisions
→I made a latch!: new section
(→Motivations behind the task (and point 1 (RC domain)): How it can fit in, and how incorrect tasks should generally be worked with.) |
(→I made a latch!: new section) |
||
| (11 intermediate revisions by 6 users not shown) | |||
Line 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)
| |||