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

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

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

int main();

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

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

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

●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0002デフォルトの名無しさん2009/03/24(火) 20:29:33
ダメな例
int main(){ return sizeof(int); } 　　　　　　　　　　// 環境依存
int main(){ return (unsigned int)-1/2; }　　　　// 環境依存
int main(){ return 'z'; }　　　　　　　　　　　　　　　// 環境依存
int main(){ return 1.0/0.0; }　　　　　　　　　　　　// 環境依存
int main(){ int a = 9; return a <<= a <<= a; }　　// 未定義動作
int main(){ int a = 9; return ++a * ++a; }　　　　　// 未定義動作
int main(){ quit(9) }　　　　　　　　　　　　　　　　// main の戻り値じゃない、ライブラリ使用不可
int main(){ while(1) printf("9"); }　　　　　　　　// main の戻り値じゃない、ライブラリ使用不可
int main(){ return 1.0/【>>1の知能指数】; }　　// ネタとしてもいまいち
int main(){ return 【このスレでの最大値】+1 ; }　　　 // ネタとしてもいまいち

小さいものの例
int main(){return 9;} // 21文字
int main(){return 99;} // 22文字
int main(){return 999;} // 23文字
int main(){return 9999;} // 24文字
int main(){return 9<<99;} // 25文字

ちょっと大きい数の例 (50文字)
int main()
{
　　int n=99,m=n;
　　while(m--)
　　　　n<<=n;
　　return n;
}
0003デフォルトの名無しさん2009/03/24(火) 21:01:23
>>言語は C++ 2003 準拠とします
その自信は何処から？
何で、言語は C++ 2003 準拠とします ？
環境依存不可としながら、糞スレ立てるな
0004デフォルトの名無しさん2009/03/24(火) 21:15:03
>>3
もしかして Visual C++ 2003 のことだと思ったのかな？
ISO/IEC 14882:2003 のことだよ。
0005デフォルトの名無しさん2009/03/24(火) 21:23:32
>>1スレで完結したプログラム！？
0006デフォルトの名無しさん2009/03/24(火) 21:26:46
まちがった。

最大でも１レスに収まる範囲とし、
１レスで完結したプログラムとしてください。
0007デフォルトの名無しさん2009/03/24(火) 22:55:48
1レスで完結したスレ
0008デフォルトの名無しさん2009/03/24(火) 23:05:08
はいはい　かちこい　かちこい
0009デフォルトの名無しさん2009/03/24(火) 23:33:37
とりあえず、ベタなところから行っとくか。（９４文字)

int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return a(9,9);}
0010デフォルトの名無しさん2009/03/25(水) 01:33:48
int main(){int a,b;for(a=b;a<++b;a=b);return a;}

４８文字。常にint型で表現可能な最大値を返す。
0011デフォルトの名無しさん2009/03/25(水) 02:05:07
int main(){int a,b;for(;(a=b)<++b;);return a;}
>10 をショートコーディング 46文字
0012デフォルトの名無しさん2009/03/25(水) 02:13:11
int main(){int i=0;for(;++i>0;);return i-1;}
普通にやったら、11より短くなった。
44文字　ついでにsageわすれる
0013デフォルトの名無しさん2009/03/25(水) 02:21:11
int main(){int a;for(;a<a+1;a++);return a;}

４３文字。アイディアは>>10と同じ。
0014デフォルトの名無しさん2009/03/25(水) 02:34:23
int main(int x){return(x<x+1)?main(x+1):x;}

４３文字。無理やり再起を使ってみた。
0015デフォルトの名無しさん2009/03/25(水) 02:42:58
int main(){int a;for(;a+1>--a;);return a;}
>13
をヒントにしたが、既に原型をとどめていない。
しかも、コンパイラ依存かな。
42文字
main()再帰もやりたかったけどプロトタイプ宣言されてたからなぁ。
0016デフォルトの名無しさん2009/03/25(水) 03:06:07
int main(){int i=0;for(;--i<0;);return i;}
>15作った後に>12を見直したら
これでいいことがわかった。
42文字
0017デフォルトの名無しさん2009/03/25(水) 03:35:07
int main(){return(1<<sizeof(int)*8-1)-1;}
1Byteが、8bitじゃないですよね。４１文字。
「char型は、1である」だっけ、これ名言だもんな。
0018デフォルトの名無しさん2009/03/25(水) 04:50:07
BigNumberをム板住民で実装するスレかと思ったら違うのか
0019デフォルトの名無しさん2009/03/25(水) 08:08:44
>>9
いきなりそんなとてつもなく大きな数が出てくるとは....

>>10-13 >>15-17
C++規格上はオーバーフロー、アンダーフロー時の値は不定で、
特殊なマシンだとintの値の１個が無効値を表すものがあるので上手く動かない場合がある
多くのコンパイラの場合に動作すれば良いなら、>>2 のダメな例の２個目の方が短くて同じ値を返す

>>14
プロトタイプが
int main();
だからmainの引数は使っちゃダメだよ
0020デフォルトの名無しさん2009/03/25(水) 08:10:28
>>1 の仕様だとintに上限が無いから >>10 は無理じゃないか?
0021デフォルトの名無しさん2009/03/25(水) 14:33:42
int main(){int i=8;float f=9e+9;for(;f>0;f-=1e-9)i*=i;return i;}
intに上限が無いと聞きまして、６４文字。
いくらになるかは知らない。シフトしたらぐはっ。
0022デフォルトの名無しさん2009/03/25(水) 18:24:08
int main(){return 1e+9;} // 24文字
int main(){return 1e+99;} // 25文字
0023デフォルトの名無しさん2009/03/25(水) 18:33:36
>>22
eまたはE表現は、double型なので、int型にキャストしてやる必要があるのではないかしらん。
C言語なら暗黙でやってくれると思うけど、C++ですから。static_cast<int>()
0024デフォルトの名無しさん2009/03/25(水) 19:15:34
C++にもその暗黙の型変換あるぜ
0025デフォルトの名無しさん2009/03/25(水) 20:12:20
>>21
i=8 より i=9 の方が大きくないか？
0026デフォルトの名無しさん2009/03/25(水) 20:37:40
運営移転ミスってるな　まぁ、乙と言っておくか

>48
もちろん9の方が、大きくなると思うけど、
あそこまでいくと些細なことなので、最適化されるように2の乗数にしておいただけ。

i*=i -> i<<=i
乗算を左シフト演算にするとA[1] = 8, A[n+1] = An*2^A[n]ほえ〜
0027デフォルトの名無しさん2009/03/25(水) 20:49:59
意味が分からんのだが、sizeof(int)が不明な場合ってことなのか？
0028デフォルトの名無しさん2009/03/25(水) 20:56:11
>>21
int main(){int i=8;float f=9e+9;for(;f>0;f-=1e-9)i<<=i;return i;}
int main(){int i=8;float f=9e+18;for(;f>0;f-=1)i<<=i;return i;}
int main(){int i=8,f=9e+18;while(f--)i<<=i;return i;}
int main(){int i=9e+99,f=i;while(f--)i<<=i;return i;} // 53文字
最適化したら >>2 とそっくりだよ〜
0029デフォルトの名無しさん2009/03/25(水) 20:58:33
>>28
よくわからんが、sizeof(int)が一定のある値だったとして、i <<= i が未定義でないとしても
1ﾋﾞｯﾄづつうごかさなければ最大値は取れんよね。
いまいちﾙｰﾙが分からん。
0030デフォルトの名無しさん2009/03/25(水) 21:21:59
>>27 >>29
int で表せる範囲は十分大きいということしか決まっていない。
決まってないにも関わらずmain関数が同じ値を返すようなプログラムに
しなくてはいけないというのがルール。

十分大きいとはどういうことかというと、
>>1 のルールでいくら大きな数を作っていったとしても、
1レスではオーバーフローさせることが出来ないほど大きいということ。

ISO/IEC 14882:2003 では int の最小範囲は決まってるが、
最大範囲は決まっていないので、
int の範囲がいくら広くても
ISO/IEC 14882:2003 に反しない。

charがintと同じサイズでsizeof(int)は1という可能性もあるし、
sizeof(int)はとてつもなく大きな値である可能性もある。
0031デフォルトの名無しさん2009/03/25(水) 21:30:58
>>13 はなぜダメかというと、
int の大きさに依存した値が返るから。
（厳密に言うとISO/IEC 14882:2003のルールでは無限ループの可能性もある）

int や float の大きさに依存しないプログラムであれば、
1レスで作れる最大の数があるはずで、
それよりも int は大きな数を保持できますよ
ということ。
0032デフォルトの名無しさん2009/03/25(水) 21:38:10
>>31
さっぱり分からんのだが、
int main() { return 1e99999999999999999999;}
じゃだめなのか？
0033デフォルトの名無しさん2009/03/25(水) 21:41:31
それじゃ小さすぎる。
0034デフォルトの名無しさん2009/03/25(水) 21:41:56
floatに関して十分な精度というのは、
たとえば内部的には整数÷整数の有理数の形で保持されていて
誤差がまったく無いようなものを想定している。

有限文字の浮動小数点定数と四則演算では
有理数しか作れないので。
0035デフォルトの名無しさん2009/03/25(水) 21:46:38
>>32
42文字使えばもっとずっと大きな数が作れる。
たとえば、

int main(){return 9<<(9<<(9<<(9<<9999)));} // 42文字
0036デフォルトの名無しさん2009/03/25(水) 22:13:25
多くのプログラマは自力で>>9を超えるプログラムは組めまい。
というか>>9のプログラムが何であるか知らずに>>9を超えるプログラムを自力で組んだらほとんど天才だが。
0037デフォルトの名無しさん2009/03/25(水) 22:24:39
>>36
ﾙｰﾙ違反だし(m)の括弧とか不要だし、ﾌﾟﾛｸﾞﾗﾏとしては三流だな。
0038デフォルトの名無しさん2009/03/25(水) 22:28:26
>>37
どの辺がルール違反？
括弧はおれもすごく気になってた。
0039デフォルトの名無しさん2009/03/25(水) 22:34:41
main関数の中にすべて入れる必要はないですよ。

int factorial(int n){ return n ? n*factorial(n-1) : 1; }
int main(){ return factorial(99); }

こんなのもＯＫ。
0040デフォルトの名無しさん2009/03/25(水) 22:37:13
できたぞ。まさか無限とは言わんだろうな。
int main(){char a=1,b=0;for(;a==b+1;a++,b++);return a;}
0041デフォルトの名無しさん2009/03/25(水) 22:38:09
もちろんcharじゃなくてintな。
0042デフォルトの名無しさん2009/03/25(水) 22:41:56
>>39
それ許すならmain()の引数許した方がよっぽどスマート。
0043デフォルトの名無しさん2009/03/25(水) 22:45:58
>>42
最初に呼ばれるmainの引数は何になるの？
不定？
0044デフォルトの名無しさん2009/03/25(水) 22:47:19
>>43
int argc, char argv[]に決まってる。
別に不定でもなんでもいいだろ。
0045デフォルトの名無しさん2009/03/25(水) 22:53:59
>>44
不定の引数なんて意味が無いと思って
int main();
に限定したんだけど、
その引数で大きな数が作れるなら是非作ってみて！
ただし、引数に依存しない数を返してね。
00469=362009/03/25(水) 22:55:50
mainの引数許してどうするんだよ。
結果がmainの引数に依存したら評価しにくいだろ。

括弧は三項演算子書くときの癖だ。
つい、いつものように書いちまった。

0047デフォルトの名無しさん2009/03/25(水) 22:58:19
>>9 を整形してみた。

// 86文字
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return a(9,9);}

たぶん下の方が大きいよね。

// 80文字
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}
int main(){return a(99,9);}
0048デフォルトの名無しさん2009/03/25(水) 23:02:40
>>40で終了だろうが。
0049デフォルトの名無しさん2009/03/25(水) 23:08:19
>>40
・charのサイズに依存した値が返る

・オーバーフローした場合の値は ISO/IEC 14882:2003 では未定義であり
　環境によっては無効値を表す値をとる場合がある
　無効値での == の結果も ISO/IEC 14882:2003 では未定義
0050デフォルトの名無しさん2009/03/25(水) 23:16:32
>>40
それ以前に、ほとんどの環境で無限ループだった。
インクリメントでオーバーフローしたときの値と
+1 でオーバーフローした時の値は
普通は同じだよ。
0051デフォルトの名無しさん2009/03/25(水) 23:23:09
オーバーフローねたは>>1の思い描くスレの趣旨とは違うので、そろそろ勘弁してやれ。
0052デフォルトの名無しさん2009/03/25(水) 23:23:30
これまでの記録

int main(){return 9;} // 21文字
int main(){return 99;} // 22文字
int main(){return 999;} // 23文字
int main(){return 1e+9;} // 24文字
int main(){return 1e+99;} // 25文字
int main(){return 9<<(9<<(9<<(9<<9999)));} // 42文字
int main(){int n=99,m=n;while(m--)n<<=n;return n;} // 50文字
int main(){int i=9e+99,f=i;while(f--)i<<=i;return i;} // 53文字

// 80文字
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}
int main(){return a(99,9);}
0053デフォルトの名無しさん2009/03/25(水) 23:30:32
>>50
無限ループじゃねーよ。+1と++の違いには依存してねーよ。
0054デフォルトの名無しさん2009/03/25(水) 23:33:54
>>52
1e+9なら9e99の方がでかい。
0055デフォルトの名無しさん2009/03/25(水) 23:54:18
>>53
b+1 の型は int になるんだったね。
うっかりしてた。

>>40 は
char の範囲よりも int の範囲が広い場合には、
char の最大値をインクリメントした値が返る。
（多くの場合 -128）

char の範囲と int の範囲が同じ場合には、
無限ループ。
0056デフォルトの名無しさん2009/03/26(木) 00:00:36
>>54
たしかに。

int main(){return 9e99;} // 24文字
int main(){int i=9e99,f=i;while(f--)i<<=i;return i;} // 52文字
0057デフォルトの名無しさん2009/03/26(木) 00:02:22
これもだ

int main(){return 9e9;} // 23文字
0058デフォルトの名無しさん2009/03/26(木) 02:00:38
>>30の
>ISO/IEC 14882:2003 では int の最小範囲は決まってるが、
が結論で、その最小範囲内における最大値が唯一の答えだと思うんだが。
それ以上は環境によってオーバーフローする可能性がある。



0059デフォルトの名無しさん2009/03/26(木) 11:52:16
表向きは数学の演習問題だが、>>1の本心は
C++の規約(ISO/IEC 14882:2003)を理解しているかどうか試したいんだろ。
0060デフォルトの名無しさん2009/03/26(木) 21:01:53
>>58
標準規格で定義してない部分を追加で定義してるんで。
int のサイズが制限されてたら大きな数を作れないでしょ。

自力で巨大な整数を保持出来るクラスを作るにも、
組み込み整数型のサイズ制限があったら、
メモリ確保時のサイズが制限を超えちゃうんで作れないし。

>>59
当方、標準規格に詳しいわけでもないし、
C++のテクニックをたくさん知っているわけでもない。
むしろ教えてもらいたい方ですよ。

単純に、C++という言語を使って限られた文字数で
どのくらい大きな数が定義できるのか知りたいのよ。

たとえば私の能力では50文字で >>2 が精一杯だけど、
C++に詳しい人やいろんな人の頭脳を使えば
もっと大きく出来たり文字数を減らせたりするんじゃないかと。

>>21 のような、浮動小数点定数を用いる発想は私には無かったわけだし。
0061デフォルトの名無しさん2009/03/26(木) 23:14:42
おりゃ！

int a(int z){ return z?z<<a(z-1):9 }
int b(int z){ return z?a(b(z-1)):9 }
int c(int z){ return z?b(c(z-1)):9 }
int d(int z){ return z?c(d(z-1)):9 }
int e(int z){ return z?d(e(z-1)):9 }
int f(int z){ return z?e(f(z-1)):9 }
int g(int z){ return z?f(g(z-1)):9 }
int h(int z){ return z?g(h(z-1)):9 }
int i(int z){ return z?h(i(z-1)):9 }
int j(int z){ return z?i(j(z-1)):9 }
int k(int z){ return z?j(k(z-1)):9 }
int l(int z){ return z?k(l(z-1)):9 }
int m(int z){ return z?l(m(z-1)):9 }
int n(int z){ return z?m(n(z-1)):9 }
int o(int z){ return z?n(o(z-1)):9 }
int p(int z){ return z?o(p(z-1)):9 }
int q(int z){ return z?p(q(z-1)):9 }
int r(int z){ return z?q(r(z-1)):9 }
int s(int z){ return z?r(s(z-1)):9 }
int t(int z){ return z?s(t(z-1)):9 }
int u(int z){ return z?t(u(z-1)):9 }
int v(int z){ return z?u(v(z-1)):9 }
int w(int z){ return z?v(w(z-1)):9 }
int x(int z){ return z?w(x(z-1)):9 }
int y(int z){ return z?x(y(z-1)):9 }
int main(){ return y(9e9999999999); }
0062デフォルトの名無しさん2009/03/26(木) 23:30:34
>>36
あっさり抜かれてるじゃん。
0063デフォルトの名無しさん2009/03/26(木) 23:41:48
>>61
それa〜yを一つの関数にできるな
第一引数が0ならa, 1ならbとして振舞うって具合に
で、そのように書き換えると>>9とほぼ同じコードになる
0064デフォルトの名無しさん2009/03/27(金) 08:07:10
int main() { return INT_MAX; }
終了。
0065デフォルトの名無しさん2009/03/27(金) 10:47:20
>>64 #include <limits.h>が必要だろ
0066デフォルトの名無しさん2009/03/27(金) 18:31:07
int の最大値を返すプログラムはいい加減かんべんしてください。
0067デフォルトの名無しさん2009/03/27(金) 18:41:15
これまでの記録

int main(){return 9;} // 21文字
int main(){return 99;} // 22文字
int main(){return 9e9;} // 23文字
int main(){return 9e99;} // 24文字
int main(){return 9<<(9<<(9<<(9<<9999)));} // 42文字
int main(){int n=99,m=n;while(m--)n<<=n;return n;} // 50文字
int main(){int i=9e99,f=i;while(f--)i<<=i;return i;} // 52文字

// 80文字
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}
int main(){return a(99,9);}

// 883文字
>>61
0068デフォルトの名無しさん2009/03/27(金) 18:43:33
883文字のやつより80文字のやつの方が大きいか。
0069デフォルトの名無しさん2009/03/27(金) 19:05:02
プログラムの終了値をbashから表示させる方法ある？
0070デフォルトの名無しさん2009/03/27(金) 19:12:22
自己解決。終了コードは$?に代入されますね。
0071デフォルトの名無しさん2009/03/27(金) 19:26:17
良く覚えてないけど、あれって0〜255しか返せないんじゃなかったっけ？
0072デフォルトの名無しさん2009/03/27(金) 19:32:33
>>71
ぽいですね。
int main(int argc, char **argv) {
if (argc < 2) return -1;
int i = atoi(argv[1]);
printf("%d\n", i);
return i;
}
$ ./a.exe 256; echo $?
256
0

$ ./a.exe 255; echo $?
255
255
0073デフォルトの名無しさん2009/03/28(土) 06:19:22
9e99999 の時点で結果は画面内に収まりきらないよ。
浮動小数点の指数表現にしても 9<<(9<<99999) の時点で無理。
0074デフォルトの名無しさん2009/03/29(日) 02:19:30
883文字も使うなら
a(9,9)->a(a(9,9),a(9,9))->a(a(a(9,9),a(9,9)),a(a(9,9),a(9,9)))
と重ねたほうがでかくなるよな。
0075デフォルトの名無しさん2009/03/29(日) 03:33:00
int p(int x,int y){return y?x*p(x,y-1):1;}
int k(int x,int y,int n){return n-1?y?k(x,k(x,y-1,n),n-1):1:p(x,y);}
int g(int z){return k(3,3,z);}
int G(int w){return w-1?g(G(w-1)):g(4);}
int main(){return G(64);}

205文字。
0076デフォルトの名無しさん2009/03/29(日) 08:46:01
結局数学的に停止が証明されてるものをコーディングするしかないんじゃねーの。
C++だからって特別に何かあるわけじゃなし、何がおもしろいんだか。
0077デフォルトの名無しさん2009/03/29(日) 09:33:16
>>75
同じ値で文字を減らせる
int k(int x,int y,int n){return n?y?k(x,k(x,y-1,n),n-1):1:x*y;}
int main(){int n=4,m=64;while(m--)n=k(3,3,n);return n;}
118文字


>>74
こんな感じかな？

// 113文字
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){int n=9,m=99;while(m--)n=a(n,n);return n;}

これで >>75 よりは大きくなったかな？
0078デフォルトの名無しさん2009/03/29(日) 10:19:23
return ~(unsigned)0;
0079デフォルトの名無しさん2009/03/29(日) 10:59:17
>>2
0080デフォルトの名無しさん2009/03/30(月) 09:30:55
インラインアセンブラで多倍長整数型演算を実装するとかそんなんじゃないのね
多ビットのそこそこ速い計算が必要で自分でJAVAのヒッグデシマルみたいなクラス作るのマンドクセとおもったから覗いてみたけど
ネタスレだったか
0081デフォルトの名無しさん2009/03/31(火) 01:12:04
>>80
うん、バイバイ。
0082デフォルトの名無しさん2009/03/31(火) 06:26:40
http://science6.2ch.net/test/read.cgi/math/1194777915/
0083デフォルトの名無しさん2009/03/31(火) 21:29:10
たとえば50文字だと >>2 みたいなループが作れるけど、
48文字で書ける最高の数って何だろう？

あと２重の再帰定義を77文字にすることは出来たんだけど、
76文字の場合の最高は何だろう？
>>2 みたいな普通のループ＋シフトかな？

// 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);}


２重再帰定義と >>2 のループを合わせると、
103文字で、大きな数で有名な >>75 を超えることが出来るけど、
100文字以下だと最大はどんな数だろう？

// 103文字
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}
int main(){
　　int n=99,m=n;
　　while(m--)
　　　　n=a(n,n);
　　return n;
}
0084デフォルトの名無しさん2009/03/31(火) 23:04:31
神に祈りながら
int main(){
   int n(0)
   while( rand()%2 == 0 ){
      n++;
   }
   return n;
}
0085デフォルトの名無しさん2009/04/01(水) 15:20:27
>>84
おしい つ >>1
0086デフォルトの名無しさん2009/04/01(水) 18:38:18
こっちの方が大きいんじゃね？
まあいずれにしろ >>1

int main(){
int n(0);
while( rand() ){
n++;
}
return n;
}
0087デフォルトの名無しさん2009/04/01(水) 18:39:29
あれ、行頭のスペースが消えた。
>>84 みたいにスペースを付けるのはどうやんの？
0088デフォルトの名無しさん2009/04/01(水) 21:20:18
>>87 &nbsp;じゃない？多分。
int main() {
    return 9;
}
0089デフォルトの名無しさん2009/04/01(水) 21:42:58
テスト

int main(){
    int n(0);
    while( rand() ){
        n++;
    }
    return n;
}
0090デフォルトの名無しさん2009/04/03(金) 00:07:42
100文字以内でのチャンピオンは俺がもらった！
100文字の制限がなくても今までで最大。

// 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);}
0091デフォルトの名無しさん2009/04/03(金) 01:47:44
int a=9;int main(){return a--?1<<main():1;}

とりあえずテトレーションを書いて見たかった。
0092デフォルトの名無しさん2009/04/03(金) 08:31:01
>>91
お〜〜〜、目から鱗。
引数無しでも再帰が書けるのか。
0093デフォルトの名無しさん2009/04/03(金) 11:16:47
>>91
その1は9にした方がいいんｼﾞｬﾏｲｶ?
つーか、それぞれいくつになるのかと1文字あたりいくつになるかくらい書いとけ。
0094デフォルトの名無しさん2009/04/03(金) 13:15:58
>>93
>>92のままだと要するに2↑↑9だから簡単な数式であらわせるから、
大きさの見積もり楽だなぁという理由であえて1にしてました。

このスレは出来る限り大きな数を目標にしてるから9のほうがいいんだろうけどねぇ。
0095デフォルトの名無しさん2009/04/03(金) 19:29:35
ちょっと質問だが、 new int[n]は使ってよいの？
もっとも使ったところで役に立つかどうかはまだわからないけど。
0096デフォルトの名無しさん2009/04/03(金) 22:49:26
>>95
もちろんOK.
C言語ではなくC++にした一番の理由が、
言語上でメモリ確保が出来ること。

メモリは十分にあるのでメモリ確保は失敗しない。
mainリターン時に解放していなくてもOK.
ということで。

>>94
このスレ的には
値の綺麗さや実行時間やメモリ使用量やバイナリサイズは一切問わず、
同じ文字数なら1でも大きい数を返す、
同じ大きさを返すなら1文字でも短くする、
のが目的。

ということで、
1を9に変えさせていただきます。
int a=9;int main(){return a--?9<<main():9;} // 43文字

きれいな数値でなくても、>>1 が責任を持って大きさを比較します。

>>93
mainの戻り値は簡単に書けないくらいの大きさになるので、
いくつになるか書くのは難しいかと。
0097デフォルトの名無しさん2009/04/03(金) 22:57:20
今までの記録

int main(){return 9;} // 21文字
int main(){return 99;} // 22文字
int main(){return 9e9;} // 23文字
int main(){return 9e99;} // 24文字
int main(){return 9<<(9<<(9<<(9<<9999)));} // 42文字
int a=9;int main(){return a--?9<<main():9;} // 43文字

// 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);}

// 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);}

大きく空いている44文字〜76文字の作品と、
文字数無制限（ただし１レス以内）の作品を特に募集中。
0098デフォルトの名無しさん2009/04/03(金) 23:33:41
環境依存だけどこんなの思いついた。
int main(){int i;return (int)&i;}//33文字？

思ったより短くないなぁ。。。
0099デフォルトの名無しさん2009/04/04(土) 01:29:05
それだったらこんなのもいいじゃない。
int main(){return (int)main;}
0100982009/04/04(土) 04:02:33
あーそれいいね。
俺よりは環境依存っぽくない。
0101デフォルトの名無しさん2009/04/04(土) 13:48:17
スタックのメモリ空間が独立していたらしょぼい結果になりそうだけど。
ロードアドレスもそうだね。少なくとも、24文字の9e99に勝てそうにないし。
ってことで、24と42の間を無駄に埋めてみる。
int main(){return 9e99*9e99;} // 29文字
0102デフォルトの名無しさん2009/04/04(土) 21:36:26
私の思いつく範囲だと、
たぶん42文字まではこんな感じじゃないかと思うんだけど、
もっと大きいのあるかなあ？

int main(){return 9;} // 21文字
int main(){return 99;} // 22文字
int main(){return 9e9;} // 23文字
int main(){return 9e99;} // 24文字
int main(){return 9e999;} // 25文字
int main(){return 9e9999;} // 26文字
int main(){return 9e99999;} // 27文字
int main(){return 9e999999;} // 28文字
int main(){return 9e9999999;} // 29文字
int main(){return 9<<(9<<99);} // 30文字
int main(){return 9<<(9<<999);} // 31文字
int main(){return 9<<(9<<9999);} // 32文字
int main(){return 9<<(9<<99999);} // 33文字
int main(){return 9<<(9<<999999);} // 34文字
int main(){return 9<<(9<<(9<<99));} // 35文字
int main(){return 9<<(9<<(9<<999));} // 36文字
int main(){return 9<<(9<<(9<<9999));} // 37文字
int main(){return 9<<(9<<(9<<99999));} // 38文字
int main(){return 9<<(9<<(9<<999999));} // 39文字
int main(){return 9<<(9<<(9<<(9<<99)));} // 40文字
int main(){return 9<<(9<<(9<<(9<<999)));} // 41文字
int main(){return 9<<(9<<(9<<(9<<9999)));} // 42文字
0103デフォルトの名無しさん2009/04/04(土) 22:02:53
VC++ 2008でint main(){return 0xffffffff;}相当
cl t.c /link /merge:.text=.data

char main[]={184,-1,-1,-1,15,195}; //34字
_int64 main=0xc30fffffffb8; //27字

今思った。VC++と縛りを入れた以上、INT_MAXの0x7ffffffffのほうがいいのではないかと。

いずれにせよ>>102には遙か及ばない。
0104デフォルトの名無しさん2009/04/04(土) 22:04:06
C++の規約で巨大数を作れとか、圏論をXMLに適応させろとか、
数学ネタのスレは良く分からん。
0105デフォルトの名無しさん2009/04/05(日) 11:56:06
>>1

「int と float は十分な精度があるとします 」
これの意味と

どうやって大きい数と判定しているかを教えてくれ


(ちゃんと勉強している者が)普通に考えたら >>36 がいってることが正しい
0106デフォルトの名無しさん2009/04/05(日) 19:59:50
>>105
> 「int と float は十分な精度があるとします 」
> これの意味と

int に関しては、
>>1 のルールを守ったプログラムの中で、
最大の数を返すプログラムでもオーバーフローしない程大きいと思ってください。
（int のサイズに依存したプログラムで無ければ、1レスで作れる最大の数が定義出来るはず）
これで意味がわからなければ、
どんな整数もあらわせる多倍長の整数クラスみたいなものと思って頂いてもいいです。
（ただし、シフトやビット演算は普通の int のふるまいと同じです。）

float に関しては、
十分大きな数も保持出来るのに加えて、
演算に誤差がないもとのします。
内部的には上のint型２個による有理数みたいなものと思ってください。
C++の言語上はfloatの演算は +-*/ しかないので
有理数の範囲で誤差がない演算ができます。
double 型の定数からも誤差なくfloatに変換できるとします。

----
多倍長整数クラスや多倍長有理数クラスでも結局
普通の環境を想定すると new int[size] のsize が大きくなりすぎるし、
ポインタ型も大きくなりすぎるんだよね。
0107デフォルトの名無しさん2009/04/05(日) 20:21:38
>>105
> どうやって大きい数と判定しているかを教えてくれ

>>1 が責任を持って比較、判定します。
答えになってないか。

1レスで書ける程度のプログラムで、
ただひたすら大きな数を作るようなプログラムなら、
>>1 は大きさを見積もれるのではと思っています。（自信過剰？）
また、逆に >>1 が大きさを見積もれないほど大きな数が作れるならそれも見てみたい。

現代数学では大きさが見積もれないようなプログラムだったとしたら、
（たとえば存在が証明されてないような数を返すプログラム）
比較が出来ないかも知れないけど、
その場合も大きさ判定不能な作品として残したいと思います。
判定不能でも文字を極限まで減らすような努力もできるし。
0108デフォルトの名無しさん2009/04/05(日) 20:23:04
>>105
> (ちゃんと勉強している者が)普通に考えたら >>36 がいってることが正しい

>>9 より力技の >>61 の方が大きいし、
たくさんの人がいろんな発想で挑戦すれば超えられるかも知れない。
文字数が少ないものは数学の知識よりもC++の知識の方が重要だし。
だれかが作ったものに文字を追加してさらに大きな数を作るようなこともできる。
数学がぜんぜんダメな人でも
C++に詳しければ同じ値で文字数を減らすことが出来るかも知れないし。

とにかくいろんな発想で大きな数を作ったり文字を減らすのが見たい。
大きさの比較は >>1 が責任を持って行います。
0109デフォルトの名無しさん2009/04/05(日) 21:05:54
>>108
比較の内容と結果をちゃんと書けよ。
01101052009/04/05(日) 22:11:37
>>106

/*
 File : test.cpp
 Compile : g++ test.cpp -lgmpxx -lgmp
*/
#include <iostream>
#include <gmpxx.h>

typedef mpz_class BigInteger;

BigInteger fact(int n){
  BigInteger ans = 1;
  do { ans *= n; } while( --n );
  return ans;
}

BigInteger f(){
  return fact(100);
}

int main(){
  std::cout << f() << std::endl;
  return 0;
}

「ライブラリ使用不可」ってのを破ってるけど
「int と float は十分な精度があるとします 」
を守るためだけに使いました
この例では単純な factorial(100) を出力するやつを書いてみた
要は上の f() を main() に変えて大きな数を作るってことでOK?
01111052009/04/05(日) 22:12:31
>>107
>>108

> >>1 が責任を持って比較、判定します。
> 答えになってないか。

はい、答えになっていません


> >>1 は大きさを見積もれるのではと思っています。（自信過剰？）
> 大きさの比較は >>1 が責任を持って行います。

たとえば
>>9 と >>61 の桁数を教えてください
本当に >>61 のほうが大きいのですか？
私にはわかりません
(両方とも)とても計算できそうにないので


> C++に詳しければ同じ値で文字数を減らすことが出来るかも知れないし。
きっとそうですが、
「数値の大きさ」と「コードサイズ」を比べるのは
アンマッチな感じがします
0112デフォルトの名無しさん2009/04/05(日) 22:52:17
お前がこのスレにアンマッチなんだろう。
0113デフォルトの名無しさん2009/04/05(日) 23:08:24
>>109
そりゃそうですね。書きます。
その文字数以内で最大の物はそれより小さい文字での最大のものより大きい説明を、
最大でないものはより文字数が小さいものorより値が大きいものとの比較を
書いていきます。

■ >>10-17,40,64,84,86,89,98,99,103
ルール違反

■ >>2
50文字
初期値 n=99 に対して、n<<=n を 100 回行っている。
>>96 の 初期値 x=9 に対し、x=9<<x を9回行ったものより明らかに大きい。
【50文字以下最大】

■ >>9
>>47で同じ数字を86文字で表現

■ >>21
>>28の３行目で同じ数字を53文字で表現している

■ >>22
>>102の方が明らかに大きい

■ >>28
>>56で同じ値を52文字で表現している
0114デフォルトの名無しさん2009/04/05(日) 23:09:06
■ >>32
>>102の方が明らかに大きい

■ >>35
>>102にまとめて記述
41文字以下のどの作品よりも明らかに大きい
【42文字以下現在最大】

■ >>39
これは99の階乗。
99の階乗 ＜ 99の99乗 ＜ 128の99乗 ＝ 2の693乗 ＜ 2の(9<<99)乗 ＜ 9<<(9<<99)

■ >>56
24文字
>>102にまとめて記述
【24文字以下現在最大】

52文字
初期値 i=9e99 に対して、i<<=i を 9e99+1 回行っている。
>>2 の50文字の作品よりも明らかに大きい
【52文字以下現在最大】

■ >>57
>>102にまとめて記述
【23文字以下現在最大】
0115デフォルトの名無しさん2009/04/05(日) 23:10:14
■ >>75
>>77 で同じ値を118文字で表現している

>>77 の k(x,y,1) も xのy乗となる為、
『 >>75 の k(x,y,n) 』＝ 『 >>77 の k(x,y,n) 』
>>75 の G(w) は 初期値 z=4 に対し z=k(3,3,z) をw回繰り返したものであり、
>>75 と >>77 の118文字は同じ値を返す。

■ >>88
>>102にまとめて記述
【21文字以下現在最大】

■ >>91
96の43文字の方が明らかに大きい

■ >>96
返る値は
9<<(9<<(9<<(9<<(9<<(9<<(9<<(9<<(9<<9))))))))
であり、
42文字以下の >>102 のいずれよりも明らかに大きい
【43文字以下現在最大】

■ >>101
>>102の29文字の方が明らかに大きい
0116デフォルトの名無しさん2009/04/05(日) 23:11:24
>>47,61,77,83,90 の比較はちょっと長いので後ほど。
0117デフォルトの名無しさん2009/04/05(日) 23:12:06
>>110
そんな感じです。
0118デフォルトの名無しさん2009/04/05(日) 23:18:54
Conwayのチェーン表記を書いてみた
ttp://en.wikipedia.org/wiki/Conway_chained_arrow_notation

int p(int x,int y){return y?x*p(x,y-1):1;}
int e(int*a,int n){
if(n==1)return a[0];
if(n==2)return p(a[1],a[0]);
if(a[0]==1)return e(a+1,n-1);
if(a[1]==1)return e(a+2,n-2);
int x,y;
a[0]--;x=a[1]--;a[1]=e(a,n);y=e(a,n);a[0]++;a[1]=x;return y;}
int main(){int a[]={9,9,9,9,9,9,9,9,9};return e(a,9);}
0119デフォルトの名無しさん2009/04/05(日) 23:58:31
無限にintは大きいんだろ？？
int main(){return (unsigned)~0;}
012012009/04/06(月) 00:00:26
>>113-115の続き

>>61 の883文字は、
int A(int y, int z){y?z?a(y-1,a(y-1,a(y,z-1)):9:9<<z;}
とすると、
A(1,z) = a(z)
A(2,z) = b(z)
A(3,z) = c(z)
...
A(25,z) = y(z)
となります。

>>77 の118文字は、
int k(int x,int y,int n){return n?y?k(x,k(x,y-1,n),n-1):1:x*y;}
これのxを3に固定し、yとnを入れ替えると
int K(int n,int y){return y?n?k(n-1,k(n,y-1)):1:3*n;}
となります。

>>90 の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;
}
これのbを0に固定すると、
int A(int c,int d){return c&&d?a(c-1,a(c,d-1)):d+9;}
となります。
012112009/04/06(月) 00:02:01
それぞれの再帰関数を並べると以下のようになって、
いずれかの引数が0の場合の定義のみ異なり、
どちらも0でない場合の定義はまったく同じであることが分かります。

47-86,77-113
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):a(m-1,1):n+1;}

47-80
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}

61-883
int A(int y, int z){y?z?a(y-1,a(y-1,a(y,z-1)):9:9<<z;}

77-118
int K(int n,int y){return y?n?k(n-1,k(n,y-1)):1:3*n;}

83-77, 83-103
int a(int b,int c){return b*c?a(b-1,a(b,c-1)):c+9;}

90-100
int A(int c,int d){return c&&d?a(c-1,a(c,d-1)):d+9;}
012212009/04/06(月) 00:03:39
左の引数が0の時の定義は、
47-86 の n+1 と 61-883 の 9<<z で大きく異なるようにみえるが、
実は左の引数を数個増やすだけでこの程度の差は吸収してしまう。

たとえば、
47-86 の場合、
a(0,n) = n+1
a(1,n) = n+2
a(2,n) = n*2+3
a(3,n) = 2の(n+3)乗 -3
となる。

同様に、右の引数が0の時の定義も、
右の引数を数個増やすだけで吸収してしまう。

つまり、>>121 の関数は、引数を数個変えると追いつく程度の差しかなく、
左の引数が9と99では、初期値が上のいずれであっても
左の引数が99である方が大きくなる。
012312009/04/06(月) 00:06:29
90-100 を見てみる。

a(1,0,d) ≧ a(0,d,d) であり、
a(1,1,d) は、初期値x=9 に対し、x=a(1,0,x) を d 回行ったものである。
つまり、
a(1,1,d) は、初期値x=9 に対し、x=A(x,x) を d回行ったものより大きいので、
a(1,1,64) で、77-118 とだいたい同じ数となって、
a(1,1,99) で、77-113 や 83-103 とだいたい同じ数となる。

a(1,2,2) = a(1,1,a(1,1,a(1,2,0))) = a(1,1,a(1,1,9)) ＞＞ a(1,1,999)
であるので、
それより大きい a(1,9,9) は 77-118,77-113,83-103 より大きい。
012412009/04/06(月) 00:07:39
■ >>47
86文字
同じレスの80文字の方が大きい

80文字
【80文字以下現在最大】

■ >>61
>>47 の80文字の方が大きい

■ >>77
118文字、113文字とも >>90 の100文字に負けている

■ >>83
77文字
【77文字以下現在最大】

103文字 >>90 の100文字に負けてる

■ >>90
100文字
【100文字以下現在最大】
012512009/04/06(月) 00:11:38
現在の記録をまとめると、

42文字以下
>>102

int a=9;int main(){return a--?9<<main():9;} // 43文字
int main(){int n=99,m=n;while(m--)n<<=n;return n;} // 50文字
int main(){int i=9e99,f=i;while(f--)i<<=i;return i;} // 52文字

// 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 m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}
int main(){return a(99,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);}

※ >>118 はこれから評価します。
0126デフォルトの名無しさん2009/04/06(月) 16:09:42
int main(){ unsigned int i=-1; return (i>>1)-1;}//48文字
環境依存かなぁ。
0127デフォルトの名無しさん2009/04/06(月) 18:55:22
>>118
このままだとあまり大きくなく、
>>125 の80文字 のより小さい。

× a[0]--;x=a[1]--;a[1]=e(a,n);y=e(a,n);a[0]++;a[1]=x;return y;}
○ x=a[1]--;a[1]=e(a,n);a[0]--;y=e(a,n);a[0]++;a[1]=x;return y;}

このように直すと今のところ最大。(290文字)

※この数が290文字で記述できるとは思わなかった
0128デフォルトの名無しさん2009/04/07(火) 01:40:07
減速しちゃったねぇ。。。
0129デフォルトの名無しさん2009/04/07(火) 19:25:18
>>126ってどうなの？？
0130デフォルトの名無しさん2009/04/07(火) 22:42:14
>>126
>>2 のダメな例の２個目と同じ発想。
int のサイズや負の数の表現方法に依存する。
激しく既出なルール違反。

ちなみに、
負の数に１の補数表現や２の補数表現を使った処理系の多くは 『{2の(intのビット数-1)乗} -2』 が返り、
負の数に符号ビット＋絶対値を使った処理系の多くは 『2の(intのビット数-2)乗』 が返る。
トラップ表現のある実装の場合はトラップ表現が返る場合もあるかも知れないし、
飽和演算の処理系では 0 が返ることがあるかも知れない。
C++の規格上は不定である。
0131デフォルトの名無しさん2009/04/07(火) 23:02:49
>>118の修正版をがんばって縮めてみました。

// 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);}
0132デフォルトの名無しさん2009/04/07(火) 23:12:39
>>130
書いてあったのね。これは不覚。。。
あと負の表現については勉強になった。色々あるんだね。
0133デフォルトの名無しさん2009/04/07(火) 23:44:45
>>132
負の数の表現とか、わりとどうでもいいことを書いちゃったけど、
要はこのスレの目的は、
「int の最大値を返すプログラムを作るスレ」じゃなくて、
「C++という言語を使って、出来るだけ短く出来るだけ大きな数を定義するスレ」
なのでよろしく。

>>102 のような表を作っていくのが目的です。
0134デフォルトの名無しさん2009/04/07(火) 23:54:34
りょーかい！
0135デフォルトの名無しさん2009/04/08(水) 00:02:47
クラス、テンプレートもありだよね？
つってもそれを生かすアイディアが無いけど。
0136デフォルトの名無しさん2009/04/08(水) 00:30:43
俺にはこれが限界。100字くらい。何文字かは削れそうだが。。。

int r(int v,int N){
if(N==0) return v<<9;
return r(v<<9,N-1)*r(v<<9,N-1);
}

int main(){
return r(9,9);
}
0137デフォルトの名無しさん2009/04/08(水) 00:31:56
>>135
もちろんありです。

構造体の struct は class より１文字多いですが、
public: の記述が不要なので、
クラスよりも使えるかもしれません。

new もメモリ確保するには必須ですが、
メモリは無尽蔵にあるので
delete は使う機会が無いかもしれません。
0138デフォルトの名無しさん2009/04/08(水) 01:00:42
>>136
r(9,9) ＝ (2の46080乗) * (3の1024乗) ≒ 1.08234329*10^14360

だから、

int main(){return 9e99999;} // 27文字

の方が大きいかも。
0139デフォルトの名無しさん2009/04/08(水) 01:21:04
>>138
ハードル高いね。
浮動少数リテラルが強すぎる。。。難しいなぁ。
0140デフォルトの名無しさん2009/04/13(月) 14:24:18
http://uproda.2ch-library.com/lib118897.zip.shtml

スレの発展には関係なくて申し訳ないのですが、やたらと大きな整数とか
を計算できる電卓を作ってみました（win32 console アプリケーション）
もし良ければ使ってみてください
２＾１０００　とか １０００！　みたいなのが問題なく計算できます
0141デフォルトの名無しさん2009/04/13(月) 17:14:18
>>140
ヘルプがないからコマンドがわからんなぁ。-hで反応しないし。
0142デフォルトの名無しさん2009/04/13(月) 17:20:15
>>141
ヘルプついてなくて大変もうしわけありません。

優先順位が同じになる二項演算を（）でくくっていただければ、
整数と実数の加減乗除とか初等関数を使った普通に書いた数式を
受け付けるはずで

リターンしていただければ普通に値を計算するはずなのです・・
要は関数電卓もどきかと
0143デフォルトの名無しさん2009/04/13(月) 17:44:39
>>142
あぁ〜！俺勘違いしてたよ。
コマンドラインツールだと思って引数で計算させようとしてた。何か無限ループしてるみたいになったような？？
0144デフォルトの名無しさん2009/04/13(月) 20:05:51
>>140
バグ報告

演算子の計算の順番がおかしい
a/b/c = a/(b/c)
a-b-c = a-(b-c)
となっている

2/3のような1未満になる分数を含んだ結果がおかしい
1+2/3 が D9 と表示される

質問
型は整数型と有理数型と小数型の３種類ですか？
sin や cos や exp はどのように計算してますか？
割り算やルートはどのように計算してますか？
0145デフォルトの名無しさん2009/04/13(月) 20:11:03
とりあえずつ　Scheme
0146デフォルトの名無しさん2009/04/13(月) 20:18:09
いやいや つ bc
0147デフォルトの名無しさん2009/04/13(月) 20:27:43
これのことか！
ttp://www.moris-shop.net/item/18921.html
0148デフォルトの名無しさん2009/04/13(月) 20:44:35
おまいら、大きい数を考えろや。
0149デフォルトの名無しさん2009/04/13(月) 22:14:11
#include <math.h>
int main()
{
return pow(9,pow(9,pow(9,pow(9,(pow(9,9))))));
}

文字数がある程度増えてくれば指数表現よりもこちらの方が大きい
ような気がしますがどうでしょうか？

ということで、>>144　さん　バグ報告をありがとうございました
スレ違いなので、改定版はどこかにまた出しますが今回だけお返事を

>>演算子の計算の順番がおかしい
式表現のＢＮＦの書き方がまずかったようです parser に手を入れます
>>1+2/3 が D9 と表示される
単純なバグでした（他にも負数負数の計算後の表示が変でした）手元では直しました

>>型は整数型と有理数型と小数型の３種類ですか？
整数型と有理数型で最後の表現のときに小数表示に直しています
sin や cos や exp はどのように計算してますか？
>> exp log sin cos asin, atan はテーラー展開で計算して
pai, tan, acos はそれらを使っての計算です
>>割り算やルートはどのように計算してますか？
割り算はそのまま、ルートは　a^2 = x -> a = (x/a + a)/2
の関係式を使って計算しています
0150デフォルトの名無しさん2009/04/13(月) 22:28:28
>>149 >>1 を見たらライブラリは使用不可でした。
前のレスは無効ということでお忘れください。大変失礼しました
0151デフォルトの名無しさん2009/04/13(月) 23:13:33
適当なクラス作ってoperator*でも定義したらいいじゃないか
0152デフォルトの名無しさん2009/04/14(火) 08:49:27
int n=99,m=n;
int main()
{
return m--?n<<=main():n;
}

何の意義もないけど、一文字縮むような感じ？　４９文字
0153デフォルトの名無しさん2009/04/14(火) 09:11:39
>>152
n<<=main()が不定。
main()を先に評価するかnを先に評価するかで結果が変わる
0154デフォルトの名無しさん2009/04/14(火) 22:31:16
まあいずれにしろ、
43文字で再帰コールでシフトをしてる作品があるからね。
これの再帰回数を単純に増やせばある程度は大きくなる。

下の45文字ので >>125 の50文字を超え、
下の47文字ので >>125 の52文字を超えるはず。

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文字

でも77文字まではずいぶんと文字数があるから、
それまでには上のような単純にaの値を増やす以外の別の方法で
もっと効率よく大きな数を作る方法があると思う。
0155デフォルトの名無しさん2009/04/14(火) 23:18:57
int main(){return (int)tan(1e-9999999);}
0156デフォルトの名無しさん2009/04/14(火) 23:56:02
tanは反則だし、tan(1/x)っておもったほど大きくならなかった希ガス。
0157デフォルトの名無しさん2009/04/15(水) 00:03:34
あれ、なんか変だな。
大きくなるのはtan(π/2(1-1/x))だっけ？
でも、この式もあんまり増加率高くなかったはず。
0158デフォルトの名無しさん2009/04/15(水) 04:01:25
寝ようとしてたのに眠れん。
で、閃いた。これ究極じゃね？
23文字位。

int main(){
return 1/0;
}

確か±無限だよね。いっちばーん。
0159デフォルトの名無しさん2009/04/15(水) 06:57:19
>>158
つまり、-∞でいちばん小さいんですね。
0160デフォルトの名無しさん2009/04/15(水) 07:35:26
>>158
マジレスするとゼロ除算で動作未定義。
>>2 のダメな例４個目の整数版。
0161デフォルトの名無しさん2009/04/15(水) 07:48:27
>>155
tan(1e-9999999) ≒ 1e-9999999 だから
戻り値0

>>157
tan(π/2-x) = 1/tan(x)
だから、
xが大きい時は、
tan(π/2(1-1/x)) = 1/tan(π/(2x)) ≒ 2x/π
0162デフォルトの名無しさん2009/04/15(水) 10:07:41
アホみたいな感想で悪いんだけど、defineありなら、
#define A 9e9999999
int main(){return A^A^A^A^A^A;}
みたいなのがAの定義とmain内の個数で調整すると、最終的に大きくなんないかな？
01631582009/04/15(水) 15:35:29
>>160
げ、書いてあったか。
一通り流し見したと思ったが。。。
浅はかでした。Orz
0164デフォルトの名無しさん2009/04/15(水) 19:03:40
>>162
たぶん短くなるとは思うけど、
一応ルール上はプリプロセッサ使用不可なので #define や #include などは禁止です。

typedef は使えるので、
長いプログラムではintやfloatやboolを1文字にtypedefすれば短くなるかも。
0165デフォルトの名無しさん2009/04/15(水) 19:18:18
>>162
float a = 9e999999;でいいだろう。
0166デフォルトの名無しさん2009/04/15(水) 23:17:45
値の定義だけならそれでも良いけど、
#define だともっといろんなことが出来る。

#define A(x) (x<<x)
#define B(x) for(int i=0;i<x;i++){
#define C(x) struct x{
#define D(x) return x;}
#define E(x) (*x)->f()

固定辞書の圧縮みたいな感じ。
0167デフォルトの名無しさん2009/04/16(木) 05:32:09
携帯から。警告でるだろうけど。
int a=9e9;class A{public:int b;A operator*(A c){for(b=a;b--;)a<<=a;return c;}};
int main(){******************************************************A();return a;}
0168デフォルトの名無しさん2009/04/16(木) 06:15:25
よく考えたらa=9e9をa=9にして*を2つ増やした方が大きかった
0169デフォルトの名無しさん2009/04/16(木) 06:54:16
コンパイル通らない
0170デフォルトの名無しさん2009/04/16(木) 07:09:01
これなら通るみたい。

int a=9e9;class A{public:int b;A operator*(){for(b=a;b--;)a<<=a;return *this;}};
int main(){******************************************************A();return a;}
0171デフォルトの名無しさん2009/04/16(木) 07:24:29
まぁコンパイル通しても無駄だらけで割とどうでもいい。
class{public:をstructに置きかえれる。
int b;int a=9e9,b;にしたほうが短い。

致命的なのは
**..**A()はfor(int i=99;i--;)*A();のほうが短い。
ここまでいくと*A()とか書く暇があったら処理の中身をinlineしたほうが短い。
結論としてはclassいらない
0172デフォルトの名無しさん2009/04/16(木) 07:48:51
無駄は多いけど、戻る値は大きいよ。

ループにして縮めてみた。
たぶん同じ値が返る。

int main(){
    int a=9e9,b,c=54;
    for(;c--;)
        for(b=a;b--;)
            a<<=a;
    return a;
}

もちろんこうした方が大きい。
    int a=9e9,b,c=a;
0173デフォルトの名無しさん2009/04/16(木) 07:52:21
int main(){int a=9e9,b,c=a;for(;c--;)for(b=a;b--;)a<<=a;return a;} // 66文字
0174デフォルトの名無しさん2009/04/16(木) 08:51:03
1重ループに圧縮してついでに大きくしてやった
int a=9e9,b,c=a;int main(){while(b?b--:b=a*c--)a<<=a;return a;}
63B
0175デフォルトの名無しさん2009/04/16(木) 12:57:22
いや皆さんのおっしゃる通りです勉強にたります。
懲りずにまた携帯からw
int a=9;int f(){for(int b=a;b--;)a<<=f(f(f(f(f()))));return a};int main(){retern a;}
0176デフォルトの名無しさん2009/04/16(木) 13:01:38
誤字がいっぱいありますね。すいません。
0177デフォルトの名無しさん2009/04/16(木) 13:08:07
あ-あ、これだと無限ループになるからだめですね;
0178デフォルトの名無しさん2009/04/16(木) 13:25:41
int a=9;int f(int b){if(!b)for(b=a;b--;)a<<=f(f(f(f(f(0)))));return a;}int main(){return f(a);}
これでループとまるかな。
0179デフォルトの名無しさん2009/04/16(木) 13:30:44
if(!b)はif(b)の間違い。b=aは不要でした。
0180デフォルトの名無しさん2009/04/16(木) 16:04:20
単純に172を関数にする方がいいことに気づいた。
int a=9e9;int f(int c){for(;c--;)for(b=a;b--;)a<<=a;return a;}int main(){return f(f(f(f(f(a)))));}
0181デフォルトの名無しさん2009/04/16(木) 20:36:13
三日前に登場した電卓男>>140 ですが、ご指摘のあったバグを一通り直した
ver 0.2 を作ってみました。今度は任意の小数点精度の計算が設定可能です

http://pc12.2ch.net/test/read.cgi/software/1238682994/

スレ違いなので、過疎ってるソフト板のスレにの方にリンクをはっおきました。
とりあえず一応努力してみたご報告ということで失礼いたしました
0182デフォルトの名無しさん2009/04/16(木) 21:15:27
やっとPC使える... 今までの中で最大のつもり。
int main(){enum{s=9e9};int a=s,b[s],*c=b+s;for(;c---b;)*c=a;for(c=b;c<b+s;){a<<=a;--*c;if(!*c){*c++=a;continue;}c=b;}return a;}//128文字
0183デフォルトの名無しさん2009/04/16(木) 23:09:09
enumとかまたトリッキーな技を持ってきたな。
0184デフォルトの名無しさん2009/04/17(金) 01:02:38
>>174
こんな技があったとは。
>>91 以来の衝撃。
3文字縮めた上に微妙に大きくなってる。

さらにループにして、同じ技を使って３重ループ相当を１重ループにしてみた。

int a=9,b,c,d=a;int main(){for(;b?b--:c?b=a*c--:c=a*d--;)a<<=a;return a;} // 73文字
0185デフォルトの名無しさん2009/04/17(金) 01:09:58
>>182
これは上のループを9e9重にした感じですか。
enum{s=9e9}; がうちの環境(VC 2005)だとエラーになってしまうのですが、
仮に s の所をそのまま9に置き換えたとしても９重ループ相当。
0186デフォルトの名無しさん2009/04/17(金) 01:17:03
enum{s=9e9};
はなんとなく暗黙の型変換が行われそうだけど、
C++の規格的にはどうなんだろう？
ダメなら const int s=9e9; だね。

9<<9e9 も VC2005 ではエラーになるけど、
もしかして規格的にはグレーだったりするのか？
0187デフォルトの名無しさん2009/04/17(金) 01:24:02
9e9で値が大きすぎるからエラーになる訳じゃなくて、
以下のように値が小さくてもVC2005だとエラーになる。

enum{s=1.0};
9<<1.0
0188デフォルトの名無しさん2009/04/17(金) 02:39:47
--*c;if(!*cはif(!--*cで、9e9は9<<9でどうか
0189デフォルトの名無しさん2009/04/17(金) 07:56:44
縮めてみた。微妙に大きくもなってるはず。
enum{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:34
さらに2文字縮まった。
enum{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
>>190
このままだと >>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
一応 >>193 を解説すると、

●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:57
番外編

int 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:49
195と混ぜてみた
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,9):*(z=y+9));return x;}
//135B
0199デフォルトの名無しさん2009/04/18(土) 12:43:43
>>196
そうですよ。

同じ数をより少ない文字で表現しているものがあったり、
同じ文字数以下でより大きな値を返すものがあれば
記録に掲載はされません。
同じ文字数、同じ大きさなら原則先に掲載された方としますが、
考え方が大きく異なるなら両方載せるかもしれません。

>>197
その手があったか。
現状80文字以下最大。
0200デフォルトの名無しさん2009/04/18(土) 13:02:28
>>198

残念ながら、
>>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:27
>>200 ダウト。かな。

9を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:15
>>192(>>195)
aへの代入が消えてるからグローバル変数の初期値に依存するってことで>>1を満たしてないことない？
0203デフォルトの名無しさん2009/04/19(日) 08:07:11
>>201
> たとえば>>200の式でA(3,3)を定義したとすると
> aと(と)と,の4つの記号と数字があれば表記できてしまう程度だろうけど、

>>201 のと同程度に表記不可能
（もし可能だと言うなら A(2,2) でも良いのでやってみてください）
A(n,x) でn重ループ相当ですよ


>>202
それは大丈夫。
初期値無しのグローバル変数は必ず0に初期化される。
0204デフォルトの名無しさん2009/04/19(日) 14:22:12
>>203
thx。やっと理解したw。A(n,x)はn重ループと本質的には変わらないのか。
なんだアッカーマン最強じゃないか。
02052042009/04/19(日) 14:54:11
>>203
アッカーマン最強なら、こんな感じでどうよ
// 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);}
02062042009/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
>>205 は大きいけど、
>>206 は77文字のと同じくらいじゃいか？
0208デフォルトの名無しさん2009/04/19(日) 21:57:59
>>207 77文字の関数のa(9,9)は、>>206の関数で表すとa(1,9,9)のつもりです。

でも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:44
誰かグッドスタイン数列ベースのやつも頼む
0211デフォルトの名無しさん2009/04/19(日) 22:36:35
for(;c*b--;)だった。88文字か。

グッドスタイン数列をググってみたけどちっちゃいな
0212デフォルトの名無しさん2009/04/19(日) 22:47:49
Ackに比べたらちっちゃいけど、1変数だから対角化したら結構でかくならんかな
文字数を考えるとAckを強化してったほうがでかいだろうけどね
0213デフォルトの名無しさん2009/04/20(月) 22:16:21
しかし>>47どうも納得いかないなあ。
上のほうは大きいけど、下の方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:26
>>213
9の(99の9乗)乗程度の小さな数だったら確実にA(5,3)よりは小さい
ここを見たらA(99,9)がどれだけとんでもないかわかると思う
ttp://en.wikipedia.org/wiki/Ackermann_function
0215デフォルトの名無しさん2009/04/21(火) 00:09:01
>>213 それではなく>>47の下の方の、偽アッカーマン関数の話です。

上の方は、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:38
自分にレスしてしまった; 上は>>214へのレスだす
0217デフォルトの名無しさん2009/04/21(火) 01:41:48
>>209
たぶんあまり大きくない。
少なくともこれよりは小さい。

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:14
>>213

int 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:56
int a(int m,int n){return m?n?a(m-1,a(m,n-1)):m:n*9;}

a(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
>>213 も >>209 と同じで、
少なくともこれよりは小さい。

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:17
>>194 の100文字を2文字縮められました。
int 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
>>217-220
わかりやすい説明ありがと。もう工夫する余地はないのか。
>>221
100文字以下になるとは思わなかった。すごい。
0223デフォルトの名無しさん2009/04/21(火) 18:55:52
>>193 の 43文字と77文字を合体
int 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:04
9^9^9ってC++的に一般的な書き方じゃないとおもうけど
9の9の9乗乗＝つまり右肩にどんどん小さく乗ってくやつのこと？
それとも9の9乗の9乗＝(9^9)^9のこと？
0225デフォルトの名無しさん2009/04/21(火) 20:49:39
xorに決まっておる。
0226デフォルトの名無しさん2009/04/21(火) 22:19:44
>>218 >>219 の ^ はべき乗の意味です。
pow(9,pow(9,pow(9,......pow(9,pow(9,9)))))...) (9がn個)

C++言語のスレなので、今後べき乗の意味で ^ は使わないようにします。
0227デフォルトの名無しさん2009/04/22(水) 07:44:42
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=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:23
int a=9,b,c=a;int main(){for(;b?b--:b=a*c--;)a<<=a;return a;} // 61
int 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:56
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int main(){return a(9);} // 77
int 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:39
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}int b=9;int main(){return a(b--?main():9);} // 96
int 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:17
tarai functionとその亜種はどうよ
0232デフォルトの名無しさん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
>>233
関数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;}

02352332009/04/28(火) 20:07:41
結構頑張ったのに既存のに負けてるのか。（´・ω・｀）
９８文字に負けてるってところを詳しく解説してホシス。
02362332009/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.
02372332009/04/29(水) 10:23:57
あーせっかくここまで考えたのに、
Ｃ言語だと関数と関数を合成して新しい関数を返す関数がかけねぇ？
関数ポインタを使えば何とかなるかなぁ…
02382332009/04/29(水) 10:43:35
Ｃ++にはテンプレートがあるぢゃまいか。ナイス！

template<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
>>238
コンパイル通るかそれ？
02402332009/04/29(水) 10:51:47
でだ。
要するに生の整数を比べずにループが何重になってるかってことを比べる、
というのをみんなやってたわけだが、loop_rankを厳密に定義しておけば議論がしやすいかなと。
02412332009/04/29(水) 10:54:14
g++では通った。
ほかはしらね。
0242デフォルトの名無しさん2009/04/29(水) 11:01:02
なんというか、大きい数を探すことよりも
「どれが大きいか」を判定することのほうがよっぽど難しいな
02432332009/04/29(水) 11:10:09
実際、２つのプログラムが与えられてどちらが大きい値を返すか判定する
なんてのは計算不能だろな。
与えられたプログラムが停止することが保障されてたとしても、
最終的な値を2進の整数に展開せずににメモリ使用量に制限かけて判定する
なんてことが可能なのかどうか…
02442332009/04/29(水) 11:27:13
さて、>>233のloop_rankがいくつか？というのを知りたいわけだが、
loop_rankじゃ結果が大きくなりすぎてだめだな。
もうすこし上の概念を導入しないと。

02452332009/04/29(水) 11:50:32
とりあえず、考察対象を>>238のfに限るとして、
f<n>とf<m>からf<n+m>を生み出すような操作ってどんなものになるだろう？

02462332009/04/29(水) 11:59:45
うん。あれだ。
今、自分が考えてるのが整数なのか関数なのかテンプレートなのか
わけが解らなくなってきたｗ
02472332009/04/29(水) 12:11:35
まあ、なんだ。とりあえず>>1さん、
>>233が>>230の98文字より小さいという根拠を聞かせてくれ。
02482332009/04/30(木) 20:41:57
>>1は優雅にバッカンスでもいったのか？
最底辺IT奴隷orひきニートたるべきム板民にあるまじきブルジョアっぷりだな。
まったくもってけしからん。
俺もGWあけたら奴隷生活に戻るんだからはやめに返事クレ。
02492332009/05/01(金) 20:39:27
>>230の98の大きさがよくわからんなぁ。
Aをアッカーマン関数とするとおおむね、
A(1,9,9)=A(A(9,9),A(9,9))
でいいんかな？
025012009/05/02(土) 16:16:35
>>236
クラスや構造体を使えば実装可能です。
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);
025112009/05/02(土) 16:25:48
>>244
loop_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;
  }
};
025312009/05/02(土) 16:39:45
function_successor は単に1を足すだけの簡単な関数。
function_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 の方が値が大きくなる。

025412009/05/02(土) 16:48:24
この時のaのloop_rankを記号ωとあらわすことにする。

>>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 を入れたものとなる。
025512009/05/02(土) 16:56:08
次に、98文字のものを考えてみる。

再帰定義をよく見てみると、
関数 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:35
>>252 の function_loop2 や、
99文字のbを1増やすのは
loop_rankをω増やす操作となる。

98文字のものは、99文字のものから1文字減らす為に、
bを0と1に制限したもの。
0257デフォルトの名無しさん2009/05/02(土) 17:09:06
>>252
function_loop2 が間違ってました。
こうですね。

virtual int operator()(int x){
  function*f=a;
  for(int i=x;i--;)
    f=new function_loop(f);
  return (*f)(x);
}
02582332009/05/04(月) 07:36:40
>>1
了解。
丁寧な解説ありがとう。
大きな関数を繰り返すことでさらに大きな関数を作る、そしてそれをまた繰り返して…
というのは>>1はもうやり尽くしていて結論が出ている。それを超えるには全く別の発想が必要になる。
ということでよろしいか？


025912009/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:46
あげ
0263デフォルトの名無しさん2009/07/06(月) 01:25:30
int main()
{
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:44
de bruijn sequence誰か実装して
B(2,5)=2048
B(2,6)=67108864
B(2,7)=144115188075855872
0266デフォルトの名無しさん2009/07/23(木) 21:55:04
>>265
定義が良くわからないけど、
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:35
あげ
0268デフォルトの名無しさん2009/08/22(土) 08:27:25
いまさらだがどれだけ長い文字列を印字できるかの方が
へんなＣ＋＋の整数型もどきを使わずに済んでルールが簡明になったな
0269デフォルトの名無しさん2009/08/28(金) 00:45:33
>>268
長い文字列を印字する為に、事実上無制限の状態数が必要。
事実上無制限の状態数を表す為に、事実上無制限のメモリが必要。
事実上無制限のメモリを実装する為に、事実上無制限のポインタサイズが必要。

ということで、
どうせポインタサイズが事実上無制限なら
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:27
いっそのことBFでステップ数を競うのもありかもね。
http://pc12.2ch.net/test/read.cgi/tech/1231384158/
0272デフォルトの名無しさん2009/09/24(木) 02:19:57
#include <iostream>
main(){for(;;)std::cout<<"9";}
0273デフォルトの名無しさん2009/09/25(金) 20:41:53
>>272
>>2 のダメな例 8個目
0274デフォルトの名無しさん2009/09/26(土) 02:50:03
#include <limits>
int main(){return numeric_limits<int>::max();}

//63文字
0275デフォルトの名無しさん2009/09/26(土) 09:27:16
>>274
多くの場合 >>2 の2個目と同じ値が返る
0276デフォルトの名無しさん2009/09/26(土) 13:27:03
>>40
int main(){int a=1,b=0;for(;a>b;a++,b++);return b;}

こうすれば無限にならないのでは?
0277デフォルトの名無しさん2009/09/26(土) 19:15:26
>>275
だから何？
0278デフォルトの名無しさん2009/09/26(土) 23:02:05
>>276
無限にならなくても環境依存なのでルール違反。

>>277
int の最大値は環境依存なのでルール違反。
0279デフォルトの名無しさん2009/09/26(土) 23:04:53
>>278
>int の最大値は環境依存なのでルール違反。

はぁ？
intの最大値は環境依存だが、>>274のコードは環境依存ではない。
0280デフォルトの名無しさん2009/09/27(日) 02:56:37
>>279
それはないだろ
規約上はオーバーフローした場合の挙動は未定義なんだから
aがオーバーフローしたとき0にするのではなく
非数字やエラーとして扱う処理系を作っても一向にかまわない
a>bが真になったり、システム自体がダウンすることもありうる
結局オーバーフロー依存は環境依存だから禁止なの
0281デフォルトの名無しさん2009/09/27(日) 02:59:49
ごめん。上のは>>276へのレスね。
>>279の方はよくわかんね
0282デフォルトの名無しさん2009/09/27(日) 03:09:01
ってこのスレそもそもインクルード禁止じゃねーかw
なにが、はぁ？だよ
0283デフォルトの名無しさん2009/09/27(日) 03:16:30
int main(){return 32767;}

//25文字
//環境依存がダメなら、intが32768以上の値をとることを期待するのは機種依存だからダメ。
0284デフォルトの名無しさん2009/09/27(日) 07:30:06
>>279
環境によって main が返す値が変わるのだから環境依存。

>>283
「int と float は十分な精度があるとします」
このスレのルールです
意味は >>30-31
0285デフォルトの名無しさん2009/09/27(日) 11:57:39
int f(x){return x?f(9<<f(x-1)):9;}
int main(){return f(9);}

//59文字
0286デフォルトの名無しさん2009/09/27(日) 11:58:37
int f(int x){return x?f(9<<f(x-1)):9;}
int main(){return f(9);}

//63文字
0287デフォルトの名無しさん2009/09/27(日) 14:50:34
int h(int f,int a){return f?a?h(f-1,h(f,a-1)):h(f-1,a):a+9;}
int main(){return h(9);}

//85文字
//結局アッカーマン
0288デフォルトの名無しさん2009/09/27(日) 16:03:36
int h(int f,int a){return f?a?h(f-1,h(f,a-1)):h(f-1,a):a+9;}
int main(){return h(9,9);}

//87文字
//結局アッカーマン

// >>285, >>287 取り消し
0289デフォルトの名無しさん2009/09/27(日) 18:38:14
int h(int f,int a){return f?a?h(f-1,h(f,a-1)):h(f-1,9):a+9;}
int main(){return h(9,9);}

//87文字
//結局アッカーマン

// >>288 取り消し
0290デフォルトの名無しさん2009/09/27(日) 23:49:12
>>285 >>286
main関数だけで再帰呼び出すを行うというスゴイ技を
>>91 さんが見せてくれました。
それを微妙に修正したのが >>96 の 43文字の作品。
>>286 とまったく同じ値となります。

>>289
アッカーマン（相当の）関数は >>9 さんが始めに書いていて、
>>83 で 77文字まで縮まっています。

現状の記録は >>227-230 にあります。
詳しそうなので、ぜひ記録更新に挑戦してみてください。
1レス内文字数無制限での記録もお待ちしております。
0291デフォルトの名無しさん2009/09/28(月) 00:08:24
やはり基本はアッカーマンなんだね。もう少し考えてみる。
0292デフォルトの名無しさん2009/09/28(月) 01:09:31
int main()[int r;for(unsigned i=1;i;i++)r=r<(int)i?i:r;return r;]

未定義動作はないぞ。(unsignedな型の計算はオーバーフローにはならないと書いてある)
0293デフォルトの名無しさん2009/09/28(月) 01:10:39
bracketはbraceの間違い…ｽﾏｿ
0294デフォルトの名無しさん2009/09/28(月) 16:01:09
プログラムを書くプログラムで大きな数できない？
0295デフォルトの名無しさん2009/09/28(月) 16:19:42
ライブラリ関数を使えないから事実上無理だね。
0296デフォルトの名無しさん2009/09/28(月) 21:23:04
>>292
r が初回不定
i を int にキャストした時点でオーバーフローする
環境依存な値が返る

上２個が解決したとしても
環境依存な値が返るのはこの方法では不可避

ところで、
このスレのルールを守って
（int が十分な精度という条件を除いて）
確実にintの最大値を返すものはいままで上がって無かったと思うけど、
出来るのかな？

>>294 >>295
簡単なインタープリタなら１レスで作れるかも。
でも大きな数を返すプログラムをプログラムで作れるかどうか。
0297デフォルトの名無しさん2009/09/29(火) 01:03:47
おっと。indeterminentの解釈がおかしかった。int r;はmain()の外でないとだめですね。
unsignedからintへのキャストで元の値がintで表現できない場合の変換後の値はimplementation definedですがそれはオーバーフローではないのでは?

環境依存なのはその通り。
0298デフォルトの名無しさん2009/09/29(火) 01:09:38
ビット数の決まってる unsigned の 0 から 1 引いて ffff... にするのは環境依存じゃなくね？
0299デフォルトの名無しさん2009/09/29(火) 01:12:00
整数の内部表現は環境依存
0300デフォルトの名無しさん2009/09/29(火) 01:20:38
-1U が unsigned の最大値なのはその通りだけどね。(ffff....とは限らないが)
0301デフォルトの名無しさん2009/09/29(火) 01:23:26
int main(){return (~(unsigned int)0)>>1;}

もダメってこと？
論理演算は全部禁止？
0302デフォルトの名無しさん2009/09/29(火) 01:25:09
最上位ビットが符号っていつ決まったの？
0303デフォルトの名無しさん2009/09/29(火) 01:29:51
じゃあ論理演算それ自体は使っていいのね？
シフト使ってる例は沢山あるし。
0304デフォルトの名無しさん2009/09/29(火) 01:34:31
ttp://xy.yu.to/
寂しい人向け
混む時間帯は人気ありすぎて定員オーバーで入れん

24時間荒れ放題の超カオスな絵チャット
本当の本当に完全無法地帯の絵チャット
（２ちゃんとは比較にならない）

荒しとプログラマーと防衛プログラマーの攻防戦
防衛側が強し、求む強力荒しプログラマー
しかも外国サーバー（イギリス）で管理人は荒し容認
殺人予告すらOKっぽい。ログなんて当然取ってないし
0305デフォルトの名無しさん2009/09/29(火) 01:44:12
左右シフトも補数も論理演算も全部使用禁止だろ。
内部での二進表現に依存してるから。
0306デフォルトの名無しさん2009/09/29(火) 02:41:33
過去ログを読むってこともできんのか？この無能ども
0307デフォルトの名無しさん2009/09/29(火) 13:41:51
オーバーフローがない限りa<<bがa*(2のb乗)に等しいってことは規格で決まってるよ
0308デフォルトの名無しさん2009/09/29(火) 22:28:14
>>307
bが負なら動作不定
bが非負でaが負なら結果は環境依存
a, b とも非負なら >>307 の通り
0309デフォルトの名無しさん2009/09/29(火) 23:36:22
>>297
ごめんなさい。その通りでした。

----
外部参照無しに、（インクルード、ライブラリ、外部入力など）
確実にintの最大値を返すC++のプログラムは存在しない
という証明が私の中では出来たつもり。

●証明
２つの環境ＡとＢがあって、
int の内部表現や動作は下記「異なる点」を除いて全く同じであるとする。
この時、環境ＡとＢではintの最大値は異なるが、
環境ＡとＢで動作の異なるプログラムを作ることは出来ない。
よって、ＡとＢ両方の環境でintの最大値を返すプログラムは存在しない。

----異なる点----
環境Ａのintの最大値はaであり、
環境Ｂのintの最大値はa-1である。
環境Ｂでは環境Ａのaと同じ内部表現でNaNを表すが、
NaNの場合の動作は環境Ａのaの時と全く同じである。
（つまり、動作は全く同じで意味付けのみ異なる）

..................................................................................................■
0310デフォルトの名無しさん2009/09/29(火) 23:41:48
全く証明になっていない件について
0311デフォルトの名無しさん2009/09/29(火) 23:50:29
>>309
「動作」とか「意味付け」とか俺用語が多すぎて意味不明
0312デフォルトの名無しさん2009/09/30(水) 05:09:29
>309
implementation-defined valueはunspecified valueのうち処理系がドキュメントすべきもので、
unspecified valueはtrap representationにならないとC++03が参照するC99に書いてあるのですが。
0313デフォルトの名無しさん2009/09/30(水) 12:59:53
template<int N>
struct 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
>>312
たしかにそう書いてありますね。
（範囲外の値から型変換してトラップ表現にならないのならトラップ表現の意味が無い気がする）

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:35
>>314 これはひどいｗｗｗｗｗ
0317デフォルトの名無しさん2009/10/01(木) 00:41:54
>>315
>>316
過去ログ嫁。
0318デフォルトの名無しさん2009/10/01(木) 00:44:48
>>317
？
>>314の酷さに過去ログ関係ないだろ
0319デフォルトの名無しさん2009/10/01(木) 01:02:18
>>318
何がどう酷いのかさっぱり。
やっぱり過去ログを読んだ方が良い気がする。
0320デフォルトの名無しさん2009/10/02(金) 04:21:43
intの最大値は一時は求まらないことが証明されたりもしたけど>313-314で出来ることになったが、最小値は何も思いつかんな…
0321デフォルトの名無しさん2009/10/02(金) 22:40:05
>>320
(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:59
嘘つくな。バカ。
0323デフォルトの名無しさん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
>2の補数表現 1000...000 はトラップ表現

？？？？
0325デフォルトの名無しさん2009/10/07(水) 00:33:35
int main(){
  for (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
>>325
あえて断言しよう。
それは無限ループであると。
0327デフォルトの名無しさん2009/11/05(木) 06:02:25
int main(){int n=9,i=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;while(i--){n<<=n;}return n;}
94文字
0328デフォルトの名無しさん2009/11/05(木) 22:41:53
>>327
2↑↑22300745198530623141535718272648361505980418
よりちょっと小さいくらい。
（↑↑ はパワータワー（テトレーション）の記号）

int a=9e99;int main(){return a--?9<<main():9;} // 46文字
こっちのが大きくて、
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
よりちょっと小さいくらい。
0329デフォルトの名無しさん2009/11/06(金) 02:51:29
int main(){int n=9,i=9e99;while(i--){n=pow(n,n);}return n;}
59文字
0330デフォルトの名無しさん2009/11/06(金) 03:08:25
int main(){int n=9,i=9e99;for(;i--;n=pow(n,n));return n;}
57文字にしとく
0331デフォルトの名無しさん2009/11/06(金) 21:21:41
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
よりちょっと大きくて
2↑↑9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
よりは小さい。

ちなみに、標準ライブラリなどの外部ライブラリや
外部ファイルのインクルードは禁止ですので、
powを使う場合はその定義も文字数に含めてください。

int pow(int a,int b){return b?a*pow(a,b-1):1;}
03322332009/12/19(土) 11:29:44
1のレスをよんですっかり理解した気になってたけど、いまふっと見返したらやっぱりちょっと理解が足りないっぽいので
１のレスを参考に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();}
}

03332332009/12/19(土) 16:54:39
すんません。mainでreturnすんのわすれてた。後、IntegerGrowをObjectGrowに統合した。大きさはω＋ωくらいなんだろか？
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;
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:58
>>333
Loop :: 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();
}

こうじゃないかと。
03363332009/12/19(土) 22:41:45
あ、ほんとだ。
おっしゃるとおり、>>335が正しいです。
ありがとうございます。
0337デフォルトの名無しさん2009/12/19(土) 23:12:05
複雑なチェーン構造がいまいち生かされてないような...
o のチェーンの長さより 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;
}
03383332009/12/19(土) 23:37:33
個人的に再帰でかかれるとメモリの大きさとかが見えにくいので
メモリの大きさが実感しやすい形にしました。
03393332009/12/19(土) 23:41:15
だいたい、再帰変数１つがチェーン一本に相当するってことですかね。

0340デフォルトの名無しさん2009/12/19(土) 23:59:34
>>339
>>337 のメモリの大きさが見えにくく、
>>333 のメモリの大きさが見えにくく無い
というのが良く分からない。

どちらもとてつもなくたくさんのメモリを使うし、
使うメモリの量を調べることは、
ほとんど main() の戻り値を調べることに等しい。

というか、
チェーンが１個伸びることで、
f の再帰を意図的に１回増やすように作った訳では無いの？
loop->f() のコール前後で loop のチェーンの長さは不変なので、
f() の再帰数は loop のチェーンの長さになることは簡単にわかるのだけど。
03413332009/12/20(日) 00:08:54
あくまで個人的な感覚なんですが、スタックに積まれたメモリというのは普段あまり意識しないので、
なんだか無い物のように感じてしまいます。
リストの形にすると実体が実感しやすいという、その程度のことです。
この場合、どちらも本質的に同じものであることは一応理解できます。

0342デフォルトの名無しさん2009/12/20(日) 08:40:36
肝心の大きさですが、
>>333 に >>335 の修正を加えると、
>>233 よりはずいぶんと大きくなって、

>>233 の、n重ループ相当の巨大化操作をn回繰り返して出来た関数を
さらにループさせた感じでしょうか。
03433332009/12/21(月) 22:05:46
ん？もしかして私の返事をまっている？
03443332009/12/22(火) 21:32:37
とりあえず、>>1さんはこちらの間違いを指摘するほど>>333のコードを理解していらっしゃるので、
>>335の修正を入れたプログラムがアッカーマン換算でどれくらいの大きさか教えてくらさい。

0345デフォルトの名無しさん2009/12/22(火) 23:10:26
>>230 の100文字のよりはずっと大きい。
この中に出てくる３変数アッカーマンもどきを
ループで回したくらいで,
下のより微妙に小さい位ではないかと。
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 が１個増えるのが大体同じ位の効果。
03463332009/12/23(水) 09:05:08
うーん。なんだかいまいち納得できない。
簡単なところから確認していっていいですか。
テーマはループと再帰、定数と自己複製ってところで。


0347デフォルトの名無しさん2009/12/23(水) 09:09:21
まずループと再帰ですが、次の記述が等価ですよね。

void f(int a) { if(a) { g() ; f(a-1) ; }}
void f(int a) { while(a--) g() ; }
0348デフォルトの名無しさん2009/12/23(水) 09:15:48
+1を使って足し算を書いてみるとこんなかんじ。

int 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
あーそうか。すんません。
勢いで書き始めちゃったけど、ちょっとまとめなおします。
しばしおまちを。
03503332009/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
>>350
(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) よりは小さい。
03523332009/12/24(木) 20:26:36
うー。
普通の数式ならごりごりっと展開していけば何とかなることが多いんですが、
３変数アッカーマンを展開しようとするとえらいことにｗ
なかなか手強いっす。
0353デフォルトの名無しさん2009/12/24(木) 21:20:00
>>352
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;}

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
a(b,c,x) は c が大きくなると、非常に増大度の大きな関数になる。

では次に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) を固定回ループさせて作った関数よりも増大度が大きい。
0355デフォルトの名無しさん2009/12/24(木) 21:44:56
３つ目の式は
a(B,0,D) = a(b-1,d,1)
や
a(B,0,D) = a(b-1,d,d)
で十分なのだが、
４つ目の式となるべく共通化した方が文字数が減らせるので
a(B,0,D) = a(b-1,d,a(b,0,d-1))
となっている。
03563332009/12/25(金) 22:28:18
ふーむ。だんだんわかってきたような。
4変数はこれで良いですか？
A(0,0,0,d)=d+9
A(a,b,c,0)=A(a,b,c-1,1)
A(a,b,0,d)=A(a,b-1,d,d)
A(a,0,0,d)=A(a-1,d,d,d)
A(a,b,c,d)=A(a,b,c-1,A(a,b,c,d-1))
0357デフォルトの名無しさん2009/12/26(土) 08:57:32
>>356
良いと思います。
03583332009/12/27(日) 00:20:39
なるほど。
ありがとうです。
>>353の展開の仕方がわかりやすかったです。
きれいな構造ですね。

a(b,x,y)=f(x,y)とおいてf(N,1)を展開すると
f(N,1)=f(N-1,f(N-2,f(N-3,f(N-4,...f(0,1)))...)
となるようでこれもまたきれいな構造です。

この構造をどう解釈すればいいのかはよくわからないですが…
03593332010/01/14(木) 20:08:38
int a=9e99;
int *dup(int *x){
      int *p,*q;
      p=x;while(*p++!=-1);
      q=new int[p-x];p=q;while(*x!=-1)*p++=*x++;*p=*x;
      return q;
}
void f(int *x){
      int *y;
      a<<=a<<a;
      if(*x==0){
            y=x;while(!*y)*y++=a;if(*y==-1)return;
            (*y)--;f(x);
      }
      else{
            for(int i=a;i--;){
                  *y=dup(x);y[0]--;f(y);
            }
      }
}
int main()
{
      int *x;
      for(int i=a;i--;)
      {
            x=new int[a+1];
            for(int j=0;j<a;j++)x[i]=a;x[a]=-1;
            f(x);
      }
      return a;
}
0360デフォルトの名無しさん2010/01/14(木) 21:35:17
>>359
おっと、一気に大きくなりましたね。

>>259 の 138文字のよりも大きくて、
138文字のを 9e99 回ループさせたくらいでしょうか。

--------
ちなみに、138文字のはもうちょっと縮んで131文字になりました。
int a=9;struct b{int c,d;b*e;void operator*(){b f={c-!d,d?d-1:++a,e},g=f;g.e=&f;if(e)**e;if(c+d)*g;}}c={a};int main(){*c;return a;} // 131文字
0361デフォルトの名無しさん2010/01/17(日) 02:09:19
発想が新しく、効率も良さそうなので、
がんばって >>359 を極限まで縮めてみました。
>>360 とほとんど同じ値になるのですが、
3文字届きませんでした。
( >>360 も限界と思ったところから 7文字縮めたので、さらに縮められるかもしれません)

>>192 もそうですが、
だいたい同じ値をまったく異なる発想で作って、
だいたい同じ文字数になっているのがおもしろいです。

// 134
int a;
struct b{
    int c[9],*d;
    void operator*(){
        b e=*this;
        d=e.c+9;
        for(;--*--d<0?*d=++a,d!=e.c:(*e,*e,0););
    }
}c={9};
int main(){
    *c;
    return a;
}
0362デフォルトの名無しさん2010/01/17(日) 02:18:30
あ、
int c[9],*d;
じゃなくて
int*d,c[9];
にしたら1文字縮まりました。

あと2文字。
0363デフォルトの名無しさん2010/01/17(日) 02:25:55
>>362 は間違いでした。
取り消します。

>>362 だと
}c={9};
のところを
}c={0,9};
にする必要があるので、逆に長くなっちゃいますね。
0364デフォルトの名無しさん2010/01/18(月) 00:38:04
>>316
8文字縮めました。
これで >>360 を抜いてこのクラス最短に。

// 126文字
int a;
struct b{
    int c[9],*d;
    void operator*(){
        b e=*this;
        for(d=e.c+9;d>e.c;--*--d>0?*e,0:*d=++a);
    }
}c={9};
int main(){
    *c;
    return a;
}
0365デフォルトの名無しさん2010/01/18(月) 21:16:57
>>364 を2文字縮めて124文字に
int a;struct b{int c[9],*d;void e(){b f=*this;for(d=f.c+9;d>f.c;--*--d>0?f.e(),0:*d=++a);}}c={9};int main(){c.e();return a;} // 124

>>192 を2文字縮めて76文字
>>83 の77文字を抜いてこのクラス最短に
int a,b[9]={9},*c=b;int main(){for(;c>=b;--*c>0?c=b+8,0:*c--=++a);return a;} // 76
0366デフォルトの名無しさん2010/02/25(木) 07:34:47
>>365 の124文字のが縮まって96文字に
>>83 の77文字のが縮まって64文字に
なりました。
0367デフォルトの名無しさん2010/06/05(土) 11:34:17
>>296
短い順にすべての文字列の組み合わせを順番に全部インタプリタで食わせてみて
同じ文字数で最も大きい値を返すプログラムになってるものを採用すればいいんじゃね?
と思ったが停止判定ができないから不可能なのか。
0368デフォルトの名無しさん2010/06/08(火) 19:34:56
そうだね。
ステップ数====>戻り値
はそれほど大きな関数には成り得ないから
ステップ数で制限しちゃうと全然大きくならないし。
0369デフォルトの名無しさん2010/06/24(木) 00:37:28
intの最大値を返すスレ？
こういうのじゃだめなのか43文字

int main()
{return (((unsigned int)0)-1)/2;}
0370デフォルトの名無しさん2010/06/24(木) 23:47:23
>>369
>>1-368
0371デフォルトの名無しさん2010/06/25(金) 20:31:32
>>369
もろに >>2 のダメな例に書いてあるし。
しかも >>2 よりも長い。
0372デフォルトの名無しさん2010/06/26(土) 13:08:14
> （int のサイズに依存したプログラムで無ければ、1レスで作れる最大の数が定義出来るはず）
これ本当かなあ。「1レスで作れる最大の数」が定義できたと仮定すると、
リシャールのパラドックス的なことをして矛盾を導ける可能性はないの?
ビジービーバー関数みたいに定義はできるけど計算不可能だから
プログラムには書けない、ということで矛盾しないのかな?
0373デフォルトの名無しさん2010/06/26(土) 16:04:23
int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return pow(a(9,9),a(9,9));}

と

int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return a(9999999,9999999);}

はどっちが大きいんだ（文字数は同じ）
0374デフォルトの名無しさん2010/06/26(土) 16:19:08
powは定義も含めないと違反(>>331)
0375デフォルトの名無しさん2010/06/26(土) 16:21:29
なんと
0376デフォルトの名無しさん2010/06/26(土) 16:51:23
int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return a(a(9,9),a(9,9));}
のほうが圧倒的に大きくて文字数も少ない
大雑把に言ってpow(x,x)はa(4,x)にも勝てない
0377デフォルトの名無しさん2010/06/26(土) 19:44:19
アッカーマン圧巻だな
0378デフォルトの名無しさん2010/06/26(土) 20:54:16
>>372
別に矛盾しないだろ。
1レスの文字数上限が決まっているので、
1レスで作れるプログラムも有限個しかない。
その中の >>1 の条件に当てはまるものの戻り値の最大値
が「1レスで作れる最大の数」になる。
>>1 のように適切に言語を制限すればベリーのパラドックスは発生しない。
（ISO/IEC 14882:2003 という言語に曖昧な部分が無いという仮定 は必要）

その最大値がどのくらいの大きさの数かを知るすべは無いとは思うが。
0379デフォルトの名無しさん2010/06/26(土) 20:58:56
>>378
たとえば
int main(){int i=0;for(;;)++i;return i;}
みたいなプログラムは停止しないから(明記されてないけどたぶん)ルール違反でしょ?
ということは1レスで作れる最大の数を定義するには
1レスで書けるプログラム全てに対して停止判定ができなきゃいけないと思うんだけど。
停止判定ができないのはプログラムサイズに上限を付けなかった場合で
任意の有限サイズ以下のプログラムに対する停止判定だったら原理的には
可能なんだっけ?
0380デフォルトの名無しさん2010/06/26(土) 21:19:43
停止判定ができないことの証明は、停止判定を行う関数h(x,y)が書けたと仮定して
その関数を使ったプログラムを書いて矛盾を導くから、
h(x,y)が1レスでは決して書けないことを証明できれば
1レスで書けるプログラム全てに対してh(x,y)で停止判定ができても矛盾しない。
0381デフォルトの名無しさん2010/06/26(土) 21:37:01
>>380
少なくともh(x,y)が書けたら停止判定できないことは証明されてるけど、
h(x,y)さえなければ停止判定できることって証明されてたっけ？
0382デフォルトの名無しさん2010/06/26(土) 21:37:39
>>376
もっともっといじると、>>197 の80文字にまで縮まる。
>>376 よりは微妙に大きい。

>>377
いままで私が把握してる中では、
64文字〜135文字、140文字〜148文字はすべてアッカーマン関数やその拡張を使った記録が続いている。
（136文字〜139文字は >>259の考えを使ったもの）
アッカーマン圧巻！

単に私の知識や発想が狭いからそうなっちゃってるという可能性も否定はできないが....
0383デフォルトの名無しさん2010/06/26(土) 21:49:01
>>379
停止判定出来ようが出来まいが、
無矛盾に値を定義することはできる。
値を返すプログラムがどのようなものかを調べるアルゴリズムが存在するかどうか
という命題とは関係無しに。

で、そのアルゴリズムが存在することも簡単にわかる。
単に十分大きな値で停止判定すれば良い。

でその十分大きな値というのがどの程度大きな値であるか
を調べるアルゴリズムが存在するかどうかはわからない。
値を調べるアルゴリズムが存在するかどうかはわからないが、
停止判定を行うのに十分な大きな値が存在するということはわかる。
0384デフォルトの名無しさん2010/06/26(土) 21:49:58
>>381
すべてのプログラムは停止するかしないかのいずれかだから、
1レスで書けるプログラムすべてを表に登録して、表引きで停止するかしないか
返すプログラムを書けば判定できる。
その表をどうやって作るんだと言われても知らないけど表の長さが有限であることさえ
示せばプログラムが存在することは確か(判定したいプログラムの長さに上限がなければ
表も有限にならないのでダメ)。
0385デフォルトの名無しさん2010/06/26(土) 22:08:54
>>383
停止判定ができるなら>>367みたいなプログラムが実際に存在するということだから
int a(){/*1レスで書ける最大値を計算するプログラム*/}
int main(){return a()+1;}
が1レスに収まるなら矛盾する。だから無矛盾に定義するには
停止判定ができないか、>>367みたいなプログラムは十分短く書けないことを
証明する必要がある。
0386デフォルトの名無しさん2010/06/26(土) 22:16:25
>>380
後半２行、
ある証明で用いたテクニックが使えない ===> 無矛盾
というのは無理がありすぎる。

----
具体的に1レスで収まるプログラムの停止判定アルゴリズムを示すと、

1レスで記述できるプログラムをすべて列挙する。
この中で、N※ ステップ以内に停止しないものを除く。
さらに、プログラム終了までの間に環境依存な動作を行ったプログラムを除く。
残ったプログラムの戻り値のうちの最大のものが求める数。

※ Nは十分大きな整数。
（1レスで記述出来るプログラムの最大ステップ数以上であればなんでも良い）
0387デフォルトの名無しさん2010/06/26(土) 22:29:51
>>386
『Nは十分大きな整数』で気に入らないなら、
N = BB(BB(10000)) とかに決めても良いよ。
0388デフォルトの名無しさん2010/06/26(土) 22:33:53
ところで、
『値が定義出来る』と
『値を求めるアルゴリズムが存在する』と
はまったく別ものなんだよね。

>>372 の疑問からなぜ『値を求めるアルゴリズムが存在するか』にすり変わったのかがわからない。
0389デフォルトの名無しさん2010/06/26(土) 23:37:29
>>388
> 定義はできるけど計算不可能だからプログラムには書けない
0390デフォルトの名無しさん2010/06/28(月) 19:45:43
>>372
> ビジービーバー関数みたいに定義はできるけど計算不可能だから
> プログラムには書けない、ということで矛盾しないのかな?
プログラムに書けない ====> 矛盾
の理屈がわからないのだけど....
0391デフォルトの名無しさん2010/06/29(火) 02:26:02
>>390
>>372には『「1レスで作れる最大の数」が定義できたと仮定すると』って書いてあるよ。
そう仮定したとき、その最大の数を求めるプログラムを1レスで書けなければ仮定と矛盾するんじゃない？
0392デフォルトの名無しさん2010/06/29(火) 19:08:53
>>391
「1レスで作れる最大の数」の定義は、
1レスプログラムを用いて定義する訳じゃないので
何も矛盾しない。

以下は21文字以内で作れるプログラムの中で（おそらく）最大の数を返すが、
int main(){return 9;}
int main(){return+9;}

このプログラム自身は21文字以内で最大であることを示してもいないし、
21文字以内で作れるプログラムの中での戻り値の最大値を探すものでもない。
またおそらく21文字ではそのようなプログラムは作れないし、
（文字数を限定せずに）そのようなプログラムを作れるかどうかは、
最大の数を定義できることとは別の問題。
0393デフォルトの名無しさん2010/06/30(水) 00:22:18
>>392
それが本当に最大かどうかを確認する最も愚直な方法は、
21文字以内で表現できうるプログラムを全て実行させてみることだけど、
その中に計算が、T秒以内に終わらない可能性もあるわけだろ。
(まぁ、Tが十分大きければ21文字ではないだろうが。)

そのT秒以内に終わらないプログラムが、最大の整数を返すプログラムでないことを示す方法はある？
止まらなかったら2*T秒動かしてみる、というのも手だけど、それだと無限ループに引っかかる。

1レス以内に書けるプログラムに限定して、停止問題を解くことができるか、という話はそこらへんから出てきてる。
停止判定ができるのなら、有限時間に終わるプログラムのみを実行して、最大の整数を確認すればよい。
0394デフォルトの名無しさん2010/07/01(木) 12:41:37
ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズムは存在する
（文字数を限定しなければ）プログラムすべての停止判定を行うことができるアルゴリズムは存在しない

プログラムの文字数が限定されていれば、
たとえばBB(BB(10000))のような非常に大きな数による
ステップ数制限を使った停止判定が行える。
よって返すことが出来る最大の数を調べるアルゴリズムも存在する。
（アルゴリズムが存在するというだけで、実際に動作してみて結果を得ることは事実上無理）

プログラムの文字数が限定されていなければ、
すべてのプログラムの停止判定を行うことができる単一アルゴリズムは存在しない。
0395デフォルトの名無しさん2010/07/03(土) 00:14:40
>>394
それをするには、ステップ数の上限を決めないといけないわけだろ。
そんなの、どうやって決める？
0396デフォルトの名無しさん2010/07/03(土) 07:22:49
>>395
『たとえばBB(BB(10000))』と書いてあるが。
0397デフォルトの名無しさん2010/07/03(土) 12:59:27
>>396
それは本当に十分なの？
0398デフォルトの名無しさん2010/07/04(日) 01:52:02
>>397
YES.
（数学的に厳密な証明は私には出来ないが、意味を考えれば十分すぎる値）

また、仮に不十分であったとしても、
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズムは存在する 』
を否定することにはならない。

nステップ以内で止まるプログラムを停止するプログラムと判断するアルゴリズムをA(n)とするとき、
A(1), A(2), A(3), ..... の中に上記アルゴリズムが存在することは確かな訳で。
0399デフォルトの名無しさん2010/07/04(日) 22:22:30
>>398
厳密な証明でなくてもいいから、なんでそれが十分といえるのか。

> nステップ以内で止まるプログラムを停止するプログラムと判断するアルゴリズムをA(n)とするとき、
> A(1), A(2), A(3), ..... の中に上記アルゴリズムが存在することは確かな訳で。

存在するが、その計算は有限時間で終わるのか。
すなわち、全てのM>0に対して
A(1) && A(2) && ... && A(N) == A(1) && A(2) && ... && A(N) && A(N+1) && ... && A(N+M)
を満たすNを有限時間で求めることはできるか。

これは、停止アルゴリズムの存在の必要十分条件になってる。
0400デフォルトの名無しさん2010/07/04(日) 23:59:52
>>399
1レスに記述できるプログラムは1E100ビットで保存出来る。
チューリングマシン語1ステートで（少なくとも）1ビットの情報を
テープに書くことが出来るので、
チューリングマシンのテープに任意の1レスプログラムを書く為に
1E100ステートあれば十分。

C++をステップ実行出来るプログラムは世の中にあり、
チューリングマシン語も（当然ながら）チューリング完全であって
世の中のコンピューター言語と本質的に同じことが出来るので、
C++のプログラムをステップ実行して終了までのステップ数を数えるような
チューリングマシンのプログラムを書くことが可能。
コンピューター言語とチューリングマシン語の記述効率がどの程度差があるかはわからないが、
それほど大きな差はないはずで、
少なくとも1E100ステートあれば十分記述は可能である。

以上より、1レスプログラムのステップ数を数えて、そのステップ数を
HALT時のテープ上の1で返すようなプログラムを
チューリングマシン語2E100ステートで記述することが可能である。
（終了しないプログラムに対してはどんな動作でも構わない）

1レスで書ける、停止するプログラムの中で最大ステップ数の物に対しても
2E100ステートでステップ数を返せることになるので、
BB(n) の定義よりこのステップ数はBB(2E100)以下であることが分かる。
（当然BB(BB(10000))以下）
0401デフォルトの名無しさん2010/07/05(月) 00:10:53
>>399
3行目以降は意味が良くわからない。

A(i) は iステップまでしか調べないのだから当然有限時間で停止する。
（そもそも有限時間で停止しないようなものはアルゴリズムとは言わない）

A(i) が
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズム』
となる i を有限時間で見つけられるか？
という意味であればそれはもう
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズムは存在する 』
という命題とは別の問題にすり変わっている。
0402デフォルトの名無しさん2010/07/05(月) 00:59:30
>>401
うん。そりゃ、iステップ目までしか調べないのだから、停止する。
が、それではi+1ステップ目で停止するプログラムを見逃すことになる。

それを見逃さないアルゴリズムは
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズム』
と等価。

>>400
ダウト。
(i) 明らかに、プログラムの文字数から、プログラムを保存するのに十分なビット数を求めるアルゴリズムは存在し、その値は有限になる
(ii) >>400により、プログラムを保存するのに十分なビット数が求まれば、そのプログラムの最大ステップ数を求めることができる
(iii) 最大ステップ数が求まれば、明らかに有限時間で停止判定ができる
これらより、任意の有限文字数のプログラムで停止判定が行えるということ結論が得られるが、
これは明らかにチューリングの停止判定不能問題に矛盾。
0403デフォルトの名無しさん2010/07/05(月) 02:13:11
>>402
前半
i+1ステップ目で停止するプログラムを見逃すことはなんら問題が無い。
十分大きな i (たとえばBB(BB(10000)) ) を選べば、
1レスで記述できるC++の（停止する）プログラムのステップ数は
i 以下になるのだから。

後半
「任意の i に対し BB(i) を得ることが出来る」アルゴリズムは存在しない
よって、単一アルゴリズムで (ii) が実現出来ない
0404デフォルトの名無しさん2010/07/05(月) 02:25:48
>>403
BBが何なのか知らん(IEEEの論文から検索かけても見つからん)が、
任意のiでなくてもいいよ。十分に大きければ。
0405デフォルトの名無しさん2010/07/05(月) 02:37:52
>>400
> コンピューター言語とチューリングマシン語の記述効率がどの程度差があるかはわからないが、
> それほど大きな差はないはずで、

これ怪しいね。
ステップ数に対して指数関数的に増加する可能性を否定するだけでも一苦労だと思うよ。
0406デフォルトの名無しさん2010/07/05(月) 02:44:30
>>403
>>398を読み直せば、ここではBB(BB(10000))が十分大きいとみなせないことが分かる。
0407デフォルトの名無しさん2010/07/05(月) 14:11:09
/* 最初に見つかった奇数の完全数を返す */

int p(int n) 
{
    int i, s = 0;
    for (i = 1; i < n; i++)
        if (n % i == 0) s += i;
    return s == n;
}

int main() 
{
    for (int n = 1; ; n += 2)
        if (p(n)) return n;
}
0408デフォルトの名無しさん2010/07/05(月) 19:10:09
>>404
BB(n) ビジービーバー関数
Σ(n) と書いた方が良かったか

>>405
初期のマイコンのアセンブラレベルのインタープリタなら比較的簡単に作れる。
これを用いれば、より記述効率の良いインタープリタが作れる。
それを用いてC++のインタープリタが作れる。
それほど大きな差はないはずだという根拠はこれだ。
1E100ステートあれば十分すぎる。

>>406
BB(BB(10000))じゃ十分じゃないというなら
証明、解説をしてくれ。
0409デフォルトの名無しさん2010/07/05(月) 19:20:41
>>407
ひさびさにC++のコードが。

これは無限ループなのか値を返すのかが、まだ人類のだれも分かってないもの。
仮に値を返すとしてもどのくらいの値が返るかもわからない。

発想としては >>325 と同じ。
だれも無限ループなのか値が返るのかわからないコード。
可能性的には、とてつもなく大きな値を返すかもしれない。
0410デフォルトの名無しさん2010/07/05(月) 19:48:56
int のオーバーフローがあるから
途中で同じ計算繰り返すことになって
無限ループ突入だろ
0411デフォルトの名無しさん2010/07/05(月) 19:52:49
>>410
>>1
0412デフォルトの名無しさん2010/07/05(月) 21:05:38
シュレディンガーの関数
0413デフォルトの名無しさん2010/07/05(月) 23:34:02
>>408
>>398はもしもBB(BB(10000))で不十分だったらという前提で話をしているから。
0414デフォルトの名無しさん2010/07/05(月) 23:39:50
>>408
> 初期のマイコンのアセンブラレベルのインタープリタなら比較的簡単に作れる。
> これを用いれば、より記述効率の良いインタープリタが作れる。
> それを用いてC++のインタープリタが作れる。
> それほど大きな差はないはずだという根拠はこれだ。
> 1E100ステートあれば十分すぎる。

作り出すことと、計算複雑性の関係が示されていない。これじゃダメ。

ところで、ビジービーバー関数なら、BB(BB(10000))は計算可能なの？
あるいは、計算可能かつBB(BB(10000))以上である数値を返す関数は存在するの？
0415デフォルトの名無しさん2010/07/05(月) 23:48:18
>>414
計算可能。むしろ有限のnならBB(n)は計算可能。
つまり>>402の方法が可能。
0416デフォルトの名無しさん2010/07/06(火) 18:52:20
>>414
厳密な証明でなくてもいいと言ってるわりには
結構細かいところをつっこんでくるんだな。
作れるってのは現実的なステート数で作れるってことだよ。

チューリングマシン語を使って簡単なインタープリタを作るのは、
考えてみると結構面白いので一度考えてみることを勧める。
個人的にも十分作れるサイズで出来る。

ヒントを言うと、
普通のチューリングマシン数ステートで
マルチトラックチューリングマシン1ステートを表現できる。
マルチトラックチューリングマシンで、
（上限無しの）整数レジスタ数本と無限長ビットフィールド数本を表現出来る。

初期マイコンのアセンブラの命令を使ってC++のインタープリタを作った場合のサイズは、
現在いろんなコンパイラやデバッグツール、変換ツール、シミュレータが存在してることと、
人類が今まで作ったデジタルデータ量の合計を考えてみれば大まかな予想が出来るはず。

1E100ステートあれば十分すぎる。
0417デフォルトの名無しさん2010/07/06(火) 19:00:50
>>415
すべての自然数nに対し、アルゴリズムAが存在し、Aは入力値nに対しBB(n)を出力する
アルゴリズムAが存在し、すべての自然数nに対し、Aは入力値nに対しBB(n)を出力する
これの違いを考えてみることを勧める。

記号で書くと、
∀n, ∃A s.t. Aは入力値nに対しBB(n)を出力する
∃A, ∀n s.t. Aは入力値nに対しBB(n)を出力する
これの違い。
0418デフォルトの名無しさん2010/07/06(火) 22:24:12
>>414
> ところで、ビジービーバー関数なら、BB(BB(10000))は計算可能なの？
すべての自然数nに対して BB(n) が計算できるアルゴリズムは存在しない。
（BBは計算不可能であるという）
一方、BB(BB(10000)) という1つの整数に対して計算可能かどうか？
という議論がされることはほとんどない。
BB(BB(10000)) を出力するアルゴリズムの存在は明らかであるから。

n を出力するアルゴリズムを A(n) とした時、
A(1), A(2), A(3), ..... の中に BB(BB(10000)) を出力するものが存在することは明らかなので。

計算理論で計算可能とは有限の情報を用いて有限ステップで終了するアルゴリズムが存在すること。
現実世界で計算が可能であるかどうか、結果が得られるかどうかの評価とは異なり、
メモリ使用量、処理量、実行時間は問わない。

> あるいは、計算可能かつBB(BB(10000))以上である数値を返す関数は存在するの？
f(n) = n だっていずれは BB(BB(10000)) を超えるし、
f(n) = BB(BB(10000))+1 という定数関数ならいつでも超えてる。
0419デフォルトの名無しさん2010/07/07(水) 01:30:18
>>416
いや、そこは重要なところだ。
素因数分解が多項式時間でできる量子コンピュータだってチューリングマシンと等価なのだから、
コンピュータで多項式時間でできる処理がチューリングマシンでも多項式時間でできることは別途証明が必要。
0420デフォルトの名無しさん2010/07/07(水) 01:34:22
そしたら、
文字数が0のとき、 10000ステップあれば十分
文字数が1のとき、BB(10000)ステップあれば十分
文字数が2のとき、BB(BB(10000))ステップあれば十分
文字数がnのとき、BB(BB(BB(....BB(10000)....)))ステップあれば十分
0421デフォルトの名無しさん2010/07/07(水) 18:53:39
>>419
勘違いしてるかもしれないので書いておくけど、
チューリングマシンのステート数ってのは
計算量や計算時間じゃなくて、
プログラムサイズのことだよ。

プログラムサイズ 1E100語 で
C++プログラムのステップ数を数えるプログラムが出来るって話。

>>420
もっと簡単に、
文字数がnのとき、BB(16*n + 1E100) ステップあれば十分。
0422デフォルトの名無しさん2010/07/08(木) 01:06:43
>>421
でもBB(16*n + 1E100) は計算できなさそう。
0423デフォルトの名無しさん2010/07/08(木) 07:23:17
>>422
そう。
すべての自然数nに対して BB(16*n + 1E100) を計算出来る単一のアルゴリズムは存在しない。
0424デフォルトの名無しさん2010/07/08(木) 22:33:46
>>423
もともと
> 文字数がnのとき、BB(BB(BB(....BB(10000)....)))ステップ
の時点で怪しかったが……
0425デフォルトの名無しさん2010/07/09(金) 19:21:12
C++プログラム：>>1 の言語仕様を満たし、int main() 関数が終了する C++のプログラム
C++関数：>>1 の言語仕様を満たす C++の関数

【1】n文字以内のC++プログラムが返すことができる最大値が存在する（この値を Cmax(n) とする）
【2】n文字以内の停止するC++プログラムの最大ステップ数が存在する（この値を Cstep(n) とする）
    n文字以内のプログラムは有限個であるため、明らか
    ただし、n文字以内のプログラムが存在しない場合は便宜的にCmax(n) = Cstep(n) = 0 としておく
    【1】【2】にそれほど大きな差がないことも簡単にわかる

【3】すべてのC++プログラムの停止判定を行えるC++関数は存在しない
【4】すべてのnに対して Cmax(n) を返すC++関数は存在しない
【5】すべてのnに対して Cstep(n) を返すC++関数は存在しない
    【4】がα文字で出来たとすると、Cmax(α*2+30) を返すプログラムがα*2+30文字未満で作れる ===> 矛盾
    【3】【5】が存在したら【4】も作れる ===> 矛盾

【6】N文字以下のすべてのC++プログラムの停止判定を行えるC++関数は存在する
【7】N以下のすべてのnに対して Cmax(n) を返すC++関数は存在する
【8】N以下のすべてのnに対して Cstep(n) を返すC++関数は存在する
    nステップ以下で停止するC++関数を停止すると判断するC++関数を A(n)とした時、
    A(1), A(2), A(3), ... の中に【6】が存在することは明らか
    【6】から【7】【8】が作れる
0426デフォルトの名無しさん2010/07/09(金) 19:25:17
【9】1000文字以下のすべてのC++プログラムの停止判定を行えるC++関数の具体例は？
    Cstep(1000) 以上のステップ数を実際に進めてみて停止判定する

【10】【9】のCstep(1000)をどうやってC++関数にするの？
 あらかじめ計算して10進数で実装する

【11】【10】を計算することも記述することも事実上出来ないが
    【9】を書き下すことは現実的には不可能なの？
    Cmax(1000)を1000文字で記述できることはわかっている。
    がんばれば人間でもCstep(1000)を超える数を作るプログラムを記述できるかもしれない
    現実を考えると、たとえ記述できたとしても実行時間やメモリサイズの制限で完了できない

【12】【11】で作ったものが【10】を超えているという証明は出来るの？
    それは非常に難しい。現実的には無理だと思う。

【13】じゃあ結局【6】〜【8】は嘘なの？
    確かに存在はするが、それを実際に書き下せることとは別

【14】Cmax(n) てどんな関数？
    C++で作れるどんな関数よりも速く増加する関数である
    事実上機械的に値を求めることは不可能
    各値は >>102 >>227-230 が返す値以上であることはわかっているが
    正しい値を知ることは非常に難しい
    おそらく Cmax(21) = 9, Cmax(22) = 99, Cmax(23) = 9e9 あたりは正しいと思われる
0427デフォルトの名無しさん2010/07/09(金) 21:00:50
42文字でループが出来たよ。
int a=9;int main(){return--a?9<<main():9;} // 42文字

こんな書き方も。
int a;int main(){return--a+9?9<<main():9;} // 42文字
int a;int main(){return++a-9?9<<main():9;} // 42文字

これ以上は無理か？
0428デフォルトの名無しさん2010/07/09(金) 22:56:05
> 【6】N文字以下のすべてのC++プログラムの停止判定を行えるC++関数は存在する
そしたら、N+1文字以下のすべてのC++プログラムの停止判定を行えるC++関数も存在して、
帰納的に【3】が存在することになる気がするんだけど、どこで間違ってるんだろ。
0429デフォルトの名無しさん2010/07/09(金) 23:18:41
>>428
N文字以下のすべてのC++プログラムの停止判定を行えるC++関数のうちの1個をA(N)とする。
A(1), A(2), A(3), .... は存在する。...【6】
ところが、
どんな文字数のC++プログラムでも停止判定を行えるようなC++関数 A(∞) は存在しない。【3】

>>417 参照
0430デフォルトの名無しさん2010/07/10(土) 00:47:23
>>429
うん。けど、A(N+1)も存在するよね。A(N+2)も存在するよね。
0431名無しさん＠そうだ選挙に行こう2010/07/10(土) 08:00:35
>>431
より身近な例で

どんな自然数Nに対しても、それより大きな自然数Mが存在する
ところが、すべての自然数Nよりも大きな自然数Mは存在しない

∀N, ∃M s.t. M>N ...○
∃M, ∀N s.t. M>N ...×
0432名無しさん＠そうだ選挙に行こう2010/07/10(土) 09:44:32
>>431
それはしってる。
A(N+1)が存在するかどうか。
0433名無しさん＠そうだ選挙に行こう2010/07/10(土) 09:55:10
>>432
なにがわからないのかさっぱりわからないのだが

A(1), A(2), A(3), .... は存在すると書いたがこれが理解できない？
別の書き方で書くと『任意の自然数Nに対して A(N) が存在する』

Nが自然数であればN+1も自然数なので
『任意の自然数Nに対して A(N+1) が存在する』も当然成り立つ
0434名無しさん＠そうだ選挙に行こう2010/07/10(土) 10:28:21
>>433
> 任意の自然数Nに対して A(N) が存在する
それはますますわからん。
プログラムの文字数を数える動作が計算可能なら、
その文字数をNとしてA(N)が存在することになるのでは？

そしたら、任意のプログラムの停止判定を行えるA(∞)は存在しなくても
任意のプログラムに対して、そのプログラムの停止判定を行えるA(N)は存在するんじゃないの？
0435名無しさん＠そうだ選挙に行こう2010/07/10(土) 10:52:45
>>434
最後の行はYES.
この最後の行と【3】の違いは >>432で 「しってる」と書いてある。
じゃあわからないのは何？
0436名無しさん＠そうだ選挙に行こう2010/07/10(土) 12:53:21
>>435
帰納法が無限まで使えないのはどういう場合か。
0437名無しさん＠そうだ選挙に行こう2010/07/10(土) 13:25:46
任意のNについてA(N)が考えられるのなら、A(∞)なんてなくても、プログラムの文字数を数える関数をf(code)として、
A(f(code))
でどんなコードでも停止判定できるんじゃないの？
04384372010/07/10(土) 13:31:01
うんにゃ、書き方がわりぃな。それだとAがnに束縛されてるように読める。
ls = [A(0), A(1), A(2), ...]の無限リストとして、ls[f(code)]はちょうどA(f(code))になってるわけだ。
0439名無しさん＠そうだ選挙に行こう2010/07/10(土) 18:29:21
>>436
じゃあ帰納法の形できちっと証明してみてください。
間違いを指摘してあげるから。

>>437 >>438
A(0), A(1), A(2), ... の無限個のプログラムを持てば出来るって主張？
有限長のプログラムで書けないとアルゴリズムが存在するとは言えないぞ。
>>425 も【4】がα文字で出来たと仮定して矛盾を導いている。
0440名無しさん＠そうだ選挙に行こう2010/07/10(土) 20:58:14
>>439
A(0)は存在する。
A(N)が存在するとき、A(N+1)は存在する。
故に任意のNについてA(N)は存在する。

A(N)が存在するとき、N文字のプログラムの停止判定が可能
故に、任意のNについて、N文字のプログラムの停止判定が可能
0441名無しさん＠そうだ選挙に行こう2010/07/11(日) 07:40:26
>>440
それは >>425 の【3】の反証にはなってない。
>>417 >>429 >>431 参照。

【3】の反証をしたい訳では無くてただ単に漠然と停止判定が出来るってことなら、
>>429 の A(0), A(1), A(2) ... をくっつけた無限長のC++関数や、
Cstep の値をすべての自然数分保持した無限の情報（オラクル）付きC++関数でも可。
0442名無しさん＠そうだ選挙に行こう2010/07/11(日) 10:50:19
>>441
もともと、停止判定にしか興味ないよ。

本当に疑問だったところは、BB(BB(10000))が計算可能ってところで、
それがA(A(10000))の計算に帰着するとしたら、
A(A(10000))の計算はできてもA(A(A(10000)))ができないアルゴリズムを拡張して、
それも計算できるようにするアルゴリズムを得ることはできるか、
できたとしたら、もっと拡張する方法はないか、ということだから。
0443名無しさん＠そうだ選挙に行こう2010/07/11(日) 20:33:21
プログラムや関数に無限長のものまで含めても、やっぱり【3】は成り立つ。

停止判定を行いたいプログラムよりも停止判定の処理を実行するプログラムの方が能力が上でないとダメ。
たとえ万能の神様でも、自分自身の考えが正しいと判定することは出来ない。

>>442
もともとって、停止判定の話をずーっとしてるんだけど。

A(A(10000)) の記述の意味がわからない。
>>425, >>429 いずれのAの定義でもこんな記述は出来ないと思う。
別の定義の A なら定義を書いて。

-----------
お願いだが、
もうちょっと言葉や文章を正確に書いてほしい。
曖昧なところや不正確なところが多すぎて文を解釈するのに苦労するので。
一応みんなが見る掲示板だし。
0444デフォルトの名無しさん2010/07/12(月) 00:03:58
A(N)が具体的に記述できても、
それを利用してA(N+1)を記述できる訳ではない
と言うことが解っていないのだと思う。
0445デフォルトの名無しさん2010/07/12(月) 00:56:39
>>443
Aの定義なんて、知らないよ。じゃあBB(BB(10000))を計算するには、どうすればいいわけよ。

>>444
それを利用する必要なんて、あるとは思ってないけどなぁ。
利用しようがしまいが、A(1)もA(2)もA(N)もあって、どうやって求めるのかは知らないけど、それを得ることができるのなら、
A(N+1)も得ることができるんだろ、としか思ってない。
0446デフォルトの名無しさん2010/07/12(月) 01:15:43
そういや、Aの定義に>>417を採用した。が、他で出てるのとはどうやら別物っぽいね。
0447デフォルトの名無しさん2010/07/12(月) 08:25:58
>>445
どうすればいい？って何を聞きたいの？
具体的にC++で記述してほしいのか？
それは無理だよ。
どんなに効率良く書いてもBB(10000)くらいの文字数が必要なんで。
BB(BB(10000)) を計算するプログラムは確かに存在するが、
それを具体的に書き表わすことは（事実上）出来ない。
当然10進数で値を知ることなど到底無理。

存在するってのは現時点のこの世の中のどこかに存在するって意味じゃなく、
考えられるすべての (有限数の) 文字の組み合わせの中に存在するって意味。

>>446
>>417 に A の定義なんて書いて無いと思うが。
単なる一時変数として使ってるだけ。
さらにその一時変数としての使い方も >>417 には2通りある。

>>425 のAの定義は
nステップ以下で停止するC++関数を停止すると判断するC++関数を A(n)とする
>>429 のAの定義は
N文字以下のすべてのC++プログラムの停止判定を行えるC++関数のうちの1個をA(N)とする
>>446 のAの定義は？
0448デフォルトの名無しさん2010/07/14(水) 01:09:30
>>447
存在しても、それを探し当てるアルゴリズムがないと計算できないんじゃない？
0449デフォルトの名無しさん2010/07/14(水) 08:27:13
>>448
計算理論で言う「計算可能」の意味ではなくて、
実際に計算して結果を得ることが出来るかって意味なら、
int main(){return 9<<(9<<99);}
この時点で無理。
0450デフォルトの名無しさん2010/07/14(水) 10:03:38
>>449
計算可能の意味だよ。
0451デフォルトの名無しさん2010/07/14(水) 18:01:17
アルゴリズムって人間がそれを証明として納得できるかどうかは関係ない？

たとえばフェルマーの最終定理が成り立つかどうかのアルゴリズムは
bool f
{
return true;
}
でもOK？
0452デフォルトの名無しさん2010/07/14(水) 19:18:06
>>450
計算理論ではアルゴリズムが存在すれば「計算可能」なので、
現実世界のリソースを用いてそのアルゴリズムを記述出来るかどうかとは無関係。

>>451
YES
0453デフォルトの名無しさん2010/07/14(水) 21:16:22
>>452
現実世界のリソースじゃなくてもいいよ。
アルゴリズムの集合の中からアルゴリズムを選び出す方法が存在することと、計算可能であることに違いはある？
0454デフォルトの名無しさん2010/07/14(水) 22:29:35
>>453
アルゴリズムの集合からアルゴリズムを選び出す方法があるかどうかにかかわらず、
アルゴリズムの存在が示されれば計算可能と言える。

そもそも、選び出す方法に対して何の限定もしなければ、
アルゴリズムの集合からアルゴリズムを選び出すのが不可能な場面なんて無い気がする。

人間じゃとても理解できない高度なアルゴリズムだって
人間じゃなければ理解できるかもしれない。
人間の能力だって人や時代によっても変わるし、
神様ならすべてお見通しかもしれない。
そんな不確定な要素に左右されないのが計算可能性の理論。
0455デフォルトの名無しさん2010/07/15(木) 23:43:10
>>454
いったい>>453の話のどこに人間が出てくるんだ？
0456デフォルトの名無しさん2010/07/15(木) 23:52:47
>>455
人間が選ばなかったらどうやってアルゴリズムを選び出すつもり？
その選び出したアルゴリズムが正しいかどうかを人間が確認しなかったら誰が確認するの？

たとえば、
>>407 が最小の奇数の完全数を返すアルゴリズム（存在すればだが）というのを
人間が確認しなかったらだれが確認するの？
アルゴリズムで確認するというなら、
その確認用アルゴリズムが正しいかどうかは誰がどうやって確認するの？
0457デフォルトの名無しさん2010/07/16(金) 00:00:38
ちなみに、
BB(BB(10000)) を計算するアルゴリズムは存在するし、
そのアルゴリズムを選び出すアルゴリズムも存在するし。
さらにそのアルゴリズムを選び出すアルゴリズムも存在する。

しかし、選び出す方のアルゴリズムの方が選び出されるアルゴリズムより複雑で、
それらのアルゴリズムが具体的にどんなものかはだれも分からないし、
0458デフォルトの名無しさん2010/07/16(金) 02:16:50
>>456
それ言い出したら人間が計算しなければ誰が計算するんだ。
0459デフォルトの名無しさん2010/07/16(金) 08:00:39
>>458
だから『それを言いだしてもしょうがないでしょ』という説明なんだけど。

計算可能性理論では、実際に計算を行う時間や方法を考えなくて良いだけじゃなく、
実際にだれが（または何が）どうやってアルゴリズムを選ぶかも、考えなくて良い。
ただアルゴリズムが存在するかしないか、というのが計算可能性の定義。

>>453 の「選び出す方法が存在する」ってのはまさか
『アルゴリズムの集合の中からある1個のアルゴリズムを選ぶアルゴリズム』が存在する
って意味なのか？
こんなことはあまりに自明でそんなことを論じてるとは思わなかったんで、
現実世界のリソースじゃなくても良い ====> じゃあ神か何か？
と思ったんだけど。

『アルゴリズムの集合の中からある1個のアルゴリズムを選ぶアルゴリズム』に限らず、
有限の文字で表せるある1個の物を吐き出すアルゴリズムは存在する。
0460デフォルトの名無しさん2010/07/16(金) 08:19:46
お願いだが、質問は意味が分かるように書いてくれ。

たぶん質問してるのは一人じゃなくていろんなレベルの人がいる。
こっちはどういう前提で何を聞かれているのかが分からないんで
回答も適切なものにならないかもしれない。

>>448 とか >>453 は結局何が聞きたいのかいまだ良くわからない。
0461デフォルトの名無しさん2010/07/16(金) 23:07:45
>>460
(計算可能な)計算を表した文字列を引数にとり、計算の結果を返す関数。
すなわち、
f("1レスで書けるプログラムの停止可能性を求める上で十分なステップ数") = BB(BB(20000))
f("BB(BB(20000))文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数") = BB(BB(BB(20000)))
なる関数。
0462デフォルトの名無しさん2010/07/16(金) 23:32:59
>>461
その関数fが計算可能かどうか？という質問？
当然関数fは計算可能ではない。

Nがある自然数の定数だとして、
"N文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数"
は計算可能である。

一方、
f は N の部分にどんな自然数定数を入れても、
f("N文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数") の値を返さなくてはならない。
この値は >>426 の Cstep(N) である。

f が計算可能だと仮定すると、Cstep も計算可能となって >>426 と矛盾するので、
f は計算不可能。
0463デフォルトの名無しさん2010/07/17(土) 01:53:57
もまいら、Wikipediaでビジービーバー読んできたばっかの俺にも分かるように説明しる。
> 入力として n を受け取り Σ(n) を計算するような単一のアルゴリズム A は存在しないものの（Σは計算不能なので）、n までの全ての自然数について Σ(n) を「計算」するようなアルゴリズム An は存在する
これが分からん。nは限りなく大きくできるんじゃないのか。
具体的には
A∞=lim(n->∞) An
とか
A(n)=An
ってできるだろ。
0464デフォルトの名無しさん2010/07/17(土) 07:27:23
>>463
An の n は（有限の値なら）いくらでも大きくすることが出来るが
A∞ は存在しない。

An のアルゴリズムを記述するのに（仮に）n文字以上必要だとすると、
A∞ のアルゴリズムを記述するのに有限文字じゃ出来ないよね？
∞文字必要になってしまう。
∞文字必要な物はアルゴリズムって呼ばないんで、
A∞ を計算する単一のアルゴリズムは存在しない。
0465デフォルトの名無しさん2010/07/17(土) 09:32:36
>>464
そしたら、A(n)=Anを、nが有限の値をとるものとして定義したら？
0466デフォルトの名無しさん2010/07/17(土) 22:09:11
>>465
nは初めから有限だが。
0467デフォルトの名無しさん2010/07/18(日) 00:08:47
>>462
うん。そう。
すると、>>394のいう
> プログラムの文字数が限定されていれば、
> たとえばBB(BB(10000))のような非常に大きな数による
は、どうやって十分に大きな数を選ぶんだ？

計算可能な数として存在はするが、それを選ぶことはできないんじゃないの？
0468デフォルトの名無しさん2010/07/18(日) 07:36:02
>>467
>>454 に戻ってループ？

一般的な計算理論での「計算可能」の定義は、
それを計算するアルゴリズムが存在すること。
そのアルゴリズムを選べるかどうかは無関係。
BB(BB(10000))を返すアルゴリズムは存在するのでBB(BB(10000))は計算可能。
（定義に不満なら、あなたがその道の権威者になって定義を変えてください）

じゃあそのアルゴリズムを選ぶことが出来るか？
これは誰がどうやって選ぶことを想定しているかでまったく結果が異なる。

●この世界のリソースを用いて人間が選ぶ
効率良く書いてもBB(10000)文字くらい必要なので事実上不可能。

●神が選ぶ
有限の文字数でC++で記述出来るのだから、神なら選べるんじゃないの？

●アルゴリズムが選ぶ
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムは存在する。
存在するがそのアルゴリズムを選べるかってのは誰がどうやって選ぶことを想定しているかでまったく結果が異なる。
これもアルゴリズムが選ぶ場合、
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
.....

●拡張マシン
オラクル付きマシン、無限実行マシン、などチューリングマシンを超える能力のあるマシンを使えば
現実的な文字数で簡単にBB(BB(10000))を求めるプログラムが記述可能。
0469デフォルトの名無しさん2010/07/18(日) 11:10:26
>>468
つまり、計算可能なアルゴリズムの集合の中には
Nstep(1)回でプログラムが止まるかを判定するアルゴリズム
Nstep(2)回でプログラムが止まるかを判定するアルゴリズム
Nstep(3)回でプログラムが止まるかを判定するアルゴリズム
...
Nstep(BB(BB(20000)))回でプログラムが止まるかを判定するアルゴリズム
...
が含まれているから、アルゴリズムのうちの「どれか」は
1レスでのプログラムの停止判定ができる、
それがどれであるかについては、議論不要
(どうせ人には書けないし、神にとっては自明すぎるから)
、ということ？

じゃあ、任意の正の整数nを取る関数として
Nstep(n)
は、なぜ存在しない？
整数がどれだったとしても、計算可能なアルゴリズムの集合の中にはNstep(n)は含まれているのでは？
0470デフォルトの名無しさん2010/07/19(月) 00:49:41
>>469
前半は大筋ではYES

> じゃあ、任意の正の整数nを取る関数として
> Nstep(n)
> は、なぜ存在しない？
Cstep が計算不可能である簡単な証明が >>425 の【3】【4】【5】に書いてある。

> 整数がどれだったとしても、計算可能なアルゴリズムの集合の中にはNstep(n)は含まれているのでは？
これはYES
0471デフォルトの名無しさん2010/07/19(月) 00:56:01
>>470
>>425 の【3】【4】【5】は理解できるし、それが事実だというのは分かったが。
全てのnについて
λn. Nstep n
は計算可能なのに、
λn. Nstep
が計算不能というのが理解できない。
0472デフォルトの名無しさん2010/07/19(月) 01:08:09
空気読まずに投稿
>>1
浮動小数点数の実現方法って、処理系依存だっけ？
int main(){
float a=1.0;
while(a/2>0.0)a/=2;
return (int)(9e9/a);
}
0473デフォルトの名無しさん2010/07/19(月) 02:17:05
>>471
自然数nに対して、『Cstep(n) の値を出力するC++プログラムを書くのにn文字以上必要』だったら
『すべての自然数の入力値に対してCstepを出力する』C++関数は、有限文字じゃ書けないでしょ？

>>472
C++の規格的にはfloatやdoubleの精度や実装方法は処理系依存。
アンダーフロー時の動作も不定だったような。

ただし、このスレでは float は十分な精度があることになっており、
事実上無限の精度があると思ってもらって問題無い。
（>>34 で補足説明をしている）
この辺はintと同じ考え。
0474デフォルトの名無しさん2010/07/20(火) 02:35:25
十分な精度があるってのがよくわからんが、
unsigned i = 0;
while (++i);
は停止すんの？しないの？
0475デフォルトの名無しさん2010/07/20(火) 02:58:27
>>474
しないんだろ。
0476デフォルトの名無しさん2010/07/20(火) 03:13:02
struct vm {
enum {SET=0,MOV,ADD,CMP,JF,OP=0xf000000,R1=0xfff000,R2=0xfff};
int i,f,r[4096];
vm *p;
int e(int *c,int l) {
for (i=0; i<4096; ++i) r[i]=0;
f=i=0;p=0;
while (0 < i && i < l) {
vm *s=p,*c = new vm(*this);
int op=r[i]&OP,r1=r[i]&R1,r2=r[i]&R2;
switch(op){
case SET:r[r1]=r2;break;
case MOV:r[r1]=r[r2];break;
case ADD:r[r1]+=r[r2];break;
case CMP:f=r[r1]<r[r2];break;
case JF:i+=((r1&2)-1)*r2-1;break;
}
i++;
while(s){if(s->eq(this))return 0; s=s->p;}
p=c;
}
return r[0];
}
int eq(vm *o) {
for(int t=0;t<4096;++t) if (r[t] != o->r[t]) return 0;
return i == o->i && f == o->f;
}
};
int n(int *c,int l){int p=0;while(p<l){if(++c[p]&0xfffffff)return 1;p++;}return 0;}
int main(int ac, char *av[]){int m = 0;for (int i=0;i<999999999; ++i) {vm v;int t, *c = new int[i];for (t = 0; t < i; ++t) c[t] = 0;while(n(c, i)){t=v.e(c,i);m=(m<t)?t:m;}}return m;}
04774762010/07/20(火) 03:13:53
適当に書いただけで動かしてないから多分バグってるけど、こういうアプローチはだめなのかな。
0478デフォルトの名無しさん2010/07/20(火) 03:17:07
って、十分な精度があるならダメだな。
0479デフォルトの名無しさん2010/07/20(火) 10:53:49
>>474
無限ループと考えてもらった方が話は簡単。
そう考えてもらっても本質的差は無い。

厳密に書くと、
一応C++上はunsigned intは有限のビットで表わされ、
unsigned int の最大値に対して++をすると0になることになってるので、
言語仕様にのっとると、無限ループせずに停止することになる。
>>474 の場合はこのループがあるだけでは環境依存な値が返らないので一応問題は無い。

十分な精度とは、
たとえばBB(BB(10000))ビットなど非常に大きなサイズ以上であるということ。
（つまり事実上無限と思って問題無い程度に大きいサイズ）
この条件の元で int や unsigned int のサイズに依存しない処理を行った場合、
1レスプログラムでは決してビット数不足になることが無い。

lim n→∞ (unsigned int のbit数がnである時のmainの戻り値)
が考えられるすべての環境で存在し値が一致するプログラム
が環境依存の無いプログラムであるとしても良い。
0480デフォルトの名無しさん2010/07/20(火) 11:07:34
>>476
いくつかバグがあるみたいだが、設計の意図をくみ取って解釈してみる。

簡単な命令からなるインタープリタ言語の、
999999999未満の命令数のプログラムをすべて実行させて、
その戻り値の最大値を返すもの。

一応簡単な無限ループ検出機能があり、
過去の状態と、すべてのレジスタ、フラグ、インストラクションポインタがすべて一致したら無限ループと判断する。

インタープリタの仕様は、
レジスタが4096個 (int の中の負でない値を取りうる)
命令が以下の5個
○0〜4095の即値のレジスタへの代入
○レジスタからレジスタへの値のコピー
○レジスタにレジスタの値を加算
○レジスタ同士の大小比較を行いフラグにセット
○フラグがセットされていたら、インストラクションポインタに -4095から4095の固定値を加える

これだけあれば、本質的にC++と同じことが出来る。
0481デフォルトの名無しさん2010/07/20(火) 11:21:27
↑の続き

このプログラムの問題点は、正確に無限ループを判断できないこと。

たとえば以下のプログラム。

0: SET r[2], 1
1: MOV r[0], r[1]
2: ADD r[1], r[2]
3: CMP r[0], r[1]
4: JF 1

インタープリタ言語的にはr[1]が1個ずつ無限に増えていく無限ループとなっているが
これを検出出来ない。
最終的にintの上限を超えてしまって環境依存の値が返ることになる。
（intが無限精度と考えれば無限ループ）
0482デフォルトの名無しさん2010/07/20(火) 11:25:41
正確に無限ループを判別するのは不可能だし、
インタープリタのレジスタの範囲を制限して正確に無限ループを判断できるようにしたら、
今度はインタープリタのレジスタのマックス値しか作れない。
0483デフォルトの名無しさん2010/07/21(水) 01:01:50
命令セットはもう少しリッチにしないといかんが、
バイトコード列の長さが有限のとき、実行する命令数に制限を作って

lp:
y = 最大x命令実行して停止するバイトコード列から得られる数の最大
if (y > x) { x = y; goto lp; }
return x;

ってした場合、停止するんかね？
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バイト
■ このスレッドは過去ログ倉庫に格納されています