Collatz conjecture with C (range 1-100,000,000) maximum loops

Question

I am making a program that calculates the most loops of the Collatz conjecture between a range of number (1 - 100,000,000) and I need it to be functional in under 4 minutes on a linux system with the

command gcc -O0 -m32 -Wall -Wextra -Werror -pedantic -o collatz collatz.c.

Any ideas on how to improve the algorithm because after 10,000,000 the program takes too long to complete, keep in mind I can't use multithreading nor pre calculated data.

All answers are welcome, thank you for your time.

// Lets find the longest collatz
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// This function finds how many times it took for a number to reach 1
unsigned long int collatz(uint32_t First_num) {
    // steps measures how many times a number needs to reach 1
    uint32_t steps = 1;
    // This is the loop that applies the rules of the collatz conjecture
    while (First_num != 1) {
        (First_num % 2 == 0) ? (First_numm >>= 1) : (First_num = (3 * First_num + 1) / 2);
        steps++;
    }
    return steps;
}

// This is the function that calculates the maximum loops a number needs to reach 1
int max(uint32_t First_num, uint32_t Second_num) {
    // This "if" determines if the number is correct
    if (First_num <= 0 || Second_num <= 0) {
        printf("0\n");
    }
    uint32_t max = 0;
    uint32_t max_num = 0;
    uint32_t i = First_num;
    // This loop is used to find the maximum times the collatz function needs to be used
    for (i; i <= Second_num; i++) {
        printf("The num %u took the most %ld!!!\n", i, collatz(i));
        // This block finds the number with the most loops
        if ((collatz(i)) >= max) {                                                                                                                                                                                                               
            max = collatz(i);                                                                                              
            max_num = i;
        }
    }
    printf("The num %u took the most %u !!!\n", max_num, max);                                                                                                                                                                        
    return 0;                                                                                                                                                                                                       
}
                                                                                                                                                                                                                               
// This is the main function in which the "max" function is used and the user gives his input and gets his output                                                                                                               
int main(int argc, char **argv) {                                                                                                                                                                                                        
    if (argc != 3) {                                                                                                                                                                                                                         
        printf("Program needs to be called as './prog num1 num2'\n");                                                                                                                                                                   
        return 1;                                                                                                                                                                                                               
    }                                                                                                                                                                                                                       
    //Users input                                                                                                                                                                                                                   
    uint32_t num1 = atoi(argv[1]);                                                                                                                                                                                                  
    uint32_t num2 = atoi(argv[2]);                                                                                                                                                                                                      
    // Users input                                                                                                                                                                                                                  
    max(num1, num2);                                                                                                                                                                                                                 
    return 0;                                                                                                                                                                                                                   
}                                                                                                                                                                                                                               
//End of the program   

Answer 1

Bug

3 * First_num + 1 readily overflows. Need more work (a wider type). @Eric Postpischil

Drop debug output

for (i;i<=Second_num;i++){
  // printf("The num %u took the most %ld!!!\n",i,collatz(i))

Any ideas on how to improve the algorithm because after 10,000,000 the program takes too long to complete

Avoid re-calculation

// if ((collatz(i)) >= max) {
//   max = collatz(i);
unsigned long cc = collatz(i);
if (cc >= max) {                                                                                                                                                                                                               
  max = cc

Save prior work

(or at least some of it.)

#define PRIOR_N (100u*1000*1000)
static uint32_t prior[PRIOR_N];

// This function finds how many times it took for a number to reach 1
unsigned long int collatz(uint32_t First_num) {
  if (First_num < PRIOR_N && prior[First_num] && First_num > 1) {
    return prior[First_num];
  }
  ...

---

After re-work to prevent overflow:

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

#define PRIOR_N (100u*1000*1000)
static uint32_t prior[PRIOR_N];

// This function finds how many times it took for a number to reach 1
unsigned collatz(uint64_t n) {
  if (n < PRIOR_N && prior[n]) {
    return prior[n]; // Use prior work if available.
  }
  // Applies the rules of the Collatz conjecture.
  if (n > 1) {
    unsigned cc;
    if(n % 2 == 0) {
      cc = collatz(n >> 1) + 1;
    } else {
      if (n >= (ULLONG_MAX - 1)/3) {
        fprintf(stderr, "Overflow\n");
        return UINT_MAX/2;
      }
      cc = collatz((3 * n + 1) / 2) + 1;
    }
    if (n < PRIOR_N) {
      prior[n] = cc;  // Save work.
    }
    return cc;
  }
  return n;
}

// 4.5 seconds.
The num 63728127 took the most 593 !!!

---

Empirical: Reverse iteration order

I reversed the order, going from most to least and it took 1/6 less time. (total 3.75 s) TBD why.

---

Aside: OP's code is loose with types changes. Improved code would avoid that.

Answer 2

There are multiple problems in the code:

• there is a typo in the update formula in the body of the while loop:

      (First_num % 2 == 0) ? (First_numm>>=1) : (First_num = (3*First_num+1)/2);
  

  There is an extra m in First_numm. Using an if statement with proper spacing is recommended for readability:

      if (First_num % 2 == 0) {
          First_num >>= 1;
      } else {
          First_num = (3 * First_num + 1) / 2;
      }
  

• timing the program with debugging output is bogus: producing the output may take longer than the computation itself.

• as posted, collatz(i) is computed 3 times: computing the value once per iteration and storing it in a temporary variable will reduce the time with very little effort.

• timing the program compiled with optimisations disabled is only of pedagogical value: on my M2 macbook, the execution time for 100 million is 37.2 seconds with -O3 and just a little more with -O0, which is very surprising. The timing difference may be more important with gcc generating 32-bit code.

• you make the silent assumption that no intermediary value exceeds the range of uint32_t, which is non obvious for starting points as large as 100 million. As a matter of fact, no less than 961803 numbers produce chains with at least one number greater or equal to 2³²!

  Using 64-bit arithmetics produces a different output:

  The num 63728127 took the most 593 !!!
  

• the formula to update First_num in the odd case can be simplified as First_num += (First_num + 1) / 2.

• you could even use a branchless formula to update First_num:

  First_num = (First_num & -(First_num % 2)) + (First_num + 1) / 2;
  

  However this does not seem to produce any runtime gains.

Taking the above remarks into consideration, the modified version below completes in about 28 seconds:

// This function finds how many times it took for a number to reach 1
unsigned long int collatz(uint32_t First_num) {
    // steps measures how many times a number needs to reach 1
    unsigned long int steps = 1;
    // This is the loop that applies the rules of the collatz conjecture
    unsigned long long n = First_num;
    while (n > 1) {
        if (n % 2 == 0) {
            n >>= 1;
        } else {
            // Detect potential overflow
            if (n > ULLONG_MAX - ULLONG_MAX / 2) {
                printf("overflow: %u -> %llu\n", First_num, n);
                return 0;
            }
            n += (n + 1) / 2;
        }
        steps++;
    }
    return steps;
}

Adding an array to cache previous results improves the timing by a factor of 10 for 100 million:

// This function finds how many times it took for a number to reach 1
unsigned long int collatz(uint32_t First_num) {
#define CACHE_SIZE  100000000
#if CACHE_SIZE
    static uint32_t cache[CACHE_SIZE];
#endif
    // steps measures how many times a number needs to reach 1
    unsigned long int steps = 1;
    // This is the loop that applies the rules of the collatz conjecture
    unsigned long long n = First_num;
    while (n > 1) {
#if CACHE_SIZE
        if (n < CACHE_SIZE && cache[n]) {
            steps += cache[n] - 1;
            break;
        }
#endif
        if (n % 2 == 0) {
            n >>= 1;
        } else {
            // Detect potential overflow
            if (n > ULLONG_MAX - ULLONG_MAX / 2) {
                printf("overflow: %u -> %llu\n", First_num, n);
                return 0;
            }
            n += (n + 1) / 2;
        }
        steps++;
    }
#if CACHE_SIZE
    if (First_num < CACHE_SIZE) {
        cache[First_num] = steps;
    }
#endif
    return steps;
}