■■C++で大きな数を作るスレ■■
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2009/03/24(火) 20:27:50以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。
int main();
●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください
●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします
機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可
●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0188デフォルトの名無しさん
2009/04/17(金) 02:39:470189デフォルトの名無しさん
2009/04/17(金) 07:56:44enum{s=9e9};int a=s,b[s],*c=b;int main(){for(b[s-1]=s;c<b+s;--*c<0?*c++=a:*(c=b))a<<=a;return a;} //97文字
>>188
9<<9 = 4608 だから 9999の方が大きい
0190デフォルトの名無しさん
2009/04/17(金) 08:11:34enum{s=9e9};int a=s,b[s],*c=b+s;int main(){for(*b=s;c>b;--*--c<0?*c=a:*(c=b+s))a<<=a;return a;} // 95文字
0191デフォルトの名無しさん
2009/04/17(金) 08:15:23// 80文字
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int main(){return a(9e99,9);}
0192デフォルトの名無しさん
2009/04/17(金) 21:03:24このままだと >>191 にかなわないので、
enum をやめて極限まで小さくしてみました。
int a,b[9]={9},*c=b+9;int main(){for(;c>b;--*--c<0?*c=++a:*(c=b+9));return a;} // 78文字
値的には >>125 の77文字よりすこし小さいくらいなので、
多少小さくなってもあと2文字縮められれば76文字以下で最大になります。
（でも個人的にはもう限界）
0193デフォルトの名無しさん
2009/04/17(金) 21:15:35>>42文字以下
>>102
int a=9;int main(){return a--?9<<main():9;} // 43文字
int a=99;int main(){return a--?9<<main():9;} // 44文字
int a=9e9;int main(){return a--?9<<main():9;} // 45文字
int a=9e99;int main(){return a--?9<<main():9;} // 46文字
int a=9e999;int main(){return a--?9<<main():9;} // 47文字
int a=9e9,b,c=a;int main(){while(b?b--:b=a*c--)a<<=a;return a;} // 63文字
int a=9,b,c,d=a;int main(){for(;b?b--:c?b=a*c--:c=a*d--;)a<<=a;return a;} // 73文字
// 77文字
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int main(){return a(9,9);}
// 80文字
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int main(){return a(9e99,9);}
// 100文字
int a(int b,int c,int d){return b+c&&d?a(c?b:0,c?c-1:d,a(b,c,d-1)):d+9;}
int main(){return a(1,9,9);}
// 191文字
int e(int*a,int n){
int x,y,&z=a[1],t[]={*a-1,z};
return n<3?*a?e(t,2)*z:1:z<2||*a<2?e(a+1,n-1):(x=z--,z=e(a,n),--*a,y=e(a,n),++*a,z=x,y);
}
int main(){int a[]={9,9,9,9,9,9,9,9,9};return e(a,9);}
0194デフォルトの名無しさん
2009/04/17(金) 21:36:11●43文字〜47文字
>>91 の数字を大きくしたもの
>>91 は 2^2^2^2^2^2^2^2^2 になる
引数を使わないで再帰コールを行っている
●63文字
a に対し a<<=a を繰り返すという操作を２重ループ相当のループで行い大きくしていく
>>170 の ***の繰り返しを >>172 が２重ループにし、
>>174 が２重ループを１重のループで記述するという技で短くした。
●73文字
上の >>63 文字の２重ループのものを３重ループ相当にし、
同じテクニックを用いて１重ループで表現した。
●77文字〜80文字
アッカーマン関数と呼ばれる関数を
>>9 がプログラムにした。
これを、値を多少変えて文字数を減らしたもの
●100文字
上のアッカーマン関数を中途半端に変数を一個追加して大きくしたもの
●191文字
>>118 が Conwayのチェーン表記 をプログラムにした。
これを >>131 が 191 文字に縮めた。
0195デフォルトの名無しさん
2009/04/17(金) 21:41:57int a,b[9]={9},*c=b+9;int main(){for(;c>b;--*--c<0?*c=++a:*(c=b+9));return a;} // 78文字
>>182 が、63文字の2重ループ相当や73文字の3重ループ相当のものを
配列を用いて9e9重ループ相当に
これを >>190 が95文字に縮める。
（ただし、enum{s=小数} の表現が微妙）
9重ループ相当に縮小してさらに短くして
>>77文字の作品より1文字長いところまでくる。
大きさ的には >>77文字の作品より若干小さい程度。
0196デフォルトの名無しさん
2009/04/18(土) 00:01:07>>102と>>193の記録は、文字数が大きいほど返る数も大きいって認識で良い？
0197デフォルトの名無しさん
2009/04/18(土) 01:13:49// 80文字
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}
int main(){return a(a(9));}
0198デフォルトの名無しさん
2009/04/18(土) 02:36:49int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int x,y[9]={9},*z=y+9;
int main(){for(;z>y;--*--z<0?*z=x=a(x,9):*(z=y+9));return x;}
//135B
0199デフォルトの名無しさん
2009/04/18(土) 12:43:43そうですよ。
同じ数をより少ない文字で表現しているものがあったり、
同じ文字数以下でより大きな値を返すものがあれば
記録に掲載はされません。
同じ文字数、同じ大きさなら原則先に掲載された方としますが、
考え方が大きく異なるなら両方載せるかもしれません。
>>197
その手があったか。
現状80文字以下最大。
0200デフォルトの名無しさん
2009/04/18(土) 13:02:28残念ながら、
>>195より
>>193の77文字の方が1文字少ないので、
>>197 と >>193の77文字を合わせるより、
>>193の77文字を２個合わせた方が微妙に文字数が少なく作れてしまう。
// 131文字
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int A(int b,int c){return b*c?A(b-1,A(b,c-1)):a(c,c);}
int main(){return A(9,9);}
aとAはほとんど表現が似てるので、
引数を追加してくっつけると、
// 100文字
int a(int n,int b,int c){return b*c?a(n,b-1,a(n,b,c-1)):n?a(0,c,c):c+9;}
int main(){return a(1,9,9);}
これを同じ文字数で微妙に値を大きくしたのが、
>>193 の 100文字
0201デフォルトの名無しさん
2009/04/18(土) 20:14:279をxに修正。8重ループ相当。
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int x,y[9]={9},*z=y+9;
int main(){for(;z>y;--*--z<0?*z=x=a(x,x):*(z=y+9));return x;}
//135B
ちなみにこれはa(a(a(…の個数どころかa(が増殖していく速度がアッカーマン級
という感じなので、>>193の100文字なんかよりはるかに大きいはず。
たとえば>>200の式でA(3,3)を定義したとすると
aと(と)と,の4つの記号と数字があれば表記できてしまう程度だろうけど、
上の式の9を3に変えても別の記号を使わなければ表記不可能な程度には
大きいと思う。
0202デフォルトの名無しさん
2009/04/19(日) 01:53:15aへの代入が消えてるからグローバル変数の初期値に依存するってことで>>1を満たしてないことない？
0203デフォルトの名無しさん
2009/04/19(日) 08:07:11> たとえば>>200の式でA(3,3)を定義したとすると
> aと(と)と,の4つの記号と数字があれば表記できてしまう程度だろうけど、
>>201 のと同程度に表記不可能
（もし可能だと言うなら A(2,2) でも良いのでやってみてください）
A(n,x) でn重ループ相当ですよ
>>202
それは大丈夫。
初期値無しのグローバル変数は必ず0に初期化される。
0204デフォルトの名無しさん
2009/04/19(日) 14:22:12thx。やっと理解したw。A(n,x)はn重ループと本質的には変わらないのか。
なんだアッカーマン最強じゃないか。
0205204
2009/04/19(日) 14:54:11アッカーマン最強なら、こんな感じでどうよ
// 102文字
int a(int n,int b,int c){return b*c?a(n,b-1,a(n,b,c-1)):n?a(n-1,c,c):c+9;}
int main(){return a(9,9,9);}
0206204
2009/04/19(日) 15:10:28// 100文字
int a(int b,int c,int d){return b*c*d?a(b-1,c,a(b,c-1,a(b,c,d-1))):d+9;}
int main(){return a(9,9,9);}
0207デフォルトの名無しさん
2009/04/19(日) 19:45:28>>206 は77文字のと同じくらいじゃいか？
0208デフォルトの名無しさん
2009/04/19(日) 21:57:59でも206より↓のがずっと大きいことに気づく。
// 84文字
int a(int b,int c){for(c*b)c=a(b-1,a(b,c-1));return c+9;}int main(){return a(9,9);}
0209デフォルトの名無しさん
2009/04/19(日) 22:01:00// 86文字
int a(int b,int c){for(c*b--)c=a(b,a(b+1,c-1));return c+9;}int main(){return a(9,9);}
0210デフォルトの名無しさん
2009/04/19(日) 22:19:440211デフォルトの名無しさん
2009/04/19(日) 22:36:35グッドスタイン数列をググってみたけどちっちゃいな
0212デフォルトの名無しさん
2009/04/19(日) 22:47:49文字数を考えるとAckを強化してったほうがでかいだろうけどね
0213デフォルトの名無しさん
2009/04/20(月) 22:16:21上のほうは大きいけど、下の方a(9,0)=9だし、a(99,9)は9の(99の9乗)乗とかそのくらいにしかみえない。
誰か数学詳しい人どのくらいの値なのか教えてくれ。
// 89文字
int a(int b,int c){for(;b--;)c=a(b,c?a(b+1,c-1):9);return c+9;}int main(){return a(9,9);}
0214デフォルトの名無しさん
2009/04/20(月) 22:35:269の(99の9乗)乗程度の小さな数だったら確実にA(5,3)よりは小さい
ここを見たらA(99,9)がどれだけとんでもないかわかると思う
ttp://en.wikipedia.org/wiki/Ackermann_function
0215デフォルトの名無しさん
2009/04/21(火) 00:09:01上の方は、a(99,2)=a(98,a(99,1))=a(98,a(98,2))=a(98,…,a(5,a(4,a(3,2))))…)
下の方は、a(99,2)=a(98,a(99,1))=a(98,a(98,a(99,0)))=a(98,a(98,99))
同じように見えて、展開と評価を繰り返していくとありえないくらいの
2が沸いてくるわけで全然違うようにみえませんか
一見、下の方が大きく見えるのは錯覚じゃないと
1以外の数字の扱いが同じだからいいじゃないかとか、
文字数が短くなった分、引数に大きな値を入れればいいとか、
そんな次元ではなくて、アッカーマンさんの発明自体が失われていないかな
// 79文字
int a(int b,int c){return b?a(b-1,c?a(b,c-1):9):c+9;}int main(){return a(9,9);}
のほうが実は
// 79文字
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(999,9);}
より大きいんじゃないの？
0216デフォルトの名無しさん
2009/04/21(火) 00:11:380217デフォルトの名無しさん
2009/04/21(火) 01:41:48たぶんあまり大きくない。
少なくともこれよりは小さい。
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int main(){return A(18,9);}
>>209 のbを1個増やす力は、
上のbを2個増やす力よりも小さい。
0218デフォルトの名無しさん
2009/04/21(火) 01:52:14int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
a(m,0) = 9
a(0,n) = n+9
a(1,n) は 初期値9 に対し a(0,x) を n 回行った数、9nより大きい数
a(2,n) は 初期値9 に対し a(1,x) を n 回行った数、9のn乗より大きい数
a(3,n) は 初期値9 に対し a(2,x) を n 回行った数、つまり9^9^9^9^...^9 (9がn個) より大きい数
.....
0219デフォルトの名無しさん
2009/04/21(火) 02:00:56a(m,0) = m
a(0,n) = n*9
a(1,n) は 初期値1 に対し a(0,x) を n 回行った数、9のn乗より大きい数
a(2,n) は 初期値2 に対し a(1,x) を n 回行った数、9^9^9^9^...^9 (9がn個) より大きい数
.....
0220デフォルトの名無しさん
2009/04/21(火) 02:13:34少なくともこれよりは小さい。
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int main(){return a(18,9);}
0221デフォルトの名無しさん
2009/04/21(火) 02:22:17int a(int b,int c,int d=9){return c*d?a(b,c-1,a(b,c,d-1)):b?a(0,d):d+9;}int main(){return a(1,9);} // 98文字
>>205 の102文字を3文字縮められました。
int a(int b,int c,int d){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int main(){return a(9,9,9);} // 99文字
0222デフォルトの名無しさん
2009/04/21(火) 12:50:09わかりやすい説明ありがと。もう工夫する余地はないのか。
>>221
100文字以下になるとは思わなかった。すごい。
0223デフォルトの名無しさん
2009/04/21(火) 18:55:52int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}int b=9;int main(){return a(b--?main():9,9);} //96文字
0224デフォルトの名無しさん
2009/04/21(火) 20:42:049の9の9乗乗＝つまり右肩にどんどん小さく乗ってくやつのこと？
それとも9の9乗の9乗＝(9^9)^9のこと？
0225デフォルトの名無しさん
2009/04/21(火) 20:49:390226デフォルトの名無しさん
2009/04/21(火) 22:19:44pow(9,pow(9,pow(9,......pow(9,pow(9,9)))))...) (9がn個)
C++言語のスレなので、今後べき乗の意味で ^ は使わないようにします。
0227デフォルトの名無しさん
2009/04/22(水) 07:44:42int a=99;int main(){return a--?9<<main():9;} // 44
int a=9e9;int main(){return a--?9<<main():9;} // 45
int a=9e99;int main(){return a--?9<<main():9;} // 46
int a=9e999;int main(){return a--?9<<main():9;} // 47
int a=9e9999;int main(){return a--?9<<main():9;} // 48
int a=9e99999;int main(){return a--?9<<main():9;} // 49
int a=9e999999;int main(){return a--?9<<main():9;} // 50
int a=9e9999999;int main(){return a--?9<<main():9;} // 51
int a=9<<(9<<99);int main(){return a--?9<<main():9;} // 52
int a=9<<(9<<999);int main(){return a--?9<<main():9;} // 53
int a=9<<(9<<9999);int main(){return a--?9<<main():9;} // 54
int a=9<<(9<<99999);int main(){return a--?9<<main():9;} // 55
int a=9<<(9<<999999);int main(){return a--?9<<main():9;} // 56
int a=9<<(9<<(9<<99));int main(){return a--?9<<main():9;} // 57
int a=9<<(9<<(9<<999));int main(){return a--?9<<main():9;} // 58
int a=9<<(9<<(9<<9999));int main(){return a--?9<<main():9;} // 59
int a=9<<(9<<(9<<99999));int main(){return a--?9<<main():9;} // 60
0228デフォルトの名無しさん
2009/04/22(水) 07:45:23int a=99,b,c=a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 62
int a=9e9,b,c=a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 63
int a=9e99,b,c=a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 64
int a=9e999,b,c=a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 65
int a=9e9,b,c=a<<a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 66
int a=9e99,b,c=a<<a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 67
int a=9e999,b,c=a<<a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 68
int a=9e9999,b,c=a<<a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 69
int a=9e99999,b,c=a<<a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 70
int a=9e9,b,c=a<<(a<<a);int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 71
int a=9e99,b,c=a<<(a<<a);int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 72
int a=9,b,c,d=a;int main(){for(;b?b--:c?b=a*c--:c=a*d--;)a<<=a;return a;} // 73
int a=99,b,c,d=a;int main(){for(;b?b--:c?b=a*c--:c=a*d--;)a<<=a;return a;} // 74
int a=9e9,b,c,d=a;int main(){for(;b?b--:c?b=a*c--:c=a*d--;)a<<=a;return a;} // 75
int a=9e99,b,c,d=a;int main(){for(;b?b--:c?b=a*c--:c=a*d--;)a<<=a;return a;} // 76
0229デフォルトの名無しさん
2009/04/22(水) 07:46:56int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(99);} // 78
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(9e9);} // 79
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(9));} // 80
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(99));} // 81
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(9e9));} // 82
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(9)));} // 83
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(99)));} // 84
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(9e9)));} // 85
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(9))));} // 86
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(99))));} // 87
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(9e9))));} // 88
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(a(9)))));} // 89
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(a(99)))));} // 90
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(a(9e9)))));} // 91
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(a(a(9))))));} // 92
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(a(a(99))))));} // 93
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(a(a(9e9))))));} // 94
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(a(a(a(a(a(a(9)))))));} // 95
0230デフォルトの名無しさん
2009/04/22(水) 07:47:39int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int b=99;int main(){return a(b--?main():9);} // 97
int a(int b,int c=9,int d=9){return c*d?a(b,c-1,a(b,c,d-1)):b?a(0,d):d+9;}int main(){return a(1);} // 98
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 main(){return a(9);} // 99
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 main(){return a(99);} // 100
0231デフォルトの名無しさん
2009/04/25(土) 17:22:170232デフォルトの名無しさん
2009/04/26(日) 00:41:14計算量がどのくらいになるかを考えてみたけど、
大きく見積もっても指数関数くらい。
0233デフォルトの名無しさん
2009/04/28(火) 04:19:51いろいろこねくり回した結果こうなりますた。
ちゃんと停止するかどうかも含めて評価よろしこ。
ところでint型関数がreturn文を持たないのはありなんだっけ？
gccではコンパイル通ったけど。
347文字
typedef int I;
I a=9e99,s=9,*x,*p,*q;
I A(){a<<=(a<<a);}
I B(I (*f)()){I b,c,d;for(d=c=b=a;d;(b--)?0:(c--)?(b=a):(d--)?(c=b=a):0)f();return a;}
I C(){s<<=B(A);x=new I[s+1];for(p=x;p<x+s;p++)*p=B(A);*p=-1;}
I D(){for(;;){for(p=x;!*p;p++);if(*p==-1)return B(A);for(q=x;q<p;q++)*q=B(A);B(A);(*p)--;}}
I E(){C();D();}
I main(){B(E);return a;}
0234デフォルトの名無しさん
2009/04/28(火) 19:13:07関数Aを３重ループを使って大きい関数Bを作り、
関数Bをｎ重ループを使ってさらに大きい関数Dを作り、
関数Dを３重ループを使ってさらに大きい関数を作るという感じですか
大きさ的には >>230 の97文字より大きく、98文字より小さい
戻り値のある関数をreturnを省略して抜けると動作不定である為、
A C D E と Bの引数の関数の戻り値はvoidにする必要あり
３重ループのBよりもｎ重ループのDの方が強いので
Bは無くしてDに引数fを付けた方が良いと思う。こんな感じで。
void D(void f()){......}
void F(){D(A);}
int main(){D(F);return a;}
0235233
2009/04/28(火) 20:07:41９８文字に負けてるってところを詳しく解説してホシス。
0236233
2009/04/29(水) 10:12:52まず、次のような関数loopとaddを用意する。
int loop(int a,int b,int ((*f)(int,int))){
int result=a;
for(int i=1;i<b;i++) result=f(a,result);
return result;
}
int add(int a,int b){return a+b;}
そうすると掛け算,指数関数は次のように実装できる。
int mul(int a,int b){loop(a,b,add);}
int pow(int a,int b){loop(a,b,mul);}
ここで、掛け算はloopを1回、指数関数はloopを2回,
関数の定義で使用していることがわかる。
そこで、その関数を定義するのに必要なloopの回数を返す関数loop_rankを考える。
loop_rank(add)==0;
loop_rank(mul)==1;
loop_rank(pow)==2;
etc.
0237233
2009/04/29(水) 10:23:57Ｃ言語だと関数と関数を合成して新しい関数を返す関数がかけねぇ？
関数ポインタを使えば何とかなるかなぁ…
0238233
2009/04/29(水) 10:43:35template<int N>
int f(int a,int b)
{
return loop(a,b,f<N-1>);
}
template<>
int f<0>(int a,int b)
{
return add(a,b);
}
だな。
これで大体アッカーマン相当とおもわれ。
0239デフォルトの名無しさん
2009/04/29(水) 10:48:13コンパイル通るかそれ？
0240233
2009/04/29(水) 10:51:47要するに生の整数を比べずにループが何重になってるかってことを比べる、
というのをみんなやってたわけだが、loop_rankを厳密に定義しておけば議論がしやすいかなと。
0241233
2009/04/29(水) 10:54:14ほかはしらね。
0242デフォルトの名無しさん
2009/04/29(水) 11:01:02「どれが大きいか」を判定することのほうがよっぽど難しいな
0243233
2009/04/29(水) 11:10:09なんてのは計算不能だろな。
与えられたプログラムが停止することが保障されてたとしても、
最終的な値を2進の整数に展開せずににメモリ使用量に制限かけて判定する
なんてことが可能なのかどうか…
0244233
2009/04/29(水) 11:27:13loop_rankじゃ結果が大きくなりすぎてだめだな。
もうすこし上の概念を導入しないと。
0246233
2009/04/29(水) 11:59:45今、自分が考えてるのが整数なのか関数なのかテンプレートなのか
わけが解らなくなってきたｗ
0248233
2009/04/30(木) 20:41:57最底辺IT奴隷orひきニートたるべきム板民にあるまじきブルジョアっぷりだな。
まったくもってけしからん。
俺もGWあけたら奴隷生活に戻るんだからはやめに返事クレ。
0249233
2009/05/01(金) 20:39:27Aをアッカーマン関数とするとおおむね、
A(1,9,9)=A(A(9,9),A(9,9))
でいいんかな？
02501
2009/05/02(土) 16:16:35クラスや構造体を使えば実装可能です。
struct OPERATOR{
virtual int operator()(int x,int y) = 0;
};
struct OPERATOR_ADD:OPERATOR{
virtual int operator()(int x,int y){
return x+y;
}
};
struct OPERATOR_LOOP:OPERATOR{
OPERATOR*a;
OPERATOR_LOOP(OPERATOR*a_):a(a_){}
virtual int operator()(int x,int y){
int r=x;
for(;--y;)
r=(*a)(x,r);
return r;
}
};
OPERATOR* mul = new OPERATOR_LOOP(new OPERATOR_ADD);
OPERATOR* power = new OPERATOR_LOOP(mul);
OPERATOR* tetration = new OPERATOR_LOOP(power);
02511
2009/05/02(土) 16:25:48loop_rank がnの関数を f[n](x) とした時、
関数 f[x](x) を考えてみる。
この関数は、f[大きな整数](x) よりも増大度が大きく、
x=大きな整数を超える場合は
f[x](x) の方が大きい。
f[x](x) はloop_rank で言うと無限みたいなもの。
0252デフォルトの名無しさん
2009/05/02(土) 16:33:39引数が１個の関数を考えてみる。
struct function{
virtual int operator()(int x) = 0;
};
struct function_successor:function{
virtual int operator()(int x){ return x+1; }
}
struct function_loop:function{
function*a;
function_loop(function*a_):a(a_){}
virtual int operator()(int x){
int r=x;
for(;x--;)
r=(*a)(r);
return r;
}
};
struct function_loop2:function{
function*a;
function_loop2(function*a_):a(a_){}
virtual int operator()(int x){
int r=x;
for(;x--;)
r=(*a)(r);
return r;
}
};
02531
2009/05/02(土) 16:39:45function_loopは function_loop(ある関数) とすることで
loop_rank を1個増やすことができる。
function_loop2 は引数の数字分function_loopを付け足すものである。
function*a=new function_loop2(new function_successor)
とした時、
(*a)(10) はfunction_successor に対してfunction_loop を10個追加した関数に10を入れたもの
(*a)(100) はfunction_successor に対してfunction_loop を100個追加した関数に10を入れたもの
である。
この時のaのloop_rankを考えると、
function_successor に function_loop を整数個つけたいかなる関数よりも
早く増大することが分かる。
たとえばfunction_loop を100個つけた関数と比べると、
引数が101以上の場合はa の方が値が大きくなる。
02541
2009/05/02(土) 16:48:24>>233 の場合、
関数B(A)はloop_rankが5と6の間くらいの関数。
関数EはB(A)に対し、loop_rankがωのループを行うので、
loop_rankが6+ωくらい。
ここで、253のaを考えてみると、
(*a)(10) に対して(*a)(20) は10 loop_rank が増えた関数に20を代入している。
>>233 の関数Eも
B(A)のloop_rankが小さくても引数をちょっと大きくするだけで追い抜いてしまう。
つまり、関数Eはloop_rankがωである (*a) などとほとんど同じ増大度であるといえる。
最終の関数 B(E) はEにloop_rankを３増加したものとなるので、
loop_rank はω+3くらいである。
つまり、 >>233 は loop_rank が ω+3 程度の関数に 9e99 を入れたものとなる。
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文字
//結局アッカーマン
■ このスレッドは過去ログ倉庫に格納されています