テーマ#0001: 円周率100桁の表示

  • (by K, 2015.11.26)

基本情報

  • テーマ提示日: 2015.11.26(木)
  • プログラム例示日: 2015.11.26(木)
  • 発表会予定日: 調整中(おそらく平日の夕刻)
    • 会場はサイボウズ日本橋オフィス27Fを予定

背景

  • 最近Kは円周率の計算にちょっと興味を持っていて、以下のような記事を書きました。
  • しかしこれらのプログラム例だと、せいぜい7桁くらいしか求められません(たとえば「314159214」とかなので)。
  • でも一方で円周率計算といえば、何万桁とか何億桁とかそういうところにロマンがあるのであって、たったの7桁では達成感もほどほどになってしまいます。
    • まあそれでも計算の基本原理が分かったということはそれなりにはうれしいはずだけど。
  • じゃあどうすれば何万桁も計算できるかですが、一般には多倍長演算というテクニックを使います。これは配列などを活用して大きな桁数の数値を記憶し、それらを上手に操作して演算をします。
  • ということで、多倍長演算における加算や乗算を説明するところから始めようとしたのですが、なんということかhikaliumさんから以下のサイトの存在を知らされてしまったのです。
  • このサイトは非常にすばらしく、C言語のソースにして134バイト(末尾の改行コード分を加算しています)のプログラムがなんと1.5万桁もの円周率を表示するのです。もはや天才としか言いようがないです。
  • ということで134バイトというとんでもないサイズの回答が既にあるという状態になってしまいました。多倍長演算をあーでもないこーでもないと改良する必要もなくなってしまいました。
  • これでは競技・研究としては面白くありません。・・・ということで課題に「ひねり」を加えて、円周率の計算ではなく表示を目指すことにします。つまり
    main(){puts("314159265358979323...");}
  • などというふざけたプログラムでもよいということです。これならおそらく118バイトで100桁を表示できます。まじめに計算してもいいですが、円周率に非常に近い値を出す近似式でもよいのです。最初の100桁さえ一致していればいいのです。
  • このような条件であれば工夫の余地は大いにあります!
  • そして他の言語ではどうでしょうか? Rubyには普通の演算式で多倍長整数演算をやってくれる方法があるらしいと聞いたことがあります。多倍長演算に強いRubyならまじめに計算しても118バイトを切ることができるでしょうか。
  • ちなみに円周率100桁は次のとおりです。
    3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067

テーマ説明

  • 円周率を10進数で100桁以上表示してください。100桁というのは小数点以下で言えば99桁ということです。小数点は表示してもしなくてもかまいません。
    • もしサイズにおいて同点であれば、より長い桁まで一致しているほうが勝ちです。
    • 桁数まで一致しているのであれば、小数点を正しく表示できているほうが勝ちです。
  • 表示さえできればよいので、内部で全く計算をしていなくもかまいません。
  • ただし実行時間がかかりすぎるものは検証できないので困ります。せめてハイスペックなノートPCで10分くらいで結果が出てほしいです。
  • 内部で乱数を振って「何億分の一」の確率で正解が表示できる、みたいなものは不適とします。99%以上の確率での期待された結果の表示をお願いします。
  • プログラムは適切なところで正常終了してください。表示がとまらなくてユーザの操作によって中断しなければいけないものは不適とします。
    • 正常に終了するためにも、最後には改行コードを出力してほしいです。実行直後にプロンプト位置が乱れるかもしれないので。
  • プログラム実行時やコンパイル時に追加の情報を与えたり取得するようなものは不適とします。実行ファイルのファイル名に依存するような実装も不適合です(たとえばファイル名の一部が円周率になっていて、それを表示させるとか)。

C言語による例示

  • 今回は背景のところで十分に例示できていると思うので、省略します。

そのほかの特記事項

  • 今回は最初ということもあり、preconditionsの中の登録日が2015.12.10までのものをすべてOKとします。
  • 今回はOSECPU-VMによるエントリは競争せずに参考程度とします。

エントリ状況

  • この欄はKが随時編集しますので、勝手に編集しないでください。エントリーしたい、自己記録を更新した、Kの書き間違いを見つけたので直して、などは、下記のこめんと欄にお願いします。
    • 何バイトを達成したか、使ったツールは何か、可能であれば発表会に出たいか、などを明記してください。
      J言語13バイト2015-12-02 (水) 14:45:37ttwilb<.@o.10x^100
      Ruby 2.2.247バイト2016-01-13 (水) 21:42:46ryna
      Python60バイト2015-12-15 (火) 10:43:29hikalium
      J言語63バイト2015-12-01 (火) 22:29:26hikalium
      .COMバイナリ81バイト2015-12-02 (水) 12:55:35Knaskで実装, デコーダ方式, 100桁
      JavaScript95バイト2015-12-01 (火) 20:42:51ttwilb
      JavaScript120バイト2015-11-29 (日) 16:22:46hikalium198桁
      C言語440バイト2015-12-01 (火) 20:42:51ttwilb500桁, デコーダ方式
      (r3未完成)62バイト2015-12-02 (水) 13:29:08K多倍長演算方式, 1.5万桁

こめんと欄

  • Javascript, 158バイトでお願いします。 -- hikalium 2015-11-26 (木) 20:20:48
  • JavaScript 111バイトで登録します -- ttwilb 2015-11-26 (木) 22:05:15
  • Javascript, 120バイトで198桁に更新します。 -- hikalium 2015-11-29 (日) 16:22:46
  • hikaliumさんから、最後に表示する数字を7ではなく8にしてもよいかという質問を受けました。というのは、円周率を90桁目からを書くと
    5342117067 9821480865
  • となって、実は...7068のほうが真のパイの値に近いのです。
  • この提案はなるほどと思ったので、認めることにします。つまり最後の数字は7でもいいですが8でもよいです。 -- K 2015-12-01 (火) 14:27:43
  • 今度もこのような発展的な提案がありましたら、どんどん教えてください。>みなさま -- K 2015-12-01 (火) 14:28:48
  • C言語 500桁 440バイト デコーダを実装しています。 -- ttwilb 2015-12-01 (火) 20:39:58
  • JavaScript, 95バイト -- ttwilb 2015-12-01 (火) 20:42:51
  • J言語, 63バイトでお願いします。 -- hikalium 2015-12-01 (火) 22:29:26
  • J言語の破壊力がすごいです! -- K 2015-12-02 (水) 11:34:39
  • MS-DOS用にデコーダ方式でやってみました。81バイトまでしか行きません・・・。手ごわい! -- K 2015-12-02 (水) 12:55:35
  • OSECPU-VMの未来の仕様で作ったらどうなりそうなのかも書いてみます。これはトップのJ言語がいかに限界に迫っているのかを示すためです。62バイトでした。 -- K 2015-12-02 (水) 13:29:08
  • OSECPU-VMが可変長の整数精度をサポートしたとすると(Rubyみたいに)、100桁なら33バイトで行けそうです。 http://k.osask.jp/wiki/?prog/02 の割り算を使わないバージョンのアルゴリズムでやっています。割り算版だとさすがに遅すぎると予想されるので。 -- K 2015-12-02 (水) 13:54:05
  • 英語版Wikipediaより,J言語では
    n=: 100
    <.@o. 10x^n
    で円周率を表示できます-- ttwilb 2015-12-02 (水) 14:45:37
  • なんですと!・・・ もしかしてnすらいらなくて、 <.@o. 10x^100 で行けてしまうのかな。うう、これはもうJ言語が圧勝の予感。テーマの敗北ですね・・・。 -- K 2015-12-02 (水) 14:53:15
  • それでいけます!空白も不要なので13バイトになります…。 -- hikalium 2015-12-02 (水) 15:07:23
  • これは100の部分を999にすれば、バイト数が変わらずに999桁までは行けてしまうんだなあ、きっと。 -- K 2015-12-02 (水) 15:17:01
  • とりあえずJ言語の13バイトは1位確定として、円周率命令を使わないでどこまで行けるのかの競争を続けましょう。 -- K 2015-12-02 (水) 15:19:02
  • GNU bcだとscale=100;4*a(1)で小数点以下99桁まで正しく出ます。 -- 名無しさん 2015-12-02 (水) 17:45:46
  • どうもありがとうございます! bcってなんだ・・・と調べて納得。計算機ツールなのですね。a()はarctanで、だから4倍するとパイになると。なるほどなあ。これだと16文字なので改行込みで17バイトと言えそうです。でも残念ながらbcは「使ってもよい言語」や「使ってもいいツール」にはなっていませんので参考記録ということで。 -- K 2015-12-02 (水) 18:12:11
  • もっと一般的ではない無限級数の和を求める課題にすればよかったなあ・・・。 -- K 2015-12-02 (水) 18:13:41
  • 変数や関数、制御構造もある軽量プログラミング言語ですね。https://ja.wikipedia.org/wiki/Bc_(UNIX) >計算機ツールなのですね。 -- 名無しさん 2015-12-02 (水) 18:17:02
  • はじめまして、Rubyのバージョン2.2.2にて、53バイトで登録します。とりあえず、このコメント欄で宣言だけすれば良いのでしょうか? -- ryna 2015-12-10 (木) 15:26:03
  • 53バイト…すごいですね。そうですね、そのうちKさんが確認して追加してくださると思いますー>ryna -- hikalium 2015-12-10 (木) 21:54:37
  • やはりRubyは強いなあ・・・。J言語の「これは一本取られた!」の13バイトを除外すると、まじめに計算している系では最強です!! -- K 2015-12-11 (金) 13:39:56
  • python, 60文字で登録します。 -- hikalium 2015-12-15 (火) 10:43:29
  • 更新しました,Rubyで51バイトでお願いします -- ryna 2015-12-16 (水) 17:51:41
  • Rubyがぶっちぎりですごいのはもちろんなのですが、Pythonで60バイトができるとは!という感嘆の声も一部では挙がっております。 -- K 2015-12-17 (木) 11:33:59
  • 締め切りが過ぎてしまったかもしれませんが、Ruby 2.2.2で47バイトいけました。 -- ryna 2016-01-13 (水) 21:42:46
  • rynaさんのRuby 47バイトがまだ反映されてないです! -- ttwilb 2016-01-27 (水) 00:15:31
  • ttwilbさん、ご指摘どうもありがとうございます! -- K 2016-02-03 (水) 17:41:53

コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-02-03 (水) 17:41:53 (1349d)