I've seen a claim that the world's reservoirs cause a small slowing in the Earth's rotation. There's a fair amount of water held at altitudes higher than "normal". Some other factors are glacial melt, and the levels of various large inland lakes. Salt Lake varies by at least 20 feet depending on drought cycles. Any volunteers for the arithmetic? Oh, and the core is spinning a tad faster than the surface, gaining a day every couple of hundred years. --- I've got a couple of tidbits about loops in circuits. In the late 1960s, I saw an example of a circuit published in some ACM rag, which used a loop to compute two outputs. The outputs were roughly A&(B'vC&(D'vE...)) and the same thing with variables negated. There was a single loop, with the variables coming in twice on opposite sides, with appropriate negations. The circuit was offered as an example where a loop gave a smaller circuit. I must have a detail wrong here, since my version doesn't seem to offer any advantage for the loop. --- Knuth mentioned an article by Lee Sallows from Math Intelligencer (1990), which discusses the 2-Nots problem. (The 2-Nots problem is to build a circuit that computes A', B', and C'. Available resources are a barrel of And and Or gates, but only two inverters. I learned it from Stu Nelson.) The next idea is to use the construction recursively, getting four inverters from three and then from two, and then any number of inverters. This holds out the possibility that any boolean function can be built from just two inverters, along with the barrel of Ands and Ors. The bug is that the recursion, building the 4-not circuit from the 2-not circuit, introduces feedback, which was implicitly barred in the original problem. Sallows apparently investigated further, and developed circuits with feedback, but which eventually stabilized with the correct answer. --- I've been mulling the minimal circuit problem for a long time, mainly as an exercise in low end computational complexity. I usually use the metric that only 2-input And and (1-input) Not gates are available, with And costing $1 and Not being free. (Knuth's thinking more about programs, so he also allows Xor.) I've been thinking about how to include feedback or memory in (mathematical) circuits, since real circuits use memory/feedback a lot. There seem to be about half a dozen reasonable ways to formalize loopy circuits, with no good excuse for selecting one over another. I'm presently leaning toward a very simple 1-bit memory with one data input and one clock input, and discrete time steps. However, introducing time into the mix means that there are now lots more functions to compute and analyze -- bit streams rather than single bit outputs. Rich -----Original Message----- From: Henry Baker [mailto:hbaker1@pipeline.com] Sent: Fri 12/30/2005 9:43 AM To: Schroeppel, Richard Cc: math-fun@mailman.xmission.com; rcs@cs.arizona.edu Subject: Re: [math-fun] Boolean synthesis request from Knuth I've always been curious about the feedback/loops restriction. Does anyone know how much things can be improved for boolean _functions_ that are implemented with feedback and/or loops? I suspect that latency can't be improved, but I suspect that the # of gates can be improved over the no feedback/loop version. (To be clear, I'm thinking about implementing functions using circuits that might have state, but the initial state is irrelevant to the output. For example, a boolean circuit might utilize some sort of hash table lookup to implement an initial guess that is verified before being output. In this case, the (mean) latency could be improved over the no-state version.) At 05:00 PM 12/29/2005, Schroeppel, Richard wrote:
The allowed gates are two-input And and two-input Xor; also, Nots may be used freely, and don't count against the total. As usual, the circuits must be DAGs (no feedback or loops), and circuit depth doesn't matter.