Meertens数 in C DouKaku?

お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．

このような数のことをMeertens数と言うそうです．

32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．

Cで書き直したら恐ろしく速くなった。 10桁実行するのに176秒＠AthlonXP2500+ pythonで書いたのと比較して、だいたい100倍高速化した計算に。

ゲーテル数って10桁でintの範囲をあっさりと突破するのね・・・バグに気づかなかった。 unsigned long long int なんて初めて使ったよ。

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

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

void searchMeertens(int keta, int count, unsigned long long int r, unsigned long long int n, int first){
    int x;
    n *= 10;
    for(x = first; x < 10; x++){
        if (x){
            r *= primes[count];
            n++;
        }    
        if (r == n){
            printf("Found Meertens %d\n",n);
        }
        if (keta > 1){
            searchMeertens(keta -1, count +1, r, n, 0);
        }
    }
}


int main(void)
{
    int keta;
    int x;
    time_t t;
    keta = 10;
    t = time(NULL);
    for(x = 1; x <= keta; x++){
        searchMeertens(x,0,1,0,1);
        printf("%d %dsec\n",x, time(NULL)-t);
        t = time(NULL);
    }
    printf("push anykey to exit.");
    getchar();
}

とりあえず40秒くらいまで縮まったけど、
他の人が何で爆速なのかが分からない。
あとどんな枝狩りすりゃいいねん。

枝狩りで分岐予測がこける関係で、Pen4系では遅いと思う。

関数型言語は読めないよ・・・

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

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

void _searchMeertens(int keta, int count, unsigned long long int r, unsigned long long int n){
    int x;
    n *= 10;
    for(x = (count == 0); x < 10; x++){
        if (x){
            r *= primes[count];
            n++;
        }    
        if (keta == 0){
            if(r > n){        //枝狩り
                return;    
            }
            else if (r == n){
                printf("Found Meertens %d\n",n);
            }
        }else{
            _searchMeertens(keta -1, count +1, r, n);
        }
    }
}

void searchMeertens(int keta)
{
    int x;
    time_t t;
    t = time(NULL);
    for(x = 0; x < keta; x++){
        _searchMeertens(x,0,1,0);
        printf("keta = %d time = %d\n", x+1, time(NULL) - t);
        t = time(NULL);
    }
}

int main(void)
{
    int keta;
    time_t t;

    keta = 10;
    t = time(NULL);
    searchMeertens(keta);
    printf("%dsec\n", time(NULL)-t);

    printf("push anykey to exit.");
    getchar();
}

最初の乗算(n *= 10)を外に出してみれば、もうちょいいけるかも....。

keta = 14 time = 2
keta = 15 time = 4
keta = 16 time = 12
keta = 17 time = 34
keta = 18 time = 96

微々たるもんしか減らないorz。

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

#ifndef ARRAYSIZE
#define ARRAYSIZE(x)  (sizeof(x)/sizeof(x[0]))
#endif

unsigned long long int dec_base[20];

void _searchMeertens(int keta, int d, unsigned long long int r, unsigned long long int n) {
    int x;
    for (int x = (d == 0); x < 10; x++) {
        if (x > 0) {
            r *= primes[d];
            if (r >= dec_base[keta])
                return;
            n += dec_base[keta - (d + 1)];
        }
        if ((d + 1) >= keta) {
            if (r >= n) {
                if (r == n)
                    printf("Found Meertens %lld\n", n);
                return;
            }
        } else {
            _searchMeertens(keta, d + 1, r, n);
        }
    }
}

void searchMeertens(int keta) {
    int x;
    time_t t;
    t = time(NULL);
    for (x = 1; x <= keta; x++) {
        _searchMeertens(x, 0, 1, 0);
        printf("keta = %d time = %d\n", x, time(NULL) - t);
        t = time(NULL);
    }
}

void main() {
    int i;
    dec_base[0] = 1;
    for (i = 1; i < ARRAYSIZE(dec_base); i++) {
        dec_base[i] = dec_base[i - 1] * 10;
    }
    searchMeertens(19);
}

DouKaku?

Meertens数

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq