High School Mathematics Extensions/Mathematical Programming

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

Before we begin

This chapter will not attempt to teach you how to program rigorously. Therefore a basic working knowledge of the C programming language is highly recommended. It is recommended that you learn as much about the C programming language as possible before learning the materials in this chapter.

Please read the first 7 lessons of "C Programming Tutorial" at About.com if you are unfamiliar with programming or the C programming language.

As you gain programming experience you will appreciate the more specific explanations like The C Programming Wikibook.

Introduction to programming

Programming has many uses. Some areas where programming and computer science in general are extremely important include artificial intelligence and statistics. Programming allows you to use computers flexibly and process data very quickly.

When a program is written, it is written into a textual form that a human can understand. However, a computer doesn't directly understand what a human writes. It needs to be transformed into a way that the computer can directly understand.

For example, a computer is like a person who reads and speaks German. You write and speak in English. The letter you write to the computer needs to be translated for the computer to speak. The program responsible for this work is referred to as the compiler.

You need to compile your English-like instructions, so that the computer can understand it. Once a program has been compiled, it is hard to "un-compile" it, or transform it back into English again. A programmer writes the program (to use our analogy, in English), called source code, which is a human-readable definition of the program, and then the compiler translates this into "machine code". We recommend using the widely available gcc compiler.

When we look at mathematical programming here, we will look at how we can write programs that will solve some difficult mathematical problems that would take us normally a lot of time to solve. For example, if we wanted to find an approximation to the root of the polynomial x⁵+x+1 - this is very difficult for a human to solve. However a computer can do this no sweat -- how?

Programming language basics

We will be using the C programming language throughout the chapter, please learn about the basics of C by reading the first 7 lessons of "C Programming Tutorial" at About.com.

Sample C Program

• Sample C Program

Data Types

Size Constraints: Header files limits.h, and float.h

Computers are machines based on Boolean logic. This means that the computer is based on some method of differentiating a state as true or false, or set and not set. Abstractly we think of computers as using 1's for true or set and 0's for false or not set. We refer to these 1's and 0's as bits. In computers we don't keep track of information as bits. Instead information in a computer is stored in addressable blocks called bytes. A byte is the smallest piece of memory that can be accessed in the computer that is not a bit. When we declare a [scalar] variable in a C program that memory has an address and a length. The address says where the memory starts, and the length states how many bytes are used to express the variable.

The include file <limits.h> is used to define the size of addressable integer types and the include file <float.h> is used to define the size of addressable floating point types. The values in these files are compiler and computer dependent. This means that if you change compilers or compile your program on a different type of computer it may execute differently.

Here are some of the values defined in these two files:

Exercises

Programming With Integers

Discrete programming deals with integers and how they are manipulated using the computer.

Understanding integer division

In C, the command

int number;

number = 3 / 2;

will set aside some space in the computer memory, and we can refer to that space by the variable name number. In the computer's mind, number is an integer, nothing else. After

number = 3 / 2;

numbers equals 1, not 1.5, this is due to that fact that / when applied to two integers will give only the integer part of the result. For example in C:

5 / 2 equals 2

353 / 3 equals 117

-5 / 2 equals -2

353 / -3 equals -117

-5 / - 2 equals 2

If the number you are testing is between one and negative one - for example 2 / 5 or -2 / 5 then the result is undefined, although most compilers return 0.

The modular operator, %, returns the remainder resulting from integer division. For example in C:

5 % 2 equals 2

353 % 3 equals 2

-5 % 2 equals -2

353 % - 3 equals 2

-5 % -2 equals -1

The sign of the result takes on the sign of the dividend as you would expect. For fractions that are between one and negative one the result is the same as the numerator.

Exercises

Exercise 1

Write down your thoughts on what a program to explore division and modulus should do.

• What processing has to occur?
• What types of input do you have?
• What does your output look like?

The following example will walk you through this exercise.

C Program Example For Exercise 1

• Program to Explore Integer Division And Integer Modulus

Modeling Recursively defined functions

The factorial function n! is recursively defined:

0! = 1

n! = n×(n-1)! if n ≥ 1

In C, if fact(n) is the functions as described above we want

$fact(0)=1;$

$fact(n)=n*fact(n-1)$; if $n\geq 1$

we should note that all recursively defined functions have a terminating condition, it is the case where the function can give a direct answer to, e.g. fact(0) = 1.

We can model the factorial functions easily with the following code and then execute it:

int fact (int n)

{

if (n == 0)

return 1;

if (n >= 1)

return n * fact(n - 1);

}

The C function above models the factorial function very naturally. To test the results, we can compile the following code:

#include <stdio.h> /* Standard Input & Output Header file */

int fact (int n)

{

if (n == 0)

return 1;

if (n >= 1)

return n * fact(n - 1);

}

int main(void)

{

int n = 5;

printf("%d", fact(n)); /* printf is defined in stdio.h */

}

We can also model the Fibonacci number function. Let fib(n) return the (n + 1)th Fibonacci number, the following should be clear

fib(0) should return 1

fib(1) should return 1

fib(n) should return fib(n - 1) + fib(n - 2); for n ≥ 2

we can model the above using C:

int fib (int n)

{

if (n == 0 || n == 1) /* if n = 0 or if n = 1 */

return 1;

if (n >= 2)

return fib(n - 1) + fib(n - 2);

}

Again, you shall see that modeling a recursive function is not hard, as it only involves translating the mathematics in C code.

Modeling non-recursive functions

There are functions that involve only integers, and they can be modelled quite nicely using functions in C. The factorial function

f(n) = n! = n(n - 1)(n - 2) ... 3×2×1

can be modeled quite simply using the following code

int n = 10;  //get factorial for 10
int f = 1;   //start f at 1
while(n > 0) //keep looping if n bigger then 0
{
   f = n * f; //f is now product of f and n
   n = n - 1; //n is one less (repeat loop)
}

---

---

Floating point Programming

Programs can not only be written with integer values, but also with various forms of floating-point values. You should normally use the double keyword to define a floating point number; the reason for this is that in many cases, the intuitive way to write an expression in floating point arithmetic is suboptimal. Floating point arithmetic is non-associative - in base-10, a system that has 2 places of accuracy has (1.0 + 0.02) + 0.04 = 1.0 (rounded down because 1.02 rounds to 1.0, and then 1.04 rounds down to 1.0), but 1.0 + (0.02 + 0.04) = 1.0 + 0.06 = 1.1. There also exists a float type, which uses 4 bytes instead of 8, but you should not use it unless you know what you are doing, since there is only 24 bits of accuracy, or roughly 9 base-10 significant digits.

Beware: If you use 2 integer operands, it still performs integer arithmetic, so this prints 1, not 1.5 as you'd expect:

double number;

number = 3/2;

printf("%f\n",number);

An example of a definition of a floating-point number and then calculating 3/2:

double number = 3;

number /= 2;

printf("%f\n",number);

A caveat: floating point numbers do not perfectly represent all decimal numbers. Obviously, because the memory consumed by a variable is finite, it cannot represent an infinite number, but only an approximation of it. In addition, some numbers cannot be perfectly represented in floating point. In this code:

double number;

number = 1/10;

the value of number is not 0.1, but actually 0.10000000000000001.

An analogy of this limitation is the value of 1/3. In the decimal system, this value cannot be exactly represented with a finite number of 3s, as in 0.333... Since 2 and 5 are the only prime factors of 10 (the base of the decimal system), only fractions with denominators comprising products of 2s and 5s, such as 5/8 $\left({\tfrac {5}{2^{3}}}\right)$ or 231/250 $\left({\tfrac {231}{2\times 5^{3}}}\right)$ (but not 1/3 or 5/14) can be exactly represented by decimal numbers (0.625 and 0.924, respectively).

Computers use base 2 arithmetic, so only fractions with denominators comprising products of 2s (powers of 2), such as 5/8 $\left({\tfrac {5}{2^{3}}}\right)$ or 231/256 $\left({\tfrac {231}{2^{8}}}\right)$ (but not 231/250, 1/3 or 1/10, as above) can be exactly represented by a floating point number.

Feedback

What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.