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

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

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

int main();

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

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

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

●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
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 しちゃうような気がするのですが。
■ このスレッドは過去ログ倉庫に格納されています