Calculate a math sequence that converges

Question

Thanks for taking the time to read this. I could use a few pointers. I have written much better code but wrote this as a quick test. There is obviously a major issue/s somewhere except for the functionality as it was dismissed immediately. There is another question on same code but a different topic.

 /*
 * Assessment Linschoten 65ft
 * calculates collatz up to limit of 10^6 on standard desktop pc
 * 
 * optionally increase stack size on linux
 * ulimit -t 300 -l 4086688 -s 81920
 */
#include "calculate.h"
uint64_t odd(uint64_t x){
 return x*3 + 1;
}
uint64_t even(uint64_t x){
 return x/2;
}
/*
 * Iterative process until sequence converges to 1.
 */
colliez* calculate(uint64_t u_limit_in) {
 //keep track of biggest number and sequence counter
 uint64_t xn = u_limit_in;
 uint64_t s_length_counter = 0;
 uint64_t max_nr = 0;
 colliez *computed_data_ptr = malloc(sizeof(colliez));
 while (xn != 1) {
 if (xn % 2 == 0) {
 xn = even(xn);
 }
 else{
 xn = odd(xn);
 if (xn>=max_nr) {
 max_nr = xn;
 }
 }
 s_length_counter++;
 }
 if (computed_data_ptr==NULL) {
 printf("null ptr");
 }
 computed_data_ptr->start_seq = u_limit_in;
 computed_data_ptr->max_nr = max_nr;
 computed_data_ptr->count_val = s_length_counter;
 return computed_data_ptr;
}
/*
 * Commandline application called with one argument
 * eg ./Colliez 3
 */
int main(int argc, char *argv[])
{
 int a, n;
 char in_limit[ 20 ];
 uint64_t in_limit_data;
 char ns[ 20 ];
 uint64_t xn;
 colliez *raw_calc;
 raw_calc = NULL;
 // first process user input
 if (argc != 2) {
 printf("\n Enter the value of the upper limit : ");
 scanf("%s", in_limit);
 printf("\n %s \n", in_limit);
 long dud = atoi(in_limit);
 in_limit_data = (uint64_t)dud;
 fflush(stdin);
 printf("\n");
 }else{
 long dud = atoi(argv[1]);
 in_limit_data = (uint64_t)dud;
 }
 
 uint64_t cmd_user_arg1 = (uint64_t) in_limit_data;
 // 40% of input value. Used to calculate the test range for longest sequence length.
 float empiric_batch_size = cmd_user_arg1*0.40;
 uint64_t empiric_batch_size_int = round(empiric_batch_size);
 uint64_t lower_limit = cmd_user_arg1 - empiric_batch_size;
 printf("Calculating Collatz: \n");
 printf("---");
 printf("\nempirical guess of lower limit with longest sequence chain : %lu \n", lower_limit);
 uint64_t x = 0;
 // run through inputs high-low
 if (cmd_user_arg1>0) {
 colliez *final = malloc(sizeof(colliez));
 uint64_t largest_start_sequence;
 uint64_t new_val = 0;
 uint64_t old_val = 0;
 //just to be safe include one more integer on limit of empiric approximation.
 uint64_t counter_res;
 while (x<=empiric_batch_size_int) {
 counter_res = cmd_user_arg1 - x;
 if (raw_calc!=NULL) {
 free(raw_calc);
 }
 raw_calc = calculate(counter_res);
 new_val = raw_calc->count_val;
 if (new_val>old_val) {
 old_val = new_val;
 largest_start_sequence = raw_calc->start_seq;
 //keep track of ptr to resulting struct
 final = raw_calc;
 raw_calc = NULL;
 }
 x++;
 }
 printf("largest value in sequence : %lu \n", final->max_nr);
 printf("start : %lu \n", final->start_seq);
 printf("steps : %lu \n", final->count_val);
 printf("\nFinished. \nLongest sequence is : %lu \n \n", final->count_val);
 } 
 return 0;
}

and the header file

/*
 *
 * Assessment
 */
#ifndef _CALCULATE_H
#define _CALCULATE_H
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
typedef struct colli{
 uint64_t start_seq;
 uint64_t max_nr;
 uint64_t count_val;
 } colliez;
uint64_t odd(uint64_t x);
uint64_t even(uint64_t x);
colliez * calculate(uint64_t u_limit_in);
#endif

For numbers larger than 108 this will run for quite a few minutes. I tried some tweaking with ulimit but did not have the time to confirm if it helps a lot.

I have been doing Web development for the last few years and have a degree in electronics. Getting a good understanding of C is essential to my career path but I have had very hostile behaviour after attempting to apply for jobs. It's almost like being tortured by the CIA.

Your comments would be appreciated.

Answer 1

Don’t Import Unnecessary Things in Headers

Currently, "calculate.h" brings in several system files that it doesn’t ever use, but either your main() or calculate() routines need. That makes the header less re-usable in other projects.

It also exposes internal interfaces, such as even and odd, that should not be part of the public API. If anybody else uses your API, that makes it harder to refactor the code into something more efficient, because you’d have no idea what other code might depend on the functions being there.

Right now, you seem to be trying to have all the files in your project include a single header that covers everything. What you instead want is something like a collatz.c module, with a matching collatz.h header containing only the interfaces for that module.

In this case, all you need are the include-guard, the declaration of calculate, and the definition of its return type.

Do You Need a Header at All?

You don’t actually have separate .c files. Therefore, you don’t need to externally link to any function or object declared elsewhere, or repeat the same boilerplate at the start of any two of them. You also don’t need function prototypes if the functions are declared before they are called. You can just declare the result type, then any helper functions calculate uses, then calculate, then main.

A .h file should either correspond to one .c file, or put in one convenient place boilerplate that multiple .c files all need, such as configuration.

Use Unambiguous, Unsurprising Names

You apparently spell Collatz three different ways in this program, although there might be a reference I’m missing. If there is, it would be a good thing to leave a comment on. Try to avoid giving things names that will confuse people.

Since C does not have namespaces, you may want to give every identifier in a module a prefix, like collatz_. The name calculate is so general that it’s very likely some other program that wants to re-use your code will use it. It would be better to call it collatz_calculate or collatz_test. If modularizing this code would be overkill, I still recommend giving it a less-generic name that says what it’s calculating, like collatz(n).

It’s customary to give types names that end with _t. So the struct holding the return value could be named something like collatz_result_t or collatz_t. It also probably doesn’t need a start_seq member, since the caller already knows what value it passed to the function.

Use const Where Appropriate

You declare most of your variables C89-style. Wherever possible, you should declare and initialize them as const.

Writing your variables as static single assignments makes the code much easier to debug and reason about, since you know that everything has been set once and only once, and exactly what it was set to. This both helps the compiler optimize (especially loops like this where there’s another reference to one of the variables in scope), and also saves you from bugs where a variable is not set on some path, or changed from what you expect.

Use Integer Math Where Possible

Currently, you convert from uint64_t to double, then float (giving yourself a huge round-off error):

float empiric_batch_size = cmd_user_arg1*0.40;

Since a factor of 0.40 is two-fifths, and integer math always rounds toward zero, it would be better to write:

const uint64_t approx_batch_size = (user_val*2U + 3U)/5U;

(Assuming your user-supplied starting value can be doubled without overflowing.)

Refactor into Helper Functions

A good example of this are the routines to read the user input. This routine uses a lot of data that the rest of the program doesn’t have any need to see, and none of it is marked const. Some of that data can confuse the optimizer or a maintainer. It would be better to separate that out into a function that returns the user-supplied value, the only output the rest of the program needs.

Dynamically Allocate Memory Only When Necessary

Others have mentioned this, but it is very important for performance. You can just return a struct, and the compiler will allocate the buffer for it automatically. That’s probably simplest. Another good approach if you want to be able to report an error is to take the address of the result buffer as a parameter. This would let you use a local variable as the buffer, or at least re-use the same buffer instead of freeing and re-allocating it each time. However, this function cannot fail (except by running out of memory), although it might possibly run forever.

Consider More-Robust Error-Checking

For example, the odd case of the conjecture could overflow the type, or the input could be invalid.

When possible, rewrite your functions so they can’t fail. For example, if you just read in an unsigned long long, you don’t need to copy it to a buffer or convert it. If you don’t allocate dynamic memory, you can’t get an out-of-memory error.

Next-best is to fail fast. There’s no point to reporting errors up the call chain unless you’ll be handling or retrying them there. But, you could retry reading the input immediately, in the input routine, and only return when you get a valid input. Or, on a fatal error, you could abort immediately. That way, functions only ever return if they succeed, and their results do not need to be checked.

Consider a Tail-Recursive Implementation

The fact that you have a comment suggesting increasing the maximum stack size is a strong warning that something’s gone wrong. It should be possible to get the compiler to write a version that uses only a constant amount of stack space.

On top of that, recursive implementations can use static single assignments and are generally easier to verify and maintain.

Consider a typedef

Several people have mentioned the possibility of changing the type used for calculations. This will be a lot easier if you can change one typedef than if you have to change a thousand lines of code that say uint64_t. (In C, though, this can easily bite you because something like the overflow check or output specifier breaks silently on the new type. C++ has many more features for working with generic types.)

Consider Memoizing the Function

There’s a lot of recalculation of the same values in this function, as you iterate over the possible starting values. If you stored some or all the previously-computed values in a table, you could mark them off in constant time as soon as you encountered them again: the sequence has that many remaining steps, and you could also look up the largest value in the rest of the sequence.

Putting it All Together

Compare this to the original, and see whether it looks more maintainable:

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
/* Use the musttail attribute to guarantee tail-call optimization, but only on
 * compilers that support it.
 */
#if __clang__ || __INTEL_LLVM_COMPILER
# define MUSTTAIL __attribute__((musttail))
#else
# define MUSTTAIL /**/
#endif
typedef unsigned long long int value_t;
/* The return values of collatz_test. */
typedef struct collatz_result_t {
 value_t max_nr; // Maximum number reached
 value_t count_val; // Count of sequence values
} collatz_result_t;
/* Tail-recursive helper function for collatz_test. Aborts if the sequence
 * would overflow an unsigned long long int.
 */
static collatz_result_t collatz_test_helper( const value_t n,
 const value_t max,
 const value_t counter ) {
 static const value_t overflow_if_odd_limit = ULLONG_MAX / 3;
 const value_t new_max = (n>max) ? n : max;
 if (n <= 1) {
 return (collatz_result_t){max, counter};
 } else if (n%2 == 0) {
 MUSTTAIL return collatz_test_helper(n/2, new_max, counter+1);
 } else if (n < overflow_if_odd_limit) {
 MUSTTAIL return collatz_test_helper(3*n + 1, new_max, counter+1);
 } else {
 fflush(stdout);
 fprintf(stderr, "Collatz sequence overflows after %llu.\n", (unsigned long long)n);
 exit(EXIT_FAILURE);
 }
}
/* Returns the length and maximum value of the Collatz sequence beginning at
 * start--If the Collatz conjecture is correct. (And, more realistically, if
 * it doesn't overflow.)
 */
collatz_result_t collatz_test(const value_t start) {
 return collatz_test_helper(start, start, 0);
}
/* Parses a start value from a command-line argument. */
value_t value_from_cl(const char* const argv1) {
 return strtoull(argv1, NULL, 10);
}
/* Reads a start value from the input FILE*. */
value_t value_from_file(FILE* const input) {
 unsigned long long value_read = 0;
 if (1 != fscanf(input, "%llu ", &value_read)) {
 fflush(stdout);
 fprintf(stderr, "Error reading a starting value from stdin.\n");
 exit(EXIT_FAILURE);
 }
 return value_read;
}
/*
 * Commandline application called with one argument
 * eg ./collatz 3
 */
int main(const int argc, const char* const argv[])
{
 const value_t start_val = (argc == 2) ? value_from_cl(argv[1]) :
 value_from_file(stdin);
 
 // 40% of input value. Used to calculate the test range for longest sequence length.
 const value_t batch_size = (start_val*2U + 3U)/5U;
 const value_t lower_limit = start_val - batch_size;
 printf("For the Collatz sequences up to %llu, the longest sequence is predicted to start with %llu.\n",
 start_val,
 lower_limit );
 value_t longest_start = 0;
 value_t longest_len = 0;
 value_t longest_max = 0;
 for (value_t i = 0; i < start_val; ++i) {
 const collatz_result_t r = collatz_test(i);
 if (r.count_val > longest_len) {
 longest_start = i;
 longest_len = r.count_val;
 longest_max = r.max_nr;
 }
 }
 printf("The longest sequence starts at %llu and has %llu steps, reaching a maximum value of %llu.\n",
 (unsigned long long)longest_start,
 (unsigned long long)longest_len,
 (unsigned long long)longest_max );
 return EXIT_SUCCESS;
}

And a link to Godbolt.

• chux: Disagree with "Wherever possible, you should declare and initialize them as const". 1) In general, it makes function definitions noisy without much gain. 1) const argv1 in value_t value_from_cl(const char* const argv1) { return strtoull(argv1, NULL, 10); } does not help much. 2) Not needed in function declaration as there it is certainly noise. 3) When not in declaration, yet in definition, more maintenance to coordinate. 4) As main() has special rules about it, better to stick to its standard form. 5) IMO, only useful in large functions that need that clarity. ...
• chux: ... As such, it is a style issue and best guided by the group's coding standard.
• chux: overflow_if_odd_limit = ULLONG_MAX / 3 and n < overflow_if_odd_limit is a tad too conservative. Better as overflow_if_odd_limit = (ULLONG_MAX - 1)/ 3 and n <= overflow_if_odd_limit. I think ULLONG_MAX as (1ULL << (3*i +2))-1 demos the edge cases.
• chux: "it would be better to write: const uint64_t approx_batch_size = (user_val*2U + 3U)/5U;" --> user_val*2U risks overflow. Since the size is "approx", something like (user_val/5*2U + ...) handles all uint64_t user_val.
• Davislor: @chux-ReinstateMonica I currently convert the value_t type to unsigned long long on output. Using %ju instead is a good suggestion. The strtoull call could've been replaced with a sscanf(arg, "%ju", &input_val) or the like. The other line of code that would break is the overflow check, and in hindsight, I should have added a static_assert for the invariant. C++ has a way to specify the maximum value of an arbitrary integral type; C doesn’t.

Answer 2

General Observations

If this is embedded code than it would be helpful to know what device it is supposed to run on. Word size on many devices is 32 bits or less. Generally allocating memory (using malloc(), calloc() or realloc()) should be avoided in embedded code to to the restricted memory size of most devices.

Does the code actually need 64 bit integers to work or can it just use the word size of the device, this might help improve performance.

If the code is not embedded, compile -O3 to improve performance, if the code is embedded you may not be able to use the highest level of optimization.

The code might run faster if there are less or no malloc() calls, memory allocation at run time is expensive.

Include Files

The include file does have the proper format, including include guards.

This code does not appear to need the header file, all the code can be in the C source file.

Do not hide all of the standard include directives in a header file, this makes the code difficult to maintain.

Only include what is necessary in any C source file. The mechanism used by C and C++ to include files is to actually copy the code from the header files into the intermediate code. This can increase the compile / build times.

If the code does need the header file, the function prototypes for the functions odd() and even() are not necessary. Those 2 functions should be static functions inside calculate.c since only the calculate() function calls them.

Convention When Using Memory Allocation in C

When using malloc(), calloc() or realloc() in C a common convention is to sizeof(*PTR) rather sizeof(PTR_TYPE), this make the code easier to maintain and less error prone, since less editing is required if the type of the pointer changes.

 colliez* computed_data_ptr = malloc(sizeof(*computed_data_ptr));

Don't malloc() memory until you actually need it. The call to malloc() in the calculate function should be after the while loop completes. I initially missed the code to test the call to malloc() since the malloc() was before the while loop and the test was after the while loop.

Compiler Warnings

When I compile the code there are a number of unused variables reported. This can lead to bugs being introduced in the code. There also a number of type mismatch warnings, this can lead to inaccuracy in the output.

'initializing': conversion from 'double' to 'float', possible loss of data
'initializing': conversion from 'double' to 'unsigned long', possible loss of data
'initializing': conversion from 'float' to 'unsigned long', possible loss of data
'a': unreferenced local variable
'ns': unreferenced local variable
'n': unreferenced local variable
'xn': unreferenced local variable

The type mismatches are on these lines:

 // 40% of input value. Used to calculate the test range for longest sequence length.
 float empiric_batch_size = cmd_user_arg1 * 0.40;
 unsigned long empiric_batch_size_int = round(empiric_batch_size);
 unsigned long lower_limit = cmd_user_arg1 - empiric_batch_size;

Use the compiler to find possible issues in the code by enabling all the warning messages.

Complexity

Both the main() function and the calculate() function are too complex (do too much).

This code in main() should be in a function:

 // first process user input
 if (argc != 2) {
 printf("\n Enter the value of the upper limit : ");
 scanf("%s", in_limit);
 printf("\n %s \n", in_limit);
 long dud = atoi(in_limit);
 in_limit_data = (unsigned long)dud;
 fflush(stdin);
 printf("\n");
 }
 else {
 long dud = atoi(argv[1]);
 in_limit_data = (unsigned long)dud;
 }

Example:

unsigned long user_input(int argc, char* argv[])
{
 char in_limit[20] = { 0 };
 unsigned long in_limit_data;
 // first process user input
 if (argc != 2) {
 printf("\n Enter the value of the upper limit : ");
 scanf("%s", in_limit);
 printf("\n %s \n", in_limit);
 long dud = atoi(in_limit);
 in_limit_data = (unsigned long)dud;
 fflush(stdin);
 printf("\n");
 }
 else {
 long dud = atoi(argv[1]);
 in_limit_data = (unsigned long)dud;
 }
 return in_limit_data;
}
/*
 * Commandline application called with one argument
 * eg ./Colliez 3
 */
int main(int argc, char* argv[])
{
 colliez* raw_calc;
 raw_calc = NULL;
 unsigned long cmd_user_arg1 = user_input(argc, argv);
...

In the calculate() function these lines should be in their own function:

 while (xn != 1) {
 if (xn % 2 == 0) {
 xn = even(xn);
 }
 else {
 xn = odd(xn);
 if (xn >= max_nr) {
 max_nr = xn;
 }
 }
 s_length_counter++;
 }

Code Organization Question

Why are these 3 lines executed if cmd_user_arg1 is less than zero?

 printf("Calculating Collatz: \n");
 printf("---");
 printf("\nempirical guess of lower limit with longest sequence chain : %lu \n", lower_limit);

• J123: Fantastic! thanks for the comment. The test was very open ended and question only a few lines long so I optimized for the input range to be quite large. this was only one of the variations for the question.
• J123: And yes they need 64 bit integers as series can grow to be much larger than the input and at time of writing code it was unknown to me how to calculate max value it is probably possible there is a formula.
• J123: cmd_user_arg1=0; does not compute since the series converges to one. thats just one way of doing it.
• chux: @pacmaninbw, scanf("%s", in_limit); is as bad as gets(). Consider alternatives.
• pacmaninbw: @chux-ReinstateMonica Agree with both your comments. I was using the OP's code with examples about how to make the code more modular.

Answer 3

Do not use "%s" without a width

scanf("%s", in_limit); is a hackers delight. Use a width:

char in_limit[ 20 ];
...
scanf("%19s", in_limit);

Even better: research fgets().

Why naked magic number 20?

What is special about 20? The range of uint64_t is [0...18,446,744,073,709,551,615] and that needs 21 char to save as a string.

#define STRINGIFY(x) #x
#define TOSTRING(x) STRINGIFY(x)
#define UINT64_STR_LEN_MAX 20
char in_limit[UINT64_STR_LEN_MAX + 1];
...
scanf("%" TOSTRING(UINT64_STR_LEN_MAX) "s", in_limit);

Avoid lots of types

Code below uses 3 integer type when less can be used.

//long dud = atoi(in_limit);
//in_limit_data = (uint64_t)dud;
unsigned long long dud = strtoull(in_limit, 0, 0);
in_limit_data = (uint64_t)dud;

Better code would also look for conversion errors.

Use matching specifier

max_nr is a uint64_t. Use PRIu64 from <inttypes.h>.

// printf("largest value in sequence : %lu \n", final->max_nr);
printf("largest value in sequence : %" PRIu64 " \n", final->max_nr);

Space before '\n'?

Printing " \n" adds an unneeded trailing space. Consider "\n".

Why uint64_t?

These is no driving reason for such a fixed width type. Consider uintmax_t if wanting a large integer type on your system.

Detect overflow

return x*3 + 1; risks overflow and lead to incorrect results.

Better to test

if (x > (UINT64_MAX - 1)/3) {
 fprintf(stderr, "Overflow on %" PRIu64 "*3 + 1\n", x);
 exit(EXIT_FAILURE);
}

Again, excess types

Consider the following which takes a uint64_t, converts it to double, double multiplies and then narrows to float

float empiric_batch_size = cmd_user_arg1*0.40;

This takes a float, promotes to double, calls double round(double) and then converts to uint64_t.

uint64_t empiric_batch_size_int = round(empiric_batch_size);

Instead: Avoid float unless truly needed.

double empiric_batch_size = cmd_user_arg1*0.40;
uint64_t empiric_batch_size_int = round(empiric_batch_size);

Or better, stay with integer math:

uint64_t empiric_batch_size_int = cmd_user_arg1 / 5 * 2; // or the like

Avoid undefined behavior (UB)

fflush(stdin) is UB. Do not use that.

Define locally

Reduce the scope and lifetime of objects to the needed range.

 // uint64_t counter_res;
 // while (x<=empiric_batch_size_int) {
 // counter_res = cmd_user_arg1 - x;
 while (x<=empiric_batch_size_int) {
 uint64_t counter_res = cmd_user_arg1 - x;
 ...
 raw_calc = calculate(counter_res);
```

Answer 4

Consecutive string literals are concatenated:

Make a single call to printf():

#if 0
printf("largest value in sequence : %lu \n", final->max_nr);
 printf("start : %lu \n", final->start_seq);
 printf("steps : %lu \n", final->count_val);
 printf("\nFinished. \nLongest sequence is : %lu \n \n", final->count_val);
 } 
else 
printf ("largest value in sequence: %lu \n"
 "start : %lu \n"
 "\nFinished. \nLongest sequence is : %lu \n \n",
 final->max_nr,
 final->start_seq,
 final->count_val);
#endif 

Answer 5

Maintainability of your code

The main problem is not necessarily the algorithm or specific misuses of functions, but rather that your code is way too convoluted. This code is equivalent to yours, but over twice as short.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
long f(long x)
{
 return (x % 2 == 0) ? x / 2 : 3 * x + 1;
}
int main(int argc, char *argv[])
{
 if (argc != 2) {
 printf("Usage: %s n\n", argv[0]);
 return EXIT_FAILURE;
 }
 long n = atol(argv[1]);
 long largest = 1;
 long start = 1;
 long steps = 0;
 long longest = 0;
 for (long i = 2; i < n; i++) {
 long x = i;
 long local_steps = 0;
 bool this_is_longest = false;
 while (x != 1) {
 x = f(x);
 local_steps++;
 if (x >= largest) {
 largest = x;
 steps = local_steps;
 this_is_longest = true;
 }
 }
 if (this_is_longest) {
 longest = local_steps;
 start = i;
 }
 }
 printf("largest value in sequence : %ld \n", largest);
 printf("start : %lu \n", start);
 printf("steps : %lu \n", steps);
 printf("\nFinished. \nLongest sequence is : %lu \n \n", longest);
 return EXIT_SUCCESS;
}

Performance

This code runs in about 30s. Commenting out everything in the tight loop except x = f(x) reduces total time to about 26s, so that suggests that the branch prediction in f is to blame. The only way to really improve this is to parallelise your code using pthreads or OpenMP. I can extend the answer with this if you want, but I understand if that is outside the scope of your question. The main performance bottleneck in your code was the (de)allocating of memory. This is not necessary. If you insist on a struct, you can declare it as a global variable or allocate it once and pass it into your functions.

• J123: I will have to accept the first answer as it was very close to perfect but also very fast to reply. Thanks for all the help I have completed several projects in the mean time.