メニエスの名のもとに

プログラミング関係を中心としたぐだぐだブログ

autotools対応中

これもウソ対応です

config.h とか作成されるけど、どこでも見ていません。まだgit pushしてないし。

shared library にしようとして失敗しました

OS X ではうまく shared library が作成されたんだけど、ubuntu でやったら作成できなかった。MTToolBox はNTLのライブラリに依存しているんだが、NTLはstatic libraryなんだよね。たぶん、そのせいだと思うので、あんまり追求しないで、さっさと諦めることにしました。

header ファイルのインストールで悩んだ

MTToolBox の正体はほとんど、C++のテンプレートヘッダーファイルなので、たくさんのヘッダファイルをインストールしなければならない。Unix系ではヘッダーは/usr/local/include にインストールすることになっているが、ファイル名の衝突が怖いので、/usr/local/include/MTToolBox/といったところにインストールしたい。つまりサブディレクトリにヘッダをまとめたい。そういうときには、pkginclude_HEADERS にヘッダファイルを記述すればよいとのことだった。
だが、それではmttoolboxとパッケージ名の部分が小文字に変換されてしまうのである。いやーん。既にヘッダファイルから他のヘッダファイルをincludeする部分に#includeとか記述しているので、全部変更しなくちゃならないじゃないですか。そこで、別のマクロでパッケージ名を指定するとか、変数に直接代入するとか、Makefile.amをやめてMakefile.inを直接編集するとかいろいろやってみましたが、駄目でした。しかし、最後にautomake の manual を見て(最初に見ろって)わかりました。

nobase_include_HEADERS = MTToolBox/*

パッケージ名を変更しないで、ヘッダのインストール先を変更できた。本当はtar ballもMTToolBox-0.2.1.tar.gz とかにしたかったのだが、まあtarball名は小文字でもいいや。

名前の衝突の問題

Unix系で/usr/local にインストールするのはシステムファイルと名前の衝突を避けるためだが、みんなが /usr/localにインストールしたら結局名前の衝突が起こる。mac ports だと opt/local だけど、やはりみんな同じところにインストールするので名前の衝突は避けられない。まあ、昔のUnix 系のコマンドはls とか短い名前だったけど、これからは可能な限り長い名前にした方がいい。
とか言っているうちに、はっと気がついてMTToolBoxで検索すると、既にあるんだなあ。駄目じゃん。だいたいToolBoxなんてツール的なプログラムには誰もが付ける名前じゃないか。そうすると最初のMTだけがユニークだけど二文字だから衝突しない方がおかしいくらいだ。バカじゃん、俺。略するならtoolboxの方をTBって略すべきだろうが。MersenneTwisterTBなら、衝突しなかったし、衝突してもウチらMersenneTwisterの本家だからお前らが名前変えろって言えないこともなかった。っていうか、名前の衝突を避けるには省略禁止にするべきなんだろう。MersenneTwisterPseudoRandomNumberGeneratorDevelopmentToolBox とかいう名前にしておけば、まず衝突しない。いやいや、一般名詞では衝突の危険は減らないだろう。ここは、アレあのI18Nみたいな掟破りの省略法を混ぜて、MersenneTwisterP4OR4MN4RG7RD9TTBとかにすればいい。おお、これならまず衝突しないはず。いや、規則的に名前をつけている以上衝突は起こる。しかしあまり長い名前にすると、Common Lispグローバル変数みたいに、使わせないためにわざと長い名前にしたと思われる可能性がある。
バージョン0.2 だから、この際パッケージ名をMersenneTwisterToolBox にしてバージョンを1.0にすることで妥協しようかな。といいつつ、別の用があるのですぐには公開されないのであった。

autotools 対応しました。

実は対応していない。

MSaito/NumPl · GitHub
./configure でコンパイルできるようにした(つもり)。その意味では、autotools 対応をした。しかし、環境依存をみてコードを変えるとかいうことはしていない。その意味では対応していない。autotoolsを利用しているとは言い難いのだ。だって、c99 に対応していないコンパイラでもコンパイル出来るようにするとか、面倒じゃないですか。まあ、GitHubで公開してるんだから、動かない環境の人からはpull request が来るでしょう。そしたら取り込むという方針でいくのです。
しかし、./configure 後の make dist で作成されるtarballとGitHubで管理されるソースに差があるような気がするのが困る。こういうの一般的にはどうするんだろう。
そんなことを読者のいないブログで聞いても誰も答えてくれないし、フォロワーのいないtwitterで聞いてもやはり誰も答えてくれないのだ。Google で検索するのも難しい。autotools 対応で疲弊しているのでちょっとやさぐれモード。

reducible ブランチをpushしました。

可約ジェネレータ開発ツール

疑似乱数生成器開発用ツールMTToolBoxの新機能、可約ジェネレータ開発ツールを入れたreducible ブランチをMSaito/MTToolBox · GitHubにpushしました。まだマージしてないけど、sample として Reducible MTを付けたので、使いたい人は試してみることができるとおもいます。

Scons でうまくコンパイル出来なかった問題(解決済み)

Scons でうまくコンパイル出来なかったのは、osx の場合 Scons がpathの設定に係わらず /usr/bin/g++ を使っているからであり、そしてそれは実際にはg++ではなく clang++ だったというところまでは、前回分かっていたのですが、なぜclang++だとストリーム関係がエラーになるか分からなかった。エラーメッセージをちゃんと読むと、使用しているライブラリのNTLで使っているストリームがエラーになっていたのであった。そういや、clang は LLVM だから、gcc とオブジェクト互換性がないんじゃないの?ってことで、コンパイラにclang++を指定して NTL のライブラリを作り直ししたら、うまくコンパイルできました。オブジェクト互換性じゃなくて、C++のライブラリ互換性がないという方が正しいのかも。そこはあまり追求したくない。

重大なバグ

TinyMT と XSadd についての重大なバグが報告されました。

xsadd_float, xsadd_double, tinymt32_generate_float, tinymt64_generate_double 関数は[0, 1)区間の浮動小数点数、つまり0以上1未満の数を返すはずですが、バグにより1.0を返すことがありました。
修正済のバージョンは
https://github.com/MersenneTwister-Lab/TinyMT
https://github.com/MersenneTwister-Lab/XSadd
からダウンロードして下さい。

浮動小数点数への変換バグ

TinyMTとXSaddの前に開発したSFMTとMTGPでは、浮動小数点数への変換はIEEE 754形式のビットパターンを作って、それを浮動小数点数として解釈し直すという方式でした。この方式は、SIMDGPUでは高速なのですが、通常のCPUでは一度メモリに書いてから読み直すので遅くなります。それでも、一度にまとめて疑似乱数を作成する場合には、もともとそのためのメモリアクセスがあるので遅くならないのですが、呼び出しの度に疑似乱数を生成する方式では遅くなります。
TinyMTやXSaddの開発動機は、メモリの小さな疑似乱数生成器を作ることにあったので、SIMDも一度にたくさんの疑似乱数を生成するという方法も使わないと決定しました。そこで、32-bit の符合なし整数を232で割って[0, 1)区間の疑似乱数を作ったわけです。これはdoubleなら正しいのですが、floatの場合は間違いになります。floatの仮数部の精度は24ビットしかないので、0xffffffffに1.0f/(232)を掛けると1.0fになってしまうのです。
オリジナルのMersenne Twister では、和田維作さんによるgenrand_res53がしっかりとした処理をしているのに、退化させてしまいました。ああ、恥ずかしい。これは完全に私のミスで松本眞先生のせいではありません。松本眞先生はこの開発の頃から、あるいはその前から大変忙しくて、細かいところは見ていないのでした。私が疑似乱数の開発に慣れてきたので、そんなに見なくても大丈夫だろうと思ってくれたのだと思います。
64ビットの符合なし整数からdoubleに変換する場合も同様の問題があります。解決法は32ビットからfloatを作る場合は8ビット右シフトしてから1/(224)で割るというものです。maskしてから割ってもいいのですが、上位ビットの方が乱数性が高いので上位の24ビットを使います。

上付き文字がでないのは困る

はてなブログでは、<sup></sup>で上付き文字が出ないのが困る。それどころか下付文字になる。

何かがおかしい

コピーしてちょっと直すという修正はおかしい

しばらく他のことをやっていて、今週頭からまたMTToolBoxの機能拡張に取り組んでいた。そして今日になって思ったのだが、何かがおかしい。コピーしてちょっと直すという修正をしているのだ。いやいや、そういうことをやらないために、様々な技法があるわけでしょ。
アルゴリズムを表すクラスであるという意味で、Algorithmなんちゃらというクラスをいくつか作っているのだが、機能拡張に対応してアルゴリズムも変わるわけだ。そうするとアルゴリズム関連のクラスが変わってしまう。それでコピーして修正してしまう。いや、そこは継承なりなんなりと思うものの、ループの中の処理が変わるというのにはなかなか対応できない。フラグを渡すというのは、これまたよくない方法だろう。ループの中身を渡すというのが、たぶんruby的な考えだろう。関数型ならそもそもループじゃないし、最初からループ内に相当する処理を渡しているから問題ないのか。
でも、コピーして直すという方法で冗長なコードを書いてから、かっと目を見開いて冗長な部分を眺め、それから後知恵を使えばきっとうまくまとめられるという気はする。そうは言っても、動くものが出来てしまってから、手を入れるのは本能が拒否する。(そんなことをしたらまたバグの嵐になるから)だいたい、C++を使っている段階で、実行速度最優先という立場なわけで、ループ内の処理を渡したりしたら速度が落ちることが予想されるわけだし。
アルゴリズムをクラスにくっつければいいということか。これまでjava の interfaceのつもりで抽象クラスを書いていたけど、そこにアルゴリズムも入れるというのが妥当な修正なのかも。メンバー変数持たなきゃ問題ないでしょ。って今気づいてもかなり手遅れなんだが。(これにも問題はあるな)
というわけで、もやもやした気持ちを持ちながらも、ソースを修正しているわけだ。機能拡張はだいたい見通しがついたが、英語ドキュメントを書かねばならないという点が、鬱陶しい。まあ、デタラメ英語でも書いておけば、「英語の間違いに気づいたら修正してpull request下さいね」と言っておけば、英語が間違っているという指摘には必ず修正がついてくるはずだ。
今回の修正はユーザーが間違いをすると、間違った疑似乱数生成器が出来てしまうので、GitHubへのpushはまだしていない。間違える人は間違えるので、あまり気にしても仕方がないけど。

配信アニメ端境期

配信アニメの端境期なので、見放題の中からめぼしい物を探してみているのだが、ビッグオーとか、なかなかいいですな。

THEビッグオー Blu-ray BOX

THEビッグオー Blu-ray BOX

mosaic.wav の新作を買った

うーん、電波ソング、秋葉pop とは、ちょっと方向性が違うというか、期待外れでした。

過去とは恥ずかしいもの

昔のソースを見直す

MTToolBoxの修正。最初はさっぱりわからんかったが、コメントの入っていないソースにコメントを入れながら読んでいたら、思い出したぁ! このやり方はイケてない。そう、昔のことを思い出した時の正しい反応は赤面することである。昔のアルゴリズムは面倒なだけで効率が悪い。そうか、見直したくないと思ったのは、イケてないアルゴリズムだったからか。人間成長しているんだなぁ。これは新しいアルゴリズムにしなければならないだろうな。しかし、古いアルゴリズムは実績があるわけで、両方実装して比較することによって新しいアルゴリズムの正しさを確認するべきだろう。
ああ、面倒くさい。

C++ で多重継承をすることになりそうだ

怖い。Javaインターフェイスのつもりで使うのだが、それでも怖い。まあ、テンプレートの方が怖いか。エラーメッセージが何を言っているのか分からなくなるという点で。あれっ、すでにテンプレート使っているから、テンプレートによるパラメータ付きの絶対抽象クラスの多重継承になるのか。ああ、やだやだ。実は、テンプレートを使っているんだから、抽象クラスとか使わずにクラスを直接テンプレートパラメータにするという手もあるんだけど、それが一番怖い。饅頭怖いというくらいなにもかも怖い。
さらに、コンパイルエラーになったとかいうユーザーからの問い合わせが怖い。

思い出したぁ!

関係ないけど「思い出し赤面」って萌えるよね。

聖剣使いの禁呪詠唱<ワールドブレイク> (GA文庫)

聖剣使いの禁呪詠唱<ワールドブレイク> (GA文庫)

疑似乱数生成器

MTToolBox

MTToolBox というのは、疑似乱数生成器を開発する際に利用できるツールである。これを公開したら、卒論や修論で疑似乱数生成器を作る人が続出して、様々な疑似乱数生成器が乱立し、どれがよいのやら速いのやらまったく分からなくなって世の中が混乱すると思ったのだが、全然そんなことにはなっていないのであった。
これはMTToolBoxの機能に不足があるからに違いない。SFMTを作るときに使った機能がMTToolBoxには入っていないのである。その機能とはいわゆるReducible Generatorの作成機能である。
MTToolBox: メインページ

GF(2)線形疑似乱数生成器とMersenne Twister

MTToolBox はGF(2)線形疑似乱数生成器の開発をサポートするC++のライブラリなのだ。その辺のことは、スライドhttp://msaito.github.io/MTToolBox/mttoolbox.pdfを見て欲しい。GF(2)というのは二元体、ゼロとイチの四則演算が出来る世界で、疑似乱数生成器が線形というのは状態遷移関数と出力関数が線形ということである。読者の前提知識が分からないと説明が面倒だ。
それはともかく、シミュレーション用の疑似乱数生成器では周期が重要なのである。何はともあれ周期を保証する必要がある。もちろん、周期というのは最低周期である。最大周期ではない。時々勘違いしている人がいるので念のため。使用メモリから最大周期はすぐに分かるのだが、最低周期は計算する必要がある。その計算過程で、素因数分解が必要になるのが問題なのである。
Mersenne Twister の発想の優れたところは、素数と分かっていれば素因数分解必要ないじゃんというところである。まあ、それだけじゃないけど、それは重要なのである。MTToolBoxはMersenne Twister タイプの周期がメルセンヌ素数になる疑似乱数生成器の開発をサポートする機能がある。
まあ、大雑把に言うと、状態遷移関数の線形写像の特性多項式の次数がメルセンヌ指数(メルセンヌ素数の指数部)で、かつ、それが既約多項式であれば、状態遷移の周期はメルセンヌ素数になる。
そのために、Mersenne Twisterでは欠けた配列を使っている。メモリの一部を敢えて使わないことによって、特性多項式の次数がメルセンヌ指数になる(なりやすい)ようにしている。

W0の右側は使っていないのである。メモリがちょっともったいないけど、メモリはたくさんあるから31ビットくらい無駄にしても大したことはない。しかし、メモリ自体は問題ないのだが、欠けた配列の場合、最終防衛ラインともいうべきものが二段になってしまうという問題がある。説明は数学的に難しいという訳ではないが、説明されて分かる人なら説明されなくても分かるような気がするので、説明しないのだが、「最終防衛ラインの全ビットを次状態の計算に使用しなければならない」という制約がある。

この制約のために、CPUの命令が少なくとも二つ余分に使われる。メモリロードも入れると更に増える。つまりAND命令でマスクして使わない部分をゼロにする。二段目とORまたはXORする。という二つである。
二段目の左側は参照しても参照しなくてもよいが、参照するならORではなくXORする必要がある。もともと、Mersenne Twister の状態遷移に使用するCPU命令は多くないので、ここで二つ使ってしまうのは惜しい。

SFMT(とdSFMT)

ところで、SFMTでは欠けた配列を使っていない。

そうすると最終防衛ラインは一段で、マスクする必要も二段目とXORする必要もない。って、周期を保証するために状態空間がメルセンヌ指数ビットである必要があるって言ったやんか。どうなってるんや。実は、状態遷移関数の特性多項式が大きなメルセンヌ指数次の既約多項式と小さな多項式の積になっている場合は、小さな周期保証ベクトルを計算することが出来て、それを使って周期を保証できるのである。

MTGP 以降

じゃあ、それ以後に作られたMTGPやTinyMTでなんでその方法を使っていないのだということになるのだが、いやあ、お恥ずかしい。どうも周期保証ベクトルの計算がややこしくて、合っているという気がしなかったのである。いや、SFMTとdSFMTは松本教授がチェックしているから大丈夫なんだけど、いつまでもいちいちチェックして貰うわけにもいかんでしょ。
しかし、人間は成長するのである。最初にやったときに面倒だったので苦手意識を持ってしまったが、今の実力をもってすれば容易に倒せる相手のような気がする。ほら、最初の頃苦戦した敵もレベルアップして装備を整えれば瞬殺というあの現象ですよ。

MTToolBox に注目

というわけで、MTToolBox に新機能を追加する予定です。今後はその話を。