Multiplication Algorithm Based on Collatz Function

[ghost]

Would you be able to share the code for the results in your new paper? It was very interesting.
Thanks.

[xbarin02]

Yes, my implementation in libgmp is as follows:

#include <gmp.h>
#include <assert.h>

mp_bitcnt_t mpz_ctz(const mpz_t n)
{
	return mpz_scan1(n, 0);
}

void mpz_divexact_by3(mpz_t q)
{
	size_t n = mpz_size(q);
	mp_limb_t *lq = mpz_limbs_modify(q, n);
	mpn_divexact_by3(lq, lq, n);
	mpz_limbs_finish(q, n);
}

void mul(mpz_t m, const mpz_t a)
{
	assert(mpz_odd_p(m));

	if (mpz_cmp_ui(m, 1UL) == 0) {
		mpz_set(m, a);
		return;
	}

	mpz_addmul_ui(m, m, 2);
	mpz_add_ui(m, m, 1);

	mp_bitcnt_t beta = mpz_ctz(m);

	mpz_fdiv_q_2exp(m, m, beta);

	mul(m, a);

	mpz_mul_2exp(m, m, beta);

	mpz_sub(m, m, a);
	mpz_divexact_by3(m);
}

If you are interested in a speed measurement program, you can find it here.