ビット転置

69倍になったあとは、一ヶ月ずっとビット転置のやり方を考えてました。
ワード単位のときのような頭のおかしい配置方法があるんじゃないかと探してたんです。

結局みつからなかったので、頭から順番にビットを詰めていく方法になりました。

qword mt_bs[32][5];

の mt_bs[i][0] には 0から127番目のワードのiビット目を並べます。残りも同じように詰めます。
実際に書いてみると分かるのですが

y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];

このkk+1が鬼門で、kk+1ワード目にあったビットをkkワード目の位置までもってくるのに、1ビットシフトが必要なだけでなく、足りない分を隣のqwordから1ビットもらって来ないといけません。
31ビット分同じことをやらないといけないので、31回のrlqwとselbが必要になります。

ここで、MTの状態空間は本当に624ワードだったかを思い出してみます。
松本先生の書いたドキュメントを読んでると、状態空間は624ワードじゃなくて623ワード+1ビットであることが分かります。
これをワード単位に切り上げた実装が624ワードになってるだけです。
623ワード+1ビットで更新処理を書いてみると、

word mt[623];
word last_bit;

for (kk = 0; kk < 623; kk++) {
  y = last_bit | (mt[kk] & LOWER_MASK);
  last_bit = mt[kk] & UPPER_MASK;
  mt[kk] = mt[(kk+M-1) % 623] ^ (y >> 1) ^ mag01[y & 0x1UL];
}

これを元に実装すると、1ビットシフトは31回も必要なくて、最上位ビット1回だけになります。