CSCI 490E/680K Assignment 6 - Android Programming - Spring 2012

04/18/2012

Overview

Overview

For this assignment you will write a mobile device application that will perform a computational intensive and lengthy process in the background while leaving the user interface thread free to respond to other user-initiated (and other) events.  The computational process will be to find all prime numbers less than a given number.  The purpose is not to devise the quickest or most efficient way to come up with the list of primes, but rather to move the computation into the background and also to illustrate and measure the speed of the computation different maximum numbers, and different execution platforms.

Background

You will recall that a prime number is a number that cannot be divided evenly by any numbers other than itself and 1.  So, for example, 5 is prime because it can only be divided by 5 and 1.  6 is not prime since it can be divided by 2 and 3 as well as by 6 and 1.  1 itself is not considered prime.  The prime numbers less than 25 are: 2, 3, 5, 7, 11, 13, 17, 19, and 23.  Prime numbers are very interesting mathematically.  The largest known prime has about 16 million digits. Google it and you will find out (too many) more amazing facts.  Anyway, for this program we will look for primes in a smaller range - maybe all primes less than a maximum of few thousand.  The algorithm you employ must be correct, but does not have to be the smallest or fastest - we do want this to take a while. 

You should write the code yourself (why rob yourself of the chance to actually code something and debug it?).  If you choose not to and just copy or adapt code from cyberspace, you must clearly cite the source of that code in the program documentation.  Failure to do so is considered plagiarism by NIU and you would be deemed responsible for academic misconduct. 

Here is a rough verbal descriptions of an algorithm you could implement (maxInt is the largest number to be considered for prime-ness):

• for each number maxInt down to 3 (or 3 up to maxInt)
• try dividing it by 2 and then 3 and then 4 and then 5, etc. up to sqrt(maxInt).  (Or you can go down rather than up.  Same difference.)
• If at any point there is a 0 remainder, quit with this number (it is not prime) and move on to the next number.
• If you never get a 0 remainder in this process (for this number) it is prime - report it (store it in an array, or something).

In either case (or using any other algorithm you may devise or find), check your results with several maxInts you can easily verify - say 10, 25, 50, and 100.  Be sure that 2 is always reported, but not 1.  Be sure that the largest prime less than or equal to maxInt is reported.  Be sure there are no extra numbers (that are not prime) or missing primes.  You might want to write a small test program just to test the correctness of your algorithm before you start to worry about threads.

Details

The value of maxInt will be set in your program, but should be displayed on the screen.  Changing this number will require recompilation.  (However, feel free to supply a user input field for this value if you want to.)

Supply one "info" TextView to display the primes, one at a time, as they are generated.  When the computation is done, display the elapsed time in milliseconds and the number of primes found.

Supply another "time" TextView to display the time/date when the Date Button is pressed.

Supply a ListView to display the primes found after the primes algorithm has completed.

Start: will clear the TextViews and the ListView. Then it will create and run the calculation thread.  While the calculation thread is running, it will update that top TextView with some or all of the intermediate results: a thread number and a prime found.  If you find that this frequent updating of the UI thread is a problem, then show only every 10th or 50th result here. 

After the thread has completed, this area will show a "done" message and the elapsed time in milliseconds for the process to complete.

Clear: will clear the various TextViews and the ListView

Time: will display the current date and time and should work even while a primes calculation is in progress.  This is proof that the UI thread is still responsive.

Show: will normally be pressed after a calculation is complete.  You should disable it while a calculation is running.  It will display the number of primes found and a list of all the primes found.

A small mobile device is not the best place to try to show hundreds or thousands of items.  The Show command, depending on your platform, the number of items to display, and the method used to display them may take many seconds to complete and may cause a warning message or a shutdown of the app.  We will not worry too much about this - the point of the program is to keep the UI system responsive while the computation is in progress.  What happens after that is less of a concern.

Other Notes

1. Your program will need to know when the thread has completed so that you can report the results and enable the Show button. So before your thread terminates, it will need to send a special message to the user interface thread so the "info" TextView can show the completion message and the ViewList can show the primes found.

2. If you decide to store the found primes in an array, you will need to dimension that array.  There is an formula for the approximate number of primes less than a given number, n.  It is (in Java):

numPrimes = (int)(n/Math.log(n));  // natural (base e) logarithm

This is not exact, and you will find - sooner or later - if you use this number you will get a program termination or other ugly problem due to array overflow (ArrayOutOfBoundsException). To avoid this, just take the value calculated and increase it by 25%.  If you prefer, you could store results in a data structure that can grow dynamically.

3. We suggest that you implement the background processing by extending the Thread class and passing its constructor any necessary information needed by and specific to that Thread instance.  Look at the allowed arguments for sendMessage() to devise a way to send the needed information back to the UI Thread.  When a prime is found and also when the computation is finished, use a Handler's sendMessage() to communicate that information to the UI thread's handleMessage().  In the case of a found prime, the UI thread will then display the newly found prime in the "info" field, replacing the previous one.  At some point, the new prime should be stored for later list display.  When the thread completes, a different message should be sent.  The UI thread will then display the time elapsed and number of primes found in the "info" field, and arrange to display the list of primes found.

4. Note that if you use a ListAdapter with an array (of ints as Strings, probably) every element of the array must have a valid String value or the adapter will raise a NullPointerException.  You could initialize each element of the array the array to a String with no-chars, that is: ""