gcc9.1.0をソースコードからコンパイルした

gcc8以前と比較して、gcc9はバイナリ生成部分が更新されているようです。 既存のコンパイラのバイナリ生成に不満を持ったため、gcc9.1.0をビルドすることにしました。

前回gcc8.2.0をソースコードからコンパイルしました。 その時の知見が生かせたので、今回はスムーズにコンパイルできました。 道しるべとして今回も記録しておきます。

今回も3stageビルドを行いましたが、意味がなかったような気がします。 3stageビルドを無効化する場合、--disable-multilibの横に--disable-bootstrapを付けます。

mkdir build_gcc91_stuff
cd build_gcc91_stuff/
wget http://ftp.gnu.org/gnu/gcc/gcc-9.1.0/gcc-9.1.0.tar.gz
tar xf gcc-9.1.0.tar.gz
cd gcc-9.1.0
./contrib/download_prerequisites
cd ..
mkdir build
cd build/
../gcc-9.1.0/configure --prefix=/home/lpha/gcc91 --enable-languages=c,c++ --disable-multilib
make -j 6 BOOT_CFLAGS='-march=native -O3'
make install

バイナリ生成の違い

詳しく解析したわけではないのでよくわからないですが、以下の既存の系列とは違ったバイナリ生成を行うようです。

  • gcc8以前
  • clang全て

定数との整数演算命令の最適化は、clangより弱いままです。しかし、総合的な最適化力はclangより高そうに見えます。特に、機械語命令の順番がいい感じになっています。

リリースノートには、switch文の最適化をいい感じにしたとか書いてありました。

干し柿落としゲームのGrundy数を求めてみた

干し柿落しゲームは、takaken氏の作成した対戦ゲームで、石取りゲーム(Nim)を拡張したものです。

遊んだことがなければ、この記事を読む前に遊ぶことをおすすめします。ぜひ、自分で必勝戦略を構築してみてください。

干し柿落としゲームはNimより複雑であり、自明にGrundy数に帰着できるわけではありませんが、意外ときれいな構造を持っていることがわかりました。

まず準備として、Grundy数の雰囲気の説明から書きます(厳密な議論は行わないので、すでに知っている読者は飛ばしてかまいません)。

Grundy数の雰囲気

Grundy数は、不偏ゲームの局面に割り当てられる非負整数です。

不偏ゲームとは、二人零和有限確定完全情報ゲームであり、さらに手番がどちらのプレーヤーにあるかと無関係に有効な着手の集合が決まるものです。 有効な着手がなくなった時点で、勝利プレーヤーが決まります。

Grundy数は、不偏ゲームの局面が必勝局面であるか、どんな着手をすればよいかの判断に役立ちます。

将棋やチェスは、手番によって動かせる駒が異なりますので、不偏ゲームではありません。 囲碁やオセロも、手番によって置ける石の色が異なりますので、不偏ゲームではありません。 このように普通の対戦型ボードゲームは不偏ゲームではありません。

しかし、意外と身近に不偏ゲームは存在します。 まずは、不偏ゲームの例とその必勝法を見てみます。

不偏ゲームの例とその必勝法

21を言ったら負けゲーム

以下のようなゲームを考えます。

  • 先手番プレーヤーは、1から始まる連続する自然数を1つか2つか3つ言う(つまり、「1」「1、2」「1、2、3」のどれかを言う)
  • 以下、プレーヤーは交互に、直前のプレーヤーが言った数に続く連続する自然数を1つか2つか3つ言う(「1、2」「3、4、5」「6」「7、8、9」のように進行する)
  • 21を言ってしまったプレーヤーの負け

これは不偏ゲームになっています。 「21を言ってしまったら負け」という部分は、「21は言えない」ということにすれば「有効な着手がないので負け」で解釈できます。

このゲームは、後手必勝です。必勝戦略は、以下の通りです。

  • 相手が1つ言ったら3つ、2つ言ったら2つ、3つ言ったら1つの自然数を言う

こうすることで、自分の手番を常に4の倍数で終わらすことができます。 特に、自分は20を言うことができます。 つまり、相手は21を言わざるを得ない(有効な着手がない)状況に追い込まれます。

二山石取りゲーム

以下のようなゲームを考えます。

  • 盤面には、石の山が二つあり、片方の山にはk1個、もう片方の山にはk2個の石が含まれる
  • 先手番プレーヤから交互に、「石が存在する山を一つ選び、そこから1つ以上任意個の石を取り除く」を行う
  • 石が取れなくなったプレーヤーの負け

これも不偏ゲームになっています。

このゲームは、k1=k2であれば後手必勝です。必勝戦略は、以下の通りです。

  • 相手が選ばなかったほうの山から、相手と同じ数の石を取り除く

こうすることで、k1=k2を保ったまま相手に手番を回すことができます。 ゲームが進行し、k1=k2=0となった時、相手には有効な着手がありませんのでこちらの勝ちです。

不偏ゲームの必勝法の特徴

二つの例から一般化するのは乱暴ですが、実際に以下のような特徴があります。

  • 何か指標があり、それが特定の値であるとき、必敗局面である
    • 21を言ったら負けゲームでは、最後に言った自然数を4で割った余り(0で手番が回ってくると必敗)
    • 二山石取りゲームでは、各山に含まれる石の数の差(0で手番が回ってくると必敗)
  • 相手の任意の着手に対して、指標の変化を"打ち消す"ような着手をすることにより、必勝局面を維持できる

Grundy

先ほど見つけた"指標"は場当たり的で、他の不偏ゲームへの適用は不可能でした。 Grundy数は、この"指標"を統一的に割り当てる方法で、いろいろと良い性質があるようです。

具体的にどういう数が割り当てられるかというと、

  • 有効な着手がない場合、0が割り当てられる
  • k未満の任意の非負整数tについてGrundy数がtである局面へ遷移する着手があり、かつG数がkである局面へ遷移する着手がない場合、kが割り当てられる

言い換えると、次のようになります。

  • Grundy数が0である局面へ遷移する着手がない場合、その局面のGrundy数は0
  • Grundy数がkの場合、k未満の任意の非負整数tについて、Grundy数がtである局面に遷移する着手がある
    • 特に、Grundy数が0である局面に遷移する着手があることが重要

このことからGrundy数は、その局面が必敗局面であるときに0、必勝局面であるときに正の数が割り当てられることがわかります。

min-max法を用いてこのゲームの必勝戦略をみつけるだけであれば、正の数を使い分ける必要はありません。 しかし、その場合には最悪指数的に大きいゲーム木を探索する必要があります。

不偏ゲームの場合、いくつかの独立な不偏ゲームの和に分解できることがあります。 この時、その局面のGrundy数は分解されたゲームのGrundy数から求めることができます。 つまり、その局面のGrundy数を、探索することなく直に計算することができます。 これが、わざわざ正の数を使い分けることの利点です。

具体的には、各部分ゲームのGrundy数を二進法で表し、そのビットごと排他的論理和(xor)が全体ゲームのGrundy数になるという性質があります。

本題:干し柿落としゲーム

遊んでみましたか? 時間がないという場合でも、自分で遊んだほうがルールが理解できると思います。 ぜひ、以下を読む前に遊ぶことをおすすめします。最初の数問だけでも、ぜひ。

干し柿落しゲームは、以下のようなゲームです。

  • 盤面には、干し柿の山(連?)がいくつかあり、各山に何個かの干し柿が含まれる
  • 先手番プレーヤから交互に、以下の3つのうちのどれかを行う
    • 干し柿が存在する山があるとき行える:干し柿が存在する山を一つ選び、そこから1つ以上任意個の干し柿を取り除く
    • "勝利条件"が確定していない場合行える:"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる
    • "勝利条件"が確定していない場合行える:"勝利条件"を【最後に着手したプレーヤーの負け】に確定させる
  • 有効な着手がなくなった時、"勝利条件"によって勝者を決める

手を動かしてみる

"勝利条件"が確定していない場合をA、"勝利条件が【最後に着手したプレーヤーの勝ち】の場合をW、勝利条件が【最後に着手したプレーヤーの負け】の場合をLと書きます。 ゲームの盤面は、山に含まれる干し柿の数を並べて書きます。山に含まれる干し柿の数は一桁の数字で表せます。

例えば、三山あり、干し柿の数がそれぞれ1、2、3であり、"勝利条件"が確定していない盤面のことを、123Aと書きます(ステージ6の初期盤面です)。

以下、ネタバレが含まれます。

山が一つの場合

  • 0Wで手番を迎えた場合、相手が最後に着手しているのでこちらの負けです。
  • 0Lで手番を迎えた場合、相手が最後に着手しているのでこちらの勝ちです。
  • 0Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる」着手を行えば勝ちです。相手には有効な着手がないためです。

  • 1Wで手番を迎えた場合、最後の一つの干し柿を落として勝ちです。

  • 1Lで手番を迎えた場合、最後の一つの干し柿を落とすしかなく、負けです。
  • 1Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの負け】に確定させる」着手を行えば勝ちです。[]の付録に詳しく説明が書かれています。

  • 2Wで手番を迎えた場合、二つの干し柿を一度に落とせば勝ちです。

  • 2Lで手番を迎えた場合、干し柿を一つだけ落とせば、必敗局面である1Lを相手に押し付けることができて勝ちです。
  • 2Aで手番を迎えた場合、負けです。有効な着手により遷移できる局面は0A, 1A, 2W, 2Lですが、いずれも必勝局面だからです。この局面を作ることが勝利への道です。

山が複数ある場合

  • 干し柿の数が同じ山のペアがある場合、そのペアを取り除いた局面が必勝局面であれば、元の局面も必勝局面です。
    • 石取りゲーム(二山)と同様に、相手の着手と同じ着手をすることで、必勝局面を維持できるためです。

その他

  • 13Aは必敗局面です。

一般化してみる

山が一つの場合

  • kW(k>2)で手番を迎えた場合、全ての干し柿を一度に落とせば勝ちです(必敗局面0Wへの遷移)。
  • kL(k>2)で手番を迎えた場合、干し柿を一つ残すように他全部を落とせば勝ちです(必敗局面1Lへの遷移)。
  • kA(k>2)で手番を迎えた場合、干し柿を二つ残すように他全部を落とせば勝ちです(必敗局面2Aへの遷移)。

つまり、3個以上の干し柿が残っている局面で手番を迎えた場合、ルール部分に依存せず必勝です。

山が二つで、片方の干し柿が1つの場合

  • 11Wで手番を迎えた場合、負けです。二山石取りゲームk1=k2=1と全く同じ状況です。
  • 11Lで手番を迎えた場合、勝ちです。
  • 11Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる」ことで必敗局面11Wを相手に押し付けることができて勝ちです。

  • 12Wで手番を迎えた場合、11Wへ遷移すれば勝てます。

  • 12Lで手番を迎えた場合、1Lへ遷移すれば勝てます。
  • 12Aで手番を迎えた場合、2Aへ遷移すれば勝てます。

  • 13Wで手番を迎えた場合、11Wへ遷移すれば勝てます。

  • 13Lで手番を迎えた場合、1Lへ遷移すれば勝てます。
  • 13Aで手番を迎えた場合、負けです。有効な着手で遷移できる先は1A, 11A, 12A, 3A, 13W, 13Lですが、いずれも必勝局面だからです。

  • 1kW(k>3)で手番を迎えた場合、11Wへ遷移すれば勝てます。

  • 1kL(k>3)で手番を迎えた場合、1Lへ遷移すれば勝てます。
  • 1kA(k>3)で手番を迎えた場合、13Aへ遷移すれば勝てます。

山が二つで、片方の山の干し柿が2つの場合

  • 22Wで手番を迎えた場合、負けです。二山石取りゲームk1=k2=2と全く同じ状況です。
  • 22Lで手番を迎えた場合、負けです。有効な着手で遷移できる先は12L, 2Lしかなく、いずれも必勝局面だからです。
  • 22Aで手番を迎えた場合、2Aにするなり、22Wや22Lにするなど選択肢がたくさんありますが、いずれにせよ勝ちです。

  • 2kW(k>2)で手番を迎えた場合、22Wへ遷移して勝てます。

  • 2kL(k>2)で手番を迎えた場合、22Lへ遷移して勝てます。
  • 2kA(k>2)で手番を迎えた場合、2Aへ遷移して勝てます。

これ以上頑張っても法則が見えてくるわけではないので、結論に移っていきます。

【最後に着手したプレーヤーの勝ち】ルールの時

これは石取りゲーム(Nim)とまったく同様です。

各山にある干し柿の数のxorがGrundy数となっています。

山が二つ以下の場合の表を書いてみます。

W 0 1 2 3
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0

Grundy数の定義に従っていることを確認しておきます。 あるマスの値は、そのマスの左にあるマスに存在しなく、上にあるマスにも存在しない最小の非負整数になっていることがわかります。

【最後に着手したプレーヤーの負け】ルールの時

一般的なゲームでは、着手がなくなったプレーヤーの負けです。 それに対して着手がなくなったプレーヤーの勝ちというルール、一般的なゲームにおいて負けることを目的にプレイすることと同義です。 こういった勝利条件が反転したゲームは、misére ゲームと呼ばれます。

【最後に着手したプレーヤーの負け】に確定したゲームは、mis'ereゲームになっています。

一般に、miséreゲームのGrundy数を求めることは容易ではありません。 しかし、石取りゲーム(Nim)の場合には比較的簡単に求めることができます。

山が二つ以下の場合の表を書いてみます。

L 0 1 2 3
0 1 0 2 3
1 0 1 3 2
2 2 3 0 1
3 3 2 1 0

この場合でもGrundy数の定義に従っていることが確認できます。

そもそも、Wの場合と見比べるとほとんど変わっていないことがわかります。0L, 1L, 11Lの部分だけが異なります。 なぜ他の部分は変わらないのでしょうか。

00L,01L,10L,11L以外の局面のGrundy数を定義に従って計算する場合を考えます。 重要なのは、00L, 01L, 10L, 11Lの部分はGrundy数の位置を入れ替えただけであるという点です。 位置を入れ替えただけであるため、「左にあるマスに書かれている数∪上にあるマスに書かれている数」は集合として一致します。 よって「そのマスの左にあるマスに存在しなく、上にあるマスにも存在しない最小の非負整数」という部分に影響を及ぼしません。

山が三つ以上ある場合を考えます。 その場合、三次元、四次元、……の表を考えることになります。 Wの場合とGrandy数が変わるのは、111...111Lより内側だけになります。 その外側では、上で書いたこととまったく同じように、"集合として一致"するためGrundy数はWの場合と変化しません*1

つまり、【最後に着手したプレーヤーの負け】ルールの時、その局面のGrundy数は以下のように算出されます。

  • 干し柿が2個以上残っている山がある場合、各山にある干し柿の数のxorがGrundy数になっている
  • 干し柿が1個の山しかない場合、各山にある干し柿の数のxorを求め、さらに1とxorしたものがGrundy数になっている
    • 干し柿が1個の山しかない場合、もっと簡単に求める方法として、「山の数が奇数なら0、偶数なら1」がありますが、「各山にある干し柿の数のxor」を用いたほうが統一感があります

ルールが未確定の時

山が二つ以下の場合の表を書いてみます。

A 0 1 2 3 4 5 6 7
0 2 3 0 1 5 4 7 6
1 3 2 1 0 4 5 6 7
2 0 1 2 3 7 6 5 4
3 1 0 3 2 6 7 4 5
4 5 4 7 6 1 0 3 2
5 4 5 6 7 0 1 2 3
6 7 6 5 4 3 2 1 0
7 6 7 4 5 2 3 0 1

Grundy数の定義に従っていることを確認しておきます。 あるマスの値は、そのマスの左にあるマスに存在しなく、上にあるマスにも存在しなく、さらにW/Lの表の同じ位置にも存在しない最小の非負整数になっていることがわかります。

どうやらこれも排他的論理和的な雰囲気があります。 実は、以下のような法則があります。

  • A33より内側は、各山にある干し柿の数のxorを求め、さらに2とxorしたものがGrundy数になっている
  • それ以外は、各山にある干し柿の数のxorを求め、さらに1とxorしたものがGrundy数になっている

このようになる理由は、A33より内側の部分はGrundy数の出現位置を入れ替えただけであり、ラテン方陣である性質を維持しているからです。

なお、山が三つ以上ある場合も同様になっています。

注意点として、いくつかのゲームに分解してこの表の値をxorするのでは正しくも止まりません。 分解された各ゲームは、"勝利条件"を決めるという手を共有してしまっていて、独立していないからです。

干し柿落としゲームにおけるGrundy数の求め方

まとめます。

  • 【最後に着手したプレーヤーの勝ち】ルールの時、各山にある干し柿の数のxorがGrundy
  • 【最後に着手したプレーヤーの負け】ルールの時、干し柿が2個以上残っている山があれば、各山にある干し柿の数のxorがGrundy
  • 【最後に着手したプレーヤーの負け】ルールの時、干し柿が2個以上残っている山がなければ、各山にある干し柿の数のxorと1をxorしたものがGrundy
  • ルールが未確定の時、干し柿が4個以上残っている山があれば、各山にある干し柿の数のxorと1をxorしたものがGrundy
  • ルールが未確定の時、干し柿が4個以上残っている山がなければ、各山にある干し柿の数のxorと2をxorしたものがGrundy

干し柿落としゲームにおける必勝法

  • 初期局面のGrundy数が0であれば、後手必勝
  • そうでなければ、以下の条件を満たす手があるはずで、それを打ち続ければ先手必勝
    • Grundy数(G)を二進法で表した時の最高位をKとおく(K=1,2,4,...)
    • 【最後に着手したプレーヤーの勝ち】ルールの時、干し柿の数を二進法で表した時にKの位が1である山のうち一つを選び、その山に残っている干し柿の数をS個として、それがS xor G個になるように取り除く
    • 【最後に着手したプレーヤーの負け】ルールの時、かつ干し柿が二つ以上残っている山がない場合
      • 干し柿が1つの山から1つ取り除く(これしか可能な着手がないですが、勝利への道です)
    • 【最後に着手したプレーヤーの負け】ルールの時、かつ干し柿が二つ以上残っている山がある場合
      • 干し柿の数を二進法で表した時にKの位が1である山のうち一つを選び、
        • その山に残っている干し柿の数をS個として、その山がS xor G個になるように取り除くと?
          • 干し柿が二つ以上残っている山がなくなるのであれば、その山がS xor G xor 1個になるように取り除く
          • そうでなければ、その山がS xor G個になるように取り除く
    • ルールが確定していないとき、かつ干し柿が4個以上残っている山がない場合
      • Grundy数が1であれば、干し柿が奇数個ある山から干し柿を1つ取リ除く
      • Grundy数が2であれば、"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる
      • Grundy数が3であり、かつ干し柿が2個以上残っている山がない場合、"勝利条件"を【最後に着手したプレーヤーの負け】に確定させる
      • Grundy数が3であり、かつ干し柿が2個以上残っている山が一つだけということはないはず
      • Grundy数が3であり、かつ干し柿が2個以上残っている山が二つ以上ある場合、干し柿が2個の山から干し柿を1つ取り除くか、干し柿が3個の山から干し柿をすべて取リ除く
    • ルールが確定していないとき、かつ干し柿が4個以上残っている山がある場合
      • 干し柿の数を二進法で表した時にKの位が1である山のうち一つを選び、
        • その山に残っている干し柿の数をS個として、その山がS xor G個になるように取り除くと?
          • 干し柿が二つ以上残っている山がなくなるのであれば、その山がS xor G xor 3個になるように取り除く
          • そうでなければ、その山がS xor G個になるように取り除く

おわりに

干し柿落としゲームにおけるGrundy数を求めてみました。一般に、miséreゲームのGrundy数や、ルールが途中で変化するゲームのGrundy数を求めることは難しいです。 しかし、干し柿落としゲームにおいては、特定の境界線があり、その内側と外側で計算方法を変化させれば、よくあるxorを用いる方法を少し拡張するだけでGrundy数を求めることができるというきれいな性質があることがわかりました。

必勝法は、その境界をまたぐ操作であるかによって場合分けが発生し、複雑です。

しかし、境界は二の冪であり、境界をまたぐ手を打つべきかどうかは求めることができます。 よって、まず「境界をまたぐ手を打つべきか」を求め、その後具体的にどのような手を打つべきかを求めることで必勝法を構成することができました。

*1:余談ですが、擬ポテンシャルに似ている感じがします。

AtCoderを退会するための問題(ABC077/ARC084のD問題)を別解法で解いた

AtCoderを退会するための問題、の元ネタは以下のツイートです。

twitter.com

どうやらこの問題はAtCoder Regular Contest (ARC) 084のD問題「Small Multiple」として出題されたことのある、過去問のようです(併設のBeginner Contest (ABC) 077のD問題でもあります)。

この問題を自力で解いた提出が以下になります。ABC側に提出しましたが、このような併設開催だったコンテストの過去問の場合、どれに提出するのが一般的なんでしょう……?

Submission #5698661 - AtCoder Beginner Contest 077 | AtCoder

私の提出した解法は、他の提出とは異なる解法のようです。 というかあまりにもdouble ended queue (deque)による0-1BFS*1を用いた解法ばかりです。 どうやらコンテストの解説資料がこの解法によるものになっているようです。 つまり、最近の提出は「過去問演習で解けなかったので解説を見てから提出」というパターンで提出されたものなので、こういう提出ばかりになったものと思われます。

……と思っていたら、コンテスト中に提出された解法もほぼすべてが似た解法でした。さすがに洗練された0-1BFSではなく、単なるBFS(幅優先探索)やDFS(深さ優先探索)によるものもありますが、グラフの構築法は同じです。

こういう解き方もあるんだよという啓発になればと思って記事を書きます。

目次的なもの

以下の節は思考の垂れ流しなので、アルゴリズムを知りたい場合は読まなくてよいです。 ただ、「なんでこんな発想に至ったのか」ということを知る方法はあまりないので、参考にしたいことがあるかと思い一応書いておきます。

着想に至った経緯

お風呂に入っていたら思いつきました。

問題文を見てからの思考

  • なるほど、7なら1001だから2と答える感じかぁ
  • すごく大きなKの倍数が1000....0001の形になるかを判断するのは難しそう
  • 2n 5m の形なら1が答えになる
  • 2n 5m K の形なら、Kの答えと同じになる
  • もしかして2n 5m 以外だと全部1000...0001の形にできて2が答えになるのかな
    • これは間違い、例えばK=3だと3が答えになる
  • 3の倍数だけ特殊扱いすればいいのかな……?*2
  • Kは小さいので、指数時間アルゴリズムを用いてよい(※入力長log Kに対しての指数時間アルゴリズムが通るという話であって、Ο(2K)が通るという話ではないです)
  • お風呂入ろう

お風呂での思考

  • 素因数分解する問題ではなさそう
    • そもそも、大きな素数に対してどう解けばいいのか不明
  • 具体的に構成する方法がありそう
    • 根拠なし
  • まず7の時にどうやって1001にたどり着くかを考えよう
  • KのT倍について考える
  • Mの1の位から考えていく
  • 1001にたどり着く場合、7×3=21を最初に選んだわけで、Tの1の位は3
    • つまり、1倍~9倍のなかで1の位が小さくなるものを選べばよさそう
    • もちろん、貪欲にやってうまくいくとは限らなさそう
  • そうすると、10の位に2が余る
  • ここで7×14=98を選べば、さっき余った2と合わせて100になって、十進法を用いたときに各桁の和が最小となる
  • つまり、7の倍数+2の形をしたものについても十進法を用いたときに各桁の和が最小となるものを探せばよい
  • 一般に、Kの倍数だけではなく、Kの倍数+rの形をしたものに対しても探せばよい
  • rの作り方は一般に複数通りある*3ので、DPっぽい*4
  • Tのu桁目tとしてあり得る0~9のすべてに対し、r+Ktを考えて、それを10で割った余りがKTのu桁目に対応
    • 下の位から確定させていくとき、KTのu桁目を変えられるラストチャンスはTのt桁目の時
    • KTを十進法で表したときの各桁の和は、確定した部分のみの和より少なくなることはあり得ない
  • r+Kmを10で割って切り捨てたものが次のr
  • rとしてあり得るのは0~K-1のK通り
  • rに対応する頂点と、遷移(今のr→次のr)に対応する辺を考えると、頂点数K・辺数10Kの疎なグラフについての最短路問題となる
  • 辺のコストとしてありえるのは0~9
  • よって優先度付きキューを用いたdijkstra法のようなソートが必要な最短路アルゴリズムではなく、キューををたくさん用意する最短路アルゴリズムが使える
  • お風呂出よう

ここまで20分くらいでした。紙とペンがあったらもっと早く思考をまとめられたのでしょうか……?

アルゴリズムの概略

スタート地点となる頂点からは9本の辺が出る。枝t(0<t<10)は頂点K*t/10への辺である。その辺のコスト(距離)は、K*t%10である。 頂点0はゴール地点である。その他の頂点rからは10本の辺が出る。枝t(0≦t<10)は頂点K*t/10への辺である。その辺のコストは、K*t%10である。

スタート地点からゴール地点への最短路長が求める答えである。

アルゴリズムの実装における工夫

  • 辺のコストは0~9であるため、キューを10個用意する幅優先探索を行う。
    • 実際に提出したコードでは、キューは再利用せず使い捨てている。その場合、キューは54個用意する必要がある。
  • グラフをあらわに持つことはせず、その頂点を訪れたときにその場で生成する。

実装は35分くらいかかりました。もっと早く書けるようになりたいなぁ……。

提出ソースコードの解説

キューとして何を用いるべきか

キューの挿入される回数の上限値が事前にわかっているため、static_vectorが最適です。検討した他のコンテナは以下の通りです。

  • std::vectorは、push_backするとイテレータが無効になるため注意が必要です。必要な量が前もってわかるため事前に確保しておけば問題ないですが、確保量を間違えた場合に危険です。
    • 必要な容量はKです。
  • std::dequeは、危険性はありません。しかし、事前に確保できないため複数回newが走り、遅いです。
  • std::queueは、普通は内部実装がstd::dequeです。
  • std::listは、毎回newが走り、非常に遅いです。

まぁそこまで遅いアルゴリズムではないので、std::queueを使っても問題にはならないでしょう。

range-based-forを使わない理由

途中でendイテレータが変更されるためです。range-based-forは最初に一回だけend( Container )を評価します。そのため、ループの中でその後にpush_backをしてendイテレータが変更されても、ループ開始前にキューに入っていたものしか取り出されません。 「距離0」が存在するような幅優先探索に用いるキューを取り扱うためには不適です。

最短路を求める方法

q.at( cost ).push_back( rem )により、「頂点remへたどり着くためのコストは、costである」ことを記憶します。 今の頂点rにたどり着くのに必要なコストがiである場合、q.at( i + cost ).push_back( rem )により、「頂点remへたどり着くためのコストは、i + costである」ことを記憶します。 これは正確には「頂点rを直前に通って、頂点remへたどり着くまでのコスト」なので、他の行き方がある可能性が残されます。 例えば、頂点0にたどり着けるとしても、その行き方が最短路ではなく、他の行き方だともっと低コストでたどり着ける可能性が残されています。 よって、枝を張る部分(内側のfor文)でrem == 0の時にi + costを出力するのでは間違いです。

このキューをコストの低いほうから順にみていけば、ある頂点rを初めて訪れた(visited.at( r ) == false)時、その時のコストiが頂点rにたどり着くための最低コストになっています。 頂点0であればゴール地点にたどり着いたので、コストを出力して終了です。 頂点0以外であれば探索を進めます。 頂点への二回目以降の訪問は、遠回りをして到着した場合なので、その先に探索を進める必要はありません。

どこまで探索すればよいか

求めるべき答えは、Kを十進法で表したときの各桁の和以下であることが明らかです。 K=99999の場合が最も大きく、その値は45です。 よって、iは0~45の範囲を探索すればよいです。

キューは何個用意すればよいか

i = 45の場合、必ず答えが出力される(つまり終了する)ことが保証されています。 よって内側のfor文に入る時、iは最大で44です。 costは最大で9なので、q.at( 53 )へのアクセスがあり得ます。 それ以上はあり得ないので、キューは54個用意すれば十分です。

実際には、同時に使われるキューの数は10個であり、使い捨てずに節約することが可能です。

想定解法との違い

想定解法の速い実装としては、準急くきさんの提出Submission #1742945 - AtCoder Regular Contest 084 | AtCoderがわかりやすいでしょうか。

アルゴリズムの違い

考えているグラフの違い

実は考えているグラフはほとんど同じものです。 想定解法では×10, +1の二種類だけを用いたグラフです。そうではなく、×10, +1, +2, +3, +4, +5, +6, +7, +8, +9の十種類の辺を用いたグラフとすれば私の解法と同じグラフになります。 繰り上がりの部分で余計なことを考えなくてよいので、十種類の辺を用いたグラフを考えるのも自然です。

辺の向きの違い

想定解法と私の解法では以下の点が異なります。

  • スタート地点とゴール地点が入れ替わっている。
  • 有向辺の向きが逆向きになっている。

この違いは、構築を上位桁から行うか、下位桁から行うかに対応しているようです。

想定解法では、上位桁から求めていっています(10倍する操作は、考える桁を一つ下に移動することに対応します)。 私の解法では、下位桁から求めていっています(10で割る操作は、考える桁を一つ上に移動することに対応します)。

下位桁から構築するのもそんなに不自然ではないと思うのですが、競技プログラマーのほとんどが想定解法で解いているようで、不思議です。 「十進法で表したときの各桁の和」に対する典型解法だったのでしょうか……?

辺を構築しやすいか

想定解法では、辺がどの頂点とどの頂点を結んでいるか、その辺のコストはいくらか、がほぼ自明です。 私の解法では、そんなに自明ではありません。

計算量

この手のBFSの正しい時間計算量

想定解法は0-1BFSにより時間計算量Θ(K)で解けるとしています。 競技プログラミングの文脈では正しいのかもしれませんが、計算量理論的にはこれは誤りです。 なぜなら、キューの一エントリは0~K-1を格納するためにΘ(log K)ビット必要で、それがΘ(K)エントリ必要ならば空間計算量はΘ(K log K)となるからです。 空間計算量より時間計算量が小さいことはあり得ませんから、0-1BFSを用いたところでΘ(K log K)であることには変わりません。

私の解法も、同様の理由により時間計算量Θ(K log K)の解法です。

なお、普通の優先度付きキューを用いたDijkstra法の時間計算量は同様の理由により時間計算量Θ(K (log K)2)となるので、それよりオーダーとして高速なアルゴリズムだという点は間違いではありません。 Radix Heapを用いた場合は、時間計算量Θ(K log K log log K)になります。

mod Kの存在

想定解法では、10倍してmod Kをとる操作があります。 私の解法では、mod 10をとる操作があります。

一般に、変数による剰余は低速です。最近のIntel CPUだと26サイクルかかるようです。 一方、定数による剰余は乗算命令とシフト命令に最適化されるため、高速です。

私の解法ではK*tを求める部分がありますが、これは誘導変数*5であり、乗算は不要です。 実際、最近のコンパイラはこの最適化を行ってくれるようです。

一頂点からでる辺の本数

想定解法では2本であり、私の解法では10本です。

この違いは大きいようで、私の解法は想定解法より3倍程度遅いです。

おわりに

こういう問題、競技プログラミングの問題として出される(=高速な解法があることが保証される)から解けるけれど、そういうメタな情報が無かったら愚直に探す解法しか思いつけなかったような気がします。 それでも、答えを見ずに解けたときはうれしいです。 それが独自の解法であったときは特にそうです。

あと、AtCoderを退会できるくらいの実力があることはわかったので、少し自信がついたかもしれません。

*1:0-1BFSとは、辺の距離が0または1だけの場合に使える、高速な最短路発見アルゴリズムです。

*2:小さな素数には反例がなかったのでこういう思考に至ったのですが、どうやら31に対しては3が答えとなるようです。

*3:7×3=21、7×4=28なので、r=2を作る方法は二通り(以上)あります。

*4:ここでいう「DPっぽい」は、探索中の特定の状態へのたどり着き方(経路)が複数通り存在し、その先の探索には経路の情報が不要なため、全探索より効率的に探索できる状況のことを言っています。

*5:誘導変数とは、ループの周回ごとに一定量増えるような変数のことを言います。帰納変数とも呼ばれます。

二重かっこの高さを中身に合わせるtexマクロを解読する

 [\![3]\!]のような二重角かっこは、\[\!\[3\]\!\]と入力すれば出すことができます。 nath.styを導入すると、\double[とか\lBrackなどと書けるようです。

しかし、このままでは中身に高さのあるもの(分数など)を入れた場合に見栄えが良くありません。 中身に応じた高さにしてくれる\leftマクロは\double[lBrackには適用できないようです。

\!で間隔を詰める方法の場合、高さが二倍くらいの分数であれば、\!\!を使って\left\[\!\!\left[ \frac{1}{2} \right]\!\!\right]のようにすれば見栄えはよくなります。 つまり、中身の高さに応じて詰める間隔を変えないといけないということです。 どうにかして自動で変わってくれないでしょうか。

これを可能にしたマクロがBracket: LaTeXにありました。 それは、以下のようなものです。

\makeatletter
\def\Left#1#2\Right{\begingroup%
   \def\ts@r{\nulldelimiterspace=0pt \mathsurround=0pt}%
   \let\@hat=#1%
   \def\sht@im{#2}%
   \def\@t{{\mathchoice{\def\@fen{\displaystyle}\k@fel}%
          {\def\@fen{\textstyle}\k@fel}%
          {\def\@fen{\scriptstyle}\k@fel}%
          {\def\@fen{\scriptscriptstyle}\k@fel}}}%
   \def\g@rin{\ts@r\left\@hat\vphantom{\sht@im}\right.}%
   \def\k@fel{\setbox0=\hbox{$\@fen\g@rin$}\hbox{%
      $\@fen \kern.3875\wd0 \copy0 \kern-.3875\wd0%
      \llap{\copy0}\kern.3875\wd0$}}%
      \def\pt@h{\mathopen\@t}\pt@h\sht@im%
      \Right}%
\def\Right#1{\let\@hat=#1%
   \def\st@m{\mathclose\@t}%
   \st@m\endgroup}
\makeatother

このマクロを解読していきます。 私はtex言語は全くの素人なので間違った解釈があるかもしれない点に注意してください。

制御綴り

\の後に「通常の文字」がいくつか並んだものを制御綴りというそうです。 もっぱらマクロ名や変数名に使われている印象です。

\makeatletter, \makeatother

@を「通常の文字」扱いに変更する命令と、「その他の文字」扱いに戻す命令のようです。 このマクロの中で現れる制御綴りはすべて@を含んでいます。 ユーザーランドでは@は「その他の文字」であるので、うっかり@を含む制御綴りを定義することはありません。 よって@を含む制御綴りは、一種の予約語としてシステムが使うことができます。

末尾の%

末尾の改行は半角スペースに変わってしまいます(和文だとこれを取り除いてくれる機能がplatexにあるようです)。 行末に%を置くことで、半角スペースの挿入を抑止できます。 しかし、インデントのために半角スペースを入れているので意味がない気がします。 他の効果もあるようですが、よくわかりません。

\Left#1#2\Right

パターンマッチという引数の取り方で、\Leftの次のトークン(開きかっこ)を#1に入れ、\Rightが見つかるまでの残りのすべてのトークン(かっこの中身)を#2に入れるようです。

\begingroup, \endgroup

{}の代替であり、グルーピングに使うようです。 変数の代入などは、この範囲でしか影響を及ぼさないという効果があるようです。 C言語でいうところのスコープのようなものでしょうか。

なぜ代替する必要があるのかはよくわかりませんでした。

\ts@r

いきなり読めない意味不明なマクロ名ですが、{\nulldelimiterspace=0pt \mathsurround=0pt}に置換されるだけです。 \mathsurroundは、数式モードに出入りするときの空白に関するパラメータのようです。数式モードでないところで書いたときでも内部的には数式モードで描画される(後述)ので、その調整用っぽいです。 \nulldelimiterspaceはよくわかりませんでした。

\@hat

これは開きかっこを保持する変数のようです。後では閉じかっこを保持することになります。

\sht@im

かっこの中身を保持する変数のようです。

\@t

今の環境(数式モードの中か?など)によって表示するものを切り替える機能を持つ\mathchoiceを使っているようです。

\g@rin

\left\@hat\vphantom{\sht@im}\right.によって正しい高さの開きかっこだけを描画しています。 \vphantomは中身を描画せず中身を描画した時の高さになるようなものです。 \right.は閉じかっこを描画しないで\leftを閉じるものです。

k@fel

二重かっこを描画する部分です。まず\setbox0=\hbox{$\@fen\g@rin$}で適切なかっこを数式モード描画したものをbox0変数に入れます。 \kernは水平方向の位置制御、\wd0box0変数の幅、\llapは中身を重ねて描画するもののようです。 \copy0box0変数の中身を描画しています。

pt@h

開きかっこの詰め具合で必要な開きかっこを描画するようです。

本体

\pt@h\sht@im\Rightが本体で、適切な開きかっこと中身を打ち出し、このマクロのパターンマッチで消えた\Rightを復活させます。

\Right

\@hat変数に閉じかっこを入れてから\@tを呼び出すことで、上と同じ方式でうまく二重かっこを描画しています。

参考文献

128bit除算のやり方

五月祭お疲れさまでした。私はクイックソートのメモリアクセス系列の可視化の展示をしていましたが、楽しんでいただけたでしょうか……。

C言語には多倍長整数のような便利なものがありません。unsigned long longを使えば64bit整数までは取り扱えますが、それ以上になると面倒です。 ちょっと64bitをはみ出すくらいの整数を扱いたい、128bit整数型があれば……。という場合、gccやclangなら__uint128_tという型が使えます。これはその名前の通り、128bitの整数型です。 ここではx86_64を前提として、64bitマシンでどのように128bitの演算を行っているか見てみます。

足し算・引き算

x86にはadc命令・sbb命令が存在します。これはキャリー付きの足し算・ボロー付きの引き算を行う命令です。 下位64bitの計算を行った後上位64bitの計算を行うとき、下位64bitの計算での繰り上がり・繰り下がり(キャリー・ボロー)を考慮に入れた計算を行うことができます。 このように多倍長演算用の命令が用意されているため、足し算・引き算は簡単に行えます。

掛け算

x86にはmul命令が存在します。これはimul命令と異なり、64bit整数同士の積を128bit整数として求めることができる命令です。 128bitのレジスタはありませんが、結果は上位64bitと下位64bitを異なる二つのレジスタに分けて書き込まれます。

あとは通常の掛け算を3回行い、筆算のように結果を足し合わせれば128bit整数同士の積(の下位128bit分)を求めることができます。

割り算

割り算はそう簡単にはいきません。gccの場合、__udivti3というライブラリ関数呼び出しにコンパイルします。 この関数を逆アセンブルした結果、__udivti3関数は以下のような254Byteのコードになっているようです。 機械語の雰囲気はコンパイラの出力っぽいコードで、プログラマが書いた雰囲気を感じ取ることができませんでした。

   0x0000000000400560 <+0>:     mov    %rcx,%r8
   0x0000000000400563 <+3>:     mov    %rdx,%r9
   0x0000000000400566 <+6>:     mov    %rdx,%r10
   0x0000000000400569 <+9>:     test   %r8,%r8
   0x000000000040056c <+12>:    mov    %rdx,%rcx
   0x000000000040056f <+15>:    jne    0x4005a8 <__udivti3+72>
   0x0000000000400571 <+17>:    cmp    %rsi,%rdx
   0x0000000000400574 <+20>:    ja     0x400628 <__udivti3+200>
   0x000000000040057a <+26>:    test   %rdx,%rdx
   0x000000000040057d <+29>:    jne    0x40058c <__udivti3+44>
   0x000000000040057f <+31>:    mov    $0x1,%eax
   0x0000000000400584 <+36>:    xor    %edx,%edx
   0x0000000000400586 <+38>:    div    %r9
   0x0000000000400589 <+41>:    mov    %rax,%rcx
   0x000000000040058c <+44>:    mov    %rsi,%rax
   0x000000000040058f <+47>:    xor    %edx,%edx
   0x0000000000400591 <+49>:    div    %rcx
   0x0000000000400594 <+52>:    mov    %rax,%rsi
   0x0000000000400597 <+55>:    mov    %rdi,%rax
   0x000000000040059a <+58>:    div    %rcx
   0x000000000040059d <+61>:    mov    %rsi,%rdx
   0x00000000004005a0 <+64>:    retq
   0x00000000004005a1 <+65>:    nopl   0x0(%rax)
   0x00000000004005a8 <+72>:    cmp    %rsi,%r8
   0x00000000004005ab <+75>:    ja     0x400620 <__udivti3+192>
   0x00000000004005ad <+77>:    bsr    %r8,%rax
   0x00000000004005b1 <+81>:    xor    $0x3f,%rax
   0x00000000004005b5 <+85>:    test   %eax,%eax
   0x00000000004005b7 <+87>:    mov    %eax,%r11d
   0x00000000004005ba <+90>:    je     0x400638 <__udivti3+216>
   0x00000000004005bc <+92>:    mov    %eax,%ecx
   0x00000000004005be <+94>:    mov    $0x40,%edx
   0x00000000004005c3 <+99>:    shl    %cl,%r8
   0x00000000004005c6 <+102>:   movslq %eax,%rcx
   0x00000000004005c9 <+105>:   sub    %rcx,%rdx
   0x00000000004005cc <+108>:   mov    %edx,%ecx
   0x00000000004005ce <+110>:   shr    %cl,%r9
   0x00000000004005d1 <+113>:   mov    %eax,%ecx
   0x00000000004005d3 <+115>:   or     %r9,%r8
   0x00000000004005d6 <+118>:   shl    %cl,%r10
   0x00000000004005d9 <+121>:   mov    %rsi,%r9
   0x00000000004005dc <+124>:   mov    %edx,%ecx
   0x00000000004005de <+126>:   shr    %cl,%r9
   0x00000000004005e1 <+129>:   mov    %eax,%ecx
   0x00000000004005e3 <+131>:   mov    %rdi,%rax
   0x00000000004005e6 <+134>:   shl    %cl,%rsi
   0x00000000004005e9 <+137>:   mov    %edx,%ecx
   0x00000000004005eb <+139>:   mov    %r9,%rdx
   0x00000000004005ee <+142>:   shr    %cl,%rax
   0x00000000004005f1 <+145>:   or     %rax,%rsi
   0x00000000004005f4 <+148>:   mov    %rsi,%rax
   0x00000000004005f7 <+151>:   div    %r8
   0x00000000004005fa <+154>:   mov    %rdx,%r9
   0x00000000004005fd <+157>:   mov    %rax,%rsi
   0x0000000000400600 <+160>:   mul    %r10
   0x0000000000400603 <+163>:   cmp    %rdx,%r9
   0x0000000000400606 <+166>:   jb     0x400618 <__udivti3+184>
   0x0000000000400608 <+168>:   mov    %r11d,%ecx
   0x000000000040060b <+171>:   shl    %cl,%rdi
   0x000000000040060e <+174>:   cmp    %rax,%rdi
   0x0000000000400611 <+177>:   jae    0x400658 <__udivti3+248>
   0x0000000000400613 <+179>:   cmp    %rdx,%r9
   0x0000000000400616 <+182>:   jne    0x400658 <__udivti3+248>
   0x0000000000400618 <+184>:   lea    -0x1(%rsi),%rax
   0x000000000040061c <+188>:   xor    %edx,%edx
   0x000000000040061e <+190>:   retq
   0x000000000040061f <+191>:   nop
   0x0000000000400620 <+192>:   xor    %edx,%edx
   0x0000000000400622 <+194>:   xor    %eax,%eax
   0x0000000000400624 <+196>:   retq
   0x0000000000400625 <+197>:   nopl   (%rax)
   0x0000000000400628 <+200>:   mov    %rdi,%rax
   0x000000000040062b <+203>:   mov    %rsi,%rdx
   0x000000000040062e <+206>:   div    %r9
   0x0000000000400631 <+209>:   xor    %edx,%edx
   0x0000000000400633 <+211>:   retq
   0x0000000000400634 <+212>:   nopl   0x0(%rax)
   0x0000000000400638 <+216>:   cmp    %rsi,%r8
   0x000000000040063b <+219>:   jb     0x40064a <__udivti3+234>
   0x000000000040063d <+221>:   xor    %edx,%edx
   0x000000000040063f <+223>:   xor    %eax,%eax
   0x0000000000400641 <+225>:   cmp    %rdi,%r9
   0x0000000000400644 <+228>:   ja     0x4005a0 <__udivti3+64>
   0x000000000040064a <+234>:   xor    %edx,%edx
   0x000000000040064c <+236>:   mov    $0x1,%eax
   0x0000000000400651 <+241>:   retq
   0x0000000000400652 <+242>:   nopw   0x0(%rax,%rax,1)
   0x0000000000400658 <+248>:   mov    %rsi,%rax
   0x000000000040065b <+251>:   xor    %edx,%edx
   0x000000000040065d <+253>:   retq

これを少しは読みやすい疑似コードにしてみたのが以下です。 以下では、上位64bitがh、下位64bitがlであるような128bit変数の意味で(y#l)という表記を使います。変数はすべてレジスタサイズと同じ64bit整数です。

__udivti3( __uint128_t x, __uint128_t y ) {
  (xh#xl) = x;
  (yh#yl) = y;
  if( yh == 0 ) {
    if( xh >= yl ) {
      // 商が64bitに収まらない時
      if (yl == 0) {
        // 零除算例外を発生させる
        rcx = 1 / yl;
      }
      // 長除法
      uint64_t qh = xh / yl;
      uint64_t r = xh % yl;
      uint64_t ql = (r#xl) / yl;
      return (qh#ql);
    } else {
      // 商が64bitに収まる
      return (xh#xl) / yl;
    }
  } else {
    if( xh >= yh ) {
      // yh != 0なので、count_trailing_zerosを計算するbsr命令が使える
      S = 63^count_trailing_zeros( yh );
      if( S != 0 ) {
        // yの上から64bitをyhに集める
        (yh#yl) = (yh#yl) << S;
        // 商の上界値を求める
        q = ((xh#xl) >> (64-S)) / yh;
        r = ((xh#xl) >> (64-S)) / yh;
        (mh#ml) = q * yl;
        if( mh >= r ) {
          // xl << Sは、(xh#xl)>>(64-S)ではみ出した部分
          if( q >= xl << S || mh != r ) { return q; }
        }
        return q - 1;
      } else {
        // (yh#yl)が2の127乗以上の時
        if (xh <= yh && xl < yl) {
          // (xh#xl) < (yh#yl) の時(xh == yh && xl < yl)
          return 0;
        }
        return 1;
      }
    } else {
      // (xh#xl) < (yh#yl) の時(xh < yh) 
      return 0;
    }
  }
}

x86には、被除数が128bit、除数が64bitの割り算命令divが存在します。 そのため、除数が64bitに収まっている場合、単純に長除法(筆算)を行うだけで終わりです。 しかし、除数が64bitに収まらない場合、そのような計算を行う命令がなく、工夫が必要です。

概念的には、次のような計算を行っています。 まずxとyを両方ともSビットシフトして、yの最上位ビットが1になるようにします。こうすることで、除数の値を切り捨てではありますが二進有効数字64桁で表すことができます。 この状態で割り算をすると、除数を切り捨てたことから、商の上界値qが求まります(被除数も切り捨てているので議論がややこしいですが、切り捨てられた部分の大きさは1未満なので割り算の結果に影響を及ぼしません)。 この時、真の商としてあり得るのはqq-1になります(真の除数は切り捨てた部分の影響は2^-63未満であることによります)。 後はylxlの情報を用いてそのどちらかになるかを決定しています(この部分はよく確認していません)。

C言語における移植性のある算術シフトの記述方法

多くのCPUには、算術シフト演算命令が含まれています。そのため、多くのコンパイラは、符号付き整数に対する右シフトを算術シフトにコンパイルします。 しかし、C言語において、符号付き整数を右シフトした場合の挙動は処理系定義です。処理系定義というのは、以下のようなものです。

  • 未定義動作ではなく、決定的な挙動を示す
  • 処理系*1によって挙動が変わるかもしれない
  • 処理系のドキュメントに、どういう動作になるかが記載されている*2

よって、移植性のあるコードを書くためには、符号付き整数に対して右シフトをすることは避けたいところです。

符号付き整数に対する右シフトと等価なコードは、if文の利用等により、書くこと自体はできます。 しかし、せっかくなので、CPUに存在する算術シフト命令を使える方法を考えてみます。

割り算を使う方法

定数での割り算の場合、コンパイラは算術シフト命令へ最適化することがあります。 これを利用できないかと考えてみます。

右シフトの代わりに除算を使う方法は、負数に対して異なる結果を与えるため不適です。 よって、オペランドの正負によって場合分けが必要です。

いろいろとif文の条件を工夫してコンパイラにヒントを与えてみましたが、コンパイラに算術シフト命令を吐かせることはできませんでした。

どうやら、定数除算を算術シフト命令に変換する最適化は、コード丸ごとの置換であり、最適化のかなり後ろの段階で行われているようです。

符号なし整数を利用する方法

clangの場合、以下のコードでやりたいことを見抜いてくれます。

std::int64_t sar( std::int64_t x ) {
    std::uint64_t y = x;
    y += 1ull << 63;
    y >>= 1;
    y -= 1ull << 62;
    return y;
}

このコードは、ystd::int64_tにキャストする際にオーバーフローする可能性があり、完全とは言えません。 分岐を行うことでオーバーフローを防ぐ、完全なコードは以下になります。std::bit_castを使うのも悪くないでしょう。

std::int64_t sar( std::int64_t x ) {
    static constexpr std::int64_t min = -0x7fffffffffffffff - 1;
    static constexpr std::uint64_t bias = 0x8000000000000000;
    std::uint64_t y = x;
    y += bias;
    y >>= 1;
    y -= bias >> 1;
    return y < bias ?  static_cast<std::int64_t>(y)
                    : static_cast<std::int64_t>(y-bias) + min;
}

これらのコードは無意味に複雑ですが、最適化オプション-O1などでコンパイルすれば単なる算術シフト命令になります(x86_64向けclangのいろんなバージョンで確認)。

今後の課題

  • clang系以外(gcc, msvc, icc)に算術シフト命令を吐かせる方法はいまだ不明
  • シフト量に変数を用いる場合の方法が不明

*1:インタプリタとかも含む表現なのですが、実質的にはコンパイラと解釈して間違いないです。

*2:記載されないものは、「未規定」と呼ばれます。

テンプレートクラスを継承したクラステンプレートを作るときの罠

何回も言われていることだけれど、つまづくことが多いところなのでメモしておきます。

以下のようなコードで、コンパイルエラーになるときの対処法です。

template<class U>
class Base {
public:
    int f() { return 1; }
};

template<class T>
class Derived : Base<T> {
  int g() { return f(); }
};

g++では、error: there are no arguments to 'f' that depend on a template parameter, so a declaration of 'f' must be available [-fpermissive]というメッセージが出ます。 clang++では、error: use of undeclared identifier 'f'というメッセージが出ます。これは不親切ですね……。

それに加えて、グローバル空間にf()が定義されていた場合、何の警告も出ずにそっちに誤爆してしまいます。こういうことが起こるとかなり混乱します(デバッガでどの関数が呼ばれているかを確認できれば、バグ取り自体は簡単ですが……)。

このような現象は、以下の条件を全て満たしたとき、起こります。

  • クラステンプレートを書いている(今回は、template<class T>Derivedが該当)
  • そのクラステンプレートが、テンプレートクラス(今回は、Base<T>が該当)を継承している
  • その継承元のテンプレートクラスのテンプレート引数として、書いているクラステンプレートのテンプレート引数(今回は、Tが該当)を使っている
    • Tを使っていない場合、たとえばstd::vector<int>を継承、といった場合は該当しません
  • 継承元のテンプレートクラスの変数や関数を使っている場合
    • ただし、関数の場合、引数によっては問題ないこともあって、混乱のもととなります

解決方法

this->f()のようにthisをつける。あるいは、Base<T>::f()とする。

なぜ問題が発生するのか

  1. 何も修飾されていないf()について、コンパイラは、Derivedメンバ関数だと思って探しに行きますが、ありません。
  2. 継承元クラスのメンバ関数の可能性を検討しますが、Tが確定していない以上、継承元クラスも確定しません。よって、継承元クラスは検索されません。
  3. 順々にスコープを広げて前方宣言があるかを探していきますが、グローバル空間まで行ってもやはりありません。
  4. よってコンパイルエラーになります。

重要なのは、f()はテンプレート引数Tと無関係な風に見えるということです。 こういう場合、コンパイラTが確定していない段階でf()がどの関数に該当するのかを探しに行きます。 テンプレートの中であってもTと無関係であれば、C言語と同様、ソースコードの上の方に探しに行きます。 Baseが上の方に書いてあるから見つけられるはず、という風に考えるのは間違いです。なぜなら、TによってはBase<T>クラスが特殊化される可能性が残されているからです。

テンプレートクラスがstd::vector<int>などのように、確定する場合は、2.の部分で継承元クラスが検索されるため、問題が発生しなくなります。 特殊化される可能性が残されている点は同じですが、使った後に特殊化した場合はコンパイルエラーになります。

なぜthisなどで問題が解決するか

thisの型は、Derived<T>*です。ここには、Tの情報が含まれています。そのような「テンプレート引数に依存したもの」が含まれている場合、Tが確定してからf()がどの関数に該当するのかを探しに行きます(Two Phase Lookup)。

Base<T>::f()とする場合も、「テンプレート引数に依存したもの」が含まれているため、Tが確定してからf()がどの関数に該当するのかを探しに行きます。