// ~ Learning Goals ~ //

(1) Learn basics of creating and running threads.

(2) Understand further the nature an limits of inbuilt types.

// ~ Submitting Your Assignment ~ //

For this assignment you must only submit the solution file

“answer08.c”. You can use the tester program to test your solution

before uploading it. Do not submit a zip file.

// ~ Introduction ~ //

So far we have only considered computer programs that try to do one

thing at a time. In this programming assignment we will learn about

computer programs that do muliple things at the same time. This is

referred to as “threading”. For example, a sufficiently smart computer

program could optimize its time by watching important TV shows on HBO,

while simultaneously doing the ironing. This example is not entirely

glib. In this case we are talk about two different simultaneous tasks

(TV and ironing), and each executing task is referred to as a thread.

There are many reasons why threading is important. For this course we

will consider speed. Although computers are still getting faster,

today they are really only getting better at doing multiple things at

the same time. (The execution of single threaded programs is not

getting much faster.) To extend our analogy, if we have lots of

ironing to do, we cannot build a faster robot to do the ironing. The

speed of the robot is maxed out. But we can set up multiple robots on

multiple ironing boards to do the work simultaneously. Ten robots (ten

threads) would mean (roughly speaking) ten times as much ironing.

In general, you rarely get ten times the speed for using ten times as

many threads. The problem is that the threads will need to communicate

with each other, and that slows everything down. To extend our

analogy, imagine that our ironing robots are getting their tasks

(particularly wrinkly shirts) from a big bin full of fresh laundry. If

the robots do not communicate with each other, then we could imagine a

situation where two robots attempt to pick up the same shirt at the

same time — probably tearing it in half. The chances of this

happening may be small, but non-zero. That means, firstly, that the

bug of a shirt being so-torn is very difficult to reproduce. If a bug

like this happens in your computer program, it can be almost

impossible to track down. Secondly, it means that all your robots need

to communicate with each other to get the job done.

In this assignment, we will create some threads (robots) to identify

whether or not a large number is prime (do the laundry). The threads

will each work on part of the task (break the laundry up into

piles). Normally you would need to consider how to make threads work

nicely together; however, this assignment has been carefully written

so that you do not need to do that. (If done straight-forwardly,

robots will never tear shirts in this assignment.) It is important to

keep in mind that threading is difficult to get right, and to do so,

you must learn how to synchronize the activities of your threads.

// ~ Determining if a Number is Prime ~ //

This is an ongoing area of research. For this assignment we will use a

very simple approach. Please read the following webpage on factorizing

prime numbers:

http://cartera.me/2012/01/10/primality-testing-and-factorization-in-c/

In this assignment, we will be using the

“primalityTestWithOnlyOddsAndSqrtLimit” function from the above

page. For your convenience, it is displayed below:

int primalityTestWithOnlyOddsAndSqrtLimit(long int n)

{

if (n % 2 == 0)

return 0;

long int max = floor(sqrt(n));

long int i;

for (i = 2; i < max; i++)

{

if (n % ((2 * i) + 1) == 0)

return 0;

return 1;

}

You will need to modify this function to make it

parallel. Furthermore, this function deals with puny “long int”

numbers. We’ll want more juice than that. So you will also have to

modify this function to use 128 bit integers.

There are some other problems with this function too. (Lesson: do not

believe everything you read on the interwebs.) Can you see the

problems?Â For starters, this function says that 2 isn’t a prime

number! Secondly, (and more perniciously), Carter Allen does not

handle the ‘i’ in the for loop correctly. For example, imagine that

you are testing if 83 is prime. In this case max = floor(sqrt(83)) ==

9, which is correct. Now you want to test every odd number between 3

and 9 inclusive, but that is not what Carter Allen has done! You will

need to fix this bug.

The webpage above (correctly) explains the very *very* simple

mathematics behind this function.

// ~ What you need to do :: Preliminaries ~ //

We will be testing LARGE prime numbers. These will be 128 bit

integers, which are far too large to fit in measly 32-bit or 64-bit

int variables. A 32-bit int variable can only contain values from 0 to

4 294 967 295, but with unsigned 128 bit numbers, you can go all the

way to 340 282 366 920 938 463 463 374 607 431 768 211 455. (If you

need that extra push over the cliff, then you what we do? See:

GCC has a native 128-bit integer type called “__int128”. In this

assignment we are interested in /unsigned/ integers, and so we will be

using the type “unsigned __int128”. There is a typedef statement in

pa06.h that defines a shorthand notation “uint128”

typedef unsigned __int128 uint128;

There are no built in functions to print these integers, or to convert

strings into these integers. You will need to write and test such a

function yourself.

You must also write your own function for printing unsigned 128-bit

numbers.

You should be able to pass the following test-case.

// Example: writing out a Biiigggg number

int main(int argc, char * * argv)

{

const char * str = “340282366920938463463374607431768211455”;

uint128 w = alphaTou128(str);

char * w_str = u128ToString(w);

printf(“Biiigggg number: %sn”, w_str);

if(strcmp(str, w_str) != 0)

printf(“ERROR!, expected %sn”, str);

free(w_str);

return EXIT_SUCCESS;

}

Before continuing with the assignment, you need to complete the

functions alphaTou128(str), and u128ToString(w).

// ~ What you need to do :: Testing primality ~ //

As Carter Allen notes on his webpage, the function

primalityTestWithOnlyOddsAndSqrtLimit lends itself to

parallelism. Simple put, if you want to test if a number is divisible

(exactly) by numbers in the range [0..n], then you can split this

range into chunks, and test each chunk in a separate thread. If /any/

chunk of the computation finds a factor, then the number is not prime.

For his threaded version, Carter Allen used “Grand Central Dispatch”,

which is a relatively new Apple technology. For this assignment we

will use the trusty pthreads library instead of Grand Central

Dispatch. pthreads is the standard threading library available on all

flavors of unix (including OS X and Linux), and can also be used on

windows. One key reason for using pthreads is that, in my experience,

it is not worth learning a shiny simplified technologies until you

understand a bit about the underlying machinery. So learning pthreads

is a very good idea, and the knowledge gained will transfer naturally

to other threading libraries.

Feel free to examine Carter Allen’s code; however, you will not be

able to compile it on the ece computers. Examining his code may help

you understand how to create a threaded version using pthreads;

however, many important details are missing.

// ~ How to Compile, Run and Test ~ //

For your convenience, the inputs folder contains two files. One file

contains 390 prime numbers. The other file contains 2116 non-prime

numbers. Your program should correctly detect all 390 primes as prime,

and all 2116 non-primes as non-prime. Don’t forget that 2 is a prime

number.

// ~ Why Prime Numbers ~ //

You might know that modern cryptography relies on the fact that no-one

knows how to efficiently determine whether or not a number is

prime. If someone ever figures this out, then they may well be the

subject of a real-life spy novel. This was the theme of the 90s hit

film “Sneakers”.

But as far as prime numbers go, cryptography is the tip of the

iceberg. If math has anything to do with the universe, then prime

numbers have a special place in how it ticks. These special numbers

have been the subject of extensive investigation by mathematicians for

all of recorded history, yet they still present many mysteries. Their

universality lead the great American scientist, Carl Sagan, to suggest

that if aliens were to communicate with humans, then they could use

prime numbers to capture our attention. This idea is the centre-piece

of Sagan’s only work of fiction, the best selling novel, “Contact”,

which has since been made into a film.

(http://www.youtube.com/watch?v=8qDjg8mdd8c)

#ifndef PA08_H #define PA08_H typedef __uint128_t uint128; #define FALSE 0 #define TRUE 1 #define MAX(X,Y) ((X) > (Y) ? (X) : (Y)) /** * Convert the initial portion of C-string ‘str’ to an unsigned 128-bit integer * * This function should be just like atoi(…), except that it returns an 128 * bit unsigned integer. Return 0 on any error. Don’t forget you must skip * white-space. * * See PA02 for hints on implementing this function. */ uint128 alphaTou128(const char * str); /** * Return a newly allocated C-string which represents the passed value. * The caller is responsible for freeing the allocated string. * * If you have already implemented alphaTou128(…) (see hint), then you should * be able to figure out how to implement u128ToString(…). */ char * u128ToString(uint128 value); /** * Test is ‘value’ is prime. * ‘n_threads’ is the number of threads to create to complete this computation. * Return TRUE of FALSE. * * LEAK NO MEMORY. * * Good luck! */ int primalityTestParallel(uint128 value, int n_threads); #endif