Question

From previous homework you are already familiar with the math function f defined on positive integers as f(x)=(3x+1)/2 if x is odd and f(x)=x/2 if x is even. Given any integer var, iteratively applying this function f allows you to produce a list of integers starting from var and ending with 1. For example, when var is 6, this list of integers is 6,3,5,8,4,2,1, which has a length of 7 because this list contains 7 integers (call this list the Collatz list for 6). Write a C or C++ program A7p3.c[pp] that accepts one command line argument which is an integer n between 2 and 6 inclusive. Use pthread to create n threads to count how many integers between 11 and 70 inclusive have their Collatz list length (a) less than the integer itself; (b) equal the integer itself; (c) greater than the integer itself. You should divide this list generation and length calculating task among the nthreads as evenly as possible. For example, if n is 3, then each thread is supposed to handle 60/3=20 Collatz lists. Print out the three numbers representing the counts for (a)(b)(c) mentioned above. Use mutex or semaphore to avoid race conditions if necessary. Note: if you do not use pthread to divide the task among the threads, you may get zero points. A sample run of the compiled program A7p4 is shown below. You do NOT need to submit screen shots. Instead submit your source file.

[kwang@computer][~/temp]$./A7p3 3

using 3 threads.

the number of integers from 11~70 whose Collatz list length is < the integer is [xx]

the number of integers from 11~70 whose Collatz list length is = the integer is [yy]

the number of integers from 11~70 whose Collatz list length is > the integer is [zz]

Answer 1

#include <iostream>

#include <bits/stdc++.h>

#include <ctype.h>

#include <pthread.h>

#include <stdio.h>

#include <assert.h>

#include <semaphore.h>

#include <errno.h>

using namespace std;

sem_t s1;

int a=0,b=0,c=0;

int gnum_threads;

void usage(char *s)

{

  fprintf(stderr,"usage: %s <num_of_threads>\n",s);

  exit(0);

}

void* thread_func(void* arg) {

  int count = 1;

  int index = (int) (long) arg;

  for(int i=(index*70)/gnum_threads;i<(index+1)*70/gnum_threads;i++){

    int var = i + 1;

    while(var!=1) {

      if(var%2==0)

        var = var/2;

      else

        var = 3*var+1;

      count++;

    }

    sem_wait(&s1);

    if(count <= 5)

      a++;

    else if(count >= 10)

      c++;

    else

      b++;

    sem_post(&s1);

    count = 1;

  }

  

  

}

int main (int argc, char* argv[]) {

  if(argc!=2) usage(argv[0]);

  gnum_threads=atoi(argv[1]);

  assert(gnum_threads>=2 && gnum_threads<=6);

  printf("using %d threads.\n",gnum_threads);

  

  pthread_t *thread;

  thread=new pthread_t [gnum_threads];

  if(thread==NULL) {std::cerr<<"out of memory\n";exit(-1);}

  

  sem_init(&s1, 0, 1);

  

  

  for (int i = 0; i < gnum_threads; i++)

    pthread_create(&thread[i], NULL, thread_func, (void *)i);

  for (int i = 0; i < gnum_threads; i++)

    pthread_join(thread[i], NULL);

  

  cout << "The number of integers from 11-70 whose Collatz list has length <=5 is " << a << "\n";

  cout << "The number of integers from 11-70 whose Collatz list has length between 5 and 10 exclusive is " << b << "\n";

  cout << "The number of integers from 11-70 whose Collatz list has length >=10 is " << c << "\n";

  

  

  return 0;

}