High School Mathematics Extensions/Mathematical programming

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" by About.com

http://cplus.about.com/library/blctut.htm

if you are unfamiliar with programming or the C programming language.

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 seven chapters of "C programming Tutorial" at About.com

http://cplus.about.com/library/blctut.htm

Discrete Programming

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:

5 / 2 equals 2

353 / 3 equals 117

99 / 7 equals 14

-19 / 2 equals -9

78 / -3 equals -29

in C.

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

5%2 equals 1.

Exercises Evaluate x

a) x = 7 / 2

b) x = -9 / -4

c) x = 1000 / 999

d) x = 2500 / 2501

Modelling 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\ge 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);

}

void main()

{

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 modelling a recursive function is not hard, as it only involves translating the mathematics in C code.

Modelling 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 modelled 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. To define a floating point number use the float or the double keyword (double retains more digits but also consumes more memory than float). For example, the following code will define a floating-point number and then calculate 3/2 as in the integer case:

float number;

number = 3/2;

However, since number has been defined as a float, not an integer, the value stored in number is now 1.5, not 1 if it had been an integer.

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.