« 「アフター・ドット問題」の高度じゃないコード(ゴルフ編) | トップページ | 「階乗フィーバー数問題」の高度じゃないコード »

2016年7月 7日 (木)

「アフター・ドット問題」の高度じゃないコード(高速編)

「高度じゃないコード」シリーズその14「アフター・ドット問題」、その後編(高速編)です。

前回のままのやり方ではそんなに高速にはならないだろうから、根本的に処理を変える必要がありました。まず、前回、b を 2 と 5 で割れるだけ割って b' を求めましたが、逆に、この b' を基準に考えてみます。さて、b' とは 2 でも 5 でも割り切れない数字なので、一の位が 1, 3, 7, 9 の自然数です。それ以外の、一の位が 0, 2, 4, 5, 6, 8 の数字は、b' に 2 と 5 をある回数掛けることで出てきます。

ここで、ある b' に対して、2 と 5 のべき乗の積を掛けたのが b ということになるので、n ÷ b' 以内に存在する 2 と 5 のべき乗の積の数が b の取り得る値の数(これを x とします)、そして、a の取り得る値の数は、前回と同様、n ÷ b'(これを y とします)なので、その2つの積( x × y )を求めればいいわけです。

さて、このように、n 以下で、一の位が 1, 3, 7, 9 の自然数全てで上記の計算をやれば答えは求めることができますが、個別に計算していたらやはり時間がかかります。そこで、上記の x が同じ値になるものを纏め、またその中で、y に関しても商によって個別で計算する部分と、同じ商が並ぶ部分は纏めて計算することで高速化することにしました。まずは、Ruby のままで、この考え方でコードを作ってみました。実行くんで 1011 が 0.9s でした。(ただし、バージョンアップ後は 0.67s に向上)

この結果から Ruby の限界を感じ、C に切り替えることにしました。少しアルゴリズムの改良をしつつ C に移植したのが次のコードです。実行くんで 3×1014 が 0.84s になりました。

さて、ここで、禁断の技を使ってみることにしました。それは、インラインアセンブラです。最も時間が掛かっている部分をアセンブラで直に書けばさらに高速化するのではないかと考えたわけです。ただ、それまで、nasm を使った単純な処理しか作ってなかったので、インラインアセンブラの使い方で四苦八苦しましたが、何とか、正しい結果が出せるようになりました。

さて、どきどきしながら、実行くんで 3×1014 を実行!・・・え?・・・まじ?・・・ 0.99s って、遅くなってるじゃん!ということで、インラインアセンブラで数日掛けて作った処理は、gcc(C コンパイラ)の最適化に完全に敗北してしまいました。最大のネックとなっていると思われる、64bit 同士の除算処理をもっと頑張れば、あるいは勝負になったかもしれませんが・・・。

インラインアセンブラは手間も時間もかかるし、このように元よりも悪化した時のがっかり感が半端ないのでやめて、C のみで頑張ることにしました。で、再度、考えていると、今まで、なぜ気付かなかったのだろうということにやっと気付きました。ここまでの処理では、y に関して個別で計算するか同じ数字で纏めるかは、その都度、計算によって処理を分けていましたが、そんなことをする必要はなく、ある値より下か上で分ければいいのでした。そして、それを踏まえて、次に示す、高速版の最終提出バージョンを作りました。これだと、実行くんで 1.5×1015 が 0.97s でした。

あれ?こうして実際に書いてみると、そんなに長くはならなかったですね・・・。

|

« 「アフター・ドット問題」の高度じゃないコード(ゴルフ編) | トップページ | 「階乗フィーバー数問題」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63884106

この記事へのトラックバック一覧です: 「アフター・ドット問題」の高度じゃないコード(高速編):

« 「アフター・ドット問題」の高度じゃないコード(ゴルフ編) | トップページ | 「階乗フィーバー数問題」の高度じゃないコード »