melancholic afternoon

Effective Modern C++勉強会#5

unique_ptrを使ったpimlの話. 最近はもう実装を全部hppに書いちゃってpimlは殆ど使わないなあ. 参加者の中には1回buildに30分かかるので必須と仰ってる人もいたけど.

しかし, この著者ですら間違ってしまうほどややこしいunique_ptrを使ったpimlの実装. この本を読めば読むほど, この複雑怪奇なC++は駄目だろうとしか思えない….

次回は6/17です.

いろいろ

ペアリングライブラリに素体にsquareRootメソッド追加. 早く別でやってる楕円曲線クラスと統合したい.

niftyのftpがようやく使えるようになったらしい. @homepageの管理サーバに不正アクセスがあったとか.

まだ喉痛い. 今回は長引くなあ.

Mersenne Twisterの次に出す値を推測する

MTはよい擬似乱数の一つだけれども暗号に使ってはいけない. しばらく値を観察すれば次の値が分かってしまうから.

と言っていたが, 本当にできることは確認していなかったので考えてみた.

MTは通常4byte * 624個の配列 uint32_t p[624]; とその配列のどこを指しているかを示すindexを内部状態として持つ. そしてその内部状態は624回に一度全てが更新され, それ以外ではその配列のindex番目の値をtemeringしてから出す.

ちょっと考えると624回に一度ではなく毎回同じ処理をさせるように変形できる.

inline uint32_t getInt32()
{
    uint32_t i = index_;
    uint32_t y;
    y = p_[i] = p_[(i + M) % N] ^ TWIST(p_[i], p_[(i + 1) % N]);

    index_ = (i + 1) % N;
    return tempering(y);
}

こうするとtempering()の逆関数ができれば連続する624個の4 byteの値を取得すれば次の値を計算できそうだと思う. indexは不要そうだ. 最初はindexを求めるために624個 + αがいるかなあと想像していた. で, temperingだが, こんな関数.

uint32_t tempering(uint32_t x)
{
    x ^= (x >> 11);
    x ^= (x << 7) & 0x9D2C5680;
    x ^= (x << 15) & 0xEFC60000;
    x ^= (x >> 18);
    return x;
}

x ^= x >> 18;の逆関数はx ^= x >> 18;で自分自身と同じだ(ちょっと面白い).

x ^= (x << 15) & 0xEFC60000;もそうだったりする.

しかしx ^= x >> 11;は自分自身ではない. 似てはいるけど(ちょっとしたパズルだ). x ^= (x << 7) & 0x9D2C5680;も少し頑張れば分かる. というわけでtempering()の逆関数ができた.

まあ, それはともかく試してみる[mt_step.cpp]. std::mt19937を適当に初期化し, いくつか値を捨てた後, 624個の値を取得すれば, それからその後MTと同じ値を出力することを確認できた(多分誰かやってる). 必要な値はきっかり624個と分かってすっきりした.

とか書いてから検索したらtemperingの逆関数を数学ちっくに解いている方がいらっしゃった[メルセンヌツイスタの調律を行列で書く].

Java api for pairing

ate-pairingをJavaから使えるようにしてほしいというのがあったので最低限のサンプルが動くようにswigで作ってみる[BN254Test.java]. JavaのBigIntegerのadd, subtractとかってC++的には

Fp add(const Fp& x) const; // return *this + x;

であって

void add(const Fp& x); // *this += x;

なんだな. そちらに合わせた方がよいのだろうか. Javaを知らないからよく分からん. 後者の方が効率がよいように思ってそちらにしたけど, そもそもJNI経由の時点で一般的な流儀に合わせた方がよいか. jpbcも前者の形のようだ.

@nifty

14日から緊急メンテナンスのためftpサーバに接続できない. 2日経ってからようやく代替手段の情報が更新されたのだけど, メールでの通知も無くてその対応はどうかと思った. メールもうまく取得できないのだけど, こちらは何故だろう. まあそれはともかくtwitterの検索を見ても何も関連情報が出なかったことに驚いた. そうか, そんなに使ってる人がいないのか.

喉が痛い

空気が乾燥しているせいか, 喉を酷く傷めた. とても痛い. 寝られない.

PHP

しばらくずっとPHP. ある操作でaddress sanitizerが落ちるのだがなぜ落ちるのかが分からない. 簡単なテストでは落ちない. 場所は分かってるのでコードを小さくしていけばよいのだけど大きいので大変だ.

『工学部ヒラノ教授』(今野浩)

工学部で出世を目指す研究者の話. とても軽いタッチ. エンジニアの守るべき原則に締め切り(会議の時間含む)や拙速(80%の出来で素早く, 残りをじっくり)などを挙げている.

papersize

TeXでhyperrefを使うのを止めたらdocumentclassで指定したa5jの大きさが無視されるようになって悩む. documentclassのオプションにpapersizeをつけるとよいらしい. 紙面サイズの指定

周知の通り、オリジナルの TeX は出力（DVI）に紙面の大きさを記録しない（そもそも「紙面の大きさ」という概念がない）。

紙面の大きさの概念がないってどういうこっちゃ. 周知の事実だったのか. 知らなくてすいません.

LaTeXによる論文作成の手引き TeXで無駄に浪費する時間を考えると, ちゃんと読むべきかなあ. 悩ましいなあ.

Re: JNA

簡単に使えるのは興味深いが, Cの関数だけでクラスメソッドは扱えなさそうだった. 使いたいと思った用途にはちょっと向かなさそうだ.

『明日の子供たち』(有川浩)

児童養護施設に転職した新入職員. 子どもやいろいろな考えの先生たちとのやりとりが考えさせられる. 多少の都合のよい偶然はまあ許容範囲. ラストのメッセージ, 数年, 十年後の未来を見据えた政治家がどれだけいるものかと思うとかなり楽観的と思ってしまった自分がちょっと悲しい.

主張自体はタイトルにからめてとてもよいと思う.

JNA

JavaからCライブラリを呼ぶ仕組みらしい. 初めて知った. 今まではSWIGでやっていたけどこちらの方が簡単にできるらしい. 今度試してみる.

アンロール

>速い. が速すぎる. asmコードみて何を計算してるのか確認しないと.
なんと本当に計算していた. expがinline化され, ベクトル化とループ展開されていた.

double fff(const double *p)
{
  double sum = 0;
  for (int i = 0; i < 100000; i++) {
    sum += exp(p[i]);
  }
  return sum;
}

がコメントありとはいえ, ざっくり5000行のsファイルになっていた. これはびっくり. ここまで展開するということはテーブル引きより計算するほうがかなりよいんだろうなあ. レジスタ数は256本もあるらしい. 以前MTの最適化で触ったCellの2倍. あれは頑張ってソフトウェアパイプラインを書いたが. -Kfast,nounroll,noswpが比較的分かりやすそうな出力(by @k_nitadoriさん)になったのでしばらくこれで勉強する.

うー, やりたいことややらないといけないことが多くて困ったな. 優先順位としてはこれが一番低いよな.

fmath::exp

以前作っていた高速な近似expをSPARCで動かすために手直し(というか簡略化)してみる[hpc]. 単純ベンチでstd::expの3.5倍程度は出ているようだ. テーブルサイズが比較的大きいので実際のところどんなものかは不明.

ところでこのコードはgcc -ffast-mathで動かないのだが, 理由を調べずほったらかしにしていた. 今日よく見てみたら

double x;
uint64_t b = 3ull << 51;
(x - b) + b;

このコードが最適化されてxになっていたからだった. 本来はround(x)に近い挙動を期待する. なるほど, これは仕方がない. が, このコードに相当するポータブルで高速な書き方ってあるのだろうか. round()関数は関数呼び出しになってしまって論外. 負数の場合分けがいるけど0.5足してintにキャストかなあ.

ただFCCpx -O3 -Kfastは大丈夫(最適化せずに意図通りに(x - b) + bを実行)してくれた.

[追記] @k_nitadoriさんより「配列に直接expだとSIMD化される」との情報でテスト. 元がstd対fmathが128:36というスコアだったところに3.89という数値がでる. 速い. が速すぎる. asmコードみて何を計算してるのか確認しないと.

憂鬱な午後のひととき