Windows 10 May 2020 Update 後に DvorakJ を使う

親指シフトなどかな入力系を使っている場合は以下が参考になります（本稿も当該記事を参考にしています。ありがとうございます）。

Windows 10 May 2020 Update とDvorakJ での親指シフト入力の問題を解消する

症状

Dvorak配列にしてローマ字入力をすると、[J]を打ったらhがIMEに送られてほしいところ、jが送られる。

ただし、アプリケーションを起動した直後の入力だけは、正しく動作する。

なぜこのような現象が起こるのか

日本語IMEが新しいバージョンにアップグレードされたからのようです。 https://support.microsoft.com/ja-jp/help/4462244/microsoft-ime#section-1

新しい IME では IME 自体のパフォーマンスを向上させるだけでなく、アプリケーションとの独立性を高めることで、アプリケーションへの影響を最小限にしました。

これが原因で、DvorakJとの相性が悪くなったのでしょう。

解決方法

以前のバージョンの Microsoft IME を使う

残念ながら新しいバージョンの Microsoft IME は相性が悪いので、以前のバージョンの Microsoft IME を使うことにします。

Windows の設定→時刻と言語→言語→（優先する言語の中の）日本語をクリック、オプション→Microsoft IMEをクリック、オプション→全般→以前のバージョンの Microsoft IME を使う、オン

DvorakJ の設定で「IME を経由せずに、特定の文字と記号を直接発行する」は適用しなくてよい

先ほど紹介したウェブページによれば、

日本語入力モードのときに数字記号を入力すると確定状態で入力されてしまう

という症状が発生したようです。

これは、NICORA配列の設定ファイルは最上段が定義されていないことが原因と思われます。

最上段を

１|２|３|４|５|６|７|８|９|０|「|」|￥|

のように定義している配列では、この問題は起こりませんでした。

逆に、この設定を適用してしまうと、キーボードにない文字（例えば、私は【】を打てるようにしています）を出力する場合にNUL文字が出力されてしまいます。

最大公約数をもっと高速に求める番外編（その2）

前回のコードを最適化していきます。

主要なループ*1のうち、最も時間がかかるのはctz部分（3サイクルレイテンシのBSF命令にコンパイルされます）です。 これを少しでも早く実行開始できれば、さらに高速に動作するはずです。

ここで、二の補数表現の特徴からctz(s) == ctz(-s)である点に着目します。 すると、ctz(x < y ? y - x : x - y)などとせずにctz(x - y)としても得られる結果は同じです。

こうすることで、1サイクルでも早くctzの計算に取り掛かれるようになります。

そのように式変形をすると、gccを使った場合は余計なおせっかい*2が発動してかえって遅くなります。 以下は、そのようなおせっかいをしないclang向けのコードです。

uint64_t gcd_stein_impl( uint64_t x, uint64_t y ) {
    if( x == y ) { return x; }
    const uint64_t a = y - x;
    const uint64_t b = x - y;
    const int n = __builtin_ctzll( b );
    const uint64_t s = x < y ? a : b;
    const uint64_t t = x < y ? x : y;
    return gcd_stein_impl( s >> n, t );
}

uint64_t gcd_stein( uint64_t x, uint64_t y ) {
    const int n = __builtin_ctzll( x );
    const int m = __builtin_ctzll( y );
    return gcd_stein_impl( x >> n, y >> m ) << ( n < m ? n : m );
}

このコードは、clang++-9 -O3でコンパイルした場合、std::gcdと比べて5.5倍ほど早く動作します。

*1:ソースコード上は末尾再帰として書かれていますが、最適化コンパイルするとループになります。

*2:条件演算子部分が条件転送命令ではなく条件分岐命令にコンパイルされてしまう

最大公約数をもっと高速に求める番外編（その1）

なんだか最近最大公約数を高速に求めたい読者（競技プログラマ？）が多いようなので、書いておきます。

最大公約数を求める改良版アルゴリズムとして、Stein's algorithm（Binary GCD）というものがあります。

ナイーブな実装では、普通の互除法よりも遅いですが、ctz（末尾に何ビット0が続くか）を分岐なしに高速に計算できれば実用的になります。

Steins; GCD - Qiitaでは、表引きを用いたctz（本文中ではntz）実装が使われています。 このctz実装は、C++11のconstexpr関数として実装できていることから明らかなように、ポータブルではありますが、乗算とメモリアクセスがあるため低速です。

高速性を重視する場合、ポータビリティは失われますが、__builtin_ctzllが使えます。なお、__builtin_ctzllはx86ではBSF命令にコンパイルされます。

生成されるコードの重要な部分に分岐命令が含まれないよう、注意深くコーディングした以下のコードは、std::gcdの3.6倍ほど高速です。

uint64_t gcd_stein_impl( uint64_t x, uint64_t y ) {
    if( x == y ) { return x; }
    const uint64_t s = x > y ? x - y : y - x;
    const int n = __builtin_ctzll( s );
    const uint64_t t = x > y ? y : x;
    return gcd_stein_impl( s >> n, t );
}

uint64_t gcd_stein( uint64_t x, uint64_t y ) {
    const int n = __builtin_ctzll( x );
    const int m = __builtin_ctzll( y );
    return gcd_stein_impl( x >> n, y >> m ) << ( n < m ? n : m );
}

ウィンナ・チューバの仕組みの予想

ウィンナ・チューバ - Wikipediaを見ていて、どういう仕組みになっているのか面白いと思ったので、メモです。

私は金管楽器を*1演奏したことが一切ないので、以下に書かれていることは、あくまで物理的な計算に基づいた憶測です。

Wikipediaによれば、ウィンナ・チューバは、

  • F管である
  • 六つのバルブ*2（①②③④⑤⑥）を持つ
  • ①を操作すると、F調を長二度下げる効果がある
  • ②を操作すると、F調を短二度下げる効果がある
  • ③を操作すると、G調を半音下げる効果がある
  • ④を操作すると、C調を長二度下げる効果がある
  • ⑤を操作すると、C調を短二度下げる効果がある
  • ⑥を操作すると、F調を完全四度下げる効果がある
  • ④と⑤を同時に操作すると、（たぶんF調を）二全音下げる効果がある
  • ①②④⑤⑥を同時に操作した状態がG調
  • ③はF調を全音（長二度よりやや狭い）下げる
  • ④はF調から一全音半下げるバルブではない
  • バルブの操作の仕方は64通りあり、一オクターブ内で異なる64種類の音が出せる
  • 64種類の音の中には、平均律、純正律、微分音への対応が可能な音が含まれる

とのことです。この内容だけから憶測を広げていきます。

各バルブの追加する実効管長の計算

計算の都合上、①→②→⑥→④→⑤→③の順番で明らかにしていきます。

①のバルブを操作したときの管長の伸び

  • F管である＝何も操作しない場合F（ファ）が出る
  • ①を操作すると、F調を長二度下げる効果がある

ので、①のバルブを操作した状態ではEs（ミ♭）が出るはずです。

ファとミ♭の振動数比は9:8なので*3、

  • ①のバルブは実効管長を、元の実効管長の1/8伸ばす

ことが結論付けられます。

②のバルブを操作したときの管長の伸び

  • F管である＝何も操作しない場合F（ファ）が出る
  • ②を操作すると、F調を短二度下げる効果がある

ので、②のバルブを操作した状態ではE（ミ）が出るはずです。

ファとミの振動数比は（純正律だとして）16:15なので、

  • ②のバルブは実効管長を、元の実効管長の1/15伸ばす

ことが結論付けられます。

⑥のバルブを操作したときの管長の伸び

  • F管である＝何も操作しない場合F（ファ）が出る
  • ⑥を操作すると、F調を完全四度下げる効果がある

ので、⑥のバルブを操作した状態ではC（ド）が出るはずです。

ファとドの振動数比は4:3なので、

  • ⑥のバルブは実効管長を、元の実効管長の1/3伸ばす

ことが結論付けられます。

④のバルブを操作したときの管長の伸び

  • F管である＝何も操作しない場合F（ファ）が出る
  • ⑥を操作すると、F調を完全四度下げる効果がある＝C調になる
  • ④を操作すると、C調を長二度下げる効果がある

ので、④と⑥のバルブを操作した状態ではB*4（シ♭）が出るはずです。

ファとシ♭の振動数比は3:2なので、

  • ④と⑥のバルブを同時に操作すると、実効管長が元の実効管長の3/2倍に伸びる

ことが結論付けられます。ここで、⑥のバルブは実効管長を元の実効管長の1/3伸ばすことがわかっていますから、差分を計算すれば

  • ④のバルブは実効管長を、元の実効管長の1/6伸ばす

ことが結論付けられます。

⑤のバルブを操作したときの管長の伸び

  • F管である＝何も操作しない場合F（ファ）が出る
  • ⑥を操作すると、F調を完全四度下げる効果がある＝C調になる
  • ⑤を操作すると、C調を短二度下げる効果がある

ので、⑤と⑥のバルブを操作した状態ではH（シ）が出るはずです。

ファとシの振動数比はきれいな整数比になりませんが、「C調を短二度下げる」と言っていることから、（純正律だとして）ドとシの振動数比が16:15になるようにしているのでしょう*5。したがって、

  • ⑤のバルブを操作すると、実効管長が⑥のバルブを操作している時の実効管長の1/15だけ追加される

ことが結論付けられます。ここで、⑥のバルブを操作した状態の実効管長は元の実効管長の4/3倍ですから、かけ合わせれば

  • ⑤のバルブは実効管長を、元の実効管長の4/45伸ばす

ことが結論付けられます。

③のバルブを操作したときの管長の伸び

  • ③を操作すると、G調を半音下げる効果がある

ので、③のバルブはG（ソ）をGes（ソ♭）に変える働きがあるはずです。

ファとソの振動数比は、16:9であり、ファとソ♭の振動数比は（純正律だとして）15:8なので、ここから計算すると、

  • ③のバルブは実効管長を、元の実効管長の7/72伸ばす

ことが結論付けられます。

「半音」の解釈について

12平均律に慣れていると気にしなくなりがちですが、ここでの「半音」が何を意味するのかを慎重に吟味する必要があります。ここでの「半音」の解釈は、以下の二通りがありえます。

  • 純正律における全音階的半音（全音階における短二度と同じ音程、振動数比は16:15）
  • 純正律における半音階的半音（長三度と短三度の差の音程、振動数比は25:24）

F調においては、GとGesの音程を全音階的半音に取り、C調やG調ではGとGesの音程を半音階的半音に取るようです。

楽器全体としてはF調ですが、「G調を半音下げる」と書かれているので一体どっちを意味しているのか全く分かりません。ただ、半音階的半音と解釈すると、「③はF調を全音（長二度よりやや狭い）下げる」というヒントとの整合性が全くなくなるため、全音階的半音と解釈しました。

ウィンナ・チューバの自由度

ウィンナ・チューバを作る時の自由度は七です。一つは管長（＝何も操作しないときに出せる音高、Fに取られている）で、残りの六つは各バルブ操作時に追加される実効管長です。

従って、ウィンナ・チューバは原理的に、チューニングに使う音を七種類しか取れません。

そして、すでに F, E, Es, C, B, H, Ges の七音を計算に使ってしまいました。

それにもかかわらず、以下のチューニング点が、まだ計算に使われていません。

  • ④と⑤を同時に操作すると、（たぶんF調を）二全音下げる効果がある
  • ①②④⑤⑥を同時に操作した状態がG調

これらが、偶然の一致によりチューニングされているのか、それとも“目的外”のバルブ操作によって疑似的に実現されているのかを確認します。

④と⑤を同時に操作すると、（たぶんF調を）二全音下げる効果がある

④と⑤を同時に操作したときの実効管長は、元の実効管長の113/90倍です。つまり、④と⑤を同時に操作すると、基準となるファより394cent低い音が出ることになります*6。

これは実用上の意味において二全音と言ってよい値だと思いますが、

  • 計算上は、②③⑤を操作したときの390cent低下のほうが、純正律の長三度（384cent）に近いはず
  • ③④を操作したときの405cent低下のほうが、12平均律の長三度（400cent）やピタゴラス長三度（408cent）に近いはず

なので、あえて④⑤の操作を選ぶ理由が謎です。

考えられる理由は、

  • 左手側のバルブと右手側のバルブを組み合わせるのは避けたほうがいい可能性*7。
  • ③のバルブを操作したときの管長の伸びを正しく計算できていない可能性

あたりでしょうか。

そもそも、きっかり“純正”な長三度音程を実現する意義があるのかも不明で、適当にその場に応じて純正律の長三度に近い音程と12平均律の長三度に近い音程を使い分けられるという意味において、④⑤の操作のほうが“柔軟性”があるのかもしれません。

①②④⑤⑥を同時に操作した状態がG調

①②④⑤⑥を同時に操作したときの実効管長は、元の実効管長の641/360倍です。これはほぼ16/9 = 640/360に等しいので、基準となるファより短七度低いソの音が出るといってよいでしょう。 その差はわずかに2.7centです。

③はF調を全音（長二度よりやや狭い）下げる

念のため確認しておきます。

③を操作したときの実効管長は、元の実効管長の79/72倍です。つまり、③を操作すると、基準となるファより161cent低い音が出ることになります*8。

確かに長二度（204cent）より適度に狭い音程を実現できており、「イントネーション補正にも役立つ」は満たされていそうです。

ただ、161centは全音というにはかなり狭く、中立二度と呼ぶべき音程な感があります。

④はF調から一全音半下げるバルブではない

ついでに確認しておきます。

④を操作したときの実効管長は、元の実効管長の7/6倍です。つまり、④を操作すると、基準となるファより267cent低い音が出ることになります*9。

確かにこれを一全音半（~300cent）下げるバルブと勘違いして使ってしまうと、かなりおかしな音が出ることになります。

ウィンナ・チューバの運指の予想

ここまでで、バルブ操作が実効管長に与える影響はすべて計算済みなので、目的の音に最も近い音を出す運指が、計算上は、わかるはずです。

12平均律で演奏する場合

複数の運指がほぼ同じ音を実現する場合、簡単そうなほうを選びました。

音名 ①：管長1/8追加 ②：管長1/15追加 ③：管長7/72追加 ④：管長1/6追加 ⑤：管長4/45追加 ⑥：管長1/3追加 管長 ずれ
ファ 1 0.00
ミ ② 16/15 +11.73
ミ♭ ① 9/8 +3.91
レ ① ② 143/120 +3.57
レ♭ ④ ⑤ 113/90 -6.01
ド ⑥ 4/3 -1.95
シ ⑤ ⑥ 64/45 +9.77
シ♭ ④ ⑥ 3/2 +1.95
ラ ④ ⑤ ⑥ 143/90 +1.62
ラ♭ ③ ④ ⑤ ⑥ 607/360 +4.44
ソ ① ② ④ ⑤ ⑥ 641/360 -1.21
ソ♭ ① ② ③ ④ ⑤ ⑥ 169/90 -9.17

左手側のバルブと右手側のバルブを変に組み合わせる部分はないのですね。

ヘ長調の純正律で演奏する場合

ヘ長調の純正律でチューニングしたと仮定して管長を計算しているので、多くの音程が純正になっています。

ついでに、偶然純正音程を実現する組み合わせとしては、①③④と操作したとき（実効管長が元の管長の25/18になる）の純正増四度音程が存在するようです。

「理論的にも実際に使用してもとても優れている」について

確かに、1オクターブの間に64の運指を持つため、実用上どんな音高の音も出すことができ、平均律も純正律もいずれもこなすことができると思われます。おおよそ15centおきに異なる音高が実現できるため、微分音への対応も完璧です。

ただし、ファ周辺は運指に乏しく、任意の音高の音が出せるわけではなさそうです。こちらは管の抜き差し等で対応するのでしょうか。

「楽器・マウスピースの個体差による誤差の補正」はさすがに無理があるように思われます。楽器やマウスピースごとに、法則性のない運指を覚えなおすというのでしょうか……？

*1:木管楽器も、演奏したことがあるのはソプラノリコーダーとオカリナくらいです。

*2:バルブは管の構造を変化させるスイッチで、操作すると迂回管を通るように管の構造が変化するようです。これにより、管長が伸びるため出る音が下がります。

*3:ほかの調だと10:9のこともありますが、「F調で長二度」の記述を重視しました。

*4:Bはドイツ語でベーと読み、シ♭を意味します。しかし英語ではBをビーと読んでシを意味するので非常に紛らわしいです。ちなみにドイツ語でシを意味するのはHで、ハーと読みます。

*5:そのようにとると、ファとシの振動数比は64/45という非常に汚い比になります。もともと減五度音程で不協和音なので、これ自体は問題ではありません。

*6:log_2(113/90)×1200=393.99

*7:「左手ブロック①②③と右手ブロック④⑤⑥の間には、クランク状のパイプが入り連結されている。このクランク状のパイプをなくして6つのバルブを1直線に配置すると音程バランスが崩れる。」と書かれていることからの推測です。

*8:log_2(79/72)×1200=160.63

*9:log_2(7/6)×1200=266.87

0からN-1までの数が入った配列

今までは以下のように作っていましたが、

template<std::size_t... Indeces>
constexpr auto make_iota_impl( std::index_sequence<Indeces...> ) { return std::array { Indeces... }; }
template<std::size_t N>
constexpr auto make_iota() { return make_iota_impl( std::make_index_sequence<N>() ); }

C++20ではstd::iotaがconstexpr対応したので、

template<std::size_t N>
constexpr auto make_iota() {
    std::array<int, N> ret;
    std::iota(ret.begin(), ret.end(), 0);
    return ret;
}

と書けるようになりました。

PPM-like分岐予測器とTAGE分岐予測器の違い

An Alternative TAGE-like Conditional Branch Predictor https://hal.inria.fr/hal-01799442/document という論文に載っていて、

TAGE分岐予測器は、PPM-like分岐予測器と異なり、 * グローバル分岐履歴の最長一致で予測を立てるのではなく、二番目に長く一致したものも考慮に入れる * 最長一致の信頼性が怪しい時などに、二番目のが使われる * uビットではなくuカウンタを持っている（uは役に立つ予測を提供した情報であることを意味する。usefullの略）。 * 予測を外した時だけではなく、時間経過でuカウンタを減少させる * 予測ミスが発生したときに、すべてのテーブルにエントリを確保するのではなく、一つのテーブルにのみエントリを確保する

このうち、最後の部分の効果がかなり大きいです。 近年では、一つのミス当たり平均して1未満のエントリしか確保しない方式が主流です。 この論文は、エントリを確保する頻度を制御する方法について書かれています。

uカウンタとかは、かなりチューニングの域です。実際、2016年の64KB TAGE-SC-L分岐予測器ではuカウンタは1ビットでよいと言っています。