HW2 Numbers

In this assignment,

You will consider multiple number representations and how they connect to applications in computer science. You will also practice tracing and working with algorithms.

Instructions and academic integrity reminders for all homework assignments in CSE20 this quarter are on the class website and on the hw1-definitions-and-notations assignment.

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw2-numbers”.

Resources: To review the topics you are working with for this assignment, see the class material from Friday of Week 1 and Monday and Wednesday of Week 2. We will post frequently asked questions and our answers to them in a pinned Piazza post.

Assigned questions

1. (Graded for fair effort completeness¹) Pick a nonnegative integer between 100 and 1000 (inclusive) and express it using at least three different representations, at least two of which must be ones discussed in class. Include at least one trace of using procedure \(baseb1\) from page 16 of the Week 0 and 1 notes to calculate the base \(b_1\) expansion of your number (for your choice of \(b_1\)) and include at least one trace of using procedure \(baseb2\) from page 16 of the Week 0 and 1 notes to calculate the base \(b_2\) expansion of your number (for your choice of \(b_2\)).

   Extra; not for credit: Consider choosing representations that might be useful in some way; what would make one representation more useful than another?

2. In this question, we will use recursive definitions to give a precise description of the set of strings that form octal (base \(8\)) expansions and the values of those expansions. Let’s start by defining the set of possible coefficients \[C_8 = \{ 0, 1, 2, 3, 4, 5, 6, 7\}\]

   1. (Graded for fair effort completeness) Fill in the recursive definition of the set of all strings that form octal expansions, \(S_8\):

      Definition The set \(S_8\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \textrm{If } x \in \underline{\phantom{\hspace{2in}}} \textrm{, then } x \in S_8\\ \textrm{Recursive Step: } & \textrm{If } s \in S_8 \textrm{ and } x \in C_8 \textrm{, then } \underline{\phantom{\hspace{2in}}} \in S_8 \end{array}\]

   2. (Graded for correctness²) Consider the function \(v_8: S_8 \to \mathbb{Z}^+\) defined recursively by

      Basis Step: If \(x \in C_8\), then \(v_8 (x) = x\).

      Recursive Step: If \(s \in S_8\) and \(x \in C_8\), then \(v_8 (sx) = 8v_8(s) + x\), where the input \(sx\) is the result of string concatenation and the output \(8 v_8 (s)\) is the result of integer multiplication.

      Calculate \(v_8(104)\), including all steps in your calculation and justifications for them.

   3. (Graded for fair effort completeness) It turns out³ that for any string \(u\) in \(S_8\), the value of the octal expansion \((u)_8\) equals \(v_8(u)\). Using this fact, write an expression relating the value of \((u000)_8\) to the value of \((u)_8\) and justify it.

3. (Graded for correctness) Recall that, mathematically, a color can be represented as a \(3\)-tuple \((r, g, b)\) where \(r\) represents the red component, \(g\) the green component, \(b\) the blue component and where each of \(r\), \(g\), \(b\) must be from the collection \(\{x \in \mathbb{N}\mid 0 \leq x \leq 255 \}\).

   As an alternative representation, in this assignment we’ll use base \(16\) fixed-width expansions to represent colors as single numbers.

   Definition: A hex color is a nonnegative integer less than or equal to \(16777215\). For \(n\) a hex color, we define its red, green, and blue components by first writing its base \(16\) fixed-width \(6\) expansion \[n = (r_1r_2g_1g_2b_1b_2)_{16,6}\] and then defining \((r_1r_2)_{16,2}\) is the red component, \((g_1g_2)_{16,2}\) is the green component, and \((b_1b_2)_{16,2}\) is the blue component.

   ---

   Sample response that can be used as reference for the detail expected in your answer:

   In RGB codes⁴ white is represented as maximum red, maximum green, and maximum blue and so has \((FF)_{16,2}\) as each of these components. This means that the hex color for white is \((FFFFFF)_{16,6}\) which is the value \[15\cdot 16^5 + 15 \cdot 16^4 + 15 \cdot 16^3 + 15 \cdot 16^2 + 15 \cdot 16^1 + 15 \cdot 16^0 = 16^6 - 1 = 16777215\]

   ---

   1. Write the hex color representing red (with no green or blue) in base \(16\) fixed-width \(6\) and also calculate its value (using usual mathematical conventions). Include your (clear, correct, complete) calculations.

   2. Write the hex color representing green (with no red or blue) in base \(16\) fixed-width \(6\) and also calculate its value (using usual mathematical conventions). Include your (clear, correct, complete) calculations.

   3. Write the hex color representing blue (with no red or green) in base \(16\) fixed-width \(6\) and also calculate its values (using usual mathematical conventions). Include your (clear, correct, complete) calculations.

   4. The human eye can’t distinguish between some hex colors because of physical limitations. Give an example of two hex colors \(c_1\) and \(c_2\) such that they look indistinguishable (the colors they represent are very very similar) but \[c_1 - c_2 > 50000\] Justify your choice with (clear, correct, complete) calculations and/or references to definitions, and connecting these calculations and/or definitions with the desired properties. Include squares with each of your two colors so that we can see how indistinguishable they are.

      Pro tip: To show a color, you can use the following LaTeX source code:

      \definecolor{UCSDaccent}{RGB}{0,198,215}

      \textcolor{UCSDaccent}{\rule{1cm}{1cm}}

      which produces

      ---

      Notice that the code to define the color uses the decimal-like values for each of the red, green, and blue components. For the UCSD accent color we defined, the base \(16\) fixed-width \(2\) values are: red is \((00)_{16,2}\), green is \((C6)_{16,2}\), blue is \((D7)_{16,2}\).

      Extra; not for credit: What does this mean about the choice of hex color for representing colors? What are advantages and disadvantages of this representation?

4. (Graded for correctness) In class (Week 2 notes page 7), we discussed fixed-width addition. In this question we will look at fixed-width multiplication. The algorithm for fixed-width multiplication is to multiply using the usual long-multiplication algorithm (column-by-column and carry), and dropping all leftmost columns so the result is the same width as the input terms. For each of the examples below, consider whether this algorithm gives the correct value for the product of the two numbers, based on the way the bitstrings are interpreted.

   ---

   Sample response that can be used as reference for the detail expected in your answer:

   The fixed-width \(5\) multiplication of \([00101]_{2c,5}\) and \([00101]_{2c,5}\) does not give the correct value for the product, as we can see from the following calculation.

   First, we calculate the values: \[[00101]_{2c,5} = 0\cdot (-2^4) + 0\cdot 2^3 + 1 \cdot 2^2 + 0\cdot 2^1 + 1 \cdot 2^0 = 4 + 1 = 5\] so the correct value for the product is \(5 \cdot 5 = 25\), which cannot be represented in 2s complement width 5 (the largest positive number that can be represented in 2s complement width 5 is \([01111]_{2c,5} = 8 + 4 + 2 + 1 = 15\)).

   When we perform the fixed-width \(5\) multiplication algorithm: \[\begin{aligned} & 0~ 0~ 1~ 0~ 1\\ \times & 0~ 0~ 1~ 0~ 1\\ &\overline{0~ 0~ 1~ 0~ 1}\\ + {0~} & {0~0~0~0~~}\\ + {0~0~} & {1~0~1~~}\\ \overline{\phantom{0~0~}}&\overline{1~ 1~ 0~ 0~ 1}\\ \end{aligned}\]

   we get \([11001]_{2c,5} = 1\cdot (-2^4) + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = -16 + 8 + 1 = -7\), which is not the required value.

   ---

   1. Does the fixed-width \(5\) multiplication of \([11101]_{2c,5}\) and \([11011]_{2c,5}\) give the correct value for the product? Justify your answer with (clear, correct, complete) calculations and/or references to definitions, and connecting these calculations and/or definitions with your answer.

   2. Does the fixed-width \(5\) multiplication of \([00100]_{2c,5}\) and \([11100]_{2c,5}\) give the correct value for the product? Justify your answer with (clear, correct, complete) calculations and/or references to definitions, and connecting these calculations and/or definitions with your answer.