Tutorial 3 - 2010 - Solution

From Process Model Formulation and Solution

Jump to: navigation, search
Due date(s): 30 September 2010
Nuvola mimetypes pdf.png (PDF) Tutorial questions
Nuvola mimetypes pdf.png (PDF) Solutions, prepared by Elliot Cameron
Other instructions Hand-in at class.

Could not pull and update the repository; please report this problem to site administrator.

Tutorial solutions: Elliot Cameron.

Tutorial objectives

Question 1 [1]

  • Convert from binary to decimal: \((0.10101)_{2}\)
  • Convert from decimal to binary: \((32.625)_{10}\)
  • Convert from decimal to binary: \((0.2)_{10}\)

Solution

  1. \((0.10101)_{2}\)

    \(\underbrace{\begin{array}{ccccccc} \underbrace{0}_{0\text{x}2^{0}} & . & \underbrace{1}_{1\text{x}2^{-1}} & \underbrace{0}_{0\text{x}2^{-2}} & \underbrace{1}_{1\text{x}2^{-3}} & \underbrace{0}_{0\text{x}2^{-4}} & \underbrace{1}_{1\text{x}2^{-5}} \end{array}}_{0.0 + 0.5 + 0.0 + 0.125 + 0.0 + 0.03125 = 0.65625}\)

    Therefore

    \((0.10101)_{2} = (0.65625)_{10}\)

  2. \((32.625)_{10}\)

    Start to the left of the decimal point (i.e. Representing 32 in binary)

    \(log_{2}(32) = 5 \rightarrow \text{This helps us determine how many binary digits are required}\)

    Rounding 5 up to 5 (obviously)

    \(2^{5} = 32 \rightarrow (32 - 32 = 0)\)

    Therefore

    \(1\text{x}2^{5}+0\text{x}2^{4}+0\text{x}2^{3}+0\text{x}2^{2}+0\text{x}2^{1}+0\text{x}2^{0} = (100000)_{2} = (32)_{10}\)

    Moving to the right of the decimal place

    \(2^{-1} = 0.5 \rightarrow (0.625 - 0.5 = 0.125)\)

    \(2^{-2} = 0.25 \rightarrow (0.125 < 0.2)\) : therefore we move to the next digit

    \(2^{-3} = 0.125 \rightarrow (0.125 - 0.125 = 0.0)\)

    Solution:

    \(1\text{x}2^{5}+0\text{x}2^{4}+0\text{x}2^{3}+0\text{x}2^{2}+0\text{x}2^{1}+0\text{x}2^{0}+1\text{x}2^{-1}+0\text{x}2^{-2}+1\text{x}2^{-3} = (100000.101)_{2} = (32.625)_{10}\)

  3. \((0.2)_{10}\)

    Start to the left of the decimal point (i.e. Representing 0 in binary)

    \((0)_{10} = (0)_{2}\)

    Moving to the right of the decimal place

    \(2^{-1} = 0.5 \rightarrow (0.2 < 0.5)\) : therefore we move to the next digit

    \(2^{-2} = 0.25 \rightarrow (0.2 < 0.25)\) : therefore we move to the next digit

    \(2^{-3} = 0.125 \rightarrow (0.2 - 0.125 = 0.075)\)

    \(2^{-4} = 0.0625 \rightarrow (0.075 - 0.0625 = 0.0125)\)

    \(2^{-5} = 0.03125 \rightarrow (0.0125 < 0.03125)\) : therefore we move to the next digit

    \(2^{-6} = 0.015625 \rightarrow (0.0125 < 0.015625)\) : therefore we move to the next digit

    \(2^{-7} = 0.0078125 \rightarrow (0.0125 - 0.0078125 = 0.0046875)\)

    \(2^{-8} = 0.00390625 \rightarrow (0.0046875 - 0.00390625 = 0.00078125)\)

    \(2^{-9} = 0.001953125 \rightarrow (0.00078125 < 0.001953125)\) :move to the next digit

    \(2^{-10} = 0.0009765625 \rightarrow (0.00078125 < 0.0009765625)\) : move to the next digit

    \(2^{-11} = 0.00048828125 \rightarrow (0.00078125 - 0.00048828125 = 0.00029296875)\)

    \(2^{-12} = 0.000244140625 \rightarrow (0.00029296875 - 0.000244140625 = 0.000048828125)\)

    \(\ldots\)

    Solution

    \[\begin{split}0\text{x}2^{0}+0\text{x}2^{-1}+0\text{x}2^{-2}+1\text{x}2^{-3}+1\text{x}2^{-4}+0\text{x}2^{-5}+0\text{x}2^{-6}+1\text{x}2^{-7}+1\text{x}2^{-8}+0\text{x}2^{-9}+0\text{x}2^{-10}+1\text{x}2^{-11}+1\text{x}2^{-12}\\\approx (0.{\bf \overline{0011}})_{2} = (0.2)_{10}\end{split}\]
    \[\]

    What this questions aims to show you is, just as in the decimal system, there are numbers that cannot be represented finitely in binary (think 1/3 in decimal notation).

Question 2 [1]

  1. Write, in binary form, the representation for the most negative floating point number that can be stored in an 8-bit word, using 1 bit for the sign, 3 bits for the signed exponent and the remainder for the significand (in normalized form).
  2. What is the decimal equivalent of this number?
  3. What is the machine number next to this one (both in binary and in decimal please)?
  4. Calculate the maximal interval-to-value ratio around these two values. Does it agree with the limit for theoretical machine precision?
  5. As which machine number would -7.22 be stored if the machine used (a) chopping, or (b) rounding?

Solution

  1. We start by recalling that normalized scientific notation assumes that the significand starts with an implied leading digit of 0 (i.e. it falls between the following bounds):

    \(\frac{1}{b} \leq m < 1\)

    Where

    \(m =\) significand

    \(b =\) base

    \(e =\) exponent

    Therefore the most negative 8-bit binary number with 1 bit for the sign, 3 bits for the signed exponent, and 4 bits for the normalized significand is:

    \[\begin{split}\begin{array}{ccc} \underbrace{1}_{\text{sign}} & \underbrace{011}_{\text{exponent}} & \underbrace{1111}_{\text{significand}} \rightarrow -\left(1\text{x}2^{-1}+1\text{x}2^{-2}+1\text{x}2^{-3}+1\text{x}2^{-4}\right)\text{x}2^{\left(1\text{x}2^{0}+1\text{x}2^{1}\right)} = -0.9375 \text{x} 2^{3} \end{array}\end{split}\]
    \[\]
  2. \[\begin{split}\begin{array}{ccc} \underbrace{1}_{\text{sign}} & \underbrace{011}_{\text{exponent}} & \underbrace{1111}_{\text{significand}} = -0.9375 \text{x} 2^{3} = -0.9375 \text{x} 8 = -7.5 \end{array}\end{split}\]
    \[\]
  3. The next closest machine number is the next physically representable number in the 8-bit floating point system. Since no more space exists "above" the current significand we must go "down" in magnitude. Therefore:

    \[\begin{split}\begin{array}{ccc} \underbrace{1}_{\text{sign}} & \underbrace{011}_{\text{exponent}} & \underbrace{1110}_{\text{significand}} = -0.8750 \text{x} 2^{3} = -7.0 \end{array}\end{split}\]
    \[\]
  4. We start by estimating the theoretical machine precision:

    \(t = 4\) : number of significant digits in the significand

    \(\beta = 2\) : base of number system

    \(\epsilon_{mach} = \beta^{1-t} = 2^{1-4} = 0.125\)

    Next we test the maximal interval-to-ratio value on either side of the values from part (a)/(b) and (c)

    \(\frac{|x_{1}-x_{2}|}{|x_{1}|} = \frac{|(-7.0)-(-7.5)|}{|(-7.0)|} = 0.0714\ldots \leq \epsilon_{mach}\)

    \(\frac{|x_{1}-x_{2}|}{|x_{2}|} = \frac{|(-7.0)-(-7.5)|}{|(-7.5)|} = 0.0666\ldots \leq \epsilon_{mach}\)

    It is easy to see above that the maximal interval-to-value ratios agree with the upper \(\epsilon_{mach}\) limit

  5. As observed in parts (a) - (c) the two closest machine numbers to -7.22 are -7.0 and -7.5. Therefore the effect of chopping (rounding towards 0) and rounding (rounding to the closest avaiable machine number) would result in the same floating point value: -7.0.

Question 3 [1.5]

  1. Increasingly we are seeing cameras being used in chemical processes to monitor and control the process, especially systems that deal with foods and solid products. How much space, in kilobytes, is required to store a digital photo with 640 rows and 480 columns of pixels and 3 layers (red, green and blue) using uint8 integer representation?

  2. Computer systems are used to archive data from each electronic measurement, such as temperature, pressure, flow measurements, etc. Each measurement is called a tag. At your plant, you wish to store 16,525 tags, recorded once per second and stored in double precision. How much space would be required on the company's server, in terabytes, to store a single copy of 1 year of data? What difference does it make to store the data in single precision?

  3. How many data points can you store in double precision in 1500 megabytes of RAM? (For example, MATLAB on a 32-bit Windows Vista machine cannot create arrays greater than 1428 megabytes.)

    Use the fact that:

    • 1024 bytes = 1 kilobyte
    • 1024 kilobytes = 1 megabyte
    • 1024 megabytes = 1 gigabyte
    • 1024 gigabyte = 1 terabyte = 240 bytes

Solution

  1. Recall that the uint8 integer representation refers to an unsigned integer with no exponential term. Therefore it refers to an integer that can store a value from 0 - 255. As such this question is simply asking us how much memory would be required to store a 640x480 pixel image using the 256/256/256 RGB colour notation. Now, if each pixel in each of the RGB matrices is represented by a uint8 then each value will logically take up 8 bits of memory. If each of the three colour matrices contains 640x480 values and we assume a standard 8 bit byte then the total space required to store the photo would be:

    \[Space = \underbrace{3}_{\text{rgb}} \times \underbrace{640*480}_{\text{pixels}} \times \underbrace{8\;\text{bits}}_{\text{uint8}} = 7372800\;\text{bits}*\frac{1\;\text{byte}}{8\;\text{bit}}*\frac{1\;\text{kilobyte}}{1024\;\text{byte}} = 900\;\text{kilobytes}\]
    \[\]
  2. Recall that a standard floating point double precision number takes up 64 bits (8 bytes) of memory. We start this problem by calculating the number of values to be stored in one year.

    \[\text{Values} = 16,525\frac{\text{values}}{s}\times\frac{60\;s}{1\;\text{min}}\times\frac{60\;\text{min}}{1\;\text{hr}}\times\frac{24\;\text{hr}}{1\;\text{day}}\times\frac{365\;\text{day}}{1\;\text{year}} = 521,132,400,000\frac{\text{values}}{\text{year}}\]
    \[\]

    Therefore the memory requirement is:

    \[Memory = 521,132,400,000\frac{\text{values}}{\text{year}}\cdot8\frac{\text{bytes}}{\text{value}}\cdot\frac{1\;\text{kilobyte}}{1024\;\text{byte}}\cdot\frac{1\;\text{megabyte}}{1024\;\text{kilobyte}}\cdot\frac{1\;\text{gigabyte}}{1024\;\text{megabyte}}\cdot\frac{1\;\text{terabyte}}{1024\;\text{gigabyte}} = 3.79\;\text{terabytes}\]
    \[\]

    A floating point single precision value takes up exactly half as much space as a floating point double precision number (i.e. 32 bits = 4 bytes). Therefore storing the same tags in single precision would take up \(1.9\;TB\).

  3. If we take the absolute value of RAM available (i.e. 1500 MB) and the standard definition of a floating point double precision number (i.e. 64 bits = 8 bytes), then

    \(1,500\;\text{MB}\times\frac{1024\;\text{KB}}{1\;\text{MB}}\times\frac{1024\;\text{B}}{1\;\text{kB}} = 1,572,864,000\;\text{bytes}\)

    Therefore the number of double precision values that could be stored would be.

    \(\text{Number} = 1,572,864,000\;\text{bytes}\times\frac{1\;\text{value}}{8\;\text{bytes}} = 196,608,000\;\text{values}\)

    If we use the maximum MATLAB array size then.

    \(1,428\;\text{MB}\times\frac{1024\;\text{KB}}{1\;\text{MB}}\times\frac{1024\;\text{bytes}}{1\;\text{kB}} = 1,497,366,528\;\text{bytes}\)

    Therefore the number of double precision values that could be stored in MATLAB would be.

    \(\text{Number} = 1,497,366,528\;\text{bytes}\times\frac{1\;\text{value}}{8\;\text{bytes}} = 187,170,816\;\text{values}\)

Question 4 [1]

Consider the following system of linear algebraic equations:

\[\begin{split}\left\{\begin{array}{rcl} 2 x_1 -2x_2 +4 x_3 & = & 0 \\ x_1 -3 x_2 + 4x_3 & = & -1 \\ 3x_1 - x_2 +5x_3 &= & 0\end{array}\right.\end{split}\]
  1. Use Gauss elimination (forward elimination and backward substitution) to solve these equations for \((x_1,x_2,x_3)\).
  2. Validate your solution in either Python or MATLAB.

Solution

  1. We are asked to solve this system of equations using Gauss Elimination (without partial pivoting).

    \[\begin{split}\begin{array}{ccccc} 2x_{1} & -2x_{2} & +4x_{3} & = & 0\\ x_{1} & -3x_{2} & +4x_{3} & = & -1\\ 3x_{1} & -x_{2} & +5x_{3} & = & 0\end{array} \rightarrow \left[ \begin{array}{ccc} 2 & -2 & 4 \\ 1 & -3 & 4 \\ 3 & -1 & 5\end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3}\end{array} \right] = \left[ \begin{array}{c} 0 \\ -1 \\ 0 \end{array} \right]\end{split}\]
    \[\]

    Forward elimination

    Divide row 1 by element (1,1)

    \[\begin{split}\left[ \begin{array}{ccc} 1 & -1 & 2 \\ 1 & -3 & 4 \\ 3 & -1 & 5\end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3}\end{array} \right] = \left[ \begin{array}{c} 0 \\ -1 \\ 0\end{array} \right]\end{split}\]
    \[\]

    Subtract row 1 from row 2 and 3 times row 1 from row 3 to eliminate all elements in column 1 below the diagonal element

    \[\begin{split}\left[ \begin{array}{ccc} 1 & -1 & 2 \\ 0 & -2 & 2 \\ 0 & 2 & -1\end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3}\end{array} \right] = \left[ \begin{array}{c} 0 \\ -1 \\ 0 \end{array} \right]\end{split}\]
    \[\]

    Divide row 2 by element (2,2)

    \[\begin{split}\left[ \begin{array}{ccc} 1 & -1 & 2 \\ 0 & 1 & -1 \\ 0 & 2 & -1\end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3}\end{array} \right] = \left[ \begin{array}{c} 0 \\ 0.5 \\ 0\end{array} \right]\end{split}\]
    \[\]

    Subtract 2 times row 2 from row 3 to eliminate all elements in column 2 below the diagonal element

    \[\begin{split}\left[ \begin{array}{ccc} 1 & -1 & 2 \\ 0 & 1 & -1 \\ 0 & 0 & 1\end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3}\end{array} \right] = \left[ \begin{array}{c} 0 \\ 0.5 \\ -1\end{array} \right]\end{split}\]
    \[\]

    Backwards substitution

    Subtract -1 times row 3 from row 2 and 2 times row 3 from row 1 to eliminate all elements in column 3 above the diagonal element

    \[\begin{split}\left[ \begin{array}{ccc} 1 & -1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3}\end{array} \right] = \left[ \begin{array}{c} 2 \\ -0.5 \\ -1\end{array} \right]\end{split}\]
    \[\]

    Subtract -1 times row 2 from row 1 to eliminate all elements in column 2 above the diagonal element

    \[\begin{split}\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ x_{3}\end{array} \right] = \left[ \begin{array}{c} 1.5 \\ -0.5 \\ -1\end{array} \right]\end{split}\]
    \[\]
  2. Checking this solution in MATLAB:

    EDU>> A = [2,-2,4;
    1,-3,4;
    3,-1,5];
    EDU>> b = [0;-1;0];
    EDU>> x = A\b
    
    x =
    
        1.5000
       -0.5000
       -1.0000

    Checking this solution in Python:

    In [1]: A = np.array([[2,-2,4],[1,-3,4],[3,-1,5]])
    
    In [2]: b = np.array([[0],[-1],[0]])
    
    In [3]: x = np.linalg.solve(A,b)
    
    In [4]: print(x)
    
    [[ 1.5]
     [-0.5]
     [-1. ]]

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox