23
\$\begingroup\$

Note: This challenge was inspired by Joe Z's many excellent questions surrounding NAND golfing.

Description

Your goal in this challenge, should you choose to accept it, is to implement a very simple ALU using just NAND gates. The ALU can only perform the the following four operations:

  1. 00, meaning increment (wrapping at 15).
  2. 01, meaning decrement (wrapping at 0).
  3. 10, meaning logical left shift.
  4. 11, meaning return zero.

Your circuit should take six inputs and give four outputs. Inputs I0 and I1 denote the operation. Inputs I2 through I5 denote the value to be operated on. Outputs O0 through O3 denote the output value.

Scoring

Your score is the number of gates you utilize to create this circuit. Lower is better.

Test cases

I0-I1 I2-I5 O0-O3
00 0001 0010
01 0000 1111
10 0100 1000
10 0011 0110
11 1100 0000
\$\endgroup\$
5
  • 4
    \$\begingroup\$ If you're new to NAND-golf: nandgame.com \$\endgroup\$
    – flawr
    Mar 16, 2022 at 14:40
  • 1
    \$\begingroup\$ I second that. I have done one playthrough and it is quite a fascinating game! \$\endgroup\$
    – Qaziquza
    Mar 16, 2022 at 16:30
  • 1
    \$\begingroup\$ Suggested test case: 10 0011 (should the result be 0001?) \$\endgroup\$
    – DLosc
    Mar 17, 2022 at 22:02
  • \$\begingroup\$ Yes (and added). By "multiply by 2", I mean logical left shift. I also fixed the other test case for "10" (it was broken). For everyone who has answered the question for the original (broken) test case: I am sorry. Please mark your answer as for the original version of the question, or fix your answer to work with the new one. \$\endgroup\$
    – Qaziquza
    Mar 17, 2022 at 22:39
  • 2
    \$\begingroup\$ For everyone interested in circuit golf, CircuitVerse is a site where you can visually build and share logic circuits. \$\endgroup\$
    – Bubbler
    Mar 18, 2022 at 0:14

5 Answers 5

11
\$\begingroup\$

71 64 49 gates

First define a few additional boolean operations in terms of NAND:

NOT(x)     := NAND(x,x)                           # 1 NAND
AND(a,b)   := NOT(NAND(a,b))                      # 2 NANDs
XOR(a,b)   := NAND(NAND(t=NAND(a,b),a),NAND(t,b)) # 4 NANDs

# AND(XOR(a,b), XOR(c,b)) in 7 NANDs:
XAX(a,b,c) := NOT(NAND(NAND(NAND(NOT(a), b), NAND(c, a)), NAND(c, b)))

Then we can define the ALU with these operations:

ni0    = NOT(i0)
ni1    = NOT(i1)
double = AND(i0,ni1)
o3     = AND(ni0,NOT(i5))
o2     = NAND(NAND(double,i5), NAND(ni0,XOR(XAX(o3,i5,i1),i4)))
o1     = NAND(NAND(double,i4), NAND(ni0,XOR(XAX(o2,i4,i1),i3)))
o0     = NAND(NAND(double,i3), NAND(ni0,XOR(XAX(o1,i3,i1),i2)))

Try it online!

This uses 9 NANDs, 3 NOTs, 2 ANDs, 3 XORs and 3 XAXs for a total of 49 NAND gates.

There is one gate that could be saved by removing some of the abstraction (we could get NOT(o3) for free and use that in the first XAX), but until I find some larger improvement I'd like to keep it simple.

The logic for the three higher bits might seem a bit intimidating, but with some transformations it is actually not bad:
NAND(NAND(...), NAND(...)) is equivalent to OR(AND(...), AND(...)). The left AND reads "operation is double and the bit to right in the input is set", and the right one flips the bit if XAX(new value of bit to the right, old value of bit to the right, decrement) evaluates to 1. And XAX(a,b,c) is equivalent to a>b if c else a<b.

\$\endgroup\$
8
\$\begingroup\$

42 gates

a, b, c, d, e, f = I

na = NOT(a)
nb = NOT(b)
nc = NOT(c)
nd = NOT(d)
ne = NOT(e)
nf = NOT(f)

xa = NAND(NAND(a, ne), NAND(na, e))
xb = NAND(NAND(b, ne), NAND(nb, e))
xc = NAND(NAND(c, ne), NAND(nc, e))

o0 = NOT(NAND(na, nf))

M = NOT(NAND(ne, f))

nxa = NOT(xa)

o1 = NAND(NAND(M, a), NAND(nf, XOR(xa, b, nxa, nb)))

nxaxb = NAND(xa,xb)
xaxb = NOT(nxaxb)

o2 = NAND(NAND(M, b), NAND(nf, XOR(xaxb, c, nxaxb, nc)))

nxaxbxc = NAND(xaxb, xc)
xaxbxc = NOT(nxaxbxc)

o3 = NAND(NAND(M, c), NAND(nf, XOR(xaxbxc, d, nxaxbxc, nd)))

Try it online!

11 NOT's, 22 NAND's, 3 XOR's (XOR(a,b) is defined as NAND(NAND(NOT(a), b),NAND(a, NOT(b))) except we pass in NOT(a) and NOT(b)).

\$\endgroup\$
6
\$\begingroup\$

88 NAND Gates

This is just the first thing i could think of, given the challenge specification... some obvious things might become apparent later.

Here shown decrementing 6.

Curcuit

\$\endgroup\$
6
  • \$\begingroup\$ @ovs yes, that's what i used here. \$\endgroup\$
    – friddo
    Mar 16, 2022 at 10:27
  • \$\begingroup\$ But then allowing NOT gates wouldn't reduce the count? Or are you suggesting NOT gates not counting? \$\endgroup\$
    – ovs
    Mar 16, 2022 at 10:28
  • 1
    \$\begingroup\$ @ovs some would assume a signal inversion isn't a gate. But I'm just leaving this with NAND gates then \$\endgroup\$
    – friddo
    Mar 16, 2022 at 10:30
  • 2
    \$\begingroup\$ You only get signal inversions for free if you can modify some of your other gates to treat their inputs as inverted. But then they're not NAND gates. If you had discrete logic chips with a bunch of NAND gates on a breadboard (like shown in wikipedia), and just wires, it's not free. In CMOS, a NOT takes 2 transistors, vs. 4 for a NAND. Or 1 vs. 2 for some other logic families. So it seems strange to me anyone would consider an inversion not being a gate, especially if we're talking about using only NAND. \$\endgroup\$ Mar 16, 2022 at 16:28
  • 1
    \$\begingroup\$ @PeterCordes thanks for the clarification :), noted for next time! \$\endgroup\$
    – friddo
    Mar 16, 2022 at 22:26
3
\$\begingroup\$

46 44 gates

input a[4]
input c[2]
tmp s[4] = a + {1,c[0],c[0],c[0]} // 1+9+9+8=27
tmp !c[1] // 1
tmp t[4] = {0,c[0]<s[0],c[0]<s[1],c[0]<s[2]} // 3+2
out {s[0]&!c[1],c[1]?t[1]:s[1],c[1]?t[2]:s[2],c[1]?t[3]:s[3]} // 11

Maybe we need a checker

s[0]: t+1 = t(!t), costing 1

c[0]>=s[0] is found when making s

out: a?b:c = (a nand b) nand (!a nand c)

You can try it by running this code in console of nandgame.com and refresh

\$\endgroup\$
3
\$\begingroup\$

59 56 53 52 51 50 gates

I thought I'd create an actual ALU here, even though it ended up taking more gates than @ovs' answer. Edit: A true ALU would actually use identical lanes for all four bits of the form Result = Input + ((Input & Mask) ^ Flip) + Carry. This would provide for eight different operations:

Mask Flip Carry Result
0    0    0     Input
0    0    1     Input + 1
0    1    0     Input - 1
0    1    1     Input
1    0    0     Input * 2
1    0    1     Input * 2 + 1 (c.f. Z80 SLL "instruction")
1    1    0     -1
1    1    1     0

Each lane (except the last, as the carry out is not required) would use 15 gates, and then 5 gates are needed to generate the desired carry in for the four operations, making a total of 64 gates. However my first approach actually special-cased the first lane, so that I could choose between the input and 1 as the RHS of the full adder:

00: IIII -> IIII + 0001
01: IIII -> IIII - 0001
10: IIII -> IIII + IIII
11: IIII -> IIII - IIII

To get the RHS takes 8 gates:

R2 = NAND(NOT(I2), I0)
R3 = NOT(NAND(I3, I0))
R4 = NOT(NAND(I4, I0))
R5 = NOT(NAND(I5, I0))

To select between + and -, I perform 2's complement on the value. 1's complement takes 16 gates:

S2 = XOR(R2, I1)
S3 = XOR(R3, I1)
S4 = XOR(R4, I1)
S5 = XOR(R5, I1)

To achieve 2's complement we simply add I1 as part of the IIII + SSSS operation:

C0, O0 = ADD(I2, S2, I1)
C1, O1 = ADD(I3, S3, C0)
C2, O2 = ADD(I4, S4, C1)
C3, O3 = ADD(I5, S5, C2)

This takes 36 gates for a grand total of 60 gates, except we don't need C3 which saves a gate.

Notes:

  • NOT takes 1 gate:

    NOT(X) = NAND(X, X)
    
  • XOR takes 4 gates:

    XOR(X, Y) = _XOR2(X, Y, NAND(X, Y))
    _XOR2(X, Y, W) = NAND(NAND(X, W), NAND(Y, W))
    
  • ADD takes 9 gates:

    ADD(X, Y, Z) = _ADD2(X, Y, Z, NAND(Y, Z))
    _ADD2(X, Y, Z, W) = _ADD3(X, W, _XOR2(Y, Z, W))
    _ADD3(X, W, V) = _ADD4(X, W, V, NAND(X, V))
    _ADD4(X, W, V, U) = NAND(W, U), _XOR2(X, V, U)
    

Edit: The LSB's adder's inputs have a lot of redundancy:

S2 = XOR(R2, I1)
C0, O0 = ADD(I2, S2, I1)

But this means that XOR(S2, I1) is just R2, so we can write this as:

C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
   = NAND(NAND(S2, I1), NAND(I2, R2))
O0 = XOR(I2, XOR(S2, I1))
   = XOR(I2, R2)
   = _XOR2(I2, R2, NAND(I2, R2))

This saves three gates.

Edit: Even more redundancy that I overlooked:

C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
   = NAND(NAND(S2, I1), NAND(I2, R2))
   = NAND(NAND(XOR(R2, I1), I1), NAND(I2, R2))
   = NAND(NAND(NOT(R2), I1), NAND(I2, R2))

Although this costs a gate, it makes S2 unnecessary which saves four gates for an overall saving of three gates.

Edit: Found another redundant gate:

C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
   = NAND(NAND(S2, I1), NAND(I2, R2))
   = NAND(NAND(XOR(R2, I1), I1), NAND(I2, R2))
   = NAND(NAND(NOT(R2), I1), NAND(I2, R2))
   = NAND(NAND(NOT(R2), I1), NAND(I2, NAND(NOT(I2), I0)))
   = NAND(NAND(NOT(R2), I1), NOT(I2))

Although this seems to just change a shared NAND to a shared NOT, I computed NOT(I2) as part of the calculation for R2, so that gate can be shared too, thus saving another gate.

Edit: This applies to O2 as well, then further allowing for a further saving of one gate:

O0 = XOR(I2, XOR(S2, I1))
   = XOR(I2, R2)
   = _XOR2(I2, R2, NAND(I2, R2))
   = _XOR2(I2, R2, NAND(I2, NAND(NOT(I2), I0)))
   = _XOR2(I2, R2, NOT(I2))
   = NAND(NAND(I2, NOT(I2)), NAND(R2, NOT(I2)))
   = NOT(NAND(R2, NOT(I2)))

Edit: One final gate can be saved by eliminating R2.

C0 = NAND(NAND(NOT(R2), I1), NOT(I2))
   = NAND(NAND(NOT(NAND(NOT(I2), I0)), I1), NOT(I2))
   = NAND(NAND(AND(NOT(I2), I0), I1), NOT(I2))
   = OR(AND(AND(NOT(I2), I0), I1), I2)
   = OR(AND(I0, I1), I2)
   = NAND(NAND(I0, I1), NOT(I2))
O0 = NOT(NAND(R2, NOT(I2)))
   = NOT(NAND(NAND(NOT(I2), I0), NOT(I2)))
   = NOT(NAND(OR(I2, NOT(I0)), NOT(I2)))
   = NOT(NAND(NOT(I0), NOT(I2)))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.