コラッツ・角谷の問題 in C DouKaku?

任意の数nを与えたときに
・nが偶数ならば2で割る　(n=n/2)
・nが奇数ならば3倍して1を足す （n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
（すべての数について成り立つかは不明）
参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

see: コラッツの問題の成り立つ範囲

これ、キミならどう書く 2.0 - ROUND 2 -と同じ問題ですね。違うのは、LL Ringの時の「どう書く」では、1の時も1と数えるので、1違うだけで。

その時にいろいろ書いて出来た最速の奴を。j詳しくは404 Blog Not Found:h(4294967295) = 2610744987 where g = 1051 をご覧下さい。

途中経過表示をやめれば、もっと速くなるでしょう。

Dan the Number Cruncher

/*
Core 2 Duo 2.33GHzで

% time ./a.out 1000000
h(1000000) = 837799 where g(837799) = 525
0.264u 0.006s 0:00.27 96.2%     0+0k 0+0io 0pf+0w
*/

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

#ifndef CACHE_SIZE
#define CACHE_SIZE 64*1024*1024 /* large enough */
#endif

#define MAX_U16        65535
typedef unsigned short U16;
typedef long long      I64;

U16 *cache;
int cachesize;
#define lookup(n)  ((n) < cachesize ? cache[(n)] : 0)
#define store(n,g) if ((n) < cachesize && g <= MAX_U16) cache[(n)] = (g)

I64 g(I64 n){
    I64 result = lookup(n);
    if (result) return result;
    I64 i = n;
    I64 l;
    result = 1;
    while (i > 1){
        i = i & 1 ? i*3+1 : i >> 1;
        l = lookup(i);
        if (l){
            result += l;
            break;
        }else{
            result++;
        }
    }
    if (i < 1)       fprintf(stderr, "overflow! g(%qd) = %qd\n", n, i);
    store(n, result);
    return result;
}

I64 *h(I64 n){
    I64 i, nmax = 0, gmax = 0, gnext = 0;
    static I64 result[2];
    for (i = n; i > 1 ; i--){
        gnext = g(i);
#ifdef VERBOSE
        fprintf(stderr, "g(%qd) = %qd\r", i, gnext);
#endif
        if (gnext > gmax){
            nmax = i; gmax = gnext;
        }
        if (i & 0xffff) continue;
       printf("nmax = %qd, gmax = %qd, n = %qd\r", nmax, gmax, i);
       fflush(stdout);
    }
    result[0] = nmax; result[1] = gmax;
    return result;
}

#define min(x,y) ((x) < (y) ? (x) : (y))

void init_cache(I64 n){
    cachesize = min(n, CACHE_SIZE);
    cache     = (U16 *)calloc(cachesize, sizeof(U16));
    if (cache == NULL) exit(-1);
}

int main(int argc, char **argv){
    I64 n = 0xffffffff; /* look @ this! */
    if (argc > 1){
        n = atoll(argv[1]);
    }
    init_cache(n);
    I64 *hg = h(n);
    printf("h(%qd) = %qd where g(%qd) = %qd\n", n, hg[0], hg[0], hg[1]);
    return 0;
}

というわけでCで書き直した。

実行結果＠AthlonXP2500+
----
f(837799)=524
time=0.093000sec

#include <stdio.h>
#include <string.h>
#include <time.h>

#define NMAX 1048576

short memo[NMAX];

int _f(unsigned long long n)
{
    int step;
    if(n == 1)
        return 0;
    if(n < NMAX && memo[n] != 0)
        return memo[n];

    if(n & 1)
        step = _f(n * 3 + 1) + 1;
    else
        step = _f(n >> 1) + 1;

    if(n < NMAX)
        memo[n] = step;
    return step;
}

int main(void)
{
    int i,mf,mi;
    
    mf = 0;
    memset(memo, 0, NMAX * sizeof(short));
    for(i = 1;i < NMAX; ++i) {
        if (memo[i] == 0){
            _f(i);
        }

        if (memo[i] > mf){
            mi = i;
            mf = memo[i];
        }    
    }

    printf("f(%d)=%d\ntime=%fsec", mi,mf, (double)clock() / CLOCKS_PER_SEC);
}

C に移植したバージョン。
最近の gcc は、コンパイル時に -O2 を付けると末尾再帰呼び出しを最適化してくれるようですね。便利。

実行例:
$ cc -O2 -o collatz collatz.c
$ time ./collatz
n=837799, steps=524
./collatz 0.07s user 0.00s system 95% cpu 0.079 total

やはりネイティブコンパイルできる処理系は早いですね。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LIMIT 1048576

int solve_collatz(long n, int step, int *cache){
    if(n == 1)
        return step;
    else if(n <= LIMIT && cache[n] != 0)
        return step + cache[n];
    else if(0 == n % 2) 
        return solve_collatz(n/2, step+1, cache);
    else
        return solve_collatz(n*3+1, step+1, cache);
}

long set_doubles(long i, int *steps, int *cache){
    for(;i <= LIMIT; i *= 2, (*steps)++)
        cache[i] = *steps;
    *steps -= 1;
    return i/2;
}

int main(){
    int *cache, steps, max_steps = 0;
    long n, mc_n, max_n = 0; 

    cache = malloc((LIMIT + 1) * sizeof(int));
    if(!cache) exit(1);
    memset(cache, 0, (LIMIT + 1) * sizeof(int));

    for(n = 1; n <= LIMIT; n++){
        if(cache[n] == 0){
            steps = solve_collatz(n, 0, cache);
            mc_n = set_doubles(n, &steps, cache);
            if(max_steps < steps){
                max_n = mc_n;
                max_steps = steps;
            }
        }
    }
    printf("n=%d, steps=%d\n", max_n, cache[max_n]);
}

DouKaku?

コラッツ・角谷の問題

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq