Computational verification of Collatz conjecture using gmplib

Question

Prerequisites

The unsigned long type has a size of 64 bits.

The following macros are defined.

/* all 3^n for n < 41 fits into 64-bit unsigned long */
#define LUT_SIZE 41
/* any reasonably high number */
#define LUT_SIZEMPZ 512

The following array is defined and properly initialized with corresponding values.

/* lut[n] contains 3^n */
mpz_t lut[LUT_SIZEMPZ];

Additionally, the following auxiliary function is defined.

/* count trailing zeros */
mp_bitcnt_t mpz_ctz(const mpz_t n)
{
 return mpz_scan1(n, 0);
}

Problem

This code review request follows my previous request Computational verification of Collatz conjecture. The implementation in this request should handle the numbers which cannot be handled with the code in previous post.

In short: My program verifies the convergence of the Collatz problem, using this algorithm. The convergence for all values n ≤ 87 ×ばつ 2⁶⁰ has already been proven.

The following function is called for n of the form \4ドルn+3\$, in order from the smallest one to the largest one, only if all preceding calls returned zero.

This function should either

• return 0 if the problem for the n is convergent, or
• loop infinitely if the trajectory for the n is cyclic.

Code

The 128-bit input n is split into two 64-bit parts nh and nl such that n = nh * 2^64 + nl.

int check_convergence(unsigned long nh, unsigned long nl)
{
 mpz_t n;
 mpz_t n0;
 mpz_t n_max;
 mp_bitcnt_t e;
 mpz_init_set_ui(n, nh);
 mpz_mul_2exp(n, n, (mp_bitcnt_t)64);
 mpz_add_ui(n, n, nl);
 mpz_init_set_ui(n_max, 87UL);
 mpz_mul_2exp(n_max, n_max, (mp_bitcnt_t)60);
 mpz_init_set(n0, n);
 do {
 if (mpz_cmp(n, n_max) <= 0) {
 mpz_clear(n);
 mpz_clear(n0);
 mpz_clear(n_max);
 return 0;
 }
 mpz_add_ui(n, n, 1UL);
 e = mpz_ctz(n);
 mpz_fdiv_q_2exp(n, n, e);
 assert( e < LUT_SIZEMPZ );
 mpz_mul(n, n, lut[e]);
 mpz_sub_ui(n, n, 1UL);
 mpz_fdiv_q_2exp(n, n, mpz_ctz(n));
 if (mpz_cmp(n, n0) < 0) {
 mpz_clear(n);
 mpz_clear(n0);
 mpz_clear(n_max);
 return 0;
 }
 } while (1);
}

Answer 1

If you need a type with exactly 64 bits, use uint64_t (from <stdint.h>). That will give a clear compilation error if no such type is available.

Given that the function never returns anything other than zero, we can move the cleanup of n, n0 and n_max outside the loop, and simply break to reach them.

Is indefinite looping really a good output if a cycle is detected? How is that distinguishable from an arbitrarily long (but finite) chain? Look up the standard algorithms for cycle detection in your graph theory textbook.

• DaBler: The problem with gmplib is that it does not support uint64_t. It only supports standard C types like unsigned int: gmplib.org/manual/Assigning-Integers.html#Assigning-Integers
• DaBler: The program is part of distributed computing project. I cannot distinguish these two situations. I can however focus on particular assignments that have not been returned for a long time or that have not been returned from several different nodes.

Answer 2

I would use uint64_t even if the API asks for an unsigned long. It's far more precise about what it is, and you can always ensure that both are the same.

Assuming your C version is>= GNU C11 you can use the following code just below your #includes (actually anywhere, but I like it on top):

_Static_assert(__builtin_types_compatible_p(uint64_t, unsigned long),
 "uint64_t != unsigned long");

This code doesn't need to go inside a function.

If you just have C99 (Edit: GNU C99), you can do something similar:

#if (sizeof(uint64_t) != sizeof(unsigned long))
#error "uint64_t != unsigned long"
#endif

You could even write your own wrapper around GMP functions that uses <stdint.h> types.

If for whatever reason unsigned long changed suddenly to uint32_t or uint128_t, you would notice, instead of having new bugs everywhere.

• DaBler: I have received similar feedback through github today. I'll make over wrappers for ligmp functions. Anyhow, I use the C89 standard (+ GNU extensions), but it shouldn't matter so much. You should be however aware of that the #if (sizeof(uint64_t) != sizeof(unsigned long)) is compiler extension. The C preprocessor does not know the unary operator sizeof. The fact that these constructs work is just due to extensions of compilers.
• DaBler: Anyway, good feedback.
• alx - recommends codidact: @DaBler Yes, it was me in GitHub :p
• alx - recommends codidact: @DaBler Good to know that about sizeof. I thought it was standard. I found this interesting: stackoverflow.com/q/4079243/6872717
• DaBler: I posted a comment in GitHub to you...