A rule known as the fundamental theorem of arithmetic states, in so many words, that any natural number is uniquely representable as a multiset of prime factors, and vice versa. Having two operands in this form makes some operations easier and other ones more difficult.

This discussion assumes certain definitions of terminology:

• natural number : A positive integer; an integer 1 or greater.
• prime number : A natural number with exactly two distinct natural factors, 1 and itself. In particular, 2 satisfies this requirement despite being even, while 1 does not satisfy this requirement because it has only one such factor instead of the required two.
• multiset : A generalization of a set wherein the multiplicity of each item is significant.

The natural number indicated by a given multiset is the product of 1 and each element of the multiset. For example, 1 is represented by the empty multiset {∅}, 3 by {3}, 5 by {5}, 15 by {3,5}, 25 by {5,5}, and so on.

Multiset operations on the multisets correspond to other operations on the natural numbers they represent:

• Intersection (i.e. retaining the lesser multiplicity per element) is equivalent to finding the greatest common divisor (gcd):
  • gcd(54, 24)
  • {2, 3, 3, 3} ⋂ {2, 2, 2, 3}
  • {2, 3}
  • 6
• Union (i.e. retaining the greater multiplicity per element) is equivalent to finding the least common multiple (lcm):
  • lcm(8, 12)
  • {2, 2, 2} ∪ {2, 2, 3}
  • {2, 2, 2, 3}
  • 24
• Addition of the multiset (i.e. retaining the sum of multiplicities per element) is equivalent to multiplication:
  • 414 * 555
  • {2, 3, 3, 23} + {3, 5, 37}
  • {2, 3, 3, 3, 5, 23, 37}
  • 229770
• Subtraction of the multiset (i.e. retaining the differences of multiplicities per element between one set and another) is equivalent to division:
  • 88088 / 2002
  • {2, 2, 2, 7, 11, 11, 13} − {2, 7, 11, 13}
  • {2, 2, 11}
  • 44
  • Note that this division is not closed on natural numbers unless the result would also be a natural number (i.e. the left operand must be divisible by the right) because the multiset subtraction itself is not closed on multisets (with nonnegative multiplicities). The multiset notation can still help to reduce the fraction to lowest terms:
  • 2310 / 273
  • {2, 3, 5, 7, 11} − {3, 7, 13}
  • {2, 5, 11} − {13} (since the multiset can’t have negative multiplicities, this is the simplest form)
  • 110 / 13
• Multiplying all of the multiplicities in the set by n yields the number to the nth power:
  • 168⁴
  • {2, 2, 2, 3, 7} multiplicities multiplied by 4
  • {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 7, 7, 7, 7}
  • 796594176
• If all of the multiplicities in the set are themselves divisible by n, dividing them yields the nth root of the number:
  • ∛474552
  • {2, 2, 2, 3, 3, 3, 13, 13, 13} multiplicities divided by 3
  • {2, 3, 13}
  • 78
• Meanwhile, the natural-to-multiset transform won’t help you at all with addition and subtraction.

Almost as fun as it looks.

Print your own, if you’d like!

This octahedral toy/tool/thing represents manipulations on a logic gate with two inputs A and B and one output Y. A face of the object says what operation it executes, such as “AND”. From there, each side of the face is marked with a variable—A, B, or Y—and rotating past that edge shows you the result of inverting that variable.

For example, if I start at AND, I might turn past Y to NAND (AND with inverted output). Then, I might turn past A to IF (another name for OR NOT), because that’s what /A NAND B is. Finally, I might turn past B to OR, since that’s A OR NOT /B.

Alternatively, you might choose a starting point and an ending point, then trace the path between them to determine how many inverters are necessary to do the conversion.

Note that any face is at most three turns from any other. Polar opposites such as AND and OR are on opposite faces, and changing one to the other involves inverting each input and the output.

The somewhat uncommon logical operator names IMP (short for IMPLIES), NIMP, IF, and NIF appear as one-word substitutes for operations that invert B (NAND NOT, AND NOT, OR NOT, and NOR NOT, respectively). The two-word versions appear as a subtitle.

This isn’t quite as great as it could be. The text sizes and layout need a lot of work; the expression text is only barely big enough to read. However, since the time may never come for improvement, here it is for you to play with.

Enjoy!

Yesterday’s post got me thinking way too hard about the ubiquitous 555 timer. Specifically, I wondered if I might have been missing an optimization that would knock out one of the 555s necessary to make the transparent latch. It turns out that I was right, provided that an active-low enable line is doable. (Details follow.)

Skip this bit if analog creeps you out: The 555 timer has some analog circuitry that seems to be used in the majority of its applications. There is a control voltage (CV) pin that sets thresholds for comparators at the TH (threshold) and /TR (trigger) pins. If TH is above CV, then it registers as high (low otherwise); if /TR is below CV/2, then it registers as low (high otherwise). CV can be set externally^[1], but usually it’s left alone, and its default setting is CV = 2V_cc/3 (making CV/2 = V_cc/3).

Really, that’s where the analog part ends. The rest is basically digital, and digital is far more comfortable for those of us from the computer side of the house. The 555 timer is basically an RS latch with mildly analog inputs, plus a preemptive additional reset (/RST). I realized that’s still vague for my taste, so I scribbled out a bunch of notes, drew up some tables, and eventually came up with the following logical equivalent of the 555:

Even if you ignore for a moment the tweakable threshold voltage settings on the threshold and trigger inputs, the 555 has interesting possibilities as a digital circuit.

(Edit: A demonstration of the above on Falstad.)

The chip has three logical inputs. One, /RST, is a legitimate TTL input that is inverted. The others feed into comparators as just described, but ignoring the level details, TH simply feeds into a buffer and /TR pin feeds into an inverter. There are also two outputs, OUT (output) and DIS (discharge) pin. Both carry the same data, but OUT is driven as a logic level while DIS is open-collector^[2].

If you ignore the /RST, the 555 is an R-/S latch, where TH and /TR pins serve as R and /S, respectively. If both of those signals are active, the result is by definition undefined.

/RST adds to this an overriding additional reset signal. When active, the output is defined as low even if /TRis also active.

By extracting the behavior of a plain RS latch from this, the relationship among the inputs is clarified:

• The latch is set if /TR is low and /RSTis high.
• The latch is reset if THis high, /RSTis low, or both.

Some degenerate cases:

• As noted before, if /RST is high then TH and /TR form an R-/S latch.
• If TH is low, then /RST and /TR form a kind of R latch^[3], with /RST and /TR as /R and /S, respectively.
• If TH and /TR are tied together as a single input, and /RST is used as another input, the result is an “AND NOT” logic gate, with TH+/TR as the inverting input and /RST as the non-inverting input.
• The inverting input is effectively Schmitt-triggered, with the hysteresis zone set between CV/2 and CV. (/RST remains a normal TTL input.)
• With /RST tied high, this becomes a Schmitt-triggered inverter.

Of particular interest is the R latch. This particular latch is set when /TR is low and /RST is high. On the other hand, this latch is reset when /RST is low with no other condition. When I saw this it seemed a bit familiar, like /RST being high enables the value of /TR having any impact.

So, I prepared a truth table for the D and E lines of a D latch, and entered the corresponding values of /R and /S. The result: /S = /E, and /R = D or /E.

My first conclusion is that, if you’re not bound to using only 555 elements, this could make things a lot easier. It requires an active-low /E, if that can’t be accomplished anywhere else, an NPN inverter (one transistor, two resistors) will suffice. /E is fed directly into /S, and a diode-logic OR gate (2 Schottky diodes, one resistor) figures /R. Even with the inverter that’s way fewer parts than yesterday’s solution.

In four parts, a D latch with active-low enable. Slap an inverter (also pictured) onto the front to make it a normal enable.

(Edit: A demonstration of the above on Falstad.)

Translating the setup to all 555s is trickier. If you can set up for active-low both /E and /D, it’s possible to get it down to three elements: The latch, an inverter into /R, and an AND NOT gate. This follows from the proposition that R = /D and E = /D and not /E. Then, /R = not R. And, of course, for active-high D you add an inverter—4 elements, no better than yesterday.

The difficulty is that the only gate a single 555 can simulate (other than an inverter) is an AND NOT. While it’s possible to make any other gate from AND NOT parts, some take more fudging than others. To make the OR gate we’d like, you need three. My derivation^[4] is as follows:

• A OR B
• NOT (A NOR B)
• NOT ((NOT A) AND NOT B)
• NOT ((1 AND NOT A) AND NOT B)
• 1 AND NOT ((1 AND NOT A) AND NOT B)

Note that in the last stage there are three “AND NOT”s and no other operators. Note also that, using (Schottky) diode logic, the parts count is the same: Two diodes and one resistor. Guess which one I’d rather breadboard.

1. ^[1] Its default value comes from a resistive divider of approximately 5K vs. 10K, so if the value is critical it’s probably better to set it via a lower impedance, such as with a voltage reference or a (unity gain) buffer. ↩
2. ^[2] 0V on low, high-impedance on high. ↩
3. ^[3] An RS latch that favors R in a tie ↩
4. ^[4] Through repeated application of DeMorgan’s laws. ↩

Younger hobbyists who want to do arithmetic in an electronics application may think that a microcontroller is the only way to do it. I present something far more old-school.

How to do simple math on real numbers in a very non-digital way.

If you can represent the scalar terms of an arithmetic expression as voltages and/or resistances, then many operations can be performed with op amps (which is, incidentally, what the “op” part means). Several of the major features are described above.

• The word “amp”, for amplifier, refers to the fact that the device amplifies, or enlarges, an input signal by a factor called gain which is represented by the letter A^[1] When A is fixed, the amplifier serves to multiply the input signal by A. By default, A is ideally infinite^[2], but can be set to a fixed value using resistors.
• Division (not pictured) can be performed using a resistor divider network. No op amp is required, though using one might be desirable to avoid loading effects.
• “Subtract then multiply by A > 0″: An op amp’s natural mode (in my opinion, anyway) is the differential amplifier. Two voltages are input; V₂ is subtracted from V₁, and then the difference is multiplied by A, which is based on the ratios of resistors used. All other linear modes pictured can be described in terms of this one:
• “Multiply by A >= 1″: If you take the divider off of V₂ and replace it with V_in, it’s equivalent to setting V₂ to V_in(1 + R_in/R_F). Then, just set V₁ to 0. The result is A(V₂ – V₁) = (R_F/R_in)V_in(1 + R_in/R_F) = V_in(1 + R_F/R_in).
• “Multiply by A < 0″: Let V₂ = 0, V₁ = V_in. The result is A(V₂ – V₁) = (R_F/R_in)(0 – V_in) = V_in(-R_F/R_in).
• “Add then multiply by A < 0″: Exactly the same as the previous case, except that the input is from a resistor divider network. If V₁ and V₂ are fed to the same point through equal resistances as shown, it’s equivalent to a single input of V_X = (V₁ + V₂)/2 through a resistance of R_X = R_in/2. With the other input at 0, the result is A(0 – V_X) = (R_F/R_X)(-V_X) = -(2R_F/R_in)((V₁ + V₂)/2) = -(R_F/R_in)(V₁ + V₂).
• “Logarithmic” and “Exponential”: An NPN transistor with a grounded base can be placed either at the feedback or the input to implement a logarithmic or exponential output, respectively. The coefficients of the expression are not well defined, since they vary from instance to instance, but if the transistors used are closely matched and thermally linked (for example, in a single-chip transistor array) then with some tuning their outputs will be consistent. A log transform can be used to easily multiply (by adding logarithms) or divide (by subtracting logarithms) two voltages.
• Comparison (not pictured): As discussed here previously, a comparator is a sort of op amp specialized to output only logical high/low depending on whether the value at the non-inverting input is higher than the value of the inverting input, outputting high and low, respectively. In a pinch, an op amp will do the same thing in the open-loop configuration—direct inputs and no feedback, resulting in the extremely high gain mentioned earlier. If the non-inverting input is even slightly different than the inverting input, that small difference is amplified so immensely that the output will be either the highest possible or the lowest possible, meaning around the positive and negative supply voltages, respectively. Use of an actual comparator is preferred though, since it is better tuned for digital use.

1. ^[1] The “A” presumably refers to “amplification”. ↩
2. ^[2] But in practice is just a very high number. ↩

Water bottles are an important resource in yuppie society.

I’ve been thinking about materials a lot lately, specifically materials that people tend to already have or at least won’t have to take any special measures to obtain. Use of such materials makes a project infinitely more reproducible in MacGyver situations. Read More

The makings of a from-scratch NES controller with a connector that's easier to source.

As mentioned previously, the NES controller is, at least from an electronics perspective, an extremely simple thing. It’s got one dirt-cheap chip, a parallel-in shift register, which receives cues from the system on two wires to send out its state over one. Even if there weren’t a currently-in-pieces NES controller on my workbench (there is), I would still have all the parts necessary to hack one up.

Well, almost. One exception.

Read More

What is the White Ranger’s sword made of?

Yet another personality feed begins. This post serves to test my feed xml output as well as my ability to post from a phone.

Yum. Thank you for your patronage.