CS assignment 4

COMP 2103X1 Assignment 4 Due Thursday, February 9 by 7:00 PM

General information about assignments (important!): http://cs.acadiau.ca/~jdiamond/comp2103/assignments/General-info.html

Information on passing in assignments: http://cs.acadiau.ca/~jdiamond/comp2103/assignments/Pass-in-info.html

Information on coding style: http://cs.acadiau.ca/~jdiamond/comp2103/assignments/C-coding-style-notes

[1] A natural number n greater than 1 is said to be prime if the only numbers which evenly divide n are 1 and n itself. Prime numbers have many uses in computing (and various branches of mathematics), and thus we want to be able to find prime numbers. For this question you will write a program which finds and outputs prime numbers.

Your program will work as follows: it will examine its command line arguments to see if exactly one argument is present. If so, it will attempt to convert that command line argument to an integer N (read, for example, man sscanf). If successful, it will then calculate and output the first N primes, one per line. Note that for this program you may find it beneficial to store all of the prime numbers you compute; I strongly urge you to do so, and then to think about why I recommend that.

Here are a couple of sample runs of my program (with the user input in red): % a4p1 5

2

3

5

7

11

% a4p1 four

Invalid argument!

Usage: a4p1 <number of primes to output>

% a4p1 1

2

%

Notice that, except for error messages, this program does not output anything but the primes. There is no explanation of what the output is (which you might initially be troubled by), no “hello”s, no “goodbye”s, and so on. This is a common paradigm for command-line programs, because it makes it easier for another program to use the first program’s output as its input. This is a very powerful facility, and extraneous pleasantries get in the way.

While this program can be very short, you might decide that it calls out for some functions, rather than having all the code in main(). Think about how you can logically break down the “big” problem into some “bite-sized” pieces and implement each of those as a function. (Don’t forget to document each of these functions!) But, at the same time, don’t write “trivial” functions just for the

1

sake of having functions. (Good judgement comes from experience, and, as they say, experience comes from bad judgement.)

When creating your script file, you should demonstrate a number of cases that work as well as a number of cases that don’t work. Also, in order to show the TA that your program works with big arguments (but without filling your script file with many primes), run the command

% a4p1 1000000 | tail -20

to output the 999,980th, 999,981st, : : : , 1,000,000th primes. (My quickly-written program running on my laptop (Intel(R) Core(TM) i7-2760QM CPU @ 2.40GHz)Ž, without compiler optimizations turned on, takes about 5.5 seconds of CPU time to do that. With optimizations on (compiled with -O3) my program runs in about 2.4 seconds. Your program may take less time, but if you aren’t careful about how you test a number for primality it could take a lot longer! Speed is not the essence of this assignment, but if your program takes an unduly “large” amount of time, you haven’t thought enough about how to test a number for primality. I don’t expect you to do research into calculating primes, but, as always, I do expect you to think a bit and apply common sense.)

It is possible that you will run out of memory when trying to create a 1,000,000 element array (and you may get the dreaded “segmentation fault”). If this happens to you, try running the command

% ulimit -s unlimited

before running your program.

If you want to get the computer to time how long a command takes to run, use the (duh) time command:

% time a4p1 1000000 | tail -20

a4p1 1000000 2.34s user 0.00s system 100% cpu 2.344 total

[2] In various places in computer science and mathematics it is useful to work with integers modulo some prime number. For example, if we choose a prime p D 11 and work modulo p, we can use the numbers 0, 1, 2, : : : , 9 and 10 (more strictly, we can talk about the equivalence classes f0g, f1g, f2g, : : : , f9g, f10g, since, for example, 2 � 13 � 24 � � � � .mod 11/).

The integers modulo some prime have some interesting properties not enjoyed by the integers at large. For example, not only do the integers modulo a prime have an additive inverse (e.g., 3 C 8 � 0 .mod 11/) just like the integers, but non-zero numbers have multiplicative inverses (e.g., 3 �4 � 1 .mod 11/). Further, some (but not all!) integers modulo a prime have square roots; for example, 3 has a square root modulo 11, since 5 � 5 � 3 .mod 11/.

Another interesting property is that if you raise any non-zero number to a high enough power, you will eventually get 1. For example (all arithmetic modulo 11 here) 42 � 16 � 5, 43 � 64 � 9, 44 � 256 � 3, and 45 � 1024 � 1. Similarly, 22 � 4, 23 � 8, 24 � 16 � 5, 25 � 32 � 10, 26 � 64 � 9, 27 � 128 � 7, 28 � 256 � 3, 29 � 512 � 6, 210 � 1024 � 1. You will notice that we only needed to raise 4 to the 5th power to get 1, but we needed to raise 2 to the 10th power to get 1. But if you think about it, you will realize we get 1 if we raise 4 to the 10th power. It turns out that (modulo 11) raising every non-zero number to the 10th power results in a value of 1. (This

Ž You may find the output of the lscpu command interesting, as well as the output of “cat /proc/cpuinfo”.

2

is a special case of both Euler’s totient theorem and Fermat’s little theorem.)

In the previous example, 10 was a “special” number because it is p�1 for the chosen p. Sometimes we are interested in finding numbers m between 2 and p � 1 which have the property that p � 1 is the smallest number n such that mn � 1 .mod p/. (Anyone interested in this can look up “primitive n-th roots of unity”.)

For this problem, you will write a program which takes exactly two command line arguments, m and p. It will test whether or not m is a primitive p�1th root of unity. Specifically, it will determine whether or not there is some n < p such that mn � 1 .mod p/.

Here are some examples of running your program, assuming that you name your program a4p2. The user input is in red.

% a4p2 2 11

2 is a primitive 10-th root of unity modulo 11.

% a4p2 4 11

4 is not a primitive 10-th root of unity modulo 11.

% a4p2 3 131565131

3 is not a primitive 131565130-th root of unity modulo 131565131.

% a4p2 2992 131565131

2992 is not a primitive 131565130-th root of unity modulo 131565131.

% a4p2 3993 131565131

3993 is a primitive 131565130-th root of unity modulo 131565131.

Note that you can’t blindly compute m to bigger and bigger powers without being a bit careful. For example, if the arguments are 2 and 14812307, and you try to compute (for example) 27406153 and then reduce that modulo 14812307, you will far over-flow the capability of even 64-bit arithmetic. However, since

an mod p � .a2 mod p/ � an�2 mod p

you can reduce the size of your numbers modulo p after every multiplication, which keeps them small enough, as long as m is less or equal to the square root of the biggest integer you can store. (Q: how can your program check for this condition on m?)

You may assume that each command-line argument fits into a 32-bit signed integer.

For “just” full points you may assume that a second argument is prime (although you should still do a basic sanity check). However, here is an additional thing you can do for up to three bonus points. Rather than assuming that the second argument is prime, test it. Don’t feel the need to do anything sophisticated, and don’t go to the effort of calculating and storing primes in an array. Just apply some “common sense” about prime numbers. (That is, what is the biggest number you have to try dividing p by, and do you have to try dividing by any even numbers bigger than 2?)

And regardless of whether you do the bonus part or not, are there any special cases that your program should handle?

3

[3] Write a function which takes a file pointerŽ (FILE *) as its only argument. The function reads the given file until EOF and prints out (i) the number of lower case letters in the input, (ii) the number of upper case letters in the input, (iii) the number of digits in the input, and (iv) the number of “white-space” characters in the input (see man 3 isspace).

Write a main program which, in a loop, prompts the user for a file name, and then tries to open the file. If it successful, it passes the file handle to your function. Otherwise it complains to the user and continues. If the user types –quit, your program exits.

There are various ways you can read in the file name, choose whichever way makes sense to you. You can declare some character array to hold the filename, but you must do something to ensure that some evil user won’t crash your program by entering an overly-long string.

I haven’t told you exactly what the output looks like. Use some common sense; imagine what someone else using your program needs to see.

Think about what testing you need to do, and what other housekeeping functions your program should do. Make sure you include appropriate test cases in your script file. What value, if any, does it make sense for your function to return? And are there any cases in which it makes sense for your main() to return EXIT_FAILURE?

When creating your script file, think about what you need to include so that the marker can know whether your program (appears to) work correctly. As one of your tests, use the input file a4p3- sample-input.txt (found in the assignments directory of the course web site); do not cat the output of this particular input file into your script file!

Are there and “special cases” your function should handle and be tested with?

Did you use functions in any of these questions? Should you have? Did you document them correctly?

Does you program “blow up” on unexpected input, or does it deal with bad input in a “graceful” way?

How does your program deal with boundary conditions, if there are any?

Did you remember to put all required comments in? Does your program call out for any other comments in the body of the code?

Ž Some people would say “file handle”. Other people may have other names yet.

4

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.