綾小路龍之介の素人思考

2の倍数と3の倍数を除いた数列のi番目の数nを返す関数

メモリの少ないマシン上で素数判定プログラムを作るときに必要になったので。アルゴリズム自体はものすごく簡単。部分数列の考え方でOK。

使われ方はこんな感じ。これで1番目から100番目までの数列の要素が出力される。mainの中で使われているi_to_nという関数をどのように作るか。

int main( void )
{
        for(i=0; i<100; i++){
                printf("%d %d\n" ,i ,i_to_n(i));
        }
        return 0;
}

まずはホワイトボードに色々書き殴ってみる。

n       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
2の倍数 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,  1,  0,  1,  0, ...
3の倍数 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,  0,  0,  1,  0, ...
i          0,          1,    2,            3,      4, ...
i%2        0,          1,    0,            1,      0, ...
i/2        0,          0,    1,            1,      2, ...

つまり、2の倍数かつ3の倍数である6の倍数ごとに周期性がある。ある6の倍数から次の6の倍数までの中には必ず2つの、2の倍数でもなく3の倍数でもない数が存在する。6の倍数で部分数列をつくると、各々の部分数列に含まれる最初の各要素は、部分数列について6だけ差がある。このことは2番目の要素についても同じ。各部分数列の番号付けはi/2で出来る。部分数列内の要素の番号付けはi%2で出来る。ということでこんな感じ。

部分行列の1番目の数の数列の一般項
n = 1 + 6 * (i / 2 の商)
部分行列の2番目の数の数列の一般項
n = 5 + 6 * (i / 2 の商)

当然ながら、int型の演算における(i/2)は「iを2で割ったときの商」というれっきとした「意味」があるので、6*i/2を3*iのようにまとめてはいけない。ということで下のようにかける。

int i_to_n(int i)
{
        int n;
        if( 0 == (i % 2) ){
                n = 1 + 6 * (i / 2);
        }else{
                n = 5 + 6 * (i / 2);
        }
        return n;
}

入出力チェックが行われていないので軽く脳内チェック。nはint型なので、iが大きいと数学的にはおかしな結果が得られるはず。例えば、(INT_MAX)/3の辺りで。テストコードを書いてみる。

void check(void)
{
        int i = 0;
        int i_sta = INT_MAX/3 - 10;
        int i_end = i_sta + 20;
        for(i=i_sta;i<i_end;i++){
                printf("%10d %10d %10u\n",i, i_to_n(i), i_to_n(i));
        }
        return;
}

走らせると明らかにおかしな出力である。出力結果が採点されるので、これでは困る。

 715827872 2147483617 2147483617
 715827873 2147483621 2147483621
 715827874 2147483623 2147483623
 715827875 2147483627 2147483627
 715827876 2147483629 2147483629
 715827877 2147483633 2147483633
 715827878 2147483635 2147483635
 715827879 2147483639 2147483639
 715827880 2147483641 2147483641
 715827881 2147483645 2147483645
 715827882 2147483647 2147483647
 715827883 -2147483645 2147483651
 715827884 -2147483643 2147483653
 715827885 -2147483639 2147483657
 715827886 -2147483637 2147483659
 715827887 -2147483633 2147483663
 715827888 -2147483631 2147483665
 715827889 -2147483627 2147483669
 715827890 -2147483625 2147483671
 715827891 -2147483621 2147483675

注目すべき点はprintf関数でフォーマット指定する際にunsigned int型とすると、上手くいくという点である。少なくとも僕がテストコードを走らせている処理系では、printf文がint型とunsigned int型を処理する場合の違いは最上位ビットを負数を表現するフラグと考えるか否かだけの違いなので、こんな感じの事が起きる。とりあえずnが負数ならperror();exit();するという手もあるが、それだと十分にビットを使えていない(半分くらいのビットが無駄になる)し出力チェックは入力チェックに比べてコストがかかるので面白くない。このままの状態で出力だけunsigned intを使うのもいいが、それだと論理的でない機がする。まずはunsigned int型にして、論理的に正しく計算できる範囲を広げよう。

unsigned int i_to_n(unsigned int i)
{
        unsigned int n;
        if( 0 == (i % 2) ){
                n = 1 + 3 * i;
        } else {
                n = 5 + 3 * i;
        }
        return n;
}
void check(void)
{
        unsigned int i = 0;
        unsigned int i_sta = UINT_MAX/3 - 10;
        unsigned int i_end = i_sta + 20;
        for(i=i_sta;i<i_end;i++){
                printf("%10d %10u %10d %10u\n",i,i, i_to_n(i), i_to_n(i));
        }
        return;
}

で、出力結果が下のような感じ。

1431655755 1431655755        -29 4294967267
1431655756 1431655756        -27 4294967269
1431655757 1431655757        -23 4294967273
1431655758 1431655758        -21 4294967275
1431655759 1431655759        -17 4294967279
1431655760 1431655760        -15 4294967281
1431655761 1431655761        -11 4294967285
1431655762 1431655762         -9 4294967287
1431655763 1431655763         -5 4294967291
1431655764 1431655764         -3 4294967293
1431655765 1431655765          1          1
1431655766 1431655766          3          3
1431655767 1431655767          7          7
1431655768 1431655768          9          9
1431655769 1431655769         13         13
1431655770 1431655770         15         15
1431655771 1431655771         19         19
1431655772 1431655772         21         21
1431655773 1431655773         25         25
1431655774 1431655774         27         27

ここまでしてから、入力チェックを行って、エラー終了させる。どこにエラーの原因が潜んでいるか微妙なので、計算のたびにエラーチェックをさせる。

unsigned int uint_dvi(unsigned int a, unsigned int b)
{
        unsigned int a_dvi_b = a;
        if (a <= (UINT_MAX * b)) {
                a_dvi_b /= b;
        } else {
                errno = ERANGE;
                fprintf(stderr,"%u / %u",a,b);
                perror("#");
                exit(EXIT_FAILURE);
        }
        return a_dvi_b;
}
unsigned int uint_mul(unsigned int a, unsigned int b)
{
        unsigned int a_mul_b = a;
        if (a <= (UINT_MAX / b)) {
                a_mul_b *= b;
        } else {
                errno = ERANGE;
                fprintf(stderr,"%u * %u",a,b);
                perror("#");
                exit(EXIT_FAILURE);
        }
        return a_mul_b;
}
unsigned int uint_add(unsigned int a, unsigned int b)
{
        unsigned int a_plus_b = a;
        if (a <= (UINT_MAX - b)) {
                a_plus_b += b;
        } else {
                errno = ERANGE;
                fprintf(stderr,"%u + %u",a,b);
                perror("#");
                exit(EXIT_FAILURE);
        }
        return a_plus_b;
}
unsigned int i_to_n(unsigned int i)
{
        unsigned int n = i;
        //n /= 2;
        n = uint_dvi(n, 2);
        //n *= 6;
        n = uint_mul(n, 6);
        if (0 == (i % 2)) {
                //n += 1;
                n = uint_add(n, 1);
        } else {
                //n += 5;
                n = uint_add(n, 5);
        }
        return n;
}

で、こんな感じ。しっかりと落ちてくれている。まぁこれで、処理系依存がないだろうと思う。採点する人間の処理系を公開してほしいものだ。おかげで色々と考えさせられるが。

1431655755 4294967267
1431655756 4294967269
1431655757 4294967273
1431655758 4294967275
1431655759 4294967279
1431655760 4294967281
1431655761 4294967285
1431655762 4294967287
1431655763 4294967291
1431655764 4294967293
4294967292 + 5#: Numerical result out of range
1431655765

ソーシャルブックマーク

  1. はてなブックマーク
  2. Google Bookmarks
  3. del.icio.us

ChangeLog

  1. Posted: 2007-07-24T00:51:01+09:00
  2. Modified: 2007-07-24T03:56:28+09:00
  3. Generated: 2017-10-16T23:09:17+09:00