Assignment 1

Due Friday March 10, 5pm.

In this assignment you will create one or more programs to answer the following questions. Your code should be accompanied by a write-up in the (digital) format of your choice. Your programs should be accompanied by a build script (if necessary) and unit tests, along with instructions on how to run those tests. Your write-up should contain the result of running each of your programs on the requested input, along with timing information where relevant.

Version control

Using the repository you created for assignment zero, create a README file in the main directory, outlining the language(s) you are using, as well as instructions for running your code and your tests (this can be done using markdown or plain text). Submission is easy: I will pull the latest commit before the due date.

Subnormal numbers

  1. Give an example of a subnormal number.

  2. Write a routine that outputs true if a given float is a subnormal number and false otherwise. Write tests to confirm this with examples of your own.

  3. Subnormal numbers allow one to represent smaller digits than can normally be represented, but this comes at a cost. When leading digits of the mantissa are set to zero, this takes away precision. This phenomenon is called gradual underflow.

    Write a routine that outputs the tightest upperbound for the relative error due to rounding to that float. In other words, for a given float \(x\), compute

    $$ f(x) = \sup_{z:\,\text{float}(z)=x} \left|\text{Rel}(z,x)\right|. $$

    For example, if input was not a subnormal number, there are a full 52 bits of precision in the mantissa, and therefore, the relative error due to rounding is bounded above by \(2^{-52}\). Again, write appropriate tests.

Quadratic formula

Consider solving the quadratic equation

$$ x(x - 2b) = c $$

for some constants \(b\) and \(c\geq 0\), which ensures the solutions are real.

  1. Using the quadratic formula, for a given input of \(b\), write a routine that outputs a pair of solutions \(x\) that satisfies the above equation.

    Write a test file that verifies your solutions by inputing them back into the equation above and verifying the magnitude of relative error of the left side is less than \(10^{-12}\) with respect to the right side.

    UPDATE (3/6): To test the accuracy of the two roots, calculate the theoretical value of \(x_1^* + x_2^*\) and \(x_1^* x_2^*\) and test against those values in terms of relative error. Evaluating the quadratic can be numerically unstable when \(b^2/c\) is large.

  2. Add unit tests for scenarios when \(b\) is large in magnitude and when \(c\) is small. What happens to the relative error and why? (Note: don’t worry about when \(b^2/c > 2^{52}\))

  3. There is more than one way to write the quadratic formula. Multiply the numerator and denominator by the conjugate to move the square root term to the denominator.

    Write a new routine that selectively chooses the more numerically stable formula depending on the right situation. Verify it passes all previous tests.

Cache efficiency

Credit to Daniel Fleischman for designing this problem.

Suppose we have a machine with a 12-way associative, 6MiB L3 cache with a 64-byte cache line, and we run the following C++ code on it.

int f(int array[], int size, int npasses)
{
  int result = 0;
  for (int pass = 0; pass < npasses; pass++) {
    for (int i = pass; i < size; i += npasses) {
      result += array[i] * pass;
    }
  }
  return result;
}

Knowing that an int takes up 4 bytes, we are interested in computing the worst-case value of npasses for a sufficiently large array array.

  1. What is the worst-case value of npasses for our hypothetical machine with a 6MiB L3 cache and a 64-byte cache line?

  2. What is the worst-case value of npasses on your machine?

    It will be helpful to look into the architecture of your computer to answer this question. If you are on Linux, the following files may be useful:

    /proc/cpuinfo
    /sys/devices/system/cpu/cpu0/cache/index3/size
    /sys/devices/system/cpu/cpu0/cache/index3/coherency_line_size
    /sys/devices/system/cpu/cpu0/cache/index3/number_of_sets
    /sys/devices/system/cpu/cpu0/cache/index3/ways_of_associativity
    

    Note that there are additional files you might find interesting. There are (likely) several other directories you can replace cpu0 with (e.g. cpu1, cpu2, cpu3, cpu4, cpu5, cpu6, cpu7 on my machine), while replacing index3 with index0, index1, or index2 will yield information on different caches.

    Although the code sample is written in C++ (or C) you can in principle write this in any language, although your assumption about the size of an int might change.

  3. Create a plot of the running time of the function for a variety of npasses values, including the worst-case value. State the size of the array you are using.

def f(arr, passes):
    result = 0
    for p in range(passes):
        for x in arr[p::passes]:
            result += x * p

Submission

There is not a particular format I want for submission, but there are several important things to consider.

  • Submit code that runs.

    I cannot give you credit for something that does not compile or run. It is extremely bad form in a programming course.

  • Write individual functions for individual problems.

    I should be able to find a function that outputs True or False depending on the input’s subnormality, for example.

  • All such functions should be accompanied with tests.

    Usually these tests are located in seperate files. Use the naming conventions for each language (e.g. for python script script.py, the testing file should be named test_script.py). All such tests should be able to be run from the language’s unittesting framework.

  • Use some build script to compile any code or tests.

    GNU Make or SCons is preferred.

  • Use README to explain how to compile and run code/tests.

    Anything non-obvious should go there. Don’t assume I know everything/anything about your repository.

  • Anything non-code related that still needs an answer (e.g. any math question) should go in a write-up.

    If you use TeX, add a compile option in the build script. The format doe not matter as long as I can read it, but PDF is best because it’s portable (it’s in the name).

Other than that, feel free to organize everything the way you want. Feel free to use subdirectories, individual files for seperate problems, or anything else to keep your repository tidy.