Function Plots
- Summary
- You will write a program to plot arbitrary functions using C functions, pointers, and arrays.
- Objectives
-
- Learn to apply good functional decomposition
- Practice working with arrays and pointers
- Apply development principles in support of testing
Background
Imagine you've been transported back to 1990 and you have been called on to write part of the plot functionality for a soon-to-be popular line of graphing calculators. How would you solve the problem?
We don't have real graphing calculators at our disposal, but the
terminal will serve as a reasonable proxy. One original line of
graphing calculators allowed the user to enter a generic function
with text like y=2*sin (x)-x^3. Calculating values
like that is certainly straightforward enough in C, but getting the
correct locations of the dots
on the screen takes some thought.
Now, what tasks might our plotter need to do? Let's try to answer that question, building up a list of (eventual) functions we'll need to write.
- Draw graphs. Better make a function for that. We can store the values to be plotted in an array.
-
Convert indices. Before we can store a mathematical function
value f(x) into an array
at
values[index], we need a way to convert the array index to the mathematical function input x. - Find ranges. In order to see all of a function on the screen, we'll need to find its minimum and maximum (calculated) function value over the plotted domain.
- Quantize values. To determine which of the discrete rows to draw a marker for the function, we'll need to quantize those continuous values, which is to say convert them into discrete integers.
- Test everything. Of course, we'll want to rigorously test all these pieces to make sure they work correctly.
We'll probably think of some other stuff along the way, but often writing out comments and working from the top down to the details as we stub out functions helps us figure that out. Now, let's go to work.
Assignment
Write a program called plot.c that will contain the
functions for generating the plots and testing the procedures within,
all according to the following specifications.
Note that because we'll be drawing to a screen with very coarse
resolution, we'll be using float
variable types; the double type has
far more precision than necessary. Except in specialized hardware
such as GPUs
or DSPs, it is rare on
today's general computer systems for there to be any significant performance
difference between these two types.
Convert Indices
As mentioned above, a mathematical function
value f(x) takes arbitrary values x as
inputs. However, we are going to store the output values
f(x) into an array at values[index].
Thus, we will need a way to convert from the array index
(corresponding to the column on the screen)
to the mathematical function input x.
Thinking in the other direction, one would typically convert (or quantize) an arbitrary continuous value x to one of a discrete set of possibilities with a transformation like where k is a scale factor, t is a shift (or translation), and ⌊·⌋ represents the floor function. The result is the discrete index i.
Write the simple inverse of this operation, which takes an index, scale, and shift factor and produces the resulting continuous value. (in other words, solve the equation above for x, so that get_x produces that value given i, k, and t; in this case the floor can be ignored).
float
get_x (int index, float x_scale, float x_shift)Examples
get_x (0,5,-2);2.0
get_x (1,5,-2);7.0
get_x (5,1,2);3.0
Testing
Along with documentation, one might arguably want to write tests for your function before you write the function itself, because they both require you to understand what you want from your function before you set about actually writing it. Such a process is called test-driven development.
In the remainder of the assignment, you might consider writing a stub of the required functions, then writing your tests, before returning to finally implement the functions themselves.
Test Macros
An exercise in the C preprocessor lab gives a simple technique for constructing unit tests similar to the following:
/* Macro for testing. Requires variable numErrors be defined in scope of use. */
#define TEST(EXPR,RESULT) \
if ((EXPR) != (RESULT)) { \
++numErrors; \
printf("Did not get expected result %s for %s.\n", #RESULT, #EXPR); \
}Add this macro to your program.
Unfortunately, we should not test floating point values using the
equality operator ==, because the math libraries may
differ in how they compute values, leading to slight
variations (usually in the mantissa).
Write another macro called FTEST that takes an
additional parameter TOL (an error tolerance) and checks
whether
using the math.h function fabsf (since our
functions will involve float rather than
double values).
Test Functions
We can now begin to assemble a test harness for our procedures, beginning with the following functions.
/* Print a report of a collection of unit tests.
* Prints OK when no errors and FAIL with a count otherwise.
*/
void
reportTests (int numErrors)
{
if (numErrors>0)
printf (" FAIL: %d errors\n",numErrors);
else
printf (" OK\n");
} // reportTests
/* Test all functionality by running test functions.
* Returns the total number of errors.
*/
int
testAll (void)
{
int numErrors = 0;
numErrors += testGetX();
if (numErrors==0)
printf ("TESTS PASSED\n");
else
printf ("TOTAL ERRORS: %d\n",numErrors);
return numErrors;
} // testAll
Include the functions reportTests
and testAll in your program, then also add and complete
the function below, which should run several tests of
your get_x routine using your test macros and return
the number of errors.
int
testGetX (void)
{
int numErrors = 0;
printf ("--GETX TESTS--");
// Add your test code here
FTEST( get_x(0, 5, -2), 2.0f, 1e-5f ) // Example 1 (above)
reportTests (numErrors);
return numErrors;
} // testGetXYou should include a complete set of tests, different from the examples shown above.
For now, your main procedure can simply consist of a
call to testAll:
int
main (void)
{
return testAll();
}
Note that a return value of 0 from main
indicates to the caller (i.e., the user who typed the command in the
terminal) that the program completed successfully.
Cosine and Cubic Functions
Now that you can move from array indices to mathematical function arguments, you can complete two relatively simple C procedures to fill in the raw values for plotting.
Cosine
The C standard library includes several mathematical functions, which
are exposed to your program through
the
math.h
header file (see King 23.3–23.4).
Write the following procedure, which should use get_x to
fill the given array values[] (having the
provided length len) with the values of cos(x).
void
cosine (float values[], size_t len, float x_scale, float x_shift )
Note that
size_t
is a system-independent type (typically an unsigned integer) used to
represent the maximum size of any object. It is defined in several
headers, including stdio.h and stdlib.h.
Examples
const double PI = 3.14159265358979323846;
float data[5] = {0,0,0,0,0};
cosine (data, 1, 0, 0);{1.0, 0.0, 0.0, 0.0, 0.0}
cosine (data, 1, 0, PI);{-1.0, 0.0, 0.0, 0.0, 0.0}
cosine (data, 5, PI/2, 0);{1.0, -0.0, -1.0, 0.0, 1.0}
Polynomial
A cubic (degree 3) function computes the values
Write the following procedure, which will also use get_x
to fill the given array values with a polyonial y(x)
using the coefficients in coeffs[].
void
polynomial (float coeffs[], size_t degree, float values[], size_t len,
float x_scale, float x_shift )
Your implementation should be as efficient as possible by re-using
incrementally computed values. (Hint: powf will
not be efficient.)
Examples
float data[4] = {0,0,0,0};
float flat[1] = {5};
polynomial (flat,0,data,4,1,0);{5.0, 5.0, 5.0, 5.0}
float line[2] = {1,2};
polynomial (line,1,data,4,1,0);{1.0, 3.0, 5.0, 7.0}
float square[3] = {0,0,1};
polynomial (square,2,data,4,1,0);{0.0, 1.0, 4.0, 9.0}
float cube[4] = {0,0,0,-1};
polynomial (cube,3,data,4,1,2);{8.0, 1.0, 0.0, -1.0}
Testing
Add functions testCosine and testPolynomial
in the style of testGetX to test these two
procedures. Be sure to augment testAll to include these
two test routines.
Note: While your test macros only operate on individual
values, your test routine can use
a for loop to run multiple tests of
values (or outcomes of a procedure). Additionally, the length of the
arrays have been specified as parameters (rather than
globally #defined values precisely
because doing so allows you to construct small tests.
Range
Now that you have calculated the values of the function over an implicitly-specified domain, we'll need to determine the range of the function so we can eventually plot it using the full extent of the available screen.
Complete the following procedure, which should place the smallest and largest value contained in the array in the pointers specified.
void
range (const float values[], size_t len, float * p_min, float * p_max)Testing
Add function testRange to test your procedure. Be sure
to augment testAll to include this test routine.
Quantization
The domain of the function to be plotted is already discrete—it's simply the indices of the values in the array. However, the range of that function remains arbitrary. We therefore need a procedure that uses the quantization calculation above to shift, scale, and round-off the y-values so we can use the result as a discrete row for the plot point.
The quantization process is illustrated in the figure at right, where a portion of a sine wave (shown in red) is quantized to eight different discrete levels (shown as the curve in blue).
Write the procedure quantize, which takes a minimum and
maximum possible value (such as would be given by range)
as well as the number of discrete levels, and returns
the discrete quantum between 0 and levels-1.
int
quantize (double value, int levels, float min, float max )Hint: The quantization calculation should look very similar to the formula (involving a floor operation) given above.
Examples
quantize (1.0, 10, 0, 100));0
quantize (49.0, 10, 0.0, 100.0));4
quantize (50.0, 10, 0.0, 100).0);5
quantize (99.0, 10, 0.0, 100.0));9
quantize (100.0, 10, 0.0, 100.0));9
quantize (sin (PI/4), 24, -1, 1);20
Testing
Add a function testQuantize to your test harness; it
should of course provide a complete set of test to convince you your
code is correct (and your tests should be different than those included
in the examples above).
Scaling
Given that printing to the terminal proceeds left to right and top to bottom, if we jumped straight to plotting now using the pieces we have implemented so far, we'd find ourselves making a lot of repeated calculations. To avoid that scenario, we'll pre-calculate and store the quantized function values.
Write the procedure scale that
applies quantize to each element
of values[] using height levels and stores
the results in scaled[].
void
scale (const float values[], int scaled[], size_t len, size_t height,
float min, float max)
We have added the keyword const to
signal to the compiler (and the programmer) that no assignments
should be made via the variable values.
Testing
Add the function testScale to your test harness to
verify correctness.
Plots
We now have all the pieces we need to generate a text-based plot of a
given set of values. The array values[]
has len elements and the plot should
be height rows high using the given symbol
at the function values (and a space otherwise).
void
plot (const float values[], char symbol, size_t len, size_t height)
For example, when plotted on a screen of height 5, the scaled/quantized
(integer) array {1, 0, 3, 1, 2, 0, 2} should result in
the following output from plot with symbol
'*'. (Row 0 is at the bottom; row 4
is at the top.)
| ' ' | ' ' | ' ' | ' ' | ' ' | ' ' | ' ' | '\n' |
| ' ' | ' ' | '*' | ' ' | ' ' | ' ' | ' ' | '\n' |
| ' ' | ' ' | ' ' | ' ' | '*' | ' ' | '*' | '\n' |
| '*' | ' ' | ' ' | '*' | ' ' | ' ' | ' ' | '\n' |
| ' ' | '*' | ' ' | ' ' | ' ' | '*' | ' ' | '\n' |
Note that to create the intermediate array of quantized values used
for plotting, you'll need to use the parameter len to
specify its size. Your program will therefore need to use
a variable length array (or
VLA) as described in King
8.3 (pp. 174-175).
Testing
Writing functions to automatically score
output procedures
such as plot is rather tricky (plus, you haven't learned
how yet). Instead, I recommend you
write 3–4 simple tests that each briefly describe the output verbally
(i.e., on a single line of terminal output) before
calling plot to visually render the small result (such
as a horizontal or diagonal line).
Wrapping Up
When all your work is complete, you should use the
following main function allowing anyone to either test or
demonstrate your code.
#ifndef NOMAIN
int
main (void)
{
#ifdef TESTING
return testAll();
#endif
float values[SCREEN_WIDTH];
cosine (values, SCREEN_WIDTH, 0.15, 0.0);
printf("Cosine\n");
plot (values, '*', SCREEN_WIDTH, SCREEN_HEIGHT);
float cubic[] = {0,1,18,1};
polynomial(cubic, 3, values, SCREEN_WIDTH, 0.375, 20);
printf("Cubic\n");
plot (values, '*', SCREEN_WIDTH, SCREEN_HEIGHT);
return 0;
} // main
#endif
Your program must include exactly this block of code, especially including the wrapping preprocessor macros. (This will be used to test your code with a separate program.) Failure to do so may result in zero scores for some portions of the assignment.
When compiled without the -DTESTING flag, this
code should produce the following output
(for SCREEN_WIDTH of 80 and SCREEN_HEIGHT
of 60).
Cosine
** ***
* * *
* *
*
*
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
*
* *
*
* *
* *
*
* *
*
* *
* *
* *
* *
* * *
*
* *
* *
* * *
*
* *
* *
* * * *
*** ***
Cubic
*
*
*
*
*
*
*
*
*
*
******** *
** **
* ** *
* **
* ** *
* *
* ** *
* * *
*
* ** *
* * *
** *
* ** *
** **
* ** **
*******
*
*
*
*
*
*
To summarize, your computational pipeline can be thought of something like this.
Whereas the function involves floating point ("real") values for functions like cosine and polynomials, you'll be starting from a discrete integer array index representing the column of the graph and ultimately need to produce the corresponding discrete integer representing the row in which the marker for the function should appear.
Grading
In addition to the general grading guidelines for evaluation, the assignment is worth 33 points.
- [17 points] Main Program
-
[2 points] Function
get_xis correct -
[2 points] Function
cosineis correct -
[3 points] Function
polynomialis correct and efficient -
[2 points] Function
rangeis correct -
[2 points] Function
quantizeis correct -
[2 points] Function
scaleis correct -
[4 points] Function
plotis correct
-
[2 points] Function
-
Evaluation of program Structure, Comments, Design, and Testing.
(Additional points not given, but points may be deducted.) -
[16 points] Testing and Development
- [2 points] Functions give clear and complete pre- and post-conditions
- [1 point] Test plan enumerates the ranges of problem circumstances
-
[10 points] Tests compare cases to be considered with expected outcomes
- [2 points] Macro
FTESTis correct and safe - [1 point] Function
testGetXtests are complete - [1 points] Function
testCosinetests are complete - [1 point] Function
testPolynomialtests are complete - [1 point] Function
testRangetests are complete - [1 point] Function
testQuantizetests are complete - [1 point] Function
testScaletests are complete - [1 point] Function
testPlottests are complete - [1 point] Function
testAllruns all tests
- [2 points] Macro
