Dual-purpose processor: factorial and prime

Assumption: one 8-bit input n is read; the processor produces both outputs, FACT = n! and PRIME (1 if n is prime). Registers I and R are shared by both functions.

Algorithm

 read n
 F = 1
 for I = 2 to n: F = F * I        // factorial
 FACT = F
 if (n < 2) PRIME = 0
 else:
    I = 2
    while (I < n):
        R = n; while (R >= I) R = R - I
        if (R == 0) { PRIME = 0; stop }
        I = I + 1
    PRIME = 1
 output FACT, PRIME

FSMD

Note: n = 0 gives 0! = 1 and n = 1 gives 1.

FSM (control signals per state)

Datapath

 n -> [N] --> comparators: I<=N, N<2, I>=N
 [F] <- mux(1, F*I) <- [ * multiplier ] <- F, I
 [I] <- mux(2, I+1) <- incrementer
 [R] <- mux(N, R-I) <- subtractor ; compare R>=I ; zero detect R==0
 [FACT] <- F ; [PRIME] flag

Components: registers N, F (16 or 32 bits for the factorial), I, R, FACT, PRIME flag; one multiplier, one incrementer, one subtractor; comparators (I <= N, N < 2, I >= N, R >= I) and a zero detector; four multiplexers.

Controller

Block diagram:

 start, status flags --> +-------------+   +-----------+
 (from datapath)         | Next-state  |-->| State     |
                         | logic       |   | register  |
                         +------^------+   +-----+-----+
                                |   current state |
                                +-----------------+
                                                  v
                                           +-------------+
                                           | Output logic|--> control
                                           +-------------+    signals

Inputs: start, status flags (le, lt2, ige, rge, rz). Outputs: loads, mux selects, done. 10 states (S0-S9): 4-bit binary state register.