Project 1

This project has two objectives. The first problem is designed to get you started thinking about how computers do useful but more complicated mathematics, like calculate integrals. You should do this problem by yourself.

The second problem is designed to further hone your programming skills and to teach you something about the efficiency of different algorithms. We will do an exercise in class on Thursday designed to help you figure out how to do this.

Problem 1: Write a program that computes definite integrals by calculating a Riemann sum. Use this to calculate the integral of y=exp(-x^2) from 0 to 2.

Then calculate the integral of y=exp(-x^2) from -infinity to infinity.

Be intelligent about how you do this. You want a reasonably accurate answer, but you don’t want the computer to take forever doing it. Make sure you discuss how you handled the infinite interval. Do you come reasonably close to the analytic answer of sqrt(pi)?

It may be helpful for you to first graph this function if you’re not familiar with it. (You should be able to quickly graph different functions using the code you wrote last week.)

Problem 2: Write a program that reads in a variable N, and then prints out the number of prime numbers less than or equal to N. (You may also want to print out the prime numbers themselves to verify that your code is working.) You may do this in any straightforward way that you can think of; we will be doing an exercise on September 5 to help you with the things you’ll need for this.

Another hint: Remember % is the modulus operator, and that you can write something like (in C)

if (a % b == 0) // check whether the remainder of a/b is zero or not
{
  do something;
}
else
{
  do something else;
}

or in Python:

if (a % b == 0): // check whether the remainder of a/b is zero or not
  do something
else:
  do something else

to check to see if one number evenly divides another. Note that you do not need the else clause, if you don’t want to do anything in the event that b does not evenly divide a.

• a) Test your code. Does it correctly detect prime numbers? Describe how you tested it in your writeup.

• b) For N = 500000, estimate (roughly, but tell me how you got the estimate) how many arithmetic operations are required to do this with your code, and how long it will take. Go ahead and do it; was your estimate accurate? How long would it take for N = 1 billion? Is this a reasonable calculation to perform? (Note that if you do this the naive way, it may take fifteen minutes or so to run! You can leave it running while you do something else. Note that you can time how long a particular program takes to complete by saying, for instance, time ./prime. Compare your performance to any colleagues using the other programming language.

• c) Can you think of any small modifications to your program that will speed it up? Discuss these modifications and estimate how much each will speed up your calculation (estimates can be of the form “this will make it go twice as fast” or “this will make it go drastically faster”). Then make these modifications. There are two modifications I have in mind, but you might have already done one of them without thinking too hard. The other one is a small change; if you’re confused about how this works, work out using pencil and paper whether 323 is prime or not. Doing this will illustrate what to do.

Reports:

In your report, you should address at least:

• How your integration program works
• How you handled the infinite interval
• How accurate your result was, and how you might make it more accurate
• What difficulties you encountered writing your prime number code
• How long you estimated it would take to run, and how long it actually did take
• How you optimized it to make it run faster