CSCI 1320 - Assignment #5

Before this is due, we will have expanded your abilities so that you can make extensive use of arrays in your code. Pick one of the options below to complete. We are now getting to the point where you don't want to just start coding. You want to start by sitting down and thinking about what your code needs to do and how you are going to make it do it, paper and pen might even be helpful for this. I can almost promise that every minute spent really thinking about what you are going to be doing will save you 2 minutes of coding/recoding/debugging.

When you work on breaking your problem down into pieces, look for pieces that are reusable. If you find yourself writing the same code three or more times, that probably means that it should be put into a function. In addition, don't write functions that are so specific to the assignment you could never reuse them if there is an alternate function you could write that would be reusable. The specific function could call the reusable one.

After each problem description I've given you sample input and output files. If you run the program with the input I give you should get something pretty much identical to my output. I've told you for each one if you want to be piping data in or not. For example, the first one is a menu based application and you will probably want to be typing things in at the keyboard there, but piping data in could be helpful for some things.

As a side note, be sure to save the code from all the programs you do. It is quite possible that later in the semester other assignments will include things that overlap with them and your code will be reusable.

To turn in this assignment just send the code in an e-mail to mlewis@cs.trinity.edu. You can do this with the command "mail mlewis@cs.trinity.edu < assn4.c" if assn4.c is the name of your source file.

Standard Problem:

Mathematicians and computer scientists alike seem to have a certain fascination with prime numbers. They are a very vital component of the study of number theory. Interestingly, mathematicians studied number theory for centuries and many of them studied it in large part because it was completely unusable for anything productive. It was a fun intellectual pursuit and nothing more. That was before computers and cryptography which have moved number theory into the lime light. We aren't going to get into any heavy number theory, but we should look at how we can play some games with numbers.

The program you are going to write is a menu based program that "plays" with numbers. The options on the menu are the following:

  1. Enter new number
  2. Print number reversed
  3. Check if number is a palindrome
  4. Check if number is prime
  5. Print all primes up to number (slow)
  6. Print all primes up to number (fast)
  7. Print the prime factorization of the number
  8. Quit

If they select 1 then the user enters a new number for the program to work with. It should start off as 2. If the number is <2 you should print a message saying it must be at least two and set it equal to 2. At this time you should also create a string that stores the string representation of that number. There are a few ways to do this, but I'd rather you write your own code for it. When trying to do that keep in mind that n%10 will always give you the value of the ones digit of a number. Also, n/10 will give you a number where the ones digit has been removed. You will be working with integer types for this. Making the character string representation will be helpful for options 2, and 3.

For 4 you will go through a loop to see if the number is prime. You can look at the test answers for code that will do this if you have a hard time with it. Options 5 and 6 should give the same output, but get it in different ways. In 5 you will count for 2 up to the number and just print out all the ones that are prime using the function you wrote to check if a number is prime. For 6 you will improve on this. With a little thinking, you can see that given a number n, you don't have to check if n is divisible by every number less than n, or even every number less than or equal to sqrt(n). What you need to do is check against the prime numbers less than or equal to sqrt(n). So to speed things up you will keep a large array of numbers that stores primes in it and when you check if each number is prime, you only divide by the primes before it. You might want to write an isPrime2 function that takes not only the number to check, but also an array of known primes less than it and the number of primes in that array. For option 7, just print the prime factorization of a number, so if the number is 588 you print 2*2*3*7*7.

To make this all more interesting, I'd like for you to use the long long type for the numbers you are passing around. This type is a 64-bit integer. It is nice because instead of being limited to roughly +/- 2 billion, a long long can store positive and negative values up to 4*10^18. This will let you use numbers big enough so that there might be a difference in speed between the fast and slow methods of printing all primes. To read in and print out long long integers, use %lld in the input and output strings.

This is not a program where you will typically want to be piping things in and out. Do play with it a bit and make sure that it works for different inputs the way that it should for all the options in it.

input : output

Physics Problem:

Now that you have arrays, you can do a bit more with the Keplerian simulator that some of you wrote in assignment #3. In that program all you had was one body in motion about a "central mass" that wasn't really moving at all. Now you can store and work with the positions and velocities of many bodies because you can store their component data in arrays. That is to say you can have an array for x positions as well as y, vx and vy. This allows you to simulate the motions of many particles at the same time which is much more fun. Earlier you only had to calculate the acceleration due to the central particle. Now you want to calculate accelerations due to all interactions between all the particles. We can also make the central particle one of the particles in our array. (If we were doing galactic dynamics we wouldn't have a central body, but that's a different issue all together.)

With multiple particles, we need to have a nested loop that calculates the accelerations on each particle from all the others and adds them all up. Keep in mind that if particle i pulls on particle j then particle j pulls back on i just as hard, but in the opposite direction that doesn't mean the accelerations are the same though. The acceleration is proportional to the mass of the puller because the mass of the pullee is canceled out by its inertia. Earlier we had ax=-x/(r*r*r) and ay=-y/(r*r*r). When the particle doing the pulling isn't at the origin, r is the distance between the particles and x and y are the distances between them in x and y directions. We also need a factor of m for the mass of the puller. You want to add up the accelerations from all other particles on each one and store that into arrays so

ax[i]=sum(-(x[j]-x[i])*m[j]/(r*r*r))

There is a similar formula for y and note that I'm being a bit sloppy with the r's which need to be recalculated for every i,j pair. When you write your formula in the code, think a bit about This formula causes a bit of a problem if we really use r because particles can get too close to one another. I suggest you make r=sqrt(dx*dx+dy*dy)+something small. You can play with how small you want it to be because that depends on the scale of your problem. I also recommend that you have your integrator not use the normal Euler method which calculates accelerations, then updates positions, then velocities. Make sure that after it does the accelerations it does velocities before the positions. Keep in mind that you want to break this up into functions that fit together nicely and are helpful. Don't make one huge main for this. It will hurt your brain more that way.

The input for the program will have a first line that is the number of bodies, timestep, stopping time, and the number of steps between outputs. This will be followed by lines with the x, y, vx, vy, and mass values for each particle. See the link below for an example. Note that the central mass has a mass of 1 and all the others are much smaller.

As output, I want you to print out the positions of all the particles in your simulation once for every n steps where n is a value given on the first line of the input. This could be quite a bit of output, but you should pipe it out to a file so that you can look at it. In fact, there is a handy program you can look at it with called gnuplot. If you run your program with a line like this "a.out < input > output" then you can run gnuplot and give it the command plot 'output' and it will make a little scatter plot showing you the paths of all the particles in the simulation.

input : output

Graphics Problem:

When we draw graphics on computers, the most standard way of doing it is with what are called raster graphics. In this style of graphics, images are made of many rows and columns of "pixels". Depending on the type of display a pixel might be just on or off, or it could have a shade, or even color to it. Computer screens are raster types displays as are most of the images that we work with (gif, jpg, and png formats are for raster type images). It is also possible to have vector images, but we aren't going to worry about those in this class. For this assignment I want you to write some functions that will basically implement a simple raster display. What you write here should be helpful in later assignments as we try to put more things together to build a little graphics package.

It should be noted that raster displays typically use a slightly different coordinate system than what is used in math. The x-axis still runs across, getting larger as you move right, but the y-axis runs down the screen. So the (0,0) location on screen is the top-left most pixel.

You will represent the raster as a 2-D arrays of integers. Each element of this array will represent a color in red, green, and blue that has been packed into the int. The lowest byte is the red, the next one is green, and the third is blue. For now we won't use the top byte for anything and it should always be zero. You will write two functions to pack colors into one int and to take them out. These functions will use bit-shifting to help you. I want you to think a bit about how to do this, but don't hesitate to ask me if you start to get hung on it at all.

Use some #defines at the top of your code to tell the program how big the raster width and height is. For this assignment you should use values of 60 for both.

int packColor(int red,int green,int blue); This function returns an int with the red, green, and blue values packed into it. This should do some checking to make sure that the values fit in the one byte that are supposed to. That means they have to be between 0 and 255. If they aren't you should force them to be so.

void unpackColor(int rgb, int *red,int *green,int *blue); This function breaks a single int RGB value into the three components.

void drawPixel(int raster[][HEIGHT],int x,int y,int rgb); Sets the value of the pixel at x,y to be this rgb value.

void fillRectangle(int raster[][HEIGHT],int x1,int y1,int x2,int y2,int rgb); Sets all the pixels in the region bound by (x1,y1) and (x2,y2) to the given rgb value. Check to make sure they aren't trying to draw outside your raster, but draw what fits in the raster.

void fillcircle(int raster[][HEIGHT],int x,int y,int r,int rgb); Sets all the pixels in the region around (x,y) with radius r to the given rgb value. You get to think a bit about how to get this to happen. Efficiency is nice, but not required. Check to make sure they aren't trying to draw outside your raster, but draw what fits in the raster.

void simplePrintRaster(int raster[][HEIGHT]); This function prints out a very simple representation of the image in the raster. It prints each row of the raster to screen, one pixel at a time. If the pixel has a value of 0 (black) it prints a space. Otherwise it prints a '#'. Obviously this doesn't give you any sense of color, but you can see the geometry quickly.

void printRaster(int raster[][HEIGHT]); This will print something that won't look like much now, but you will be able to modify and use later to actually see color images of what you draw in future programs. For this print it should print the width and height first, then print a series of 6 characters for each pixel. Those 6 characters are hex values for red, green, and blue much like what is used on web pages to represent colors. Don't put any new lines in the middle of this though you can put one at the end to make things look better. For example, if a pixel is black this will print 000000 for that pixel. If it is white it will print ffffff. If it is pure red you get ff0000, etc.

In a later assignment you will extend this some by writing other functions that give you the ability to print the raster in such a way that it will be readable by an outside program so that you can display a full color version of it.

For the main functionality of this program you will write a menu driven application that gives the user the following options:

  1. Draw Pixel
  2. Fill Rectangle
  3. Fill Circle
  4. Simple Print Raster
  5. Print Display Raster
  6. Quit

When they choose one of the first three, you need to prompt the user for values related to the inputs of that function. Being a menu driven program, you won't normally want the operation to be done through piping in files, but you can do that to speed things up when you are just working with it.

input : output