Here is rules for generating Collatz sequence:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Problem 14 contains a question:Which starting number, under one million, produces the longest chain?
I decided to play with C++ little bit and utilize CPU cores. So my solution written using C++ and multithreading programming.
//============================================================================ // Name : LongestCollatzSequence.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include <cstdlib> #include <pthread.h> #include <sys/time.h> #include <ctime> using namespace std; long maxVal=0; long actualNumber=0; #define NUM_THREADS 5 #define LIMIT 1000000 pthread_mutex_t lock; 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; } long calcNCount(long n) { long result = n; if (result <= 1) return 1; if (result % 2 == 0) return 1+calcNCount(result/2); return 1+calcNCount(3*result+1); } void* DoJob(void* num){ long result=calcNCount((long)num); pthread_mutex_lock(&lock); if(result>maxVal){ maxVal=result; actualNumber=(long)num; } 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; } pthread_t threads[NUM_THREADS]; pthread_attr_t attr; void *status; int rc; // Initialize and set thread joinable pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); long i=1; while(i<LIMIT){ int countThreads=0; for(int j=0; j < NUM_THREADS; j++ ){ i++; if(i<LIMIT){ rc = pthread_create(&threads[j], NULL, DoJob, (void *)i ); if (rc){ cout << "Error:unable to create thread," << rc << endl; exit(-1); } countThreads++; } else break; } for( int j=0; j < countThreads; j++ ){ rc = pthread_join(threads[j], &status); if (rc){ cout << "Error:unable to join," << rc << endl; exit(-1); } } //cout<<"processed:"<<i<<endl; } pthread_mutex_destroy(&lock); // free attribute and wait for the other threads pthread_attr_destroy(&attr); timestamp_t t1 = get_timestamp(); double secs = (t1 - t0) / 1000000.0L; cout<<"time elapsed="<<secs<<endl; cout<<"result:"<<actualNumber<<endl; pthread_exit(NULL); }
Current NUM_THREADS= 5 T tried different numbers of threads- but 5 thread - achieved best time result.
According to lscpu I have 6 cores only, so I'm not really sure if I understood why 5 threads calculate result faster then 6 threads.
