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

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

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

int main();

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

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

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

●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
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;}

■ このスレッドは過去ログ倉庫に格納されています