Help us understand the problem. What is going on with this article?

円周率13兆桁から特定の数列を検索するプログラムを作りました

More than 3 years have passed since last update.

2017/07/25追記

 情報源(http://piworld.calico.jp/index.html)のサイトが消滅しまったことにより、以下のコードが使えなくなりました。新たな情報源を探しませんと……

概要

 ある方から「円周率から特定の数列を探せないか」という依頼がありました。1.6万桁100万桁辺りまではWeb上で簡単にアクセスできますが、それ以上となると計算結果をlzhzipなどでうpしている場合が多いです。特に後者のサイト(http://piworld.calico.jp/index.html)だとギネス記録の13兆桁(2014年10月7日に達成)までアクセスできるのでオススメなのですが、いちいちzipファイルをダウンロードして検索するのは面倒ですよね?
 というわけで、全自動で行えるようにするツールを作成しました。

※円周率世界記録を達成したソフト「y-cruncher」はここからダウンロードできます。
http://www.numberworld.org/y-cruncher/

まずはzipをダウンロードしよう

 とりあえずRubyで実装することにしたわけですが、そもそもRubyでzipファイルはどう扱われるのでしょうか?
 そこでググッたところ、zipファイルを扱えるライブラリがあることが判明。「gem install rubyzip」で入るので早速導入しました。で、解凍自体は問題なく高速に行える……のですが、zipをダウンロードするのが辛かった
 まずファイル自体のサイズが大きいので、光回線でダウンロードしようにも1ファイル20秒近くかかります。1ファイルには1億桁が収められているので、これが13万個もあると考えるだけで頭がくらくらしてきました。1ファイルの大きさは約57MBなので、円周率全体で7TB以上(全てダウンロードするのに30日)存在することになります!
 ちなみにダウンロードする際のURLですが、次のようなルールで決められているようです。

  • ファイル名は、sprintf("pi-%04d.zip",k)
  • ファイル名の1つ上の階層は、"pi-"+(((k-1)/1000+1)*100).to_s+"b"
  • ファイル名の2つ上の階層は、k=1~34000まで"value"、それ以降が"value"+((k-1)/34000+1)

次にテキストを読み取ろう

 さて、zip内のテキストファイルは、次のように記録されています。
cap.png
 つまり、10桁毎に半角空白・100桁毎に改行・1ファイルに100万改行というわけです。文字コードはShift_JIS・CRLFですが、どうせASCII文字しか無いので瑣末な問題でしょう。
 幸い、検索自体は遅くない(最初の1億桁から「1683139375」を探しだすのが一瞬だった)のですが、問題は加工。半角空白および改行部分をどう対処するか……と考えつつ適当にgsub!(/ |:.+|\n/, '')したところ、3秒ほどで置換が完了しました。ダウンロードの重さを考えると許容範囲内ですね。
 ただ、こうなると次に気になるのが、数列が複数ファイルに跨る際の対処です。流石に3ファイル以上に跨るケースは無視するとしても、2ファイルの境界に跨るケースは考慮する必要があります。そこで、ファイルを読み込んだ後、バッファに前のファイルの1億桁+今のファイルの1億桁と足し合わせて検索することにしました。そこそこメモリを食うことになりますが仕方ありませんね。

完成したコードがこちらになります

 ダウンロードしたzipファイルを2度もダウンロードしないようにしたので、1回実行すれば2回目以降は高速に実行できます。もっとも、大量に・かつ高速に検索クエリが存在する場合は、ハッシュに格納する等の改造を加える必要がありますが。

search.rb
require 'open-uri'
require 'zip'

# 検索する終端(最大130000まで)
max_files = 5
# 検索したい文字列
str = '1234'

const_number = 100000000 #1億
txt_data = ''
1.upto(max_files){|k|
    puts k.to_s + '億桁目まで...'
    # ダウンロードするURLを生成する
    url = 'http://piworld.calico.jp/value'
    if k <= 34000 then
        url << '/'
    else
        url << "#{(k - 1) / 34000 + 1}/"
    end
    url << "pi-#{((k - 1) / 1000 + 1) * 100}b/"
    url << sprintf("pi-%04d.zip", k)
    # ダウンロードする
    file_name = File.basename(url)
    unless File.exist?(file_name)
        open(file_name, 'wb'){|output|open(url){|data|output.write(data.read)}}
    end
    # ZIPファイルを解凍し、中のファイルを読み取る
    txt_data_ = ''
    Zip::File.open(file_name) do |zip_file|
        zip_file.each do |f|
            txt_data_ = zip_file.read(f.name)
        end
    end
    # 整形処理
    txt_data_.gsub!(/ |:.+|\n/, '')
    txt_data = txt_data[const_number, const_number] if k > 2
    txt_data << txt_data_
    # 検索処理
    pos = txt_data.index(str)
    unless pos.nil? then
        puts "☆発見しました! 位置:小数点以下#{(k == 1 ? pos + 1 : (k - 2) * const_number + pos + 1)}桁目"
        break
    end
}
puts '検索終了'

参考

ファイルをWebからダウンロードして保存する

YSRKEN
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした