白と黒のとびら

4130633570川添愛『白と黒のとびら: オートマトンと形式言語をめぐる冒険』(東京大学出版会, 2013)(参考文献リストあり・索引なし)

チョムスキー階層のすべてに対応するオートマトンを「扉を持った遺跡」に例えて組み込んだファンタジー。計算理論の基礎を学ぶのにはふつうの教科書の方がいいだろうが、ひと通り学んだ後なら楽しめるだろう。計算複雑性の理論など、進んだ話題を扱う続編に期待。

線形拘束オートマトン(ゼウ山の塔)への入力が、○と●という2つのボタンなのだが、塔はどうやって入力の終わりを認識しているのだろう。

スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C++)

追記:対称性の活用法をコメントで教えていただきました。それを採用すると本稿の結果よりもかなり高速になります(10分→2分30秒。解を数えるだけなら約90秒)。(コード。本文にはまだ反映していません。)

筑波大学のスパコン「T2K-Tsukuba」で約2時間36分かけて5×5の魔方陣(≠魔法陣)の全解を求めたというニュースがありました。

「スパコン」ではなく「パソコン」だったらどうなのだろう、と思って試してみたら、10分でした(Core i7 4930K)。

解の「数」がわかればいいだけ、つまり全解をディスクに書き出さなくてももいいならもう少し早くなります。

コードはこちら(最初のバージョン)。頭の悪そうなコードですが、スクリプトで生成した枠組みを手直しして作れば、そんなに大変ではないかと。理想は全自動生成ですが。Visual Studio 2013 ExpressとICC 14.0.2、GCC 4.6.3、Clang 3.4で動作を確認しています。ClangはOpenMPに対応させるのが面倒なうえに、ちょっと試したところでは、GCCより遅かったです。(実際に試す場合は、OpenMPを有効にしてください。計算中のCPU使用率は100%になるはずです。)

多重for文(笑)ですべての場合を探索するというのが基本方針ですが、それではさすがに終わらないので、次のような工夫をします(工夫というほどのものではありませんが)。

  • 各行・各列・対角線の和は65。(1から25までの和 / 5)
  • (カンで)効率が良くなりそうなところから順番に埋めていく(下図の番号順)。
  • 回転と裏返しで同一になるものを重複して数えないように、下図の緑部分に、「左上<右上<左下」かつ「左上<右下」のような制約を入れる。左上は22以下としてよい。
  • a+b+c+d+eのうち、a,b,c,dが決まったら、e=65-a-b-c-dになる(下図の紫部分)。
  • a+b+c+d+eのうち、a,b,cが決まったら、dはmax(1,65-a-b-c-25)からmin(25,65-a-b-c-1)の範囲で調べればよい。max(un,65-a-b-c-ux)からmin(ux,65-a-b-c-un)にするとさらに速くなる(unは未使用の最小数,uxは未使用の最大数。これを調べるのに時間をかけると効果はなくなる)。

この方針の場合、ループを関数で表現したり、盤面をコンテナで表現したりすると遅くなります。

数を埋める順番
6 10 11 12 8
20 1 18 2 21
22 13 5 16 23
24 3 19 4 25
9 14 17 15 7

魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、(「数」を求めるだけだとしても)GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します(Xeon Phiなら簡単なのでしょうか→追記参照)。

一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します(schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します)。変数iは上の図の緑の部分(カンで5個にしました)を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。

出力はバイナリ形式で、1つの解に25バイト使います(1つのマスに入る数を1バイトで表現する)。これもちょっと冗長ですが、テキスト形式よりは小さくて速いはずなので、とりあえずはよしとしましょう。

解は全部で2億7530万5224個、1つの解を25バイトで表現するので、(スレッド数と同数できる)出力ファイルのサイズの合計は275305224 x 25 = 6882630600バイト(約6.4GB)になります。

最初のバージョンの実行時間は以下の通りです。最終的には、先述の通り、もう少し速くなります。

Core i7 4930K(12スレッド・出力先はRAMディスク)
  • Windows 7 64 bit, Visual Studio 2013 Express, 593秒(約10分)(ターゲットはx64。/openmp /Ox /arch:AVX
  • Fedora 20 64 bit, Intel C++ Compiler 14.0.2, 471秒(約8分)-fopenmp -O3 -xHost
  • Fedora 20 64 bit, GCC 4.8.2, 583秒(約10分)-fopenmp -O3 -march=native
Core i7 4700MQ(8スレッド・出力先はSSD)
  • Windows 7 64 bit, Visual Studio 2013 Express, 1156秒(約20分)/openmp /Ox /arch:AVX

4535786569大森清美『魔方陣の世界』(日本評論社, 2013)(参考文献リストあり・索引あり)を見たら、a+b+c+d+e=65のとき、(26-a)+(26-b)+(26-c)+(26-d)+(26-e)=65なので、解の、すべての数xを(26-x)に置き換えたものもやはり解になるということが載っていました。コメントでご指摘いただいたように、この知識を使って、真ん中のセルに入る数字を1から13までに限定し、そこが13ではない解が見つかったら、すべての数xを(26-x)に置き換えたものも解として出力するようにするとさらに速くなります(同条件でちょうど6分)。

『魔方陣の世界』では、この問題のためのコードも紹介されていますが、並列化されていないこともあって、解の「数」を調べる場合は約5000秒(確認済み)、全解を出力する場合は約3日(未確認)と、あまりふるいません。

この問題は、パソコン・プログラミングに最適の題材である。(p.111)

今日では、5次方陣の総数検索問題は、パソコンに最適な題材となった。(p.124)

パソコンに最適とも、スパコンに不適とも思いませんが、興味深い題材であることは確かです。

追記

  • 正解の数(2億7530万5224個)を知っているから速いのか? 正解の数は1981年にはすでに知られていましたが、ここで試した方法では、その知識は使っていません。ディスクの空き容量は小さくてよいことがわかっているとか、下に書くような理由で、正解が既知だと試すのが気楽だということはあります。
  • 結果の正しさをどうやって確認したのか? 確認していません。解の数は既知なので、それと同じ数が出てくればまあいいかなと。正しさを確認するためには、(1)得られたものが本当に解であること、(2)結果に重複がないこと、(3)すべての場合を調べていること、の確認が必要です。(1)はループの最も内側で解になっているかどうかをチェックすることによって、(2)は得られた解をハッシュテーブル等に格納することによって確認できますが、ある程度のメモリと時間(上のマシンだと約200秒)が余分に必要です(コード)。(3)はここでは難しいですね。
  • アルゴリズム? 穴埋め問題の穴を多重for文(笑)で埋めているだけなので、アルゴリズムというほどのものはありません。(参考:Puzzles for Hackers
  • 10分くらいならやってみようかなという人が、きれいな書き方やGPUで解く方法、効率的な方法を見つけてくれればと思います。(参考:Toy problemsは役立たずか
  • Xeon Phiなら(ほぼ)そのままのコードが動いて、計算は5分で終わるそうです。(スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙をXeon Phiで試す – パラレルに恋して

Mathematica 10への期待(とその後)

昨年ついに無料になったMathematicaですが、思ったほど盛り上がってはいないようです。盛る上がらない原因の一つに、性能の悪さがあるのは間違いないでしょう。特にGUIはかなり重く、Manipulateなどでインタラクティブに遊ぶのは無理です。(無料のMathematicaが動くのは、700MHzのCPU、最大でも512MBしか主記憶のないRaspberry Pi上。)

実際にベンチマークを取ってみると、Windows上のMathematica 9.01(CPUはCore i7 4700MQ、主記憶は16GB)で10秒で終わるMathematicaMark9が、Raspberry Pi上では約3300秒かかりました(800MHzにオーバークロックして約3000秒)。Core i7で動かすエミュレータ上でもおそらく同じ程度でしょう。

しかし不思議なことに、Raspberry Pi上のMathematicaのほうが早く解ける問題があります。

たとえば、A^2 + B^2 == 1かつP^2 + Q^2 == 1という条件で、以下のsの最小値を単純にMinValueで「解析的に」求めようとすると、上述のWindowsマシンではなんと約20000秒かかるのに対して、Raspberry Piでは約2200秒で終わります。追記:Raspberry Pi 2では約800秒です。

s = 1/24 (3 Sqrt[3] Abs[A P] + Sqrt[3] Abs[A P + 2 Sqrt[2] Q] + 
     Abs[Sqrt[3] A P - 3 Sqrt[2] B P - Sqrt[6] Q] + 
     Abs[Sqrt[3] A P + 3 Sqrt[2] B P - Sqrt[6] Q]);

MinValue[{s, And[A^2 + B^2 == 1, P^2 + Q^2 == 1]}, {A, B, P, Q}]

(これは比較のために作った問題ではなく、実際に私が遭遇した問題です。実は、単純にMinValueを使うというのが間違っているのですが、本来Mathematicaはそういうことを気にせず使うソフトウェアのはずです。)

Raspberry Piの方が速い原因は、Windows版Mathematicaのバージョンが9.01なのに対して、Raspberry Pi版Mathematicaのバージョンが10であり、バージョン9.01と10の間で、このあたりのアルゴリズムが改良されたためだと思われます。

非力なRaspberry Piでの話なので、比較的速いCPUがあれば、エミュレートされたRaspberry Piでも同程度の時間でできるでしょうし(Windowsの場合Ubuntuの場合)、ユーザーモードエミュレーションならこの半分くらいの時間でできるでしょう(ライセンス違反なので想像しているだけです)。

というわけで、Windows版Mathematica 10のリリースを待っています。

追記:Windows版Mathematica 10がリリースされたので試したところ54秒でした(CPUはCore i7 4700MQ、主記憶は16GB)。Raspberry Piは約2200秒なので、遅すぎです

MathematicaのNMinimize, NMinValueのバグ

Ver.11で修正されました。

Mathematica 9.0, 10.0, 10.1, 10.2, 10.3, 10.4.1 for Microsoft Windows (64-bit)と10.0.0 for Linux ARM (32-bit)でのことです。

a2 + c2 == 1, b2 + d2 == 1という条件の下で、次のような関数の最小値を求めたいとします。

Mathematicaには最大・最小を求めるためのさまざまな関数が用意されていますが、NMinimizeMinimizeNMinValueMinValueは、頭にNをつけるかどうかで、数値的な方法と解析的な方法を切り替えられて便利です。最小値とその時の各変数の値を知りたいときは[N]Minimize、最小値だけを知りたいときは[N]MinValueを使います。

しかし、ちょっとうまくいかない例に遭遇しました。バグが修正されたバージョンを受け取るために、プレミアユーザになっています。

問題その1

f1 = Sqrt[
 1 + 4 Sqrt[3] b c d + d^2 - 5 c^2 (-1 + d^2) + 
  2 a (-Sqrt[2] b d + Sqrt[6] c (-1 + d^2))];

NMinimize[{f1, a^2 + c^2 == 1 && b^2 + d^2 == 1}, {a, b, c, d}]

このように実行すると、

関数の値4.35271 +1.45672\ Iは{a,b,c,d} = {0.79784,1.52261,-0.444508,0.634251}において実数ではありません.

という警告とともに結果{1.22618, {a -> -0.82781, b -> 0.492467, c -> 0.224354, d -> -0.333602}}が返ります。このとき、a2 + c2は約0.74、b2 + d2は約0.35なので、与えた制約条件から大きくずれています。

問題その2

f2の最小値を求めようとしたときにも問題が起こります。

f2 = Sqrt[
  1 - 4 Sqrt[3] b c d + d^2 - 5 c^2 (-1 + d^2) + 
   2 a (-Sqrt[2] b d - Sqrt[6] c (-1 + d^2))];

NMinimize[{f2, a^2 + c^2 == 1 && b^2 + d^2 == 1}, {a, b, c, d}]

このように実行しても、入力がそのまま返ってくるだけで、まとも(?)な結果が得られません(間違った答えが返ってくるよりはましかもしれません)。

この問題は、WolframAlphaでも起こります(2015年5月17日確認)。

f1に関しては間違った結果が返ってきます(下はNMinValueの場合。NMinimizeでも同様)。

f2に関しては、珍しいことに、WolframAlphaは完全に沈黙します(下はNMinValueの場合。NMinimizeは違う結果になります)。

MathematicaからWolframAlphaに問い合わせたときはまた違う結果で、f2は解釈できないとのことでした。ほとんど同じf1は解釈できたので、そんなことはないと思うのですが。

そもそも、こういう関数の最小値を何の工夫もせずに得ようとするのが間違いなのかもしれませんが、あえて工夫をしないのにも理由があるのです。それについては別の機会に書きます。

病的な計算式?(『ソフト・エッジ』から)

4621053833中島 震・みわ よしこ『ソフト・エッジ: ソフトウェア開発の科学を求めて』(丸善出版, 2013)で、数値計算の面白い例が紹介されていました。(参考文献リストあり。索引なし。)

精度を向上させれば近似はよくなるというのが、自然な考え方でしょう。でも、この直観に当てはまらない「病的な計算式」の例があります。(p.132)

ということで、f(a, b)=(333.75-a**2)*b**6+a**2*(11*a**2*b**2-121*b**4-2)+5.5*b**8+a/(2*b)としたときの、f(77617, 33096)が紹介されています。単精度・倍精度・4倍精度の浮動小数点数での計算結果は約1.17で、正しい値(約-0.827)とは符号も違ってしまうとのことです。

これだけ読むと、精度を向上させても近似はよくならないと思うかもしれませんが、そんなことはないはずです。実際、精度をある程度高くすれば、正しく計算できます。

Pythonで試します(ideone.comでも動きます)。

from decimal import getcontext, Decimal
for n in range(16, 40):
  getcontext().prec = n
  a = Decimal("77617")
  b = Decimal("33096")
  print(n, (Decimal("333.75")-a**2)*b**6+a**2*(11*a**2*b**2-121*b**4-2)+Decimal("5.5")*b**8+a/(2*b))
16 1.000000000000000E+21
17 -4.0000000000000000E+20
18 -2.00000000000000000E+19
19 2000000000000000001
20 -99999999999999998.827
21 1.17260394005317863186
22 -999999999999998.8273961
23 100000000000001.17260394
24 10000000000001.1726039401
25 -3999999999998.827396059947
26 -99999999998.827396059946821
27 -19999999998.8273960599468214
28 -999999998.8273960599468213681
29 100000001.17260394005317863186
30 20000001.1726039400531786318588
31 -999998.8273960599468213681411651
32 300001.17260394005317863185883490
33 -9998.82739605994682136814116509548
34 -1998.827396059946821368141165095480
35 -198.82739605994682136814116509547982
36 21.1726039400531786318588349045201837
37 -0.827396059946821368141165095479816292
38 -0.8273960599468213681411650954798162920
39 -0.82739605994682136814116509547981629200

このようにPythonでは、getcontext().precの値が37以上なら適切な結果が得られます。

Rubyでも、ちょっと工夫すれば適切な結果が得られます(ideone.comで確認)

Windows付属の電卓では、何の工夫も要りません(WIndows 7で確認)。xyのショートカットキーが「Y」なので、「(333.75-77617Y2)*33096Y6+77617Y2*(11*77617Y2*33096Y2-121*33096Y4-2)+5.5*33096Y8+77617/(2*33096)=」と打てば、適切な結果が得られます。

Mac OS Xでも計算できます(10.8.4で確認。できるようになったのは比較的最近のことだと思いますが)。「計算機」で計算する方法はよくわかりませんが、Spotlightに「(333.75-77617^2)*33096^6+77617^2*(11*77617^2*33096^2-121*33096^4-2)+5.5*33096^8+77617/(2*33096)」と入力すれば、適切な結果が得られます。

Windowsの電卓は32桁までの入力にしか対応していないので、230928922463004537535516678003369の平方根を求めたいというようなときに不便ですが、Spotlightなら、sqrt(230928922463004537535516678003369)とすればとりあえず計算できます。

参考:電卓に求められるコト

本稿執筆時点のWolframAlphaでは、まったく違う結果が2つ返ってきて、片方はあっていました

Googleはだめでした

Googleの例は別として、精度を上げてもうまくいかないようにするには、もっと「病的」でなければなりません。