sol1.c File Reference

Problem 14 solution More...

#include <stdio.h>
#include <stdlib.h>

Include dependency graph for sol1.c:

Functions
long long	collatz (long long start_num)
	Computes the length of collatz sequence for a given starting number.
int	main (int argc, char **argv)
	Main function.

Detailed Description

Problem 14 solution

Author

Krishna Vedala

Since the computational values for each iteration step are independent, we can compute them in parallel. However, the maximum values should be updated in synchrony so that we do not get into a "race condition".

To compile with supporintg gcc or clang, the flag "-fopenmp" should be passes while with Microsoft C compiler, the flag "/fopenmp" should be used. If you are using the provided CMAKE compilation, it will automatically detect OPENMP and compile with it for you.

Automatically detects for OPENMP using the _OPENMP macro.

Function Documentation

collatz()

long long collatz

(

long long

start_num

)

Computes the length of collatz sequence for a given starting number.

{
    long long length = 1;
 
    while (start_num != 1) /* loop till we reach 1 */
    {
        if (start_num & 0x01) /* check for odd */
            start_num = 3 * start_num + 1;
        else
            start_num >>= 1; /* simpler divide by 2 */
        length++;
    }
 
    return length;
}

main()

int main	(	int	argc,
		char **	argv
	)

Main function.

{
    long long max_len = 0, max_len_num = 0;
    long long MAX_NUM = 1000000;
 
    if (argc ==
        2) /* set commandline argumnet as the maximum iteration number */
    {
        MAX_NUM = atoll(argv[1]);
        printf("Maximum number: %lld\n", MAX_NUM);
    }
 
    long long i;
#ifdef _OPENMP
#pragma omp parallel for shared(max_len, max_len_num) schedule(guided)
#endif
    for (i = 1; i < MAX_NUM; i++)
    {
        long long L = collatz(i);
        if (L > max_len)
        {
            max_len = L;     /* length of sequence */
            max_len_num = i; /* starting number */
        }
 
#if defined(_OPENMP) && defined(DEBUG)
        printf("Thread: %2d\t %3lld: \t%5lld\n", omp_get_thread_num(), i, L);
#elif defined(DEBUG)
        printf("%3lld: \t%5lld\n", i, L);
#endif
    }
 
    printf("Start: %3lld: \tLength: %5lld\n", max_len_num, max_len);
 
    return 0;
}

Here is the call graph for this function: