Solution for this question Please

[Smac89]

So here is the one I used when I did mine: I went a bit fancy and tried it with multi-threading

#include <cstdlib>
#include <cstdio>
#include <pthread.h>
#include <cstring>
#include <cmath>

void* GenerateCollatzSequence2(void*);
void* GenerateCollatzSequence(void*);

struct collatz
{
  int num;
  int sequence;
};

collatz* num1 = new collatz;
collatz *num2 = new collatz;
  
int mod_sqrt(int num)
{
  float num2 = num * 1.0;
  num = pow(num2, 0.5) * 1;
  return num;
}

bool isPrime(int arr[], int val)
{
  int B = mod_sqrt(val);
  while( *arr <= B)//it will not check all primes in the array
  {
    if (val % *arr == 0)
    {
      return false;
      break;
    }
    arr++;
  }
  return true;
}

int* extend_arr(int arr[], int length, int val)
{
  int* array2 = new int[length + 1];
    for (int J = 0; J < length; J++)
      array2[J] = arr[J];
    
    array2[length] = val;
    
    delete[] arr;
    arr = NULL;
  
   return array2;
}

void* GenerateCollatzSequence(void*)
{
  int MAX_SIZE = 0;
  int MAX_NUM = 0;
  int SIZE = 0;
  int NUM;
  int * Brry = new int[1];
  int sz = 1;
  Brry[0] = 2;
  for (int u = 3; u < 1000000; u +=2)
    if (isPrime(Brry, u))
    {
      Brry = extend_arr(Brry, sz, u);
      sz++;
    }
    
   for (;sz > 1;sz--, Brry++)
   {
     NUM = *Brry;
     for (;*Brry > 1; SIZE++)
     {
      if (*Brry % 2 != 0)
	*Brry = (3 * *Brry) + 1;
      else
	*Brry /= 2;
     }
     
     if (MAX_SIZE < SIZE)
     {
       MAX_SIZE = SIZE;
       MAX_NUM = NUM;       
     }
     SIZE = 0;
   }
   num1->num = MAX_NUM;
   num1->sequence = MAX_SIZE;
   pthread_exit(&num1);
}

void* GenerateCollatzSequence2(void*)
{
  int M_NUM = 0;
  int _NUM;
  int M_SZ = 0;
  int _SZ = 0;
  long int temp;
  
  for (int b = 999999; b > 1; b-=2)
  {
    _NUM = b;
    temp = b;
    for (;temp > 1; _SZ++)
      if (temp % 2 == 0)
	temp /= 2;
      else
	temp = (3 * temp) + 1;
      
      if (M_SZ < _SZ)
      {
	M_SZ = _SZ;
	M_NUM = _NUM;
      }
      _SZ = 0;
  }
  num2->num = M_NUM;
  num2->sequence = M_SZ;
  pthread_exit(&num2);
}

int main(void)
{
  pthread_t NumThread, primThread;
  
  pthread_create(&NumThread, NULL, GenerateCollatzSequence2, NULL);
  pthread_create(&primThread, NULL, GenerateCollatzSequence, NULL);
  
  pthread_join( NumThread, NULL);
  pthread_join( primThread, NULL);
  
  if (num2->sequence > num1->sequence)
    printf("The colatz number with the largest sequence is %d with %d sequence(s)\n", num2->num, num2->sequence);
  else
    printf("The colatz number with the largest sequence is %d with %d sequence(s)\n", num1->num, num1->sequence);
  
  pthread_exit(NULL);
}

If you want it to be faster, just remove the thread for prime numbers. I made a better version of this which uses vectors instead of arrays so this makes the primes thread run much faster. Infact it finds the largest under 1 billion 10 million in under 2 secs. I will post it here when I get home



Edit:

#include <cstdio>
#include <vector>
#include <pthread.h>
#include <cmath>

void* GenerateCollatzSequence2(void*);
void* GenerateCollatzSequence(void*);

struct collatz
{
  int num;
  int sequence;
};

collatz num1;
collatz num2;

int mod_sqrt(int num)
{
  return (int) (pow(num, 0.5));
}

void isPrime(std::vector<int> *arr, int val)
{
  int B = mod_sqrt(val);
  for(std::vector<int>::iterator Prime = arr->begin(); *Prime <= B; ++Prime)
    if (val % *Prime == 0)
    {
      return;
      break;
    }
  arr->push_back (val);
}

void* GenerateCollatzSequence(void*)
{
  int MAX_SIZE = 0;
  int MAX_NUM = 0;
  int SIZE = 0;
  int NUM;
  std::vector<int> Brry(1, 2);

  for (int u = 3; u < 10000000; u +=2)
    isPrime(&Brry, u);
  int sz = Brry.size();
  
  for (std::vector<int>::iterator isColl = Brry.begin(); sz > 1; sz--, ++isColl)
  {
     NUM = *isColl;
     for (;*isColl > 1; SIZE++)
     {
      if (!((*isColl - 1) & 1))
       *isColl = (*isColl << 1) + (*isColl + 1);
     else
       *isColl >>= 1;
   }

   if (MAX_SIZE < SIZE)
   {
     MAX_SIZE = SIZE;
     MAX_NUM = NUM;       
   }
   SIZE = 0;
 }
 num1.num = MAX_NUM;
 num1.sequence = MAX_SIZE;
 pthread_exit(&num1);
}

void* GenerateCollatzSequence2(void*)
{
  int M_NUM = 0;
  int _NUM;
  int M_SZ = 0;
  int _SZ = 0;
  long int temp;
  
  for (int b = 9999999; b > 1; b-=2)
  {
    _NUM = b;
    temp = b;
    for (;temp > 1; _SZ++)
      if (((temp-1)  & 1))
       temp >>= 1;
     else
       temp = (temp << 1) +(temp + 1);//(temp = (temp * 3) + 1

     if (M_SZ < _SZ)
     {
       M_SZ = _SZ;
       M_NUM = _NUM;
     }
     _SZ = 0;
   }
   num2.num = M_NUM;
   num2.sequence = M_SZ;
   pthread_exit(&num2);
 }

 int main()
 {
  pthread_t NumThread, primThread;
  
  pthread_create(&NumThread, NULL, GenerateCollatzSequence2, NULL);
  pthread_create(&primThread, NULL, GenerateCollatzSequence, NULL);
  
  pthread_join( NumThread, NULL);
  pthread_join( primThread, NULL);
  
  if (num2.sequence > num1.sequence)
    printf("The collatz number with the largest sequence is %d with %d sequence(s)\n", num2.num, num2.sequence);
  else
    printf("The collatz number with the largest sequence is %d with %d sequence(s)\n", num1.num, num1.sequence);
  
  pthread_exit(NULL);
}

[champishere]

Hi cPlusN00b,

Thanks a lot for everything you are doing to me ...I am very very thankful to you and yeah i will start looking into the tutorials for further use thanks once again and please post the code once again when you have it ready after testing.

Thanks

[champishere]

Hi Smac89,

Thanks a lot for your help.You can post the code when you get back home with the vectors instead of arrays and in the meanwhile i will look into this code.


Thanks once again