大人の塗り絵:塗り分けに五色必要な地図(1975年のエイプリルフール)


4102184619四色あれば,地図上の隣り合う領域の色が同じにならないように塗り分けられるという「四色定理」は,1800年代後半に予想され,1976年にコンピュータを使って「証明」された。

定理が「証明」される前の1975年に,マーチン・ガードナーが塗り分けに五色必要だとして発表した次の絵が話題になったという。(参考:Martin Gardner's April Fool's Map

これはエイプリルフールのネタだったのだが,四色で塗り分けたという手紙が数百通届いたらしい。(ロビン・ウィルソン『四色問題』(新潮社, 2013)p.38)

この大人の塗り絵をやってみたい。

0387753664Mathematica in Action で,塗り分ける方法が紹介されているのだが,http://extras.springer.com/からダウンロードできるコードは,最近のMathematicaでは動かない。(Mathematicaの言語仕様は後方互換性を保持しながら進化しているのだが,外部パッケージが本体に取り込まれた場合は,大抵うまくいかない。)

そこで,簡易版を作る。領域の境界線が垂直または水平の2pxの黒い実線の場合にのみ対応するという意味で「簡易」である。

Importで画像を読み込み,MorphologicalComponentsで領域に分割する(Colorize[matrix]で描画)。

四色で塗り分ける。(参考:ヨーロッパの地図の4色を求める

色を1組の真偽値で表し,色が同じでないという条件を連言標準形で記述することで,高速化している。

細かい注意:上の結果は周りが海に囲まれていても大丈夫なように,条件を追加して求めたもので,このコードの結果とはちょっと違うものになっている。

最後の描画はColorize[matrix, ColorRules -> cTable]でもいいのだが,この関数にはバグがあり,Mathematica 10.4.1では正しく動作しない。(製造元には報告済み。Ver.11で修正された。

Mathematica 10.4のRegionPlotのバグ


10.3.1ではできたことが,

10.4でできなくなってしまいました(10.4.1, 11もダメ)。(報告済み)

Mathematicaのサジェスチョンバーはオフにすべき(10.4)(10.4.1で修正)


10.4.1で直ったようです。

Mathematica 9で導入されたサジェスチョンバーのせいで計算結果がおかしくなることがあるようです。テクニカルサポートにバグを報告したら,その回答として教えてもらいました。

例1:以下のコードを1行ずつ実行するとMathematicaが落ちます。

m = SparseArray[{{0, 1, 0}, {1, 0, 1}, {0, 0, 0}}];

n = Map[With[{s = Total[#]}, If[s == 0, #, #/s]] &, Normal[m]];

n.n

例2:以下のコードを1行ずつ実行するとコンテキストが勝手に変わってしまいます。

Context[]

f = Solve[{2 x + y == p, x - 2 y == q}, {x, y}][[1]];

x + y ≤ 4 /. f

Context[]

せっかくフロントエンドとカーネルを分けているのにどうしてこんなことになるのか不思議ですが,文句を言っても計算結果は変わらないので,以下の資料に従って,サジェスチョンバーはオフにしておきましょう。

入力予測インターフェースの機能をオフにする方法

(インテルとAMDのCPUの)三角関数は不要


インテルとAMDのCPUには,三角関数を数値的に計算するための命令が備えられていますが,その結果は正しくありません。たとえば,CPUの命令FCOSの結果とstd::cosでソフトウェア的に計算した結果を比べると,後者の方が真の値に近くなります。

再現のためのコード(FCOSを使う部分だけインラインアセンブラを使っています。)

Core i5 6600とg++ 4.8.4で試した結果はこんな感じです。

x = 0.98233490762409514385
c1 = fcos(x)     = 0.55508189550073283591
c2 = std::cos(x) = 0.55508189550073294694
c  = mp::cos(x)  = 0.555081895500732891425063460345544265145531916268
abs(c - c1) = 5.5512e-17
abs(c - c2) = 5.551e-17

c1 is better: 0
c2 is better: 25
total: 100000

(その正しさをどうやって確かめるのかという問題はありますが)Boost.Multiprecisionで計算した結果と比較すると,命令`FCOS`より`std::cos`の方が正確なようです(Visual Studioの場合はまた違った結果になるようです)。

Pentiumが割り算を間違うといって大騒ぎになったことがありましたが(Pentium FDIV バグ),数値計算はどうせ近似値だからでしょうか,この問題は,ドキュメントに注意書きが追記されただけで,根本的な解決はされないままのようです。

おまけ:

結論:CUDAのcos,FCOS,gccのstd::cos(double)の順に正確になります。もちろん,gccのcos(long double), gccのcos(__float128), boost/multiprecisionは,さらに正確です。

JavaではMath.cosとStrictMath.cosがどっちもどっちだったり,数値計算は難しいです。

参考:サイン、コサインをインテルの CPU で計算すると少しバグっているらしい

MathematicaのMaxValueとMinValueのバグ


Mathematica 10.1, 10.2, 10.3, 10.4.1, 11

Mathematicaの最大化MaxValueと最小化MinValueには,簡約のためのSimplifyの中では使えないというバグがあります(製造元には報告済みです)。

例として,0 <= t <= 1, 0 <= p <= 2 Pi, 0 <= q <= 2 Piという制約のもとで,f = Abs[t Sin[p] Sin[q]]という関数の最大値と最小値を求めます。

f = Abs[t Sin[p] Sin[q]];
cond = And[0 <= t <= 1, 0 <= p <= 2 Pi, 0 <= q <= 2 Pi];

当たりを付けるために,まずは数値的に求めます。

{NMaxValue[{f, cond}, {t, p, q}], NMinValue[{f, cond}, {t, p, q}]}

結果が{1., 0.}になることに,特に問題はないでしょう。

解析的に求めようとすると,うまく行きません。

MaxValue[{f, cond}, {t, p, q}]
(*結果は割愛。入力がそのまま返される*)

こういう関数の最大・最小は,そのままではうまくいかないとしたものです。残念ですが,これはしょうがない。

しかし,Simplifyの中で使うと計算が進むことがあります。制約条件を仮定して結果を整理することを試みます。

Simplify[MaxValue[{f, cond}, {t, p, q}], cond]

得られる結果は「∞」,もちろん間違いです。MinValueの場合も同様で,「-∞」という間違った結果が得られます。

Simplifyの仮定(外側のcond)が,MaxValueの制約(内側のcond)を簡約しているのが一因だと思います。そういうことがあるのは,次の例でわかります。

Simplify[MaxValue[{1/x^2, 0 < x}, x, Integers], 0 < x]

結果はMaxValue[{x^(-2), True}, x, Integers]になります。制約がTrueになっていますが,これはいけません。

Tweet-a-Programではちょっと違うことが起きているみたいです(こういうのは初めて見ました)。

他に原因があるかどうかはよくわかりません。

MaximizeMinimaizeでは,この問題は発生しません。一般に,MaximizeMinimizeMaxValueMinValueより遅いということになっているのですが,速さよりは正確さが大事なので,こちらを使った方がいいのかもしれません。