Collatz問題 #2

問題とは、関数collatzに与えるシーケンスの初期値xの値次第で関数内のxがオーバーフローを起こすこと、
および、シーケンスが1に至るとして、そこに至るまでの操作回数がどの程度になるか分からないことである。
操作回数については多分unsigned intの範囲の初期値に対してunsigned intの範囲を超えないような気もするが、
初期値に関しては3倍してunsigned intの範囲を超えるような、
例えば手元の環境ならx=2000000001を与えれば一発でオーバーフローする。
初っ端のオーバーフローは簡単に予見できても、操作途中でいつオーバーフローするかは分からないので対策は必要である。
そこで、とりあえず両者ともに多倍長精度の変数として実装してみることにする。
というわけで以前にも使用した多倍長精度演算ライブラリのGMPを用いて書いてみる。

#include <gmp.h>

void collatz(mpz_t iter, mpz_t x);

void collatz(mpz_t iter, mpz_t x)
{
    mpz_t n;
    mpz_init_set(n, x);
    mpz_set_ui(iter, 0UL);
    while (mpz_cmp_ui(n, 1UL) > 0) {
        if (mpz_odd_p(n)) {
            mpz_mul_ui(n, n, 3UL);
            mpz_add_ui(n, n, 1UL);
        } else {
            mpz_tdiv_q_2exp(n, n, 1);
        }
        mpz_add_ui(iter, iter, 1UL);
    }
    mpz_clear(n);
}

int main(void)
{
    mpz_t x, iter;
    mpz_init_set_ui(x, 2000000001UL);
    mpz_init(iter);
    collatz(iter, x);
    gmp_printf("%Zu\n", iter);
    mpz_clear(x);
    mpz_clear(iter);
    return 0;
}

main関数最後の二つのmpz_clearは、

    mpz_clears(x, iter, NULL);

でもいいが、stdio.hをインクルードするなどしてNULLの定義が必要。
さて、実行の結果、初期値2000000001のシーケンスは、
2000000001 6000000004 3000000002 1500000001 4500000004 2250000002 ... 8 4 2 1
のようになって、collatz(2000000001) = 163 となった。
これをオーバーフロー対策前のコードで実行すると、
2000000001 1705032708 852516354 426258177 1278774532 639387266 ... 8 4 2 1
と、いきなり間違い計算（範囲外の上位ビットを無視）をし、操作回数も125と誤ってしまう。