Problem 12. Highly divisible triangular number implementation in C++

Hi,

today, I going to show  solution of one more problem from http://projecteuler.net.
What is triangular numbers? A triangular number or triangle number counts the objects that can form an equilateral triangle. Please refer Wikipedia for additional information.
In general, triangular number can be calculated using formula bellow

triangleNumber=n*(n+1)/2;

So here is rough  solution. It's working, but  it will take forever to complete. :)
Sure, you can use threads to improve performance, but it's not help you too much.

//============================================================================
// Name        : HighlyDivisibleTriangularNumber.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <sys/time.h>
#include <ctime>
#include<math.h>

using namespace std;





int coutDividers(const long num){
 int tmp=1;
for(long i=1; i<num; i++)
 if(num% i==0)tmp++;
return tmp++;
}

typedef unsigned long long timestamp_t;

static timestamp_t
   get_timestamp ()
   {
     struct timeval now;
     gettimeofday (&now, NULL);
     return  now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
   }

int main() {
 timestamp_t t0 = get_timestamp();
 //n(n+1) /2
 int counter=1;
 long triangleNumber=1l;
 int dividers=0;
 while (dividers<=500){
  triangleNumber=counter*(counter+1)/2;
  dividers=coutDividers(triangleNumber);
  //cout<<triangleNumber<<"="<<dividers<<endl;
  counter++;
 }
 cout<<triangleNumber<<"="<<dividers<<endl;

 timestamp_t t1 = get_timestamp();
 double secs = (t1 - t0) / 1000000.0L;
  cout<<"time elased="<<secs<<endl;

 return 0;
}

We shouldn't calculate and count prime numbers for required number, we can simplify by using square root .

//============================================================================
// Name        : HighlyDivisibleTriangularNumber.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <sys/time.h>
#include <ctime>
#include<math.h>

using namespace std;



int coutDividers(const long num){
 int tmp=1;
for(long i=1; i<sqrt(num); i++)
 if(num% i==0)tmp++;
return (tmp++)*2;
}

typedef unsigned long long timestamp_t;

static timestamp_t
   get_timestamp ()
   {
     struct timeval now;
     gettimeofday (&now, NULL);
     return  now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
   }





int main() {
 timestamp_t t0 = get_timestamp();
 //n(n+1) /2
 int counter=1;
 long triangleNumber=1l;
 int dividers=0;
 while (dividers<=500){
  triangleNumber=counter*(counter+1)/2;
  dividers=coutDividers(triangleNumber);
  //cout<<triangleNumber<<"="<<dividers<<endl;
  counter++;
 }
 cout<<triangleNumber<<"="<<dividers<<endl;

 timestamp_t t1 = get_timestamp();
 double secs = (t1 - t0) / 1000000.0L;
  cout<<"time elased="<<secs<<endl;

 return 0;
}

This solution works so fast, comparing to previous, brute force solution.

Less then 1 second- incredible performance.

How can we improve it even more?
Lets try to rewrite all this things using  thread.

//============================================================================
// Name        : HighlyDivisibleTriangularNumberMultithreaded.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdlib>
#include <pthread.h>
#include <unistd.h>
#include <sys/time.h>
#include <ctime>
#include<math.h>

using namespace std;

#define NUM_THREADS     6
pthread_mutex_t lock;
long searchResult=0l;
long searchDividers=0l;

typedef unsigned long long timestamp_t;
static timestamp_t
    get_timestamp ()
    {
      struct timeval now;
      gettimeofday (&now, NULL);
      return  now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
    }

void* coutDividers(void* num){
 int tmp=1;
 long dest=(long)num;
for(long i=1; i<sqrt(dest); i++)
 if(dest% i==0)tmp++;

 pthread_mutex_lock(&lock);
  if(searchResult==0l){
   if(tmp*2>=500){
    searchResult=dest;
    searchDividers=tmp*2;
   }
  }
 pthread_mutex_unlock(&lock);


pthread_exit(NULL);
}


int main ()
{
  timestamp_t t0 = get_timestamp();
 if (pthread_mutex_init(&lock, NULL) != 0)
     {
         cout<<"\n mutex init failed\n";
         return 1;
     }
 int counter=1;
  long triangleNumber=1l;

  while (true){


   int rc;
   int i;
   pthread_t threads[NUM_THREADS];
   pthread_attr_t attr;
   void *status;

   // Initialize and set thread joinable
   pthread_attr_init(&attr);
   pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

   for( i=0; i < NUM_THREADS; i++ ){
      triangleNumber=counter*(counter+1)/2;
      counter++;
      rc = pthread_create(&threads[i], NULL, coutDividers, (void *)triangleNumber );
      if (rc){
         cout << "Error:unable to create thread," << rc << endl;
         exit(-1);
      }
   }

   // free attribute and wait for the other threads
   pthread_attr_destroy(&attr);
   for( i=0; i < NUM_THREADS; i++ ){
      rc = pthread_join(threads[i], &status);
      if (rc){
         cout << "Error:unable to join," << rc << endl;
         exit(-1);
      }

   }

   pthread_mutex_lock(&lock);
     if(searchResult>0l){
      cout<<"searchResult="<<searchResult<<endl<<"searchDividers="<<searchDividers<<endl;
      timestamp_t t1 = get_timestamp();
         double secs = (t1 - t0) / 1000000.0L;
         cout<<"time elapsed="<<secs<<endl;

   pthread_exit(NULL);
      pthread_mutex_destroy(&lock);
      }
   pthread_mutex_unlock(&lock);

  }
     cout << "Main: program exiting." << endl;
     pthread_exit(NULL);
}

Because of a task solving time cost relative  small,  threads wouldn't help you  here.

In my case time execution even increased, because of a lot of  threads handling routines.
I've did several tests, and  result  still  not so good as without threads.

But anyway- its  a good experience.