# What is the relationship between modulo and $\log_2$ in this problem?

Here's a screenshot of a diagram from my computer architecture course. You don't need to understand the technical terms here. It's essentially mapping locations from one piece of memory to locations in another piece of memory.

According to the book, we determine the mapping based on the following formula:

$\text{cacheLineNumber} \equiv \text{memoryAddress} \pmod{\text{numberOfLinesInCache}}$

For example, if we're looking at $\text{memoryAddress} = 00001$, and we have $\text{numberOfLinesInCache} = 8$ as in this diagram, then we have $1 \equiv 1\pmod{8}$. Thus, that memory address should map to the cache line numbered $001$.

Below the diagram is an explanation noting that this is the equivalent of using the lower $3$ bits of the given memory address. But I don't understand what the mathematical motivation is for this discovery. I see that it's true, but I don't get it.

Note that a number $$N = b_{n} b_{n-1} \cdots b_{4}b_{3}b_{2}b_{1}{}_{\text{two}} = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+\cdots+2^{n-3}b_n).$$ Therefore, $$N \equiv b_1 + 2b_2 + 4b_3 +0 \equiv b_3 b_2 b_1 {}_{\text{two}}\pmod{8}.$$ Following the above procedure, it is easy to observe that $$b_{n} b_{n-1} \cdots b_{4}b_{3}b_{2}b_{1}{}_{\text{two}} \equiv b_{m} b_{m-1} \cdots b_{1}{}_{\text{two}} \pmod{2^{m}},$$ where $m \le n$.

• I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math. Aug 3, 2018 at 17:38
• @AleksandrH Can you please inform me which point is difficult to understand. I considered $N$ which has $n$-bit binary representation. The RHS is the decimal value of $N$. The term $8(b_4+2b_5+\cdots+2^{n-3}b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+\cdots+2^{n-3}b_n) \equiv 0 \pmod{8}$. Aug 3, 2018 at 17:41
• I don't understand how that last term suddenly became a $0$. Aug 3, 2018 at 17:53
• @AleksandrH Note that $8 \times x \equiv 0 \pmod{8}$, where $x$ is an integer. For example, $8 \times 2 \equiv 0 \pmod{8}$. Aug 3, 2018 at 18:47

I felt the other answer still didn't clear up my confusion, but messing around with the numbers on paper, I managed to arrive at an explanation (I think this is somewhat similar to what @Math Lover was saying, but the answer he/she gave was a bit confusing):

If I consider $00101$, that's:

$0*2^4+0*2^3+1*2^2+0*2^1+1*2^0$

And we can isolate $2^3 = 8$ from the two frontmost terms (in fact, from all terms in front of $2^3$, no matter how many bits there are in the string:

$2^3 (0) + (1*2^2 + 0*2^1 + 1*2^0)$

And that matches the format of:

$n = dq + r$

Where $r$ is the remainder.