■■C++で大きな数を作るスレ■■
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2009/03/24(火) 20:27:50以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。
int main();
●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください
●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします
機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可
●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
02551
2009/05/02(土) 16:56:08再帰定義をよく見てみると、
関数 a(b,c,x) に対して、関数 a(b,c+1,x) はloop_rankが1個増えた関数だということがわかる。
a(0,0,x) はx+9 でloop_rankは0なので、
a(0,c,x) のloop_rank はcになる。
a(1,0,x) = a(0,x,9) なので、
a(1,0,x) はloop_rankが整数であるどんな関数よりも増大度が大きく、
loop_rank は >>253 の(*a) と同じωとなる。
さらに、2番目の引数を9にした a(1,9,x) は
loop_rankがω+9
関数 a(1,x,x) を考えてみると、
loop_rankがω+整数であるどんな関数よりも増大度が大きく、
loop_rankはω+ωになる。
0256デフォルトの名無しさん
2009/05/02(土) 16:58:3599文字のbを1増やすのは
loop_rankをω増やす操作となる。
98文字のものは、99文字のものから1文字減らす為に、
bを0と1に制限したもの。
0257デフォルトの名無しさん
2009/05/02(土) 17:09:06function_loop2 が間違ってました。
こうですね。
virtual int operator()(int x){
function*f=a;
for(int i=x;i--;)
f=new function_loop(f);
return (*f)(x);
}
0258233
2009/05/04(月) 07:36:40了解。
丁寧な解説ありがとう。
大きな関数を繰り返すことでさらに大きな関数を作る、そしてそれをまた繰り返して…
というのは>>1はもうやり尽くしていて結論が出ている。それを超えるには全く別の発想が必要になる。
ということでよろしいか？
02591
2009/05/04(月) 11:41:45とてもやり尽くせないと思うけど。
とりあえず >>252 の loop, loop2, loop3 を一般化したloop_n 相当を作ってみました。
最適化して解読しにくいと思うので多少説明。
{b,c,d} は関数bにloop_cを(d+1)回行ったもの
{0,0,0} は特別扱いで f(x) = x+9
変数 d は無くても作れるけど、ループより再帰の方が短かったので足しました。
関数は１文字で右から計算を行う operator = で作るのが一番短かったので
みにくいけど = で実装
// 138文字
struct a{
a*b;
int c,d;
int operator=(int f){
a g={b,c-!d,d?d-1:f},h={&g,c};
return c+d?*b=(c*d?h:g)=f:f+9;
}
}b,c={&b,9};
int main(){return c=9;}
0260デフォルトの名無しさん
2009/05/31(日) 14:54:05反復対数関数lg* n
lg^i n =def
n (i=1の時)
lg(lg^(i-1) n) (i>0,lg^(i-1) n>0の時)
未定義 (i>0,lg^(i-1) n<=0またはlg^(i-1) nが未定義の時)
lg* 2 = 1
lg* 4 = 2
lg* 16= 3
lg* 65536=4
lg* 2^65536=5
と思って調べていたら
逆アッカーマン関数(α)ってのもあるのか
α(m,n)=min{i>=1 : Ack(i,floor(m/n)) >= log2 n}
α(2^(2^(2^65536)) - 3) = 4
0261デフォルトの名無しさん
2009/06/04(木) 00:00:36>>91 が43文字で作ってる。
アッカーマンは >>9 が最初で
現在は77文字まで縮まってる。
0262デフォルトの名無しさん
2009/07/02(木) 00:25:460263デフォルトの名無しさん
2009/07/06(月) 01:25:30{
return 1.0/【>>1の人間としての存在価値】;
}
0264デフォルトの名無しさん
2009/07/08(水) 20:23:17// 149文字
struct a{
int b;
a*c,*d;
a*e(int f){
a*g=f?e(f-1):d,h={b-!c,c?c->e(f):g,g};
return b||c?new a(h):d;
}
}b,*c=&b;
int main(){
for(;c=c->e(b.b+=9););
return b.b;
}
0265デフォルトの名無しさん
2009/07/22(水) 19:03:44B(2,5)=2048
B(2,6)=67108864
B(2,7)=144115188075855872
0266デフォルトの名無しさん
2009/07/23(木) 21:55:04定義が良くわからないけど、
B(2,n) = 1<<(1<<n-1)-n
なので、
int main(){return 2;} // B(2,3) 21文字
int main(){return 16;} // B(2,4) 22文字
int main(){return 2048;} // B(2,5) 24文字
int main(){return 1<<57;} // B(2,7) 25文字
int main(){return 1<<502;} // B(2,10) 26文字
int main(){return 1<<8178;} // B(2,14) 27文字
int main(){return 1<<65519;} // B(2,17) 28文字
int main(){return 1<<524268;} // B(2,20) 29文字
int main(){return 1<<8388584;} // B(2,24) 30文字
int main(){return 1<<67108837;} // B(2,27) 31文字
int main(){return 1<<536870882;} // B(2,30) 32文字
int main(){return 1<<(1<<98)-99;} // B(2,99) 33文字
int main(){return 1<<(1<<998)-999;} // B(2,999) 35文字
0267デフォルトの名無しさん
2009/08/22(土) 08:00:350268デフォルトの名無しさん
2009/08/22(土) 08:27:25へんなＣ＋＋の整数型もどきを使わずに済んでルールが簡明になったな
0269デフォルトの名無しさん
2009/08/28(金) 00:45:33長い文字列を印字する為に、事実上無制限の状態数が必要。
事実上無制限の状態数を表す為に、事実上無制限のメモリが必要。
事実上無制限のメモリを実装する為に、事実上無制限のポインタサイズが必要。
ということで、
どうせポインタサイズが事実上無制限なら
int のサイズも事実上無制限にしてしまえ！
というのがintサイズ無制限のルールにした理由。
>>267 のルールだと、
void pchar(void);
を１文字印刷する関数として、
プログラム終了までにこの関数を何回コール出来るか競う感じか。
単純にステップ数を競うのでも良い。（ステップの定義が必要だが）
0270デフォルトの名無しさん
2009/08/28(金) 00:51:00多倍長整数の実装を普通の方法で行うことは出来ない。
整数型のサイズに依存しない符号なし無制限整数型の実装を考えてみた。
struct UINT {
UINT*next;
}
UINT*inc(UINT*a){
return new UINT(a);
}
UINT*dec(UINT*a){
return a->next;
}
UINT*add(UINT*a,UINT*b){
while(a){
a=dec(a);
b=inc(b);
}
return b;
}
UINT*mul(UINT*a,UINT*b){
UINT*c=0;
while(a){
a=dec(a);
c=add(b,c);
}
return c;
}
....
0271名無しさん＠そうだ選挙に行こう
2009/08/30(日) 08:16:27http://pc12.2ch.net/test/read.cgi/tech/1231384158/
0272デフォルトの名無しさん
2009/09/24(木) 02:19:57main(){for(;;)std::cout<<"9";}
0274デフォルトの名無しさん
2009/09/26(土) 02:50:03int main(){return numeric_limits<int>::max();}
//63文字
0276デフォルトの名無しさん
2009/09/26(土) 13:27:03int main(){int a=1,b=0;for(;a>b;a++,b++);return b;}
こうすれば無限にならないのでは?
0277デフォルトの名無しさん
2009/09/26(土) 19:15:26だから何？
0279デフォルトの名無しさん
2009/09/26(土) 23:04:53>int の最大値は環境依存なのでルール違反。
はぁ？
intの最大値は環境依存だが、>>274のコードは環境依存ではない。
0280デフォルトの名無しさん
2009/09/27(日) 02:56:37それはないだろ
規約上はオーバーフローした場合の挙動は未定義なんだから
aがオーバーフローしたとき0にするのではなく
非数字やエラーとして扱う処理系を作っても一向にかまわない
a>bが真になったり、システム自体がダウンすることもありうる
結局オーバーフロー依存は環境依存だから禁止なの
0281デフォルトの名無しさん
2009/09/27(日) 02:59:49>>279の方はよくわかんね
0282デフォルトの名無しさん
2009/09/27(日) 03:09:01なにが、はぁ？だよ
0283デフォルトの名無しさん
2009/09/27(日) 03:16:30//25文字
//環境依存がダメなら、intが32768以上の値をとることを期待するのは機種依存だからダメ。
0284デフォルトの名無しさん
2009/09/27(日) 07:30:06環境によって main が返す値が変わるのだから環境依存。
>>283
「int と float は十分な精度があるとします」
このスレのルールです
意味は >>30-31
0285デフォルトの名無しさん
2009/09/27(日) 11:57:39int main(){return f(9);}
//59文字
0286デフォルトの名無しさん
2009/09/27(日) 11:58:37int main(){return f(9);}
//63文字
0287デフォルトの名無しさん
2009/09/27(日) 14:50:34int main(){return h(9);}
//85文字
//結局アッカーマン
0288デフォルトの名無しさん
2009/09/27(日) 16:03:36int main(){return h(9,9);}
//87文字
//結局アッカーマン
// >>285, >>287 取り消し
0289デフォルトの名無しさん
2009/09/27(日) 18:38:14int main(){return h(9,9);}
//87文字
//結局アッカーマン
// >>288 取り消し
0290デフォルトの名無しさん
2009/09/27(日) 23:49:12main関数だけで再帰呼び出すを行うというスゴイ技を
>>91 さんが見せてくれました。
それを微妙に修正したのが >>96 の 43文字の作品。
>>286 とまったく同じ値となります。
>>289
アッカーマン（相当の）関数は >>9 さんが始めに書いていて、
>>83 で 77文字まで縮まっています。
現状の記録は >>227-230 にあります。
詳しそうなので、ぜひ記録更新に挑戦してみてください。
1レス内文字数無制限での記録もお待ちしております。
0291デフォルトの名無しさん
2009/09/28(月) 00:08:240292デフォルトの名無しさん
2009/09/28(月) 01:09:31未定義動作はないぞ。(unsignedな型の計算はオーバーフローにはならないと書いてある)
0293デフォルトの名無しさん
2009/09/28(月) 01:10:390294デフォルトの名無しさん
2009/09/28(月) 16:01:090295デフォルトの名無しさん
2009/09/28(月) 16:19:420296デフォルトの名無しさん
2009/09/28(月) 21:23:04r が初回不定
i を int にキャストした時点でオーバーフローする
環境依存な値が返る
上２個が解決したとしても
環境依存な値が返るのはこの方法では不可避
ところで、
このスレのルールを守って
（int が十分な精度という条件を除いて）
確実にintの最大値を返すものはいままで上がって無かったと思うけど、
出来るのかな？
>>294 >>295
簡単なインタープリタなら１レスで作れるかも。
でも大きな数を返すプログラムをプログラムで作れるかどうか。
0297デフォルトの名無しさん
2009/09/29(火) 01:03:47unsignedからintへのキャストで元の値がintで表現できない場合の変換後の値はimplementation definedですがそれはオーバーフローではないのでは?
環境依存なのはその通り。
0298デフォルトの名無しさん
2009/09/29(火) 01:09:380299デフォルトの名無しさん
2009/09/29(火) 01:12:000300デフォルトの名無しさん
2009/09/29(火) 01:20:380301デフォルトの名無しさん
2009/09/29(火) 01:23:26もダメってこと？
論理演算は全部禁止？
0302デフォルトの名無しさん
2009/09/29(火) 01:25:090303デフォルトの名無しさん
2009/09/29(火) 01:29:51シフト使ってる例は沢山あるし。
0304デフォルトの名無しさん
2009/09/29(火) 01:34:31寂しい人向け
混む時間帯は人気ありすぎて定員オーバーで入れん
24時間荒れ放題の超カオスな絵チャット
本当の本当に完全無法地帯の絵チャット
（２ちゃんとは比較にならない）
荒しとプログラマーと防衛プログラマーの攻防戦
防衛側が強し、求む強力荒しプログラマー
しかも外国サーバー（イギリス）で管理人は荒し容認
殺人予告すらOKっぽい。ログなんて当然取ってないし
0305デフォルトの名無しさん
2009/09/29(火) 01:44:12内部での二進表現に依存してるから。
0306デフォルトの名無しさん
2009/09/29(火) 02:41:330307デフォルトの名無しさん
2009/09/29(火) 13:41:510309デフォルトの名無しさん
2009/09/29(火) 23:36:22ごめんなさい。その通りでした。
----
外部参照無しに、（インクルード、ライブラリ、外部入力など）
確実にintの最大値を返すC++のプログラムは存在しない
という証明が私の中では出来たつもり。
●証明
２つの環境ＡとＢがあって、
int の内部表現や動作は下記「異なる点」を除いて全く同じであるとする。
この時、環境ＡとＢではintの最大値は異なるが、
環境ＡとＢで動作の異なるプログラムを作ることは出来ない。
よって、ＡとＢ両方の環境でintの最大値を返すプログラムは存在しない。
----異なる点----
環境Ａのintの最大値はaであり、
環境Ｂのintの最大値はa-1である。
環境Ｂでは環境Ａのaと同じ内部表現でNaNを表すが、
NaNの場合の動作は環境Ａのaの時と全く同じである。
（つまり、動作は全く同じで意味付けのみ異なる）
..................................................................................................■
0310デフォルトの名無しさん
2009/09/29(火) 23:41:480311デフォルトの名無しさん
2009/09/29(火) 23:50:29「動作」とか「意味付け」とか俺用語が多すぎて意味不明
0312デフォルトの名無しさん
2009/09/30(水) 05:09:29implementation-defined valueはunspecified valueのうち処理系がドキュメントすべきもので、
unspecified valueはtrap representationにならないとC++03が参照するC99に書いてあるのですが。
0313デフォルトの名無しさん
2009/09/30(水) 12:59:53struct T {
enum { A = N + 1U };
static int f() { regturn g(+A); }
static int g(int x) { return T<A>::f(); }
static int g(unsigned x) { return N; }
static int g(long x) { return N; }
static int g(unsigned long x) { return N; }
};
int main() { return T<0>::f(); }
オーバーロードの解決のとこまだ読めてないから長いけど、implementation-definedなものに依存しないんのができた。
0314デフォルトの名無しさん
2009/09/30(水) 22:44:19たしかにそう書いてありますね。
（範囲外の値から型変換してトラップ表現にならないのならトラップ表現の意味が無い気がする）
int r;
unsigned i;
int main(){ while(--i)r=r<(int)i?i:r;return r; }
これで int の最大値が返るかな？
まあいずれにしろ環境依存な値が返るので
ルール違反ですが。
0315デフォルトの名無しさん
2009/09/30(水) 23:33:13結局は >>9 で終わってるスレ。
0316デフォルトの名無しさん
2009/09/30(水) 23:47:350317デフォルトの名無しさん
2009/10/01(木) 00:41:54>>316
過去ログ嫁。
0318デフォルトの名無しさん
2009/10/01(木) 00:44:48？
>>314の酷さに過去ログ関係ないだろ
0319デフォルトの名無しさん
2009/10/01(木) 01:02:18何がどう酷いのかさっぱり。
やっぱり過去ログを読んだ方が良い気がする。
0320デフォルトの名無しさん
2009/10/02(金) 04:21:430321デフォルトの名無しさん
2009/10/02(金) 22:40:05(3 & -1) == 1 なら 符号+絶対値表現
(3 & -1) == 2 なら 1の補数表現
(3 & -1) == 3 なら 2 の補数表現
負の数が、
1の補数表現の場合と、符号+絶対値表現の場合は、
int の最小値は -[int の最大値]
2の補数表現の場合は
int の最小値は -[int の最大値] または -[int の最大値]-1
2の補数表現の場合に、
このどちらになるかが調べられれば
int の最小値が得られる。
0322デフォルトの名無しさん
2009/10/02(金) 23:11:590323デフォルトの名無しさん
2009/10/02(金) 23:49:56符号+絶対値表現 1000...000 はトラップ表現
符号+絶対値表現 1000...000 はマイナスゼロ
1の補数表現 1111...111 はトラップ表現
1の補数表現 1111...111 はマイナスゼロ
2の補数表現 1000...000 はトラップ表現
2の補数表現 1000...000 は1000...001より1小さい数
規格書によるとこの６種類しか許されていないとある。
0324デフォルトの名無しさん
2009/10/02(金) 23:53:51？？？？
0325デフォルトの名無しさん
2009/10/07(水) 00:33:35for (int n = 2 ; ; n++)
for ( int a = n ; a = a%2 ? 3*a+1 : a/2, a != 1 ; )
if (a == n)
return n;
}
0326デフォルトの名無しさん
2009/10/07(水) 22:57:33あえて断言しよう。
それは無限ループであると。
0327デフォルトの名無しさん
2009/11/05(木) 06:02:2594文字
0328デフォルトの名無しさん
2009/11/05(木) 22:41:532↑↑22300745198530623141535718272648361505980418
よりちょっと小さいくらい。
（↑↑ はパワータワー（テトレーション）の記号）
int a=9e99;int main(){return a--?9<<main():9;} // 46文字
こっちのが大きくて、
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
よりちょっと小さいくらい。
0329デフォルトの名無しさん
2009/11/06(金) 02:51:2959文字
0330デフォルトの名無しさん
2009/11/06(金) 03:08:2557文字にしとく
0331デフォルトの名無しさん
2009/11/06(金) 21:21:41よりちょっと大きくて
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
よりは小さい。
ちなみに、標準ライブラリなどの外部ライブラリや
外部ファイルのインクルードは禁止ですので、
powを使う場合はその定義も文字数に含めてください。
int pow(int a,int b){return b?a*pow(a,b-1):1;}
0332233
2009/12/19(土) 11:29:44１のレスを参考に233を書き直してみた。これだとどれぐらいの大きさ？
struct Object {
Object *next;
virtual void f() {}
virtual Object *dup() { return this; }
Object **last_next(){if(next)return next->last_next();return &next;}
Object(){ next=(Object *)0;}
};
Object *o;
int a;
void IntegerGrow() { a<<=a<<a;}
struct ObjectGrow : Object { void f(){ Object *t=o->dup(); *(o->last_next())=t;} };
struct Loop : Object
{
void f(){ int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++){
if(*p==-1)return;
for(q=x;q<p;q++){IntegerGrow();*q=a;}
(*p)--;next->f();}}}
Object *dup() { Loop *l=new Loop(); if(next)l->next=next->dup(); return l;}
};
int main()
{
Object *loop;o=new Loop();a=99;
for(int i=a;i--;){loop=o->dup();*(loop->last_next())=new ObjectGrow();loop->f();}
}
0333233
2009/12/19(土) 16:54:39struct Object {
Object *next;
virtual void f() {}
virtual Object *dup() { return this; }
Object **last_next(){if(next)return next->last_next();return &next;}
Object(){ next=(Object *)0;}
};
Object *o;
int a;
struct ObjectAndIntegerGrow : Object { void f(){ Object *t=o->dup(); *(o->last_next())=t; a=a<<a;} };
struct Loop : Object
{
void f(){ int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++){
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;next->f();}}}
Object *dup() { Loop *l=new Loop(); if(next)l->next=next->dup(); return l;}
};
int main()
{
Object *loop;o=new Loop();a=99;
for(int i=a;i--;){loop=o->dup();*(loop->last_next())=new ObjectAndIntegerGrow();loop->f();}
return a;
}
0334デフォルトの名無しさん
2009/12/19(土) 22:02:58Loop :: f() の二重ループの中身って合ってます？
!*p の部分が１回も false にならずに
右端の -1 までたどりついて return しちゃうような気がするのですが。
0335デフォルトの名無しさん
2009/12/19(土) 22:26:34!*p の部分が１回も true にならないで無限ループ
の間違いでした。
>>233 のようにしたければ、
for(;;){
for(p=x;!*p;p++);
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;
next->f();
}
こうじゃないかと。
0337デフォルトの名無しさん
2009/12/19(土) 23:12:05o のチェーンの長さより a の方が大きく、
o のチェーンの長さ分 f を再帰コールしてるだけなので、
以下で良い気がする。
----------------
int a;
void f(int o){int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++);
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;a<<=a;if(o)f(o-1);}}
int main()
{
a=99;
for(int i=a;i--;)f(a);
return a;
}
0338333
2009/12/19(土) 23:37:33メモリの大きさが実感しやすい形にしました。
0339333
2009/12/19(土) 23:41:150340デフォルトの名無しさん
2009/12/19(土) 23:59:34>>337 のメモリの大きさが見えにくく、
>>333 のメモリの大きさが見えにくく無い
というのが良く分からない。
どちらもとてつもなくたくさんのメモリを使うし、
使うメモリの量を調べることは、
ほとんど main() の戻り値を調べることに等しい。
というか、
チェーンが１個伸びることで、
f の再帰を意図的に１回増やすように作った訳では無いの？
loop->f() のコール前後で loop のチェーンの長さは不変なので、
f() の再帰数は loop のチェーンの長さになることは簡単にわかるのだけど。
0341333
2009/12/20(日) 00:08:54なんだか無い物のように感じてしまいます。
リストの形にすると実体が実感しやすいという、その程度のことです。
この場合、どちらも本質的に同じものであることは一応理解できます。
0342デフォルトの名無しさん
2009/12/20(日) 08:40:36>>333 に >>335 の修正を加えると、
>>233 よりはずいぶんと大きくなって、
>>233 の、n重ループ相当の巨大化操作をn回繰り返して出来た関数を
さらにループさせた感じでしょうか。
0343333
2009/12/21(月) 22:05:460344333
2009/12/22(火) 21:32:37>>335の修正を入れたプログラムがアッカーマン換算でどれくらいの大きさか教えてくらさい。
0345デフォルトの名無しさん
2009/12/22(火) 23:10:26この中に出てくる３変数アッカーマンもどきを
ループで回したくらいで,
下のより微妙に小さい位ではないかと。
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=99;int main(){return a(b--?main():9);} // 119
たぶんこの２つの数の間だと思う。
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=97;int main(){return a(b--?main():9);} // 119
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=98;int main(){return a(b--?main():9);} // 119
>>333 + >>335 で、o のLoopのチェーンが１個伸びるのと、
上の３変数アッカーマンもどきの一番左の引数b が１個増えるのが大体同じ位の効果。
0346333
2009/12/23(水) 09:05:08簡単なところから確認していっていいですか。
テーマはループと再帰、定数と自己複製ってところで。
0347デフォルトの名無しさん
2009/12/23(水) 09:09:21void f(int a) { if(a) { g() ; f(a-1) ; }}
void f(int a) { while(a--) g() ; }
0348デフォルトの名無しさん
2009/12/23(水) 09:15:48int add(a,b) { if(a) { return 1+add(a-1,b);} return b;}
int add(a,b) { while(a--) b++ ; return b; }
0349デフォルトの名無しさん
2009/12/23(水) 09:41:04勢いで書き始めちゃったけど、ちょっとまとめなおします。
しばしおまちを。
0350333
2009/12/23(水) 22:43:02ざっくりと疑問のポイントだけ書くと
（１）Loop :: f()の中の配列の長さがNならLoop :: f()の大きさは２変数アッカーマンA(N,x)と同じくらいの大きさになるんじゃないか？
（２）もしそうなら>>233の配列の大きさはN重ループと４重ループを使って、繰り返し大きくしているので
>>233自体の大きさは3変数アッカーマンのA(4,a,b)くらいになるんじゃないか？
の２点です。
どうでもいいけど、>>346で自己複製とか書いたけどただのコピーと自己複製の区別がついてませんでした。
すんませんw。
0351デフォルトの名無しさん
2009/12/23(水) 23:37:35(1) は YES.
(2) は NO.
fを関数,b,cをある定数とし、
f(x) ≒ a(b,c,x) である場合、
f をループさせた関数 f' は f'(x) ≒ a(b,c+1,x)
f を3重ループさせた関数 f''' は f'''(x) ≒ a(b,c+3,x)
>>233 の関数D は大まかには
D(x) ≒ a(x ,x) ≒ a(1,0,x) となり、
D(x) を3重ループさせて出来た関数は大まかに a(1,3,x) 位、
これをループさせで出来る a(1,4,x) よりは小さい。
0352333
2009/12/24(木) 20:26:36普通の数式ならごりごりっと展開していけば何とかなることが多いんですが、
３変数アッカーマンを展開しようとするとえらいことにｗ
なかなか手強いっす。
0353デフォルトの名無しさん
2009/12/24(木) 21:20:00int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}
a(b,c,0) = 9
a(0,0,D) = d+9
a(B,0,D) = a(b-1,d,a(b,0,d-1))
a(b,C,D) = a(b,c-1,a(b,c,d-1))
大文字の引数は1以上、小文字の引数は0以上の値とすると、
引数は上の４パターンのどれかになる。
４つめがアッカーマンの心臓部となる式である。
cを1以上の数の場合、f(x) = a(b,c-1,x) とおく。
a(b,c,0) = 9
a(b,c,1) = a(b,c-1,a(b,c,0)) = a(b,c-1,9) = f(9)
a(b,c,2) = a(b,c-1,a(b,c,1)) = a(b,c-1,f(9)) = f(f(9))
a(b,c,3) = f(f(f(9)))
a(b,c,4) = f(f(f(f(9))))
となる。
つまり、a(b,c,x) は a(b,c-1,x) をループさせて出来る関数になる。
0354デフォルトの名無しさん
2009/12/24(木) 21:42:34では次に1個目の引数bについて考えてみる。（とりあえずbを固定して考える）
３つ目の式の出番である。
a(3,c,x) を考える。
a(3,c,x) はcが大きくなればどんどん増大度が増えていく。
ところが、いくらcが大きくても、a(3,x,x) にはいずれ抜かれることになる。
（実際、xがc を超えれば、a(3,c,x) < a(3,x,x) となることがわかる）
a(3,x,x) でなくて、たとえば a(3,x,1) でも大した差はなく、
a(3,c,x) をいずれ抜くことになる。
つまり、a(3,x,1) は a(3,0,x) を固定回ループさせて作ったどんな関数よりも増大度が大きい。
a(4,0,x) を考えてみる。
式3によると、xが1以上の時、
a(4,0,x) = a(3,x,a(4,0,x-1)) ≧ a(3,x,9)
となるので、a(3,0,x) を固定回ループさせて作った関数よりも増大度が大きい。
■ このスレッドは過去ログ倉庫に格納されています