Mixing
What is the relationship between modulo and $log_2$ in this problem?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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:
$textcacheLineNumber equiv textmemoryAddress pmodtextnumberOfLinesInCache$
For example, if we're looking at $textmemoryAddress = 00001$, and we have $textnumberOfLinesInCache = 8$ as in this diagram, then we have $1 equiv 1pmod8$. 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.
modular-arithmetic logarithms computer-science
edited Aug 3 at 17:50
Math Lover
12.2k21132
asked Aug 3 at 17:17
AleksandrH
1,165821
add a comment |Â
up vote
2
down vote
favorite
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:
$textcacheLineNumber equiv textmemoryAddress pmodtextnumberOfLinesInCache$
For example, if we're looking at $textmemoryAddress = 00001$, and we have $textnumberOfLinesInCache = 8$ as in this diagram, then we have $1 equiv 1pmod8$. 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.
modular-arithmetic logarithms computer-science
edited Aug 3 at 17:50
Math Lover
12.2k21132
asked Aug 3 at 17:17
AleksandrH
1,165821
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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:
$textcacheLineNumber equiv textmemoryAddress pmodtextnumberOfLinesInCache$
For example, if we're looking at $textmemoryAddress = 00001$, and we have $textnumberOfLinesInCache = 8$ as in this diagram, then we have $1 equiv 1pmod8$. 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.
modular-arithmetic logarithms computer-science
edited Aug 3 at 17:50
Math Lover
12.2k21132
asked Aug 3 at 17:17
AleksandrH
1,165821
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:
$textcacheLineNumber equiv textmemoryAddress pmodtextnumberOfLinesInCache$
For example, if we're looking at $textmemoryAddress = 00001$, and we have $textnumberOfLinesInCache = 8$ as in this diagram, then we have $1 equiv 1pmod8$. 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.
modular-arithmetic logarithms computer-science
edited Aug 3 at 17:50
Math Lover
12.2k21132
asked Aug 3 at 17:17
AleksandrH
1,165821
edited Aug 3 at 17:50
Math Lover
12.2k21132
edited Aug 3 at 17:50
Math Lover
12.2k21132
edited Aug 3 at 17:50
Math Lover
12.2k21132
12.2k21132
asked Aug 3 at 17:17
AleksandrH
1,165821
asked Aug 3 at 17:17
AleksandrH
1,165821
asked Aug 3 at 17:17
AleksandrH
1,165821
1,165821
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
Note that a number $$N = b_n b_n-1 cdots b_4b_3b_2b_1_texttwo = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+cdots+2^n-3b_n).$$
Therefore, $$N equiv b_1 + 2b_2 + 4b_3 +0 equiv b_3 b_2 b_1 _texttwopmod8.$$
Following the above procedure, it is easy to observe that
$$b_n b_n-1 cdots b_4b_3b_2b_1_texttwo equiv b_m b_m-1 cdots b_1_texttwo pmod2^m,$$
where $m le n$.
answered Aug 3 at 17:36
Math Lover
12.2k21132
I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math.
– AleksandrH
Aug 3 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-3b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+cdots+2^n-3b_n) equiv 0 pmod8$.
– Math Lover
Aug 3 at 17:41
I don't understand how that last term suddenly became a $0$.
– AleksandrH
Aug 3 at 17:53
@AleksandrH Note that $8 times x equiv 0 pmod8$, where $x$ is an integer. For example, $8 times 2 equiv 0 pmod8$.
– Math Lover
Aug 3 at 18:47
add a comment |Â
up vote
0
down vote
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.
answered Aug 3 at 23:34
AleksandrH
1,165821
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Note that a number $$N = b_n b_n-1 cdots b_4b_3b_2b_1_texttwo = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+cdots+2^n-3b_n).$$
Therefore, $$N equiv b_1 + 2b_2 + 4b_3 +0 equiv b_3 b_2 b_1 _texttwopmod8.$$
Following the above procedure, it is easy to observe that
$$b_n b_n-1 cdots b_4b_3b_2b_1_texttwo equiv b_m b_m-1 cdots b_1_texttwo pmod2^m,$$
where $m le n$.
answered Aug 3 at 17:36
Math Lover
12.2k21132
I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math.
– AleksandrH
Aug 3 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-3b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+cdots+2^n-3b_n) equiv 0 pmod8$.
– Math Lover
Aug 3 at 17:41
I don't understand how that last term suddenly became a $0$.
– AleksandrH
Aug 3 at 17:53
@AleksandrH Note that $8 times x equiv 0 pmod8$, where $x$ is an integer. For example, $8 times 2 equiv 0 pmod8$.
– Math Lover
Aug 3 at 18:47
add a comment |Â
up vote
1
down vote
Note that a number $$N = b_n b_n-1 cdots b_4b_3b_2b_1_texttwo = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+cdots+2^n-3b_n).$$
Therefore, $$N equiv b_1 + 2b_2 + 4b_3 +0 equiv b_3 b_2 b_1 _texttwopmod8.$$
Following the above procedure, it is easy to observe that
$$b_n b_n-1 cdots b_4b_3b_2b_1_texttwo equiv b_m b_m-1 cdots b_1_texttwo pmod2^m,$$
where $m le n$.
answered Aug 3 at 17:36
Math Lover
12.2k21132
I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math.
– AleksandrH
Aug 3 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-3b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+cdots+2^n-3b_n) equiv 0 pmod8$.
– Math Lover
Aug 3 at 17:41
I don't understand how that last term suddenly became a $0$.
– AleksandrH
Aug 3 at 17:53
@AleksandrH Note that $8 times x equiv 0 pmod8$, where $x$ is an integer. For example, $8 times 2 equiv 0 pmod8$.
– Math Lover
Aug 3 at 18:47
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Note that a number $$N = b_n b_n-1 cdots b_4b_3b_2b_1_texttwo = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+cdots+2^n-3b_n).$$
Therefore, $$N equiv b_1 + 2b_2 + 4b_3 +0 equiv b_3 b_2 b_1 _texttwopmod8.$$
Following the above procedure, it is easy to observe that
$$b_n b_n-1 cdots b_4b_3b_2b_1_texttwo equiv b_m b_m-1 cdots b_1_texttwo pmod2^m,$$
where $m le n$.
answered Aug 3 at 17:36
Math Lover
12.2k21132
Note that a number $$N = b_n b_n-1 cdots b_4b_3b_2b_1_texttwo = b_1 + 2b_2 +4b_3 +8(b_4+2b_5+cdots+2^n-3b_n).$$
Therefore, $$N equiv b_1 + 2b_2 + 4b_3 +0 equiv b_3 b_2 b_1 _texttwopmod8.$$
Following the above procedure, it is easy to observe that
$$b_n b_n-1 cdots b_4b_3b_2b_1_texttwo equiv b_m b_m-1 cdots b_1_texttwo pmod2^m,$$
where $m le n$.
answered Aug 3 at 17:36
Math Lover
12.2k21132
edited Aug 3 at 17:48
answered Aug 3 at 17:36
Math Lover
12.2k21132
answered Aug 3 at 17:36
Math Lover
12.2k21132
answered Aug 3 at 17:36
Math Lover
12.2k21132
12.2k21132
I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math.
– AleksandrH
Aug 3 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-3b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+cdots+2^n-3b_n) equiv 0 pmod8$.
– Math Lover
Aug 3 at 17:41
I don't understand how that last term suddenly became a $0$.
– AleksandrH
Aug 3 at 17:53
@AleksandrH Note that $8 times x equiv 0 pmod8$, where $x$ is an integer. For example, $8 times 2 equiv 0 pmod8$.
– Math Lover
Aug 3 at 18:47
add a comment |Â
I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math.
– AleksandrH
Aug 3 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-3b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+cdots+2^n-3b_n) equiv 0 pmod8$.
– Math Lover
Aug 3 at 17:41
I don't understand how that last term suddenly became a $0$.
– AleksandrH
Aug 3 at 17:53
@AleksandrH Note that $8 times x equiv 0 pmod8$, where $x$ is an integer. For example, $8 times 2 equiv 0 pmod8$.
– Math Lover
Aug 3 at 18:47
I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math.
– AleksandrH
Aug 3 at 17:38
I'm not sure I follow. Could you break down your reasoning in the steps? I've never been good at following math.
– AleksandrH
Aug 3 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-3b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+cdots+2^n-3b_n) equiv 0 pmod8$.
– Math Lover
Aug 3 at 17:41
@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-3b_n)$ is a multiple of $8$. Therefore, $8(b_4+2b_5+cdots+2^n-3b_n) equiv 0 pmod8$.
– Math Lover
Aug 3 at 17:41
I don't understand how that last term suddenly became a $0$.
– AleksandrH
Aug 3 at 17:53
I don't understand how that last term suddenly became a $0$.
– AleksandrH
Aug 3 at 17:53
@AleksandrH Note that $8 times x equiv 0 pmod8$, where $x$ is an integer. For example, $8 times 2 equiv 0 pmod8$.
– Math Lover
Aug 3 at 18:47
@AleksandrH Note that $8 times x equiv 0 pmod8$, where $x$ is an integer. For example, $8 times 2 equiv 0 pmod8$.
– Math Lover
Aug 3 at 18:47
add a comment |Â
up vote
0
down vote
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.
answered Aug 3 at 23:34
AleksandrH
1,165821
add a comment |Â
up vote
0
down vote
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.
answered Aug 3 at 23:34
AleksandrH
1,165821
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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.
answered Aug 3 at 23:34
AleksandrH
1,165821
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.
answered Aug 3 at 23:34
AleksandrH
1,165821
answered Aug 3 at 23:34
AleksandrH
1,165821
answered Aug 3 at 23:34
AleksandrH
1,165821
answered Aug 3 at 23:34
AleksandrH
1,165821
1,165821
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2871311%2fwhat-is-the-relationship-between-modulo-and-log-2-in-this-problem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password