フェルマーの最終定理の反「反例」(MPFR対応Gawk)


4904807154かつて、awk用のフェルマーの最終定理の「反例」を紹介したことがありましたが、最近のGawkでは「反例」にならないようです。

Ubuntu 16.04のGawkで試せます。

$ echo '5999856 99992800 100000000' | gawk '{print $1**3+$2**3-$3**3}'
0

$ echo '5999856 99992800 100000000' | gawk -M '{print $1**3+$2**3-$3**3}'
-2985984

Ubuntu 14.04の場合は準備が必要です。

下の方法では、管理者権限を使ってふつうにインストールしています。アンインストールする場合は、作業ディレクトリで「make uninstall」としてください。

sudo apt-get -y install texinfo libmpfr-dev libgmp-dev

git clone git://git.savannah.gnu.org/automake.git
cd automake-1.15
./configure && make && sudo make install
cd ..

git clone git://git.savannah.gnu.org/gawk.git
cd gawk
./configure && make && sudo make install
cd ..

参考:GNU AWKはまだまだ成長中! ユーザーの声をもとに作成された拡張機能を組み込んでみよう

MathematicaのFindShortestTourのバグ


先日CodeIQで、巡回セールスパースン問題を出題しました。

Mathematicaには、指定した点をすべて通る最短の巡回路を求める関数 FindShortestTour があるので、これを使えば簡単なはずでしたが、実はそこにはトラップがあったかもしれません。

追記:問題は3つありますが、Mathematica 10.4.1, 11.2で未解決なのは3番目のみです。

問題1(10.0.2 for Windowsで解決)

Mathematica 10.0.1 for Windowsでは、{{6, 2}, {4, 6}, {3, 4}, {6, 7}}という4点を通る最短巡回路を求められませんでした。

問題2(10.0 for Linux ARM (32-bit) (August 4, 2014)で解決)

10.0 for Linux ARM (32-bit) (January 29, 2014)の FindShortestTour は、仕様がマニュアルと違っていました。

pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 1}, {5, 2}, {5, 3}, {5, 4}};
FindShortestTour[%]

マニュアルによれば、巡回路の最初と最後は同じ(この例では1)はずなのですが、ここで得られる結果は「{14 + 5 Sqrt[2], {1, 2, 7, 3, 4, 5, 8, 12, 11, 15, 19, 14, 18, 17, 16, 13, 9, 10, 6}}」で、仕様とは違っていました。

問題3(10.4.1, 11.2, 11.3 for Windowsで未解決)

1分待っても結果が返ってこない場合があります(Core i7-4930K)。(Wolfram/Alphaでは計算できたこともある

FindShortestTour[{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0, 536870913}}]

浮動小数点で近似値だけでも・・・と思っても、やはりダメな場合があります(カーネルが落ちます)。

FindShortestTour[{{1., 0}, {0, 1}, {6421482390570520, 4284269602932036}, {239817909316376, 7744567430237013}, {2528914430818969, 5966759469595075}}]

マニュアルでは見つけられませんでしたが、「Method -> "IntegerLinearProgramming"」を付けておくとうまくいくと、サポートから教えてもらいましたが、計算はできても結果が正しくない場合があります。(この例でオプションを外すとカーネルが落ちます。)

cities = {
 {12581820340729273, 10017935966728831},
 {12754218452664193, 14539145895971681},
 {14822745302277607, 14565274414261943},
 {11873373307008371, 9781014188323403},
 {16116822349097741, 15873203518310113},
 {12701673778654019, 11291535066125623},
 {9392560345300883, 14963106019249771},
 {11529795864075473, 17759422650313613},
 {9007199254742147, 18014398509483463},
 {9007199254742149, 18014398509483461}};
FindShortestTour[cities, Method -> "IntegerLinearProgramming"]

一部のバージョンでは、巡回路{1, 4, 7, 9, 10, 8, 5, 3, 2, 6, 1}が得られますが、正解は{1, 4, 7, 10, 9, 8, 5, 3, 2, 6, 1}です。

何も気にせず使えるようになるにはまだ時間がかかりそうです。

名前に非ASCII文字を含むユーザーがRを使う方法


注意:名前に非ASCII文字を含まないにもかかわらずうまく行かない場合にも遭遇したことがあります。その時は、セキュリティソフトを一時的にオフにすることで解決できました。

Windowsでは、ユーザー名に非ASCII文字を含めることができますが、ユーザー名が非ASCII文字を含んでいるといろいろ問題が起こります。たとえばRでは、パッケージのインストールに失敗します。

Windows環境で「R」を導入するための絶対確実な方法という記事によると、(1)マルチバイト文字を含まない名前のユーザーを新たに作り、(2)マルチバイト文字を含まない名前のディレクトリにRやRStudioをインストールすればいいそうです。

しかし、ユーザーを作り直すのはかなり大変な作業ですし、そもそも、共有PCなど、管理者権限を使えない状況では不可能です(絶対?)。

そこで、管理者権限が無くても使える、ユーザーを作り直さなくていい方法を紹介しましょう。

RStudioを使わない場合

  1. インストーラのいいなりにRをインストールする。
  2. c:/rlibsのような、ASCII文字だけで構成される名前のディレクトリを作り、環境変数R_LIBS_USERの値がこのディレクトリ名になるようにする。
  3. WIndowsを再起動する。

RStudioを使う場合

  1. Rをアンインストールし、c:/Users/ユーザ名/Documents/Rを削除する。
  2. c:/Rのような、ASCII文字だけで構成される名前のディレクトリを作り、そこにRをインストールする。
  3. c:/RStudioのような、ASCII文字だけで構成される名前のディレクトリにRStudioのzipファイルを展開する(管理者権限がないため、インストーラは使えない)。
  4. c:/tmpのような、ASCII文字だけで構成される名前のディレクトリを作り、環境変数TMPの値がこのディレクトリ名になるようにする。
  5. WIndowsを再起動する。

管理者がアプリをインストールし、標準ユーザーがアプリを利用するという、MacやLinuxでは一般的な運用方法を採用している場合は、次のような方法でも大丈夫です。(環境変数TMPの値を変更しています。ここで指定したディレクトリを削除すると、Excelなど,他のアプリに悪影響があります。)

  1. 管理者としてインストーラを起動し、インストーラのいいなりにRとRStudioをインストールする。
  2. c:/rlibsc:/tmpc:/homec:/ruserのような、ASCII文字だけで構成される名前のディレクトリを作り、環境変数R_LIBS_USERTMPhomeR_USERの値がこれらのディレクトリ名になるようにする。環境変数は、コントロールパネルの検索窓に「PATH」と入れて出てくる「環境変数の編集」をクリックして編集する。ここで挙げた例ならば、次のように設定する。
    変数
    R_LIBS_USER c:/rlibs
    TMP c:/tmp
    home c:/home
    R_USER c:/ruser
  3. WIndowsを再起動する。(不要かも)

Windows 10上のR 3.3.2、RStudio 1.0.136で動作を確認しています。

MacやLinuxに比べると、Windowsはいろいろよくわからない部分があるのは確かですが、ここで扱っている問題は、Windowsの問題というよりは、RやRStudioの問題という気がします(テストが不十分)。WindowsもMacのように、サポート期間を短くして、古いユーザーをどんどん切り捨てていくなら、こういうことは少なくなるのでしょうが。

白と黒のとびら


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

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

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