一人一党党

一人一人の、一人一人による、一人一人のための政治制度を!

メルセンヌ素数でxorshift疑似乱数の軽量化

とってもお手軽な割にそこそこ高速で高品質な疑似乱数生成アルゴリズム「xorshift」。
32bit版などの実装では、乱数生成一回あたりxor演算とshift演算を3組、計6回演算命令を使わねばならない。
ところが64bit版実装では、xorとshiftの組を2組しか使わずとも、2の64乗の周期が出る。
そこで、31bit版などbit数がメルセンヌ素数の場合、2組で可能か試してみた。
一般的なCPUのレジスタは32bitや64bitなど2のベキ乗なので、bit数を調整するためにand演算でbitmaskをかける必要がある。
しかしand演算はxorやshfit同様に軽い整数演算だ。
従って、xorとshiftの組を一組、すなわち整数演算を二つ減らせるなら、and演算一つ払っても整数演算ひとつ分だけ高速化できる。
メルセンス素数なら、周期は1かbit幅一杯かのどちらかなので生成パラメータが見つかる可能性が高そうだ。
しかも周期が素数なので、乱数を利用する側のプログラムの持つ周期と同期してしまう可能性が低い。
普通のxorshift疑似乱数は周期が素数ではないので、利用するプログラム側と組み合わせた周期が小さくなる場合がある。
パラメータ探索には下記のサイトのpythonスクリプトを拝借した。
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理 – びりあるの研究ノート
https://blog.visvirial.com/articles/575
31bit版と5bit版しか試していないが、例えば31bit版だと14組も生成パラメータが見つかった。
bitmaskを即値として演算命令に格納しないと、命令節約効果が打ち消される。
下位bit側をクリアするbitmaskなら、符号拡張により即値フィールドを小さくできる。
即値フィールド制限の厳しいRISC命令では不可欠だし、制限の緩いx86でも命令長節約になる。

--- C言語コード ---
#include <stdint.h>
uint32_t xorshift31(void)
{
    static uint32_t seed = 2;
    seed = seed ^ (seed << 7);
    seed = seed ^ (seed >> 12);
    return seed = seed & (~1);
}

--- x86へのコンパイル結果 ---
00000000 <xorshift31>:
   0:   8b 15 00 00 00 00       mov    0x0,%edx
   6:   89 d0                   mov    %edx,%eax
   8:   c1 e0 07                shl    $0x7,%eax
   b:   31 c2                   xor    %eax,%edx
   d:   89 d0                   mov    %edx,%eax
   f:   c1 e8 0c                shr    $0xc,%eax
  12:   31 d0                   xor    %edx,%eax
  14:   83 e0 fe                and    $0xfffffffe,%eax
  17:   a3 00 00 00 00          mov    %eax,0x0
  1c:   c3                      ret

コンパイル結果での0x14バイト目の命令の長さは3byteしかないが、符号拡張により4byteのbitmaskをかけることができている。
x86は2オペランド命令であり、演算結果を格納するために元データを破壊するため、xorとshiftの組ごとにデータ複製のためのmov命令が余計に加わっている。
xorとshiftの組を3組用いる32bit版実装では、31bit版より2命令多く必要になるはずだ。
上記31bit版の命令数が10個なので、2命令分の増加は2割増し。
なお、左シフトのパラメータを3以下にすると、x86の場合元データを破壊しないlea命令が使え、mov命令を回避できる。
31bit版の有効なパラメータとして(3,28)があり、これを使うと命令数を9個に減らせる。

統計不正が国の根幹を揺るがす犯罪になる国は似非民主主義国家です

最近は厚生労働省の統計不正が話題の様で、私は不思議に感じる。

神戸新聞NEXT|社説|ずさんな統計/民主主義の根幹に関わる
https://www.kobe-np.co.jp/column/shasetsu/201901/0011969710.shtml
確かに、統計不正は政権の判断には大きく影響するかもしれない。
しかし、特に今回の勤労調査や経済調査に限れば、「国民の判断」には殆ど影響しないはずだ。
言い換えれば、それら政権の存続・交代を左右する選挙に於いては、今回の不正の影響は少ないはずだ。

確かに、国民全員の経済や勤労状況は統計でしか知りえない。
ある政策Aで大半の国民の所得が向上するなら、政権はその政策Aを支持すべきだろう。
しかし国民個々の経済や勤労状況は、国民個々が一番熟知しているはずだ。
そして選挙で個々の一票に託されるのは、その票を投ずる個々の国民の意見であり、国民全員の意見ではない。
その政策Aの恩恵から漏れる国民の一人Bさんについては、たとえその政策Aが政権の支持すべき政策だとBさん自身が理解していたとしても、政策Aへ支持の一票を投ずるのは誤りだ。
Bさんの一票はBさん個人の意見を代表すべきで、国民全員の意見を代表するのは誤りであり、その投票行動に於いてBさんは国民全員の意見なんて無視すべきだ。
国民全員の意見は、開票結果の集計、選挙結果で得られれば十分だからだ。
個々の一票に託されるのが国民個々の都合であっても、その集計では、国民個々で相反する利害は打ち消し合い、国民全員に共通する意見のみが浮かび上がる。
もし、Bさんの意見ではなく全員の意見をBさんの一票に託したら、Bさんと相反する国民の意見が、打ち消されないまま反映され、「国民全員の意見」が歪められてしまう。
こうして誰も個々の我侭を投票し無かった結果が、誰の我侭も実現しない「アビリーンのパラドックス」だ。
アビリーンのパラドックス - Wikipedia
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%93%E3%83%AA%E3%83%BC%E3%83%B3%E3%81%AE%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9
このことは特定個人のBさんにとどまらない。
全ての国民は選挙時に、自分の意見を最優先すべきであり、国民全員の意見や統計など気にすべきではない。
選挙に於いて国民全員の統計なんて誰も気にしないのであれば、その統計が不正であろうと公正であろうと同じように、選挙は行われるはずだ。

あるいは選挙それ自身が、国民全員を対象とする統計の一種といえる。
選挙とは、個々の国民の政治的意見を集計したものだからだ。
個々の国民の○○状況を集計したものが○○統計ならば、選挙は政治的意見の統計だ。
だから、不正統計が別に行われていても、その統計に依存することなく独立して選挙は動く。
元々、比例代表制選挙制度で構成された議会は「国民の縮図」と言われる。
構成員の100%が議員職に就いているという凄まじく偏った構成であるにも拘らずだ。
正確には「国民の『政治的意見』の縮図」なのだが、そうであるためには、あたかも議員職なんて一度も経験した事のない彼らの支持者達を複製したかの様に、個々の議員は振る舞わねばならない。
だから「国民の複製の縮図」ともいえる。
もちろん、依然として複製は版元とは異なり、複製に富を配分しても版元は全く豊かにはならない。
しかし版元と同じ情報は持つから、複製に対して統計をとれば、版元の統計結果が得られる。
ならば、その元となる開票結果には、縮図にする前の国民の状態が複製されているはずだ。
そして比例代表制に限らず小選挙区制などに於いても選挙である以上、開票結果=国民の複製は集計されている。
つまり、比例代表制に限らず、選挙は統計のバックアップ機能を持つ。
マトモな民主主義国家ならばマトモな選挙が行われるはずで、統計不正単独では大した問題にはならないはずだ。

逆に言えば、統計不正が重大な問題になるということは、統計不正とは別に選挙の機能不全も存在することになる。
そして民主主義国家では、統計不正より選挙の機能不全の方が重要だ。
独裁国家でも統計調査をやっていることから分かるように、統計のバックアップは選挙でできても、選挙のバックアップは統計ではできない。
したがって、この国が民主主義国家を目指すのであれば、統計不正は話題にならない。
統計不正が大した問題でない場合は言うまでもない。
そうでない場合は、より重要な選挙の機能不全の話題に埋没するはずだからだ。

しかし先に述べたように、どうやら統計不正は話題になっているようだ。
このことは、選挙の機能不全が存在しながら、それが話題になっていないことを意味する。
これこそ、民主主義の根幹に関わる。

--- 題名のネタ元 ---
統計不正は民主主義の根幹を揺るがす犯罪です
https://anond.hatelabo.jp/20190206194752

Windows10のライセンス認証をせずに20年間放置した結果

20年くらい後の予言ではない。
2年くらい前の記憶。

私はLinux使いであり、主に使っているパソコンもLinuxを入れているが、テストプログラム用などのためにWindowsを入れた仮想マシンも用意している。
現在はWindows10だ。
当然、Windowsの本格使用は考えていないので、ライセンスを購入する気が起きない。
だが、WindowsXPのように90日(だったかな?)過ぎると実質操作不能になり、いちいち再インストールするのも大変だ。
しかしネットで検索してみると、Windows10については猶予期間について明確な情報が得られなかった。
そこで、Windows10を仮想マシンにインストールしている点を活用して、仮想マシンを「タイムスリップ」させることにした。
とはいえ、アインシュタイン相対性理論に挑戦するわけではない。
仮想マシンのエミュレートしている内蔵時計を20年分進めるだけだ。
しかし、仮想マシン内部の20年後の状態をシミュレートするには十分だ。
私の使っている仮想マシンソフトであるQEMUでは
qemu-system-x86_64 -rtc base=2040-2-30 ...
のようにコマンドラインオプション "-rtc base=..." を使う。
その結果、WindowsXPとは違ってWindows10では、OS操作が不能になるようなことはなかった。
ライセンス認証をしないとwindows updateを受けられないのだそうだが、インターネットなどに繋がないオフライン状態など、セキュリティ上の脆弱性が問題にならない使い方なら、ライセンス認証をしなくても支障はなさそうだ。

わたしがprintf()デバッグをする理由

現在、私はprintfデバッグに頼っているのに、
わたしがprintf()デバッグをする理由
http://freak-da.hatenablog.com/entry/20090325/p1
が半分どころか3/4ネタのようなので、真面目に言い訳してみた。

Coders at Work プログラミングの技をめぐる探求 | Peter Seibel, 青木 靖 |本 | 通販 | Amazon
https://www.amazon.co.jp/Coders-Work-%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E6%8A%80%E3%82%92%E3%82%81%E3%81%90%E3%82%8B%E6%8E%A2%E6%B1%82-Peter-Seibel/dp/4274068471
は生ける伝説達へ聞き取り調査の記録だが、驚くべきことに、彼らにはprintfデバッグを使う者がいるということだ。
Coders at Work on finding and preventing bugs
https://www.benkuhn.net/caw-errors

print文。
プログラミングの神は曰っているではないか。
『汝、誤りあらんと汝の思うところにprintf文を設え、再コンパイル、実行せよ。』
– Joe Armstrong
大抵は、単に値をprintするだけです。
私がプログラムを書いているとき、大量のprint処理が生じます。
そして、私がprint処理をコメントアウトしたり取り除いた時には、それらからprintされていた値は確かなものとなります。
取り除いたprint処理を再挿入することは滅多にありません。
– Ken Thompson
GHCには、様々なものをややバッチ処理的に印字する機能があります。
もしくは、それでも何が悪いのか分からないときが時々あるので、"unsafe printf"を少々バラ撒いて、何が起きているのか印字させます。
– Simon Peyton Jones
このうち、C言語の作者であるKen Thompsonがprintfデバッグを使うのは、驚くには当たらない。
C言語すら存在しない彼の時代には、マトモなデバッガは望むべくもないからだ。
しかしhaskellの主要開発者であるSimon Peyton Jonesと、Erlangの作者Joe Armstrongは違う。
これらは新しいプログラミング言語であり、それなりの各種ツールが利用可能な時代に作られている。
そして、情報不足を理由にそれらの各種ツールを避けるには、彼らはプロフェッショナル過ぎる。
なのに、特にJoe Armstrongはprintfデバッグが第一選択だ。
 
私はbrainfuckJITコンパイラを書いたとき、GNU gdbデバッガを沢山つかった。
GNU CとUNIXシステムコールだけで実行時アセンブラ ( ソフトウェア ) - 一人一党党
コンパイラの場合、生成した機械語命令が正しく動いているか確認する必要がある。
しかしデバッグ対象が機械語命令の粒度になると、printf呼び出しの影響が大きくなりすぎる。
機械語命令一個の動作をみるのに、機械語命令十個程度を挿入するのだから、元のプログラムが1/10しか含まれていない別物をデバッグすることになる。
一方、自作のプログラミング言語処理系上で動くプログラムを書いている現在の私は、gdbデバッガを使わない。
デバッガは自作の言語処理系には対応していないからだ。
自作の言語処理系はC言語で書かれているので、言語処理系自体をデバッグするにはgdbデバッガは有効だろう。
だが、そのデバッグ機能を、もう一段上の言語処理系や仮想マシンインタプリタを越えて使うのは、デバッガ自体をその仮想マシンアーキテクチャに移植するのと等価だ。
移植作業と同等の手間がかかるだろう。
Coders at Workに登場する巨人達は、ほとんどが新しい処理系の作者だ。
彼らに必要なデバッグツールは、既存処理系のものではなく、まだ見ぬ新しい処理系向けでなければならない。
これが、彼らがprintfデバッグを重視する理由だと私は考える。


勿論、大抵のソフトウェア開発では、一見すると、自作の言語処理系をデッチ上げることはないように見える。
だが、抽象化を駆使して、ソースコードの再利用性を高めたりサイズを圧縮するプログラミングスタイルでは、知らないうちに自作言語処理系を作っている可能性が高い。
ARMプロセッサなどいくつかのCPUには除算などの命令がなく、これらのCPU向けの処理系では、除算処理を標準ライブラリ内の関数として実装している。
逆に言えば、あらゆる箇所で使う処理を一つの関数に纏めて抽象化するのは、新しい命令を処理系に追加するのと同等だ。
関数=追加命令が多くなるほど、自作の言語処理系との差は埋まる。
高階関数を使えば遅延評価など制御構造まで抽象化でき、ソースコードレベルではhaskellの真似事に手が届く。
本物のhaskellに対応していないデバッグツールが、そのようなhaskellモドキのコードに対応できるはずがない。
ドメイン固有言語、仮想マシンインタプリタ、新しい言語処理系…、これらは抽象化のうち、明示的に既存言語の枠を踏み越えたものに過ぎない。

つまり、それぞれのデバッグツールには、扱える言語に対応した、扱える抽象化の限界が存在する。
その限界を越えた抽象化を欲するなら、新しい言語を生んだ巨人達と同様にprintfデバッグを使うしかない。

ディープラーニングによるフェイクメディア

今日、本屋で立ち読みしたら、
特集 だますAI vs 見抜くAI | 日経サイエンス
http://www.nikkei-science.com/201901_037.hml
が目に入った。
内容としては、
まるで本物 「ディープフェイク」動画の危険性 (1/4) - ITmedia ビジネスオンライン
http://www.itmedia.co.jp/business/articles/1805/10/news009.html
より少し新しめ&詳細な情報が載っている。
偽造写真は昔からあったが、今は映像すら偽造できる時代らしい。
「見抜くAI」は一つでもボロを見つければ勝てるため、同レベルの技術量の場合、「だますAI」の方が極めて不利らしい。

しかし、「だますAI」は「見抜くAI」だけ相手にしていればいいが、「見抜くAI」は「だますAI」だけでなく「本物のメディア」も検査しなければならない。
不特定多数が動画をアップロードする現代では、藁の中に針が混ざってないか調べるようなものだ。
実際には、多くの人々に広がった有名なもの、つまり、騙された人が既に沢山いて手遅れのものに検査対象を絞ることとなろう。

さらに面倒なのは、「見抜くAI」が行うのは判定までで、説明はしてくれないことだ。
昔の偽造写真鑑定は、鑑定士も人間だから、他の人間が鑑定士の思考・作業を辿り再検証することができた。
しかしAIは人間とは大きく違う思考・作業をするため、人間がAIの思考・作業を再検証するのは絶望的だ。
ならば、AIはAIによって再検証すればいいかというと、二つのAIに食い違いが生じたとき、どちらのAIを信用すべきかが問題になる。
これが人間であれば、鑑定結果を疑っている人自身が検証作業を行えば良い。
他人と自分、食い違いが生じるなら、どちらを信用すべきかは自明だからだ。

スカイネット誕生の日は近い。

参考
スカイネット
http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AB%E3%82%A4%E3%83%8D%E3%83%83%E3%83%88

フフ、OSの性能の差が、人気の差と逆であることを教えてやる

備忘録。

本の虫: C++標準化委員会の10月の興味深い文書
https://cpplover.blogspot.com/2018/10/c10.html

不自由で低能なWindowsはプロセスの作成もスレッドの作成も遅いし、ましてやファイルの作成に至っては、i7でNVMeのSSDを積む高性能なコンピューター上で動くWindows 10がRaspberry PiとSDカード構成のRaspbianにすらパフォーマンスで負けるという信じられないほどの低能を誇っている。

Benchmarking OS primitives - Bits'n'Bites
http://www.bitsnbites.eu/benchmarking-os-primitives/

プログラムの起動速度でもWindowsはRaspbianに負けているが、こちらはストレージの性能差は影響しないので、ファイル生成よりは信じ易い。
ちなみに、Raspbianはdebian GNU/Linuxの派生なので、Linuxの一種。
Benchmarking OS primitives - Bits'n'Bites
同上

Obviously each operating system has its merits, but in general it seems that Linux > macOS > Windows when it comes to raw kernel and file system performance.
明らかにそれぞれのOSにはそれぞれの長所があるが、
一般的には、Linux > macOS > Windowsの順でOSカーネルファイルシステムの性能が高い。

これは正に、使える人が多いOSの順と逆だ。

--

題名の元ネタは「機動戦士ガンダム」。

Betfairから見た自民党総裁選

最近は自民党総裁選挙の報道が賑やかだ。
安倍首相と石破元幹事長の一騎打ちらしい。
安倍氏が優勢なようだが、それを具体的な数字で表現してくれるものの一つが、賭博サイトだ。
国内では賭博サイトは法律に触れるので、海外サイトから探すことになる。
賭博サイトとして有名なbetfairをみると、直接総裁選を扱っているわけではないが、安倍首相の任期についての賭け
Shinzo Abe to leave before end of 2018
https://www.betfair.com/exchange/plus/politics/market/1.144153051
を見つけた。
「2018年までに安倍氏が首相を辞めるか?」という賭けに対し
辞めない 1.08倍 - 1.2倍
のオッズがついている。
(「辞める」側のオッズは、対応する「辞めない」側のオッズより甘いので省略。)
オッズではなく100分率の確率に直せば
辞めない 83.3% - 92.6%
となる。
衆参両院の議席の半数を自民党が握っている状況に於いて、自民党総裁が首相になれないという事はないだろう。
逆に言えば、総裁選に落ちれば、新総裁に首相に就けるため安倍氏は退陣せざるを得ない。
総裁選以外にも首相を続けられない要因はあるので(微小隕石に当たるとか、自民党が分裂するとか、スキャンダルが発覚するとか…)、上記の賭けは総裁選に於ける安倍氏の勝率の下限を示すことになる。
それが最低でも83.3%。
「いや、83.3%は勝率として高すぎるだろう」という人がいれば、今すぐbetfairに参加すれば、期待値がプラスの賭けができる。
裏を返せば、そんな人がいないから、このオッズが残っているというわけだ。