Facebook Page
Twitter
RSS
Thanks Thanks:  0
+ Reply to Thread
Results 1 to 3 of 3
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,838
    Thanks
    2,271 times
    Thanked
    707 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #1
    Hey!!

    Let $\text{Val} = \{0, 1\}^8$, $\text{Adr} = \{0, 1\}^{32}$ and $\text{Mem} = \text{Val}^{\text{Adr}}$.

    The addition modulo $2^8$ of two numbers in binary system of length $8$, is given by the mapping:
    $$\text{add}_{\text{Val}} : \text{Val}\times \text{Val}\rightarrow \text{Val} \\ (u,v) \mapsto \text{bin}_8 ((\text{Num}_2(u)+\text{Num}_2(v))\mod 2^8)$$

    The addition modulo $2^{32}$ of two numbers in binary system of length $32$ and $8$, is given by the mapping:
    $$\text{add}_{\text{Adr}} : \text{Adr}\times \text{Val}\rightarrow \text{Adr} \\ (a,v) \mapsto \text{bin}_{32} ((\text{Num}_2(a)+\text{Num}_2(v))\mod 2^{32})$$

    A queue is a data structure with the operations „enqueue“, „dequeue“ and „first“.

    In our memory model a queue can be represented with at most $2^8$ values by an address. The address and the next field save an pointer at the beginning and the end of the queue. The pointer gives the address relative to the basic address +2.

    The mappings init_queue, is_empty, enqueue, dequeue and first are defined as follows:



    For each memory $m \in \text{Mem}$, each address $a \in \text{Adr}$ and each value $v \in \text{Val}$, the init_queue(m, a) initializes a queue at $a$ in $m$, is_empty(m, a) checks if the queue at $a$ in $m$ is empty or not, enqueue(m, a, v) places the value $v$ in the queue at $a$ in $m$, dequeue(m, a) takes the oldest value from the queue at $a$ in $m$ and first(m, a) gives the oldest value of the queue at $a$ in $m$.





    Let $m\in \text{Mem}$ and $a = \text{bin}_{32}(0)$. I want to compute the value of

    first(dequeue(enqueue(enqueue(init_queue(m, a), a, 00101111), a, 00001100), a), a)

    First the most inner function is init_queue(m, a). This initializes a queue at $a$ in $m$.

    Then we have to compute the mapping enqueue(init_queue(m, a), a, 00101111).

    For that we have to compute the $a'=\text{add}_{\text{Adr}}(a,1)$ and $a^{\star}=\text{add}_{\text{Adr}}(a,\text{bin}_8(2))$. How can we do that? I haven't really understood the function $\text{add}$...

  2. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,838
    Thanks
    2,271 times
    Thanked
    707 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #2 Thread Author
    Quote Originally Posted by mathmari View Post
    For that we have to compute the $a'=\text{add}_{\text{Adr}}(a,1)$ and $a^{\star}=\text{add}_{\text{Adr}}(a,\text{bin}_8(2))$. How can we do that? I haven't really understood the function $\text{add}$...
    We have that $a'=\text{add}_{\text{Adr}}(a,1)=\text{bin}_{32}(1)$ and $a^{\star}=\text{add}_{\text{Adr}}(a,\text{bin}_8(2))=\text{bin}_{32}(2)$, right?
    Last edited by mathmari; December 7th, 2016 at 13:04.

  3. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,838
    Thanks
    2,271 times
    Thanked
    707 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #3 Thread Author
    I want to define inductively, using only $\text{add}_{\text{Val}}$, is_empty, dequeue and first, a function sum: Mem × Adr → Val such that for each memory m ∈ Mem and each address a ∈ Adr it holds that sum(m, a) is in the binary system the sum modulo $2^8$ of all values, expressed in binary system of numbers, in the queue at a in m, where the empty sum is 0.

    Does this mean that $\text{sum}(m,a)=\text{bin}_8( (m+a) \mod 2^8)$ ?

Similar Threads

  1. How do we apply the proposition?
    By evinda in forum Differential Equations
    Replies: 4
    Last Post: November 23rd, 2016, 19:06
  2. How to apply the simplex method
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 0
    Last Post: January 7th, 2016, 19:21
  3. Could we apply DFS?
    By evinda in forum Computer Science
    Replies: 17
    Last Post: May 10th, 2015, 14:26
  4. Why can we not apply the theorem?
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 13
    Last Post: November 5th, 2014, 18:13
  5. Apply the Euclidean division
    By evinda in forum Linear and Abstract Algebra
    Replies: 2
    Last Post: May 1st, 2014, 15:12

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards