# The amount of ROM needed to implement a 4-bit multiplier?

For a 4-bit multiplier there are $2^4 \cdot 2^4 = 2^8$ combinations.

The output of 4-bit multiplication is 8 bits, so the amount of ROM needed is $2^8 \cdot 8 = 2048$ bits.

Why is that? Why does the ROM need all the combinations embedded into it?

What will be the case with RAM?

-
Welcome to cs.SE! ROM (Read-Only Memory) and RAM (Random Access Memory) are two non-exclusive types of memory. The first says that the memory cannot be written, the second that all addresses of memory take the same time to be accessed. On an unrelated point, you should provide more context about your question, I don't remember multipliers requiring any memory to work, just logical gates. Are there any constraints that you forgot to mention? –  Khaur Feb 4 '13 at 14:11
At the expense of adding more circuitry at the input, you can reduce the ROM size into half, taking advantage of commutativity of multiplication. To elaborate, 3 * 5 = 5 * 3, so put some combinatorial logic before the input decoder which maps (5, 3) input to the same row as (3, 5). Also note that not all 256 products appear in the output. For example, 202 < 255, but it doesn't appear, neither does 255 itself or any of the prime numbers (>15). For a 4 * 4 multiplication, there are only 90 possible outputs, but the next power of 2 is 128. –  user13027 Jan 22 at 5:05

to address 8-bit numbers correctly your ROM size should be: $2^8 \times 8$ bits.
If you are storing all the value of the function (in this case, multiplication) in a big table, then the size of this table is $2^{\text{# input bits}}\cdot \text{# output bits}$. This becomes impractical rather quickly, so CPUs implement arithmetic operations differently.