--- title: "Dual-purpose processor: factorial and prime" subject: "Embedded System" chapter: 2 key: "semester_6/embedded_system:dual-purpose-factorial-prime" source: https://www.bctengineer.com/q/semester_6/embedded_system/dual-purpose-factorial-prime site: BCT Engineering --- # Dual-purpose processor: factorial and prime Embedded System · Chapter 2: Hardware Design Issues - Asked in: 2071 Magh, 8 marks - Video: [Designing Single Purpose Processor To Calculate GCD (HCF).](https://www.youtube.com/watch?v=Wy344fMRnOo) — AFlick - Page: https://www.bctengineer.com/q/semester_6/embedded_system/dual-purpose-factorial-prime - Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-2 ## Question Show the algorithm, FSMD, FSM, data-path, and controller design for a dual-purpose processor that can calculate the factorial of a number and also check if that number is a prime number. ## Short answer The processor computes factorial by iterative multiplication (F=1, I=2..n) and checks primality by trial division with repeated subtraction. Datapath shares registers N, I, R, F, multiplier, subtractor; controller is a 10-state FSM with status flags le, lt2, ige, rge, rz. ## Answer **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 ```text 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 | State | Condition | Actions | Next | |---|---|---|---| | S0 | start = 0 | wait | S0 | | S0 | start = 1 | N = n; F = 1; I = 2 | S1 | | S1 | I <= N | none | S2 | | S1 | I > N | FACT = F | S3 | | S2 | always | F = F * I; I = I + 1 | S1 | | S3 | N < 2 | none | S9 | | S3 | N >= 2 | I = 2 | S4 | | S4 | I >= N | none | S8 | | S4 | I < N | R = N | S5 | | S5 | R >= I | none | S6 | | S5 | R < I | none | S7 | | S6 | always | R = R - I | S5 | | S7 | R = 0 | none | S9 | | S7 | R != 0 | I = I + 1 | S4 | | S8 prime | always | PRIME = 1, done = 1 | S0 | | S9 not prime | always | PRIME = 0, done = 1 | S0 | Note: n = 0 gives 0! = 1 and n = 1 gives 1. #### FSM (control signals per state) | State | Signals | |---|---| | S0 | N_ld, F_set1, I_set2 (on start) | | S1 | none (compare I <= N) | | S2 | F_ld (multiplier), I_inc | | S3 | FACT_ld (compare N < 2) | | S4 | R_ld (R = N) when I < N | | S5 | none | | S6 | R_sub | | S7 | I_inc when R != 0 | | S8 | PRIME = 1, done | | S9 | PRIME = 0, done | #### Datapath ```text 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: ```text 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does a dual-purpose design share? A. Nothing, two separate processors B. Only the output port C. Registers such as I and R and the same controller D. Only the clock Answer: C. Registers I and R are reused by factorial and the prime check. (Key point: Shared resources) 2. How is the factorial computed? A. F = n + (n-1) repeatedly B. F = n * n C. F = 0; add I each time D. F = 1; for I = 2 to n: F = F * I Answer: D. Multiplying F by I for each I from 2 to n gives n!. (Key point: Factorial loop) 3. What are 0! and 1!? A. Both equal 1 B. 0! = 0 and 1! = 1 C. Both equal 0 D. 0! is undefined Answer: A. The loop does not run when n < 2, leaving F = 1. (Key point: Special cases) 4. How does the prime check detect a divisor? A. F is odd B. R = n minus repeated I gives 0 for some I < n C. I > N D. R >= I at the end Answer: B. A zero remainder for I from 2 to n-1 means n is not prime. (Key point: Prime test) ## Related in Embedded System - [Dual-purpose processor: median and variance](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Adual-purpose-median-variance) — Embedded System, chapter 2 - [Prime number checking processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-prime-check) — Embedded System, chapter 2 - [Factorial single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-factorial) — Embedded System, chapter 2 - [Design LCM single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-lcm-datapath-controller) — Embedded System, chapter 2 - [Single-purpose processor for power](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-power) — Embedded System, chapter 2, asked 2× - [Fibonacci single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-fibonacci) — Embedded System, chapter 2, asked 2× ## Related in other subjects - [Dual processor modes in centralized SPC](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Adual-processor-modes-spc) — Telecommunications, chapter 4, asked 4× - [nth Fibonacci term prime check](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afibonacci-nth-prime) — Computer Programming, chapter 6 - [SPC and dual processor architecture](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aspc-dual-processor) — Telecommunications, chapter 4 - [Prime number program: procedural and OOP](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Aprime-procedural-oop) — Object Oriented Programming, chapter 1