トップページ⇒tech
523コメント255KB

■■C++で大きな数を作るスレ■■

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん2009/03/24(火) 20:27:50
C++ で大きな数を返すプログラムを作るスレです。
以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。

int main();

●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください

●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします

機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可

●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0484デフォルトの名無しさん2010/07/21(水) 02:01:03
基本的には下と同じでしょ。
-----
lp:
y = x+1
if (y > x) { x = y; goto lp; }
return x;
-----
つまり
lim n→∞ (intのbit数がnである時のmainの戻り値)
が存在しない環境依存コード。

命令セット的には SET MOV ADD CMP JF の5個だけで十分ぽいよ。
（C++やチューリングマシンと同じ能力がある）

JFの動作が以下の間違いだと仮定しての話だけど。
× case JF:i+=((r1&2)-1)*r2-1;break;
○ case JF:if(f)i+=((r1&2)-1)*r2-1;break;
0485デフォルトの名無しさん2010/07/21(水) 02:34:10
有限の長さのバイトコードで、任意の自然数xに対して、xステップ以内にxより大きな自然数yを生成できるアルゴリズムが必ず存在するってこと？
0486デフォルトの名無しさん2010/07/21(水) 02:34:57
s/生成する/生成して停止する/
0487デフォルトの名無しさん2010/07/21(水) 09:54:29
>>473
またループになってしまって申し訳ないのだが、λn.Cstepは、
計算可能なアルゴリズム集合の中からちょうどλn.Cstep nを選び出すアルゴリズムに帰着する気がするんだが、
そういうことでいいのかな？
0488デフォルトの名無しさん2010/07/21(水) 21:03:39
>>485
n命令から成るプログラムで、
nステップ実行して 4095*pow(2,n-1) の値を返せる

MOV r[0], 4095
ADD r[0], r[0]
ADD r[0], r[0]
ADD r[0], r[0]
.....
0489デフォルトの名無しさん2010/07/21(水) 21:43:24
>>487
帰着って？
0490デフォルトの名無しさん2010/07/22(木) 00:23:45
>488
命令数は増やさないんですよ。
0491デフォルトの名無しさん2010/07/22(木) 01:26:58
>>489
計算可能なアルゴリズム集合の中からちょうどλn.Cstep nを選び出すアルゴリズムがあれば、λn.Cstepは表現可能。
0492デフォルトの名無しさん2010/07/22(木) 19:51:41
>>490
ああ、有限じゃなくて、ある自然数以下ってことね。
ある自然数以下の長さのコードでのステップ数には当然限界があるので、
当然停止する。

で、肝心のどのくらいで停止するかをちょっと考えてみたけど、
全然大きさが見積もれない。
しばらく考えてみます。
0493デフォルトの名無しさん2010/07/22(木) 23:39:05
>>483
大きさが見積もれました。

●1回のループでのxの増加分
最大プログラム長をn命令とする。
1回のループで x が f(x, n) になるとする。

>>488 の通り、xステップでの戻り値は 4095*pow(2,x-1)以下なので、
f(x, n) ≦ 4095*pow(2,x-1) ≦ pow(4095, x)

●ループ回数
最大プログラム長をn命令とした時のループ回数を g(n) とする。
n命令以下のプログラムは
pow(0x10000000, 1) + pow(0x10000000, 2) + ... + pow(0x10000000, n)
通りである為、
g(n) ≦ pow(0x10000000, 1) + pow(0x10000000, 2) + ... + pow(0x10000000, n) ＜ pow(0x10000001, n)

●戻り値
xの初期値に対し、f(x, n) を g(n)回繰り返した値以下である。

上記より、大きく見積もっても、
4095↑↑(0x10000001↑[最大プログラム長(命令数)]) 程度であることが分かる。
※↑はべき乗、 ↑↑ はテトレーション
0494デフォルトの名無しさん2010/07/23(金) 01:25:54
あとはスタックマシンにしたり、ADDじゃなくてMULとかPOWとかAckermannにすればどうとでもって感じか。
0495デフォルトの名無しさん2010/07/23(金) 07:45:53
>>494
1命令でできる演算を2重ループしたくらいにしかならないから、
それほど大きくならない。
0496デフォルトの名無しさん2010/07/23(金) 10:25:35
n文字以下のC++プログラムは
pow(95, 1) + pow(95,2) + ... + pow(95,n)
通りであるため (95 = 127 - 32)、
ループ回数 g(n)≦ pow(95, 1) + pow(95, 2) + ... + pow(95, n) ＜ p(96, n)

ってそんなアホな。
0497デフォルトの名無しさん2010/07/23(金) 20:00:29
>>496
たぶんすごい勘違いをしてると思う。
0498デフォルトの名無しさん2010/07/23(金) 21:27:32
超簡単なインタープリタを作りました。
1命令は6bit, レジスタは8個、命令はSUB reg, reg の1個のみです。
条件ジャンプは特定のレジスタに値を書くことで行います。
ip が負になったらプログラム終了で、-ipが返ります。
指定stepを超えたら0以下の値が返ります。
一応これだけでチューリング完全な言語になっています。
議論の手助けにでも使ってください。

int emu(int code, int step){
    int reg[7] = {1}, ip = 0;

    for ( ; step-- && ip >= 0 ; ip+=6){
        reg[code >> ip & 7] -= reg[code >> ip+3 & 7];
        if (reg[0] < 0){
            ip += reg[1];
        }
    }
    return -ip;
}

指定step数以下で停止するcode以下のプログラムの戻り値の最大値
int cmaxs(int code, int step){
    int m = 0;
    while (code){
        int r = emu(code--, step);
        if (r > m){
            m = r;
        }
    }
    return m;
}
0499デフォルトの名無しさん2010/07/23(金) 22:10:51
>>483 をコードにすると、こんな感じ。

int cmax483(int n){
    int x, y = 9;
    do {
        x = y;
        y = cmaxs(1<<n*6, x);
    } while (y > x);
    return x;
}

インタープリタの命令の種類によってステップ数の増える速さが大きく変わってしまうので、
初めからstepの増加度合いを関数にしてみる。

int cmax483_(int n, int func(int)){
    int x, y = 0, step = 9;
    do {
        x = y;
        y = cmaxs(1<<n*6, step);
        step = func(step);
    } while (y > x);
    return x;
}

>>493 と同じ方法で見積もると、
cmax483_(Ackermann(9e9999999,9), Ackermann)
とやっても、Ackermann(9,9,9)よりはるかに小さい値しか返らないというのは驚きである。
Ackermann(9e9999999,9)命令程度という、人間が組めるサイズを大きく超えたプログラム長をもってしても、
返すことの出来る値はAckermann(9,9,9)付近ではかなりスカスカであることになる。
0500デフォルトの名無しさん2010/07/24(土) 02:45:47
停止させなきゃいかんのがネックになっとるなぁ。
0501デフォルトの名無しさん2010/07/24(土) 08:59:45
こっちの方が微妙にループ回数を多く出来る。
（とはいっても >>493 の見積もりは超えられないが）

//指定step数以下で停止するcode以下のプログラムの数を数える
int ccnts(int code, int step){
    int c = 0;
    while (code){
        c += emu(code--, step) > 0;
    }
    return c;
}

//ccnts の値が増えなくなるまでstepを増やし続ける
int cmax501(int n, int func(int)){
    int x, y = 0, step = 9;
    do {
        x = y;
        y = ccnts(1<<n*6, step);
        step = func(step);
    } while (y > x);
    return cmaxs(1<<n*6, step);
}
0502デフォルトの名無しさん2010/07/24(土) 18:20:58
>>501
どうせループ回数はcodeの取り得る値を超えられないので、
単にこれの方がマシか。

int cmax502(int n, int func(int)){
    int step = 9;
    for (int i = 0 ; i < 1<<n*6 ; i++){
        step = func(step);
    }
    return cmaxs(1<<n*6, step);
}

結局cmaxsはstepより極端に大きな数は返らないので、
cmaxsを使って大きな数を作るのは厳しいか。

int main(){return emu(適当な大きな数, -1);}
とやる方が、
偶然とてつもなく大きな数が返る可能性があって、
しかも大きさを簡単に見積もれない為、夢がある分マシかも。

int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}
int e(int c,int s){int r[7]={1},i=1;for(;s--&&i>0;i+=6)r[c>>i&7]-=r[c>>i+3&7],*r<0&&(i+=r[1]);return-i;}
int main(){return e(a(9e9999999)/a(9e999999), -1);}
0503デフォルトの名無しさん2010/07/24(土) 18:28:16
>>502
無限ループかもしれないし、とてつもなく大きな値が返るかもしれない。
現在では誰も分からない。
>>325 や >>407 と同じ分類になるのかな。
0504デフォルトの名無しさん2010/11/02(火) 23:58:28
int a=9e99;
int *max(){int *x=new int[a+1];for(int i=a;i--;)x[i]=a;x[a]=-1;return x;}
int next(int *x){while(!*x)*x++=a;if(*x==-1)return 0;(*x)--;return 1;}

void f(int *b,int *c,int *d,int *e)
{
a<<=a<<a;
if(!next(e)){e=max();
if(!next(d)){d=max();
if(!next(c)){c=max();
if(!next(b)){
return;
}
}
}
}
for(int i=a;i--;)
{
f(dup(b),dup(c),dup(d),dup(e));
}
}


int main()
{
int *b,*c,*d,*e;
b=max();c=max();d=max();e=max();
f(b,c,d);
return a;

}
0505デフォルトの名無しさん2010/11/03(水) 00:11:34
すいません。いろいろ抜けてました。
int a=9e99;
int *max(){int *x=new int[a+1];for(int i=a;i--;)x[i]=a;x[a]=-1;return x;}
int *dup(int *x){int i=0;while(x[i]==-1)i++;int **y=new int[i];i=0;while(x[i]==-1)y[i]=x[i];y[i]=-1;return y;}
int next(int *x){while(!*x)*x++=a;if(*x==-1)return 0;(*x)--;return 1;}
void f(int *b,int *c,int *d,int *e)
{
a<<=a<<a;
if(!next(e)){e=max();
if(!next(d)){d=max();
if(!next(c)){c=max();
if(!next(b)){
return;
}
}
}
}
for(int i=a;i--;)
{
f(dup(b),dup(c),dup(d),dup(e));
}
}


int main()
{
int *b,*c,*d,*e;
b=max();c=max();d=max();e=max();
f(b,c,d,e);
return a;

}
0506デフォルトの名無しさん2010/11/03(水) 10:06:44
>>505
記述ミスと思える所(dup)があるので適当に修正して大きさを見積もると、
大きさが分からないものと >>264 とを除けば
今まででダントツにデカイ。
コードも読みやすく、処理の流れも綺麗。

現段階だと文字数が多いけど、
可読性や処理の流れのきれいさを犠牲にすれば、
文字数はかなり減らせそう。
0507デフォルトの名無しさん2010/11/10(水) 21:32:53
バグがないか不安だが、一応自分の中で最終形にたどり着いた。
int a=9e99;

template<class T>
void max(T *t){t=new T[a+1];for(int i=0;i<a;i++)max(t[i]);t[a]=NULL;}

void max(int *t){t=new int[a+1];for(int i=0;i<a;i++)t[i]=a;t[a]=-1;}

template<class T>
bool next(T *t){while(t&&!next(*t))max(*t++);return !t;}

bool next(int *t){while(!*t)*t++=a;if(*t==-1)return 0;*t--;return 1;}

template<class T>
T *dup(T *t){int i,j;for(i=0;t[i]!=NULL;i++);T *x=new T[i+1];for(j=0;j<i;j++)x[j]=dup(t[j]);x[i]=NULL;return x;}

int *dup(int *t){int i,j;for(i=0;t[i]!=-1;i++);int *x=new int[i+1];for(j=0;j<i;j++)x[j]=t[j];x[i]=-1;return x;}

template<class T>
void f(T *t)
{
a<<=a<<a;
if(next(t)){for(int i=a;i--;){f(dup(t));}}
}

int main()
{
int *****************************t;
f(max(t));
return a;
}
0508デフォルトの名無しさん2010/11/10(水) 22:26:57
はやくもバグ発見
main()
{
0509デフォルトの名無しさん2010/11/10(水) 22:28:16
int main()
{
int ******************************t;
max(t)
f(t);
return a;
}
が正しい。
0510デフォルトの名無しさん2010/11/10(水) 23:40:11
nextもまちがってた。
template<class T>
bool next(T *t){while(t&&!next(*t))max(*t++);return t!=NULL;}
0511デフォルトの名無しさん2010/11/11(木) 21:00:52
>>505 を30次元配列に拡張ですか。
とてつもなく大きい予感が。

----
NULLは未定義なので0で

void max(T *t){
void max(int *t){
はぞれぞれ
void max(T *&t){
void max(int *&t){
こうですかね？
0512デフォルトの名無しさん2010/11/11(木) 21:30:50
テンプレートの初期関数とテンプレート関数が
すごく似てるのがなんかもったいない気がする。

配列の各要素を1ずつ増やして、
終端が0, 各要素の最低値を1にすると、
テンプレートの初期関数を簡単に出来そう。
以下でたぶん返る値は同じ。

void max(int &t){
    t = a+1;
}
bool next(int &t){
    return --t||(max(t),0);
}
int dup(int t){
    return t;
}
0513デフォルトの名無しさん2010/11/11(木) 21:48:00
> bool next(int *t){while(!*t)*t++=a;if(*t==-1)return 0;*t--;return 1;}
bool next(int *t){while(!*t)*t++=a;if(*t==-1)return 0;--*t;return 1;}

>max(t)
max(t);
0514デフォルトの名無しさん2010/11/11(木) 22:21:55
肝心の大きさは？
>>507 に解説願いたい。
0515５０７2010/11/14(日) 19:02:29
多重リストアッカーマンくらいの大きさかな？たぶん。

0516デフォルトの名無しさん2010/11/15(月) 00:59:03
たぶんそんなに大きくない。
おそらく２重リストアッカーマンくらい。
0517５０７2010/11/15(月) 20:16:15
>>516
解説おながいします。
0518デフォルトの名無しさん2010/11/16(火) 21:29:00
f( b, a ) ≒ Ak( [1, b], [0, a] )
f( c, b, a ) ≒ Ak( [2, c], [1, b], [0, a] )
f( d, c, b, a ) ≒ Ak( [3, d], [2, c], [1, b], [0, a] )
f( e, d, c, b, a ) ≒ Ak( [4, e], [3, d], [2, c], [1, b], [0, a] )

f( [d, c], [b, a] )
        ≒ Ak( [1, 1, d], [1, 0, c], [0, 1, b], [0, 0, a] )
f( [i, h, g], [f, e, d], [c, b, a] )
        ≒ Ak( [2, 2, i], [2, 1, h], [2, 0, g], [1, 2, f], [1, 1, e], [1, 0, d], [0, 2, c], [0, 1, b], [0, 0, a] )

f( [[h, g], [f, e]], [[d, c], [b, a]] )
        ≒ Ak( [1, 1, 1, h], [1, 1, 0, g], [1, 0, 1, f], [1, 0, 0, e], [0, 1, 1, d], [0, 1, 0, c], [0, 0, 1, b], [0, 0, 0, a] )

f( [[[b, 0], [0, 0]], [[0, 0], [0, 0]]], [[[0, 0], [0, 0]], [[0, 0], [0, a]]] )
        ≒ Ak( [1, 1, 1, 1, b], [0, 0, 0, 0, a] )

....
0519デフォルトの名無しさん2010/12/06(月) 05:29:40
これ、lispでやったらどうなるんだろう？
0520デフォルトの名無しさん2010/12/16(木) 22:08:46
>>519
だれかやってみて！

0521デフォルトの名無しさん2010/12/17(金) 02:06:03
Lispはevalが組み込みだから「1レスで表せる最大の数」の概念がwell definedにならない
0522デフォルトの名無しさん2010/12/17(金) 02:26:24
いやevalの停止性が保証されてるわけではないから大丈夫か
0523デフォルトの名無しさん2010/12/17(金) 20:30:42
(define(a m n)(if(= m 0)(+ n 1)(if(= n 0)(a(- m 1)1)(a(- m 1)(a m(- n 1))))))(a 9 9)
手始めにschemeで>>9
84バイト
■ このスレッドは過去ログ倉庫に格納されています