浮動小数点型の典型撃墜ケース

これいる？

諸々の形式でのそれっぽい状況における撃墜ケースを挙げる。 f32, f64, f80, f128 はそれぞれ 24-, 53-, 64-, 113-bit 仮数部の二進浮動小数点型、Decimal は Python における Decimal のデフォルトの精度（getcontext().prec = 28）に相当する。

精度が上がると最小反例も大きくなるタイプの問題設定とそうでないものがある。また、定数回の演算によって境界条件（整数との比較など）が成り立たなくなるものを主な対象とし、演算をたくさん繰り返すことにより誤差が累積するものは対象外とする。

撃墜ケースたち

素朴な問題設定における、実数での性質が浮動小数点型で成り立たない例を挙げる。過去の記事を書いたものも多いので、関連するリンクも併せて載せてある。 実際の問題設定においては、期待される値よりも大きくなることで撃墜できる状況と、小さくなることで撃墜できる状況があるため、可能な限り両側についての例を構成した。

約分

$x_0, x_1\in\N$ であって $( (x_1\oslash x_0)\otimes x_0) \ne x_1$ を満たす例。$x_1$ より小さくなる例と大きくなる例をそれぞれ示す。

• f32:
  • $( (13\oslash 11)\otimes 11) = 13 - 2^{-20}$
  • $( (7\oslash 13)\otimes 13) = 7 + 2^{-21}$
• f64:
  • $( (15\oslash 11)\otimes 11) = 15 - 2^{-49}$
  • $( (7\oslash 25)\otimes 25) = 7 + 2^{-50}$
• f80:
  • $( (13\oslash 11)\otimes 11) = 13 - 2^{-60}$
  • $( (7\oslash 13)\otimes 13) = 7 + 2^{-61}$
• f128:
  • $( (15\oslash 11)\otimes 11) = 15 - 2^{-109}$
  • $( (11\oslash 19)\otimes 19) = 11 + 2^{-109}$
• Decimal
  • $( (1\oslash 3)\otimes 3) = 1 - 10^{-28}$
  • $( (5\oslash 3)\otimes 3) = 5 + 10^{-27}$

rsk0315.hatenablog.com

整数への変換

十進表記で受け取って $10$ の冪乗を掛けることにより整数への変換を試みた際に誤差が生じる例。各桁数について大小両側を示す。

$1$ 以上の例については以下の通り。

• f32:
  • $\roundcirc{4.01} \otimes 10^{2} = 401 + 2^{-15}$
  • $\roundcirc{1.05} \otimes 10^{2} = 105 - 2^{-17}$
  • $\roundcirc{1.001} \otimes 10^{3} = 1001 + 2^{-14}$
  • $\roundcirc{2.001} \otimes 10^{3} = 2001 - 2^{-13}$
  • $\roundcirc{2.0001} \otimes 10^{4} = 20001 - 2^{-9}$
  • $\roundcirc{1.0003} \otimes 10^{4} = 10003 + 2^{-10}$
  • $\roundcirc{8.00001} \otimes 10^{5} = 800001 - 2^{-4}$
  • $\roundcirc{1.00003} \otimes 10^{5} = 100003 + 2^{-7}$
  • $\roundcirc{1.000001} \otimes 10^{6} = 1000001 - 2^{-4}$
  • $\roundcirc{2.000003} \otimes 10^{6} = 2000003 + 2^{-3}$
• f64:
  • $\roundcirc{2.01} \otimes 10^{2} = 201 - 2^{-45}$
  • $\roundcirc{8.05} \otimes 10^{2} = 805 + 2^{-43}$
  • $\roundcirc{1.001} \otimes 10^{3} = 1001 - 2^{-43}$
  • $\roundcirc{4.001} \otimes 10^{3} = 4001 + 2^{-41}$
  • $\roundcirc{2.0001} \otimes 10^{4} = 20001 + 2^{-38}$
  • $\roundcirc{1.0009} \otimes 10^{4} = 10009 - 2^{-39}$
  • $\roundcirc{4.00001} \otimes 10^{5} = 400001 - 2^{-34}$
  • $\roundcirc{2.00003} \otimes 10^{5} = 200003 + 2^{-35}$
  • $\roundcirc{1.000001} \otimes 10^{6} = 1000001 - 2^{-33}$
  • $\roundcirc{2.000001} \otimes 10^{6} = 2000001 + 2^{-32}$
  • $\roundcirc{1.0000002} \otimes 10^{7} = 10000002 - 2^{-29}$
  • $\roundcirc{2.0000007} \otimes 10^{7} = 20000007 + 2^{-28}$
  • $\roundcirc{8.00000001} \otimes 10^{8} = 800000001 + 2^{-23}$
  • $\roundcirc{2.00000003} \otimes 10^{8} = 200000003 - 2^{-25}$
  • $\roundcirc{1 + 1\cdot 10^{-9}} \otimes 10^{9} = (1\cdot 10^{9} + 1) + 2^{-23}$
  • $\roundcirc{2 + 3\cdot 10^{-9}} \otimes 10^{9} = (2\cdot 10^{9} + 3) - 2^{-22}$
  • $\roundcirc{1 + 12\cdot 10^{-10}} \otimes 10^{10} = (1\cdot 10^{10} + 12) + 2^{-19}$
  • $\roundcirc{1 + 14\cdot 10^{-10}} \otimes 10^{10} = (1\cdot 10^{10} + 14) - 2^{-19}$
  • $\roundcirc{8 + 1\cdot 10^{-11}} \otimes 10^{11} = (8\cdot 10^{11} + 1) - 2^{-13}$
  • $\roundcirc{1 + 93\cdot 10^{-11}} \otimes 10^{11} = (1\cdot 10^{11} + 93) + 2^{-16}$
  • $\roundcirc{1 + 1\cdot 10^{-12}} \otimes 10^{12} = (1\cdot 10^{12} + 1) + 2^{-13}$
  • $\roundcirc{2 + 3\cdot 10^{-12}} \otimes 10^{12} = (2\cdot 10^{12} + 3) - 2^{-12}$
  • $\roundcirc{2 + 3\cdot 10^{-13}} \otimes 10^{13} = (2\cdot 10^{13} + 3) + 2^{-8}$
  • $\roundcirc{1 + 4\cdot 10^{-13}} \otimes 10^{13} = (1\cdot 10^{13} + 4) - 2^{-9}$
  • $\roundcirc{2 + 1\cdot 10^{-14}} \otimes 10^{14} = (2\cdot 10^{14} + 1) + 2^{-5}$
  • $\roundcirc{8 + 7\cdot 10^{-14}} \otimes 10^{14} = (8\cdot 10^{14} + 7) - 2^{-3}$
  • $\roundcirc{1 + 1\cdot 10^{-15}} \otimes 10^{15} = (1\cdot 10^{15} + 1) + 2^{-3}$
  • $\roundcirc{4 + 3\cdot 10^{-15}} \otimes 10^{15} = (4\cdot 10^{15} + 3) - 2^{-1}$
• f80:
  • $\roundcirc{4.01} \otimes 10^{2} = 401 + 2^{-55}$
  • $\roundcirc{1.05} \otimes 10^{2} = 105 - 2^{-57}$
  • $\roundcirc{1.002} \otimes 10^{3} = 1002 + 2^{-54}$
  • $\roundcirc{1.003} \otimes 10^{3} = 1003 - 2^{-54}$
  • $\roundcirc{1.0001} \otimes 10^{4} = 10001 + 2^{-50}$
  • $\roundcirc{8.0005} \otimes 10^{4} = 80005 - 2^{-47}$
  • $\roundcirc{8.00001} \otimes 10^{5} = 800001 - 2^{-44}$
  • $\roundcirc{1.00002} \otimes 10^{5} = 100002 + 2^{-47}$
  • $\roundcirc{2.000001} \otimes 10^{6} = 2000001 - 2^{-43}$
  • $\roundcirc{4.000001} \otimes 10^{6} = 4000001 + 2^{-42}$
  • $\roundcirc{1.0000001} \otimes 10^{7} = 10000001 - 2^{-40}$
  • $\roundcirc{8.0000011} \otimes 10^{7} = 80000011 + 2^{-37}$
  • $\roundcirc{1.00000001} \otimes 10^{8} = 100000001 + 2^{-37}$
  • $\roundcirc{4.00000003} \otimes 10^{8} = 400000003 - 2^{-35}$
  • $\roundcirc{2 + 1\cdot 10^{-9}} \otimes 10^{9} = (2\cdot 10^{9} + 1) - 2^{-33}$
  • $\roundcirc{8 + 1\cdot 10^{-9}} \otimes 10^{9} = (8\cdot 10^{9} + 1) + 2^{-31}$
  • $\roundcirc{8 + 1\cdot 10^{-10}} \otimes 10^{10} = (8\cdot 10^{10} + 1) - 2^{-27}$
  • $\roundcirc{2 + 3\cdot 10^{-10}} \otimes 10^{10} = (2\cdot 10^{10} + 3) + 2^{-29}$
  • $\roundcirc{1 + 1\cdot 10^{-11}} \otimes 10^{11} = (1\cdot 10^{11} + 1) - 2^{-27}$
  • $\roundcirc{2 + 3\cdot 10^{-11}} \otimes 10^{11} = (2\cdot 10^{11} + 3) + 2^{-26}$
  • $\roundcirc{8 + 1\cdot 10^{-12}} \otimes 10^{12} = (8\cdot 10^{12} + 1) + 2^{-21}$
  • $\roundcirc{1 + 8\cdot 10^{-12}} \otimes 10^{12} = (1\cdot 10^{12} + 8) - 2^{-24}$
  • $\roundcirc{8 + 3\cdot 10^{-13}} \otimes 10^{13} = (8\cdot 10^{13} + 3) - 2^{-17}$
  • $\roundcirc{4 + 5\cdot 10^{-13}} \otimes 10^{13} = (4\cdot 10^{13} + 5) + 2^{-18}$
  • $\roundcirc{4 + 1\cdot 10^{-14}} \otimes 10^{14} = (4\cdot 10^{14} + 1) - 2^{-15}$
  • $\roundcirc{2 + 3\cdot 10^{-14}} \otimes 10^{14} = (2\cdot 10^{14} + 3) + 2^{-16}$
  • $\roundcirc{1 + 1\cdot 10^{-15}} \otimes 10^{15} = (1\cdot 10^{15} + 1) - 2^{-14}$
  • $\roundcirc{2 + 1\cdot 10^{-15}} \otimes 10^{15} = (2\cdot 10^{15} + 1) + 2^{-13}$
  • $\roundcirc{2 + 3\cdot 10^{-16}} \otimes 10^{16} = (2\cdot 10^{16} + 3) + 2^{-9}$
  • $\roundcirc{8 + 5\cdot 10^{-16}} \otimes 10^{16} = (8\cdot 10^{16} + 5) - 2^{-7}$
  • $\roundcirc{8 + 1\cdot 10^{-17}} \otimes 10^{17} = (8\cdot 10^{17} + 1) + 2^{-4}$
  • $\roundcirc{1 + 2\cdot 10^{-17}} \otimes 10^{17} = (1\cdot 10^{17} + 2) - 2^{-7}$
  • $\roundcirc{2 + 1\cdot 10^{-18}} \otimes 10^{18} = (2\cdot 10^{18} + 1) + 2^{-3}$
  • $\roundcirc{4 + 1\cdot 10^{-18}} \otimes 10^{18} = (4\cdot 10^{18} + 1) - 2^{-2}$
• f128:
  • $\roundcirc{2.01} \otimes 10^{2} = 201 - 2^{-105}$
  • $\roundcirc{8.05} \otimes 10^{2} = 805 + 2^{-103}$
  • $\roundcirc{8.001} \otimes 10^{3} = 8001 + 2^{-100}$
  • $\roundcirc{1.003} \otimes 10^{3} = 1003 - 2^{-103}$
  • $\roundcirc{4.0001} \otimes 10^{4} = 40001 + 2^{-97}$
  • $\roundcirc{1.0043} \otimes 10^{4} = 10043 - 2^{-99}$
  • $\roundcirc{8.00001} \otimes 10^{5} = 800001 + 2^{-93}$
  • $\roundcirc{1.00002} \otimes 10^{5} = 100002 - 2^{-96}$
  • $\roundcirc{2.000001} \otimes 10^{6} = 2000001 + 2^{-92}$
  • $\roundcirc{4.000001} \otimes 10^{6} = 4000001 - 2^{-91}$
  • $\roundcirc{2.0000001} \otimes 10^{7} = 20000001 - 2^{-88}$
  • $\roundcirc{8.0000005} \otimes 10^{7} = 80000005 + 2^{-86}$
  • $\roundcirc{2.00000001} \otimes 10^{8} = 200000001 + 2^{-85}$
  • $\roundcirc{8.00000001} \otimes 10^{8} = 800000001 - 2^{-83}$
  • $\roundcirc{1 + 1\cdot 10^{-9}} \otimes 10^{9} = (1\cdot 10^{9} + 1) - 2^{-83}$
  • $\roundcirc{1 + 2\cdot 10^{-9}} \otimes 10^{9} = (1\cdot 10^{9} + 2) + 2^{-83}$
  • $\roundcirc{2 + 3\cdot 10^{-10}} \otimes 10^{10} = (2\cdot 10^{10} + 3) - 2^{-78}$
  • $\roundcirc{1 + 4\cdot 10^{-10}} \otimes 10^{10} = (1\cdot 10^{10} + 4) + 2^{-79}$
  • $\roundcirc{2 + 1\cdot 10^{-11}} \otimes 10^{11} = (2\cdot 10^{11} + 1) - 2^{-75}$
  • $\roundcirc{8 + 5\cdot 10^{-11}} \otimes 10^{11} = (8\cdot 10^{11} + 5) + 2^{-73}$
  • $\roundcirc{1 + 1\cdot 10^{-12}} \otimes 10^{12} = (1\cdot 10^{12} + 1) - 2^{-73}$
  • $\roundcirc{4 + 1\cdot 10^{-12}} \otimes 10^{12} = (4\cdot 10^{12} + 1) + 2^{-71}$
  • $\roundcirc{2 + 1\cdot 10^{-13}} \otimes 10^{13} = (2\cdot 10^{13} + 1) + 2^{-68}$
  • $\roundcirc{1 + 9\cdot 10^{-13}} \otimes 10^{13} = (1\cdot 10^{13} + 9) - 2^{-69}$
  • $\roundcirc{1 + 2\cdot 10^{-14}} \otimes 10^{14} = (1\cdot 10^{14} + 2) + 2^{-66}$
  • $\roundcirc{1 + 8\cdot 10^{-14}} \otimes 10^{14} = (1\cdot 10^{14} + 8) - 2^{-66}$
  • $\roundcirc{1 + 1\cdot 10^{-15}} \otimes 10^{15} = (1\cdot 10^{15} + 1) + 2^{-63}$
  • $\roundcirc{4 + 3\cdot 10^{-15}} \otimes 10^{15} = (4\cdot 10^{15} + 3) - 2^{-61}$
  • $\roundcirc{8 + 7\cdot 10^{-16}} \otimes 10^{16} = (8\cdot 10^{16} + 7) - 2^{-56}$
  • $\roundcirc{1 + 10\cdot 10^{-16}} \otimes 10^{16} = (1\cdot 10^{16} + 10) + 2^{-59}$
  • $\roundcirc{8 + 1\cdot 10^{-17}} \otimes 10^{17} = (8\cdot 10^{17} + 1) + 2^{-53}$
  • $\roundcirc{2 + 3\cdot 10^{-17}} \otimes 10^{17} = (2\cdot 10^{17} + 3) - 2^{-55}$
  • $\roundcirc{1 + 1\cdot 10^{-18}} \otimes 10^{18} = (1\cdot 10^{18} + 1) + 2^{-53}$
  • $\roundcirc{8 + 1\cdot 10^{-18}} \otimes 10^{18} = (8\cdot 10^{18} + 1) - 2^{-50}$
  • $\roundcirc{1 + 2\cdot 10^{-19}} \otimes 10^{19} = (1\cdot 10^{19} + 2) + 2^{-49}$
  • $\roundcirc{8 + 13\cdot 10^{-19}} \otimes 10^{19} = (8\cdot 10^{19} + 13) - 2^{-46}$
  • $\roundcirc{8 + 1\cdot 10^{-20}} \otimes 10^{20} = (8\cdot 10^{20} + 1) + 2^{-43}$
  • $\roundcirc{2 + 3\cdot 10^{-20}} \otimes 10^{20} = (2\cdot 10^{20} + 3) - 2^{-45}$
  • $\roundcirc{2 + 1\cdot 10^{-21}} \otimes 10^{21} = (2\cdot 10^{21} + 1) - 2^{-42}$
  • $\roundcirc{1 + 2\cdot 10^{-21}} \otimes 10^{21} = (1\cdot 10^{21} + 2) + 2^{-43}$
  • $\roundcirc{1 + 1\cdot 10^{-22}} \otimes 10^{22} = (1\cdot 10^{22} + 1) - 2^{-39}$
  • $\roundcirc{4 + 23\cdot 10^{-22}} \otimes 10^{22} = (4\cdot 10^{22} + 23) + 2^{-37}$
  • $\roundcirc{8 + 3\cdot 10^{-23}} \otimes 10^{23} = (8\cdot 10^{23} + 3) + 2^{-33}$
  • $\roundcirc{1 + 4\cdot 10^{-23}} \otimes 10^{23} = (1\cdot 10^{23} + 4) - 2^{-36}$
  • $\roundcirc{1 + 1\cdot 10^{-24}} \otimes 10^{24} = (1\cdot 10^{24} + 1) + 2^{-33}$
  • $\roundcirc{8 + 1\cdot 10^{-24}} \otimes 10^{24} = (8\cdot 10^{24} + 1) - 2^{-30}$
  • $\roundcirc{2 + 7\cdot 10^{-25}} \otimes 10^{25} = (2\cdot 10^{25} + 7) - 2^{-28}$
  • $\roundcirc{8 + 13\cdot 10^{-25}} \otimes 10^{25} = (8\cdot 10^{25} + 13) + 2^{-26}$
  • $\roundcirc{1 + 1\cdot 10^{-26}} \otimes 10^{26} = (1\cdot 10^{26} + 1) + 2^{-26}$
  • $\roundcirc{4 + 3\cdot 10^{-26}} \otimes 10^{26} = (4\cdot 10^{26} + 3) - 2^{-24}$
  • $\roundcirc{2 + 1\cdot 10^{-27}} \otimes 10^{27} = (2\cdot 10^{27} + 1) - 2^{-22}$
  • $\roundcirc{1 + 3\cdot 10^{-27}} \otimes 10^{27} = (1\cdot 10^{27} + 3) + 2^{-23}$
  • $\roundcirc{8 + 19\cdot 10^{-28}} \otimes 10^{28} = (8\cdot 10^{28} + 19) + 2^{-16}$
  • $\roundcirc{1 + 78\cdot 10^{-28}} \otimes 10^{28} = (1\cdot 10^{28} + 78) - 2^{-19}$
  • $\roundcirc{2 + 1\cdot 10^{-29}} \otimes 10^{29} = (2\cdot 10^{29} + 1) - 2^{-15}$
  • $\roundcirc{8 + 7\cdot 10^{-29}} \otimes 10^{29} = (8\cdot 10^{29} + 7) + 2^{-13}$
  • $\roundcirc{1 + 2\cdot 10^{-30}} \otimes 10^{30} = (1\cdot 10^{30} + 2) + 2^{-13}$
  • $\roundcirc{2 + 3\cdot 10^{-30}} \otimes 10^{30} = (2\cdot 10^{30} + 3) - 2^{-12}$
  • $\roundcirc{2 + 1\cdot 10^{-31}} \otimes 10^{31} = (2\cdot 10^{31} + 1) + 2^{-9}$
  • $\roundcirc{1 + 2\cdot 10^{-31}} \otimes 10^{31} = (1\cdot 10^{31} + 2) - 2^{-10}$
  • $\roundcirc{8 + 1\cdot 10^{-32}} \otimes 10^{32} = (8\cdot 10^{32} + 1) - 2^{-3}$
  • $\roundcirc{1 + 6\cdot 10^{-32}} \otimes 10^{32} = (1\cdot 10^{32} + 6) + 2^{-6}$
  • $\roundcirc{2 + 1\cdot 10^{-33}} \otimes 10^{33} = (2\cdot 10^{33} + 1) + 2^{-2}$
  • $\roundcirc{1 + 2\cdot 10^{-33}} \otimes 10^{33} = (1\cdot 10^{33} + 2) - 2^{-3}$

また、$1$ 未満の例については以下の通り。

• f32:
  • $\roundcirc{0.15} \otimes 10^{2} = 15 + 2^{-20}$
  • $\roundcirc{0.53} \otimes 10^{2} = 53 - 2^{-18}$
  • $\roundcirc{0.127} \otimes 10^{3} = 127 + 2^{-17}$
  • $\roundcirc{0.251} \otimes 10^{3} = 251 - 2^{-16}$
  • $\roundcirc{0.0003} \otimes 10^{4} = 3 + 2^{-22}$
  • $\roundcirc{0.0007} \otimes 10^{4} = 7 - 2^{-21}$
  • $\roundcirc{0.00015} \otimes 10^{5} = 15 + 2^{-20}$
  • $\roundcirc{0.00027} \otimes 10^{5} = 27 - 2^{-19}$
  • $\roundcirc{0.000123} \otimes 10^{6} = 123 + 2^{-17}$
  • $\roundcirc{0.000247} \otimes 10^{6} = 247 - 2^{-16}$
• f64:
  • $\roundcirc{0.07} \otimes 10^{2} = 7 + 2^{-50}$
  • $\roundcirc{0.29} \otimes 10^{2} = 29 - 2^{-48}$
  • $\roundcirc{0.0003} \otimes 10^{4} = 3 - 2^{-51}$
  • $\roundcirc{0.0051} \otimes 10^{4} = 51 + 2^{-47}$
  • $\roundcirc{0.00007} \otimes 10^{5} = 7 - 2^{-50}$
  • $\roundcirc{0.00051} \otimes 10^{5} = 51 + 2^{-47}$
  • $\roundcirc{0.000123} \otimes 10^{6} = 123 + 2^{-46}$
  • $\roundcirc{0.000249} \otimes 10^{6} = 249 - 2^{-45}$
  • $\roundcirc{21\cdot 10^{-7}} \otimes 10^{7} = 21 - 2^{-48}$
  • $\roundcirc{25\cdot 10^{-7}} \otimes 10^{7} = 25 + 2^{-48}$
  • $\roundcirc{3\cdot 10^{-8}} \otimes 10^{8} = 3 - 2^{-51}$
  • $\roundcirc{7\cdot 10^{-8}} \otimes 10^{8} = 7 + 2^{-50}$
  • $\roundcirc{15\cdot 10^{-9}} \otimes 10^{9} = 15 - 2^{-49}$
  • $\roundcirc{61\cdot 10^{-9}} \otimes 10^{9} = 61 + 2^{-47}$
  • $\roundcirc{21\cdot 10^{-10}} \otimes 10^{10} = 21 + 2^{-48}$
  • $\roundcirc{43\cdot 10^{-10}} \otimes 10^{10} = 43 - 2^{-47}$
  • $\roundcirc{1\cdot 10^{-11}} \otimes 10^{11} = 1 - 2^{-53}$
  • $\roundcirc{99\cdot 10^{-11}} \otimes 10^{11} = 99 + 2^{-46}$
  • $\roundcirc{31\cdot 10^{-12}} \otimes 10^{12} = 31 + 2^{-48}$
  • $\roundcirc{61\cdot 10^{-12}} \otimes 10^{12} = 61 - 2^{-47}$
  • $\roundcirc{7\cdot 10^{-13}} \otimes 10^{13} = 7 + 2^{-50}$
  • $\roundcirc{27\cdot 10^{-13}} \otimes 10^{13} = 27 - 2^{-48}$
  • $\roundcirc{7\cdot 10^{-14}} \otimes 10^{14} = 7 + 2^{-50}$
  • $\roundcirc{23\cdot 10^{-14}} \otimes 10^{14} = 23 - 2^{-48}$
  • $\roundcirc{29\cdot 10^{-15}} \otimes 10^{15} = 29 + 2^{-48}$
  • $\roundcirc{115\cdot 10^{-15}} \otimes 10^{15} = 115 - 2^{-46}$
• f80:
  • $\roundcirc{0.15} \otimes 10^{2} = 15 + 2^{-60}$
  • $\roundcirc{0.53} \otimes 10^{2} = 53 - 2^{-58}$
  • $\roundcirc{0.001} \otimes 10^{3} = 1 - 2^{-64}$
  • $\roundcirc{0.253} \otimes 10^{3} = 253 + 2^{-56}$
  • $\roundcirc{0.0023} \otimes 10^{4} = 23 + 2^{-59}$
  • $\roundcirc{0.0031} \otimes 10^{4} = 31 - 2^{-59}$
  • $\roundcirc{0.00013} \otimes 10^{5} = 13 - 2^{-60}$
  • $\roundcirc{0.00027} \otimes 10^{5} = 27 + 2^{-59}$
  • $\roundcirc{0.000123} \otimes 10^{6} = 123 + 2^{-57}$
  • $\roundcirc{0.000125} \otimes 10^{6} = 125 - 2^{-57}$
  • $\roundcirc{15\cdot 10^{-7}} \otimes 10^{7} = 15 - 2^{-60}$
  • $\roundcirc{21\cdot 10^{-7}} \otimes 10^{7} = 21 + 2^{-59}$
  • $\roundcirc{7\cdot 10^{-8}} \otimes 10^{8} = 7 - 2^{-61}$
  • $\roundcirc{13\cdot 10^{-8}} \otimes 10^{8} = 13 + 2^{-60}$
  • $\roundcirc{31\cdot 10^{-9}} \otimes 10^{9} = 31 - 2^{-59}$
  • $\roundcirc{125\cdot 10^{-9}} \otimes 10^{9} = 125 + 2^{-57}$
  • $\roundcirc{93\cdot 10^{-10}} \otimes 10^{10} = 93 + 2^{-57}$
  • $\roundcirc{101\cdot 10^{-10}} \otimes 10^{10} = 101 - 2^{-57}$
  • $\roundcirc{419\cdot 10^{-11}} \otimes 10^{11} = 419 + 2^{-55}$
  • $\roundcirc{497\cdot 10^{-11}} \otimes 10^{11} = 497 - 2^{-55}$
  • $\roundcirc{31\cdot 10^{-12}} \otimes 10^{12} = 31 + 2^{-59}$
  • $\roundcirc{61\cdot 10^{-12}} \otimes 10^{12} = 61 - 2^{-58}$
  • $\roundcirc{31\cdot 10^{-13}} \otimes 10^{13} = 31 + 2^{-59}$
  • $\roundcirc{45\cdot 10^{-13}} \otimes 10^{13} = 45 - 2^{-58}$
  • $\roundcirc{3\cdot 10^{-14}} \otimes 10^{14} = 3 - 2^{-62}$
  • $\roundcirc{61\cdot 10^{-14}} \otimes 10^{14} = 61 + 2^{-58}$
  • $\roundcirc{15\cdot 10^{-15}} \otimes 10^{15} = 15 - 2^{-60}$
  • $\roundcirc{29\cdot 10^{-15}} \otimes 10^{15} = 29 + 2^{-59}$
  • $\roundcirc{3\cdot 10^{-16}} \otimes 10^{16} = 3 - 2^{-62}$
  • $\roundcirc{195\cdot 10^{-16}} \otimes 10^{16} = 195 + 2^{-56}$
  • $\roundcirc{15\cdot 10^{-17}} \otimes 10^{17} = 15 - 2^{-60}$
  • $\roundcirc{27\cdot 10^{-17}} \otimes 10^{17} = 27 + 2^{-59}$
  • $\roundcirc{7\cdot 10^{-18}} \otimes 10^{18} = 7 - 2^{-61}$
  • $\roundcirc{29\cdot 10^{-18}} \otimes 10^{18} = 29 + 2^{-59}$
• f128:
  • $\roundcirc{0.07} \otimes 10^{2} = 7 + 2^{-110}$
  • $\roundcirc{0.29} \otimes 10^{2} = 29 - 2^{-108}$
  • $\roundcirc{0.001} \otimes 10^{3} = 1 - 2^{-113}$
  • $\roundcirc{0.127} \otimes 10^{3} = 127 + 2^{-106}$
  • $\roundcirc{0.0015} \otimes 10^{4} = 15 - 2^{-109}$
  • $\roundcirc{0.0029} \otimes 10^{4} = 29 + 2^{-108}$
  • $\roundcirc{0.00013} \otimes 10^{5} = 13 - 2^{-109}$
  • $\roundcirc{0.00027} \otimes 10^{5} = 27 + 2^{-108}$
  • $\roundcirc{0.000001} \otimes 10^{6} = 1 - 2^{-113}$
  • $\roundcirc{0.000495} \otimes 10^{6} = 495 + 2^{-104}$
  • $\roundcirc{11\cdot 10^{-7}} \otimes 10^{7} = 11 + 2^{-109}$
  • $\roundcirc{77\cdot 10^{-7}} \otimes 10^{7} = 77 - 2^{-106}$
  • $\roundcirc{7\cdot 10^{-8}} \otimes 10^{8} = 7 - 2^{-110}$
  • $\roundcirc{15\cdot 10^{-8}} \otimes 10^{8} = 15 + 2^{-109}$
  • $\roundcirc{1\cdot 10^{-9}} \otimes 10^{9} = 1 - 2^{-113}$
  • $\roundcirc{15\cdot 10^{-9}} \otimes 10^{9} = 15 + 2^{-109}$
  • $\roundcirc{3\cdot 10^{-10}} \otimes 10^{10} = 3 - 2^{-111}$
  • $\roundcirc{7\cdot 10^{-10}} \otimes 10^{10} = 7 + 2^{-110}$
  • $\roundcirc{15\cdot 10^{-11}} \otimes 10^{11} = 15 - 2^{-109}$
  • $\roundcirc{27\cdot 10^{-11}} \otimes 10^{11} = 27 + 2^{-108}$
  • $\roundcirc{31\cdot 10^{-12}} \otimes 10^{12} = 31 + 2^{-108}$
  • $\roundcirc{59\cdot 10^{-12}} \otimes 10^{12} = 59 - 2^{-107}$
  • $\roundcirc{5\cdot 10^{-13}} \otimes 10^{13} = 5 + 2^{-110}$
  • $\roundcirc{105\cdot 10^{-13}} \otimes 10^{13} = 105 - 2^{-106}$
  • $\roundcirc{25\cdot 10^{-14}} \otimes 10^{14} = 25 + 2^{-108}$
  • $\roundcirc{29\cdot 10^{-14}} \otimes 10^{14} = 29 - 2^{-108}$
  • $\roundcirc{15\cdot 10^{-15}} \otimes 10^{15} = 15 - 2^{-109}$
  • $\roundcirc{31\cdot 10^{-15}} \otimes 10^{15} = 31 + 2^{-108}$
  • $\roundcirc{3\cdot 10^{-16}} \otimes 10^{16} = 3 - 2^{-111}$
  • $\roundcirc{29\cdot 10^{-16}} \otimes 10^{16} = 29 + 2^{-108}$
  • $\roundcirc{13\cdot 10^{-17}} \otimes 10^{17} = 13 - 2^{-109}$
  • $\roundcirc{23\cdot 10^{-17}} \otimes 10^{17} = 23 + 2^{-108}$
  • $\roundcirc{7\cdot 10^{-18}} \otimes 10^{18} = 7 - 2^{-110}$
  • $\roundcirc{29\cdot 10^{-18}} \otimes 10^{18} = 29 + 2^{-108}$
  • $\roundcirc{19\cdot 10^{-19}} \otimes 10^{19} = 19 - 2^{-108}$
  • $\roundcirc{23\cdot 10^{-19}} \otimes 10^{19} = 23 + 2^{-108}$
  • $\roundcirc{3\cdot 10^{-20}} \otimes 10^{20} = 3 - 2^{-111}$
  • $\roundcirc{23\cdot 10^{-20}} \otimes 10^{20} = 23 + 2^{-108}$
  • $\roundcirc{15\cdot 10^{-21}} \otimes 10^{21} = 15 - 2^{-109}$
  • $\roundcirc{109\cdot 10^{-21}} \otimes 10^{21} = 109 + 2^{-106}$
  • $\roundcirc{43\cdot 10^{-22}} \otimes 10^{22} = 43 - 2^{-107}$
  • $\roundcirc{55\cdot 10^{-22}} \otimes 10^{22} = 55 + 2^{-107}$
  • $\roundcirc{29\cdot 10^{-23}} \otimes 10^{23} = 29 + 2^{-108}$
  • $\roundcirc{51\cdot 10^{-23}} \otimes 10^{23} = 51 - 2^{-107}$
  • $\roundcirc{1\cdot 10^{-24}} \otimes 10^{24} = 1 - 2^{-113}$
  • $\roundcirc{27\cdot 10^{-24}} \otimes 10^{24} = 27 + 2^{-108}$
  • $\roundcirc{103\cdot 10^{-25}} \otimes 10^{25} = 103 + 2^{-106}$
  • $\roundcirc{109\cdot 10^{-25}} \otimes 10^{25} = 109 - 2^{-106}$
  • $\roundcirc{11\cdot 10^{-26}} \otimes 10^{26} = 11 - 2^{-109}$
  • $\roundcirc{353\cdot 10^{-26}} \otimes 10^{26} = 353 + 2^{-104}$
  • $\roundcirc{1\cdot 10^{-27}} \otimes 10^{27} = 1 - 2^{-113}$
  • $\roundcirc{1657\cdot 10^{-27}} \otimes 10^{27} = 1657 + 2^{-102}$
  • $\roundcirc{73\cdot 10^{-28}} \otimes 10^{28} = 73 - 2^{-106}$
  • $\roundcirc{369\cdot 10^{-28}} \otimes 10^{28} = 369 + 2^{-104}$
  • $\roundcirc{7\cdot 10^{-29}} \otimes 10^{29} = 7 - 2^{-110}$
  • $\roundcirc{31\cdot 10^{-29}} \otimes 10^{29} = 31 + 2^{-108}$
  • $\roundcirc{15\cdot 10^{-30}} \otimes 10^{30} = 15 - 2^{-109}$
  • $\roundcirc{29\cdot 10^{-30}} \otimes 10^{30} = 29 + 2^{-108}$
  • $\roundcirc{255\cdot 10^{-31}} \otimes 10^{31} = 255 + 2^{-105}$
  • $\roundcirc{507\cdot 10^{-31}} \otimes 10^{31} = 507 - 2^{-104}$
  • $\roundcirc{15\cdot 10^{-32}} \otimes 10^{32} = 15 - 2^{-109}$
  • $\roundcirc{31\cdot 10^{-32}} \otimes 10^{32} = 31 + 2^{-108}$
  • $\roundcirc{13\cdot 10^{-33}} \otimes 10^{33} = 13 - 2^{-109}$
  • $\roundcirc{25\cdot 10^{-33}} \otimes 10^{33} = 25 + 2^{-108}$

rsk0315.hatenablog.com

また謎の定理が出てきました。f64 では下記が成り立つらしいです。

Claim: $\ForallL{x\in[0\lldot 999]}{( (x\oslash 10^3)\otimes 10^3) = x}$.

平方根の和

$x, y\in\N$ であって $\sqrt{x}, \sqrt{y}\notin\N$ であるが $\roundcirc{\sqrt{x}}\oplus\roundcirc{\sqrt{y}} \in\N$ となる例。

• f32:
  • $\roundcirc{\sqrt{874}} \oplus \roundcirc{\sqrt{1118}} = 63$
    • $\sqrt{874} + \sqrt{1118} = {\small 62.999997992789941}{\footnotesize 684670036634930{\dots}}$
  • $\roundcirc{\sqrt{1432}} \oplus \roundcirc{\sqrt{1694}} = 79$
    • $\sqrt{1432} + \sqrt{1694} = {\small 79.000007111362356}{\footnotesize 983672864227084{\dots}}$
• f64:
  • $\roundcirc{\sqrt{16740665}} \oplus \roundcirc{\sqrt{16912362}} = 8204$
    • $\sqrt{16740665} + \sqrt{16912362} = {\small 8203.999999999999094}{\footnotesize 484527497898279{\dots}}$

大変そうだったので他の型はまだ探していない。最小反例の下界は以前示した。

rsk0315.hatenablog.com

$x, y, z\in\N$ であって $\sqrt{x}, \sqrt{y}, \sqrt{z}\notin\N$ であるが $\roundcirc{\sqrt{x}}\oplus\roundcirc{\sqrt{y}}\oplus\roundcirc{\sqrt{z}} \in\N$ となる例。 可換ではないので注意が必要だが、ここでは $x\le y\le z$ に限って探索した。

• f32:
  • $\roundcirc{\sqrt{79}} \oplus \roundcirc{\sqrt{136}} \oplus \roundcirc{\sqrt{155}} = 33$
    • $\sqrt{79} + \sqrt{136} + \sqrt{155} = {\small 32.99999780499492}{\footnotesize 216667571809728{\dots}}$
  • $\roundcirc{\sqrt{56}} \oplus \roundcirc{\sqrt{71}} \oplus \roundcirc{\sqrt{123}} = 27$
    • $\sqrt{56} + \sqrt{71} + \sqrt{123} = {\small 27.000001053133658}{\footnotesize 563853237473445{\dots}}$
• f64:
  • $\roundcirc{\sqrt{3619}} \oplus \roundcirc{\sqrt{9711}} \oplus \roundcirc{\sqrt{18577}} = 295$
    • $\sqrt{3619} + \sqrt{9711} + \sqrt{18577} = {\small 294.999999999999989}{\footnotesize 686344092579607{\dots}}$
  • $\roundcirc{\sqrt{8981}} \oplus \roundcirc{\sqrt{26365}} \oplus \roundcirc{\sqrt{26523}} = 420$
    • $\sqrt{8981} + \sqrt{26365} + \sqrt{26523} = {\small 420.000000000000023}{\footnotesize 026456026620227{\dots}}$

等比数列

$x_0, x_1, x_2\in\N$ であって

• $x_1/x_0 = x_2/x_1$,
• $( (x_1\oslash x_0)\otimes x_0) \ne x_1$,
• $( (x_1\oslash x_0)\otimes x_1) \ne x_2$

をすべて満たす例。約分の項目に挙げた例の上位互換。

• f32:
  • $\angled{25, 105, 441}$
    • $(105 \oslash 25)\otimes 25 = 105 + 2^{-17}$
    • $(105 \oslash 25)\otimes 105 = 441 + 2^{-15}$
  • $\angled{81, 45, 25}$
    • $(45 \oslash 81)\otimes 81 = 45 - 2^{-18}$
    • $(45 \oslash 81)\otimes 45 = 25 - 2^{-19}$
• f64:
  • $\angled{25, 55, 121}$
    • $(55 \oslash 25)\otimes 25 = 55 - 2^{-47}$
    • $(55 \oslash 25)\otimes 55 = 121 - 2^{-46}$
  • $\angled{169, 195, 225}$
    • $(195 \oslash 169)\otimes 169 = 195 + 2^{-45}$
    • $(195 \oslash 169)\otimes 195 = 225 + 2^{-45}$
• f80:
  • $\angled{169, 91, 49}$
    • $(91 \oslash 169)\otimes 169 = 91 - 2^{-57}$
    • $(91 \oslash 169)\otimes 91 = 49 - 2^{-58}$
  • $\angled{81, 171, 361}$
    • $(171 \oslash 81)\otimes 81 = 171 + 2^{-56}$
    • $(171 \oslash 81)\otimes 171 = 361 + 2^{-55}$
• f128:
  • $\angled{25, 55, 121}$
    • $(55 \oslash 25)\otimes 25 = 55 - 2^{-107}$
    • $(55 \oslash 25)\otimes 55 = 121 - 2^{-106}$
  • $\angled{169, 195, 225}$
    • $(195 \oslash 169)\otimes 169 = 195 + 2^{-105}$
    • $(195 \oslash 169)\otimes 195 = 225 + 2^{-105}$
• Decimal:
  • $\angled{18, 24, 32}$
    • $(24\oslash 18)\otimes 18 = 24 - 10^{-26}$
    • $(24\oslash 18)\otimes 24 = 32 - 10^{-26}$
  • $\angled{18, 30, 50}$
    • $(30\oslash 18)\otimes 18 = 30 + 10^{-26}$
    • $(30\oslash 18)\otimes 30 = 50 + 10^{-26}$

rsk0315.hatenablog.com

比

$x_1, y_1, x_2, y_2\in\N_{\gt 0}$ であって、$x_1/y_1 \ne x_2/y_2$ かつ $x_1\oslash y_1 = x_2\oslash y_2$ である例。 下記の値を $a$ として $a\oslash (a-1) = (a+1)\oslash a$ が成り立つ。

• f32:
  • $2948$
• f64:
  • $67114657$
• f80:
  • $3037041293$
• f128:
  • $72057594227740468$
• Decimal:
  • $31622781975974$

一次関数

さまざまな形があるため割愛。下記を参照。

rsk0315.hatenablog.com

その他

有理数に関する例を探したいときは Stern–Brocot 木を使うと便利。

rsk0315.hatenablog.com

知りたい

$\gdef\libmatantwo#1#2{\operatorname{\texttt{a\hspace{-0.06em}t\hspace{-0.08em}a\hspace{-0.04em}n\hspace{-0.04em}2}}(#1, #2)}$

• atan2
  • $\arctan(y_1/x_1)\ne\arctan(y_2/x_2)$ だが $\libmatantwo{y_1}{x_1} = \libmatantwo{y_2}{x_2}$ となる例。
  • long double の怪しい偏角ソートって結局のところ撃墜可能なんですか？
  • atan2 は correctly rounded を保証するのが大変そうな気がするから、実装によるところも大きそう。

おまけ

参照したくなることがありそうなので Rump’s example。

$$ f(a, b) = 333.75b^6 + a^2 (11a^2b^2 - b^6 - 121b^4 - 2) + 5.5b^8 + \frac a{2b} $$ に対して $f(77617, 33096)$。

たまに思い出しそうなので xkcd 217。

xkcd.com

$$ \begin{aligned} e^{\pi} - \pi &= {\small 19.999099979189475}{\footnotesize 767266442984669{\dots}}, \\ \left(9^2 + \frac{19^2}{22}\right)^{1/4} &= {\small 3.141592652582646}{\footnotesize 125206037179644{\dots}}. \end{aligned} $$ 後者は、$\pi^4$ の最良近似分数を考えることで構成できる。

おまけ (2)

glibc 関連のお話。追記です。

処理系によりがちなのと、TMD が解消されて correct rounding が規定されて実装も整った夢の世界では関係なくなる話たちです。

大抵の数学関数は correct rounding ではない実装になっていることが多いです。「相対誤差が $2^{-53}$ より大きくなってもどうでもよくない？ correct rounding がそんなにうれしいんですか」と仰る方は多いと思いますが、correct rounding が保証されることの大きい意義として、処理系ごとに好き勝手な値が返ることがなくなるというのがあります。

rsk0315.hatenablog.com

たとえば、次のようなものが成り立ちます。コンパイル時計算が行われると別の結果になりうるので、再現させる際には気をつけましょう。

sqrt(_) は correct rounding が保証されていますが、cbrt(_) はそうなってはいません。また、pow(_, 0.5) が sqrt(_) と同様であることを期待してはいけず、correctly rounded な平方根の値を得られない例もあります。

sqrt(2921)     == 0x1.B05EC632536FBp+5 == 54.04627646748664204778833664022386074066162109375
pow(2921, 0.5) == 0x1.B05EC632536FAp+5 == 54.0462764674866349423609790392220020294189453125

cbrt(15*15*15) == 0x1.DFFFFFFFFFFFFp+3 == 14.9999999999999982236431605997495353221893310546875
cbrt(3*3*3)    == 0x1.8000000000001p+1 == 3.000000000000000444089209850062616169452667236328125

また、hypot についても hard-to-round case が知られているようです。

hypot(0x1.000001CC784CBp+52, 0x1.FDD67BCEB35Fp+52) == 0x1.1D400ABA3C4DBp+53

が出力されますが、 $$ \begin{aligned} &\phantom{{}={}} \texttt{1000001CC784CB}_{(16)}^2 + \texttt{1FDD67BCEB35F}_{(16)}^2 \\ &= \texttt{23A801574789B5}_{(16)}^2 \\ &= (2\cdot \texttt{11D400ABA3C4DA}.\texttt{8}_{(16)})^2 \end{aligned} $$ となるため、0x1.1D400ABA3C4DAp+53 と丸められるのが正しいです。

core-math/src/binary64/hypot/hypot.wc から拝借しました。atan2 や pow をはじめとする 2 変数関数についてもたくさん載っているほか、binary80 や binary128 についても用意されています。

その手の実装で correctly rounded な値が得られないがちな入力が欲しい場合には有用なことが多いですが、競プロ文脈での撃墜には直接使えない場合が多いんじゃないかなぁと思っています。えびちゃんはわくわくしますが他の人々にはあまり共感を得られない気がしています。勝手にしょんぼり。

あとがき

「誤差で落ちてるのかなあ」と言っている人が手元でケースを作る用にしたり、怪しい解法を落とすケースを作る用にしたり、「そもそもこういう例があるらしい」ということを知ることで変な解法を避ける手助けになればいいかなぁとは思っています。 未来のえびちゃんが Twitter で見かけた他の人の解法を落とすときに使うかもしれません。

double を落とすケースは入れたのに long double を落とすケースは入れておらず、依然として嘘である long double 解法が通ってしまう（+ 正当だと信じている）という不幸はしばしば発生しているので、さまざまな型に対して構成しました。Decimal に関しては、.prec を変えることでいくらでも（実質的に）別の型を作れてしまうので、困ったなぁというところです。.prec を実行時に乱択する解法もありうるかもしれません。そんなことするな。

逆に、「この制約下であればこの解法は正当」の補題たちのまとめも有用そうかもしれません^{[誰にとって?]}。

面白そうな問題設定を見つけたり、Twitter で誰かの解法を落としたら更新するかもしれません。飽きて一生そのままになる可能性もあります。

おわり

おわりです。

ABC 010 C の浮動小数点型の解法について

今日はこちらの問題です。

atcoder.jp

$i$ 番目の座標 $(x_i, y_i)$ に対して、浮動小数点型 (binary64, tiesToEven) で下記のように判定する解法の正当性について考えます。

sqrt((tx_a - x_i) ** 2 + (ty_a - y_i) ** 2) + sqrt((x_i - tx_b) ** 2 + (y_i - ty_b) ** 2) <= t * v

導入

一般性を失わずに $n = 1$ としてよいです。 また、 $$ \begin{aligned} (\mathit{tx}_a - x_i)^2 + (\mathit{ty}_a - y_i)^2 &\le 2\cdot 10^6, \\ (x_i - \mathit{tx}_b)^2 + (y_i - \mathit{ty}_b)^2 &\le 2\cdot 10^6, \\ T\cdot V &\le 5\cdot 10^3 \end{aligned} $$ より、整数 $a, b\in[0\lldot 2\cdot 10^6]$ および $c\in[0\lldot 5\cdot 10^3]$ に対して $\sqrt{a}+\sqrt{b} \le c$ を sqrt(a) + sqrt(b) <= c で判定することの正当性を示せば十分です。

記法

実数 $x$ に対して、$x$ から最も近い整数との差を $\|x\|$ で表します。すなわち、 $$ \|x\| = \min{\{x-\floor x, \ceil x-x\}} $$ です。

実数 $x$ に対し、$\roundcirc{x}$ で該当の浮動小数点型への丸めた値を表します。浮動小数点数 $x, y$ に対して $x\oplus y = \roundcirc{x+y}$ とします。

Lemma 0.1: $x-\floor x \le \tfrac12$ のとき $\|x\| = x-\floor x$ が成り立つ。また、$\ceil x-x \le \tfrac12$ のとき $\|x\| = \ceil x-x$ が成り立つ。

Proof. 明らか。

Lemma 0.2: 任意の正整数 $m$ と実数 $|r|\in(0\lldot\tfrac12]$ に対し、ある $\delta\in (0\lldot\tfrac12]$ が存在して $$ \|(2m+r)\cdot r\| \ge \delta $$ が成り立つとき、 $$ \|r\| \ge \frac{\delta}{2m+\tfrac12} $$ が成り立つ。

Proof

一般性を失わず $r\gt 0$ とする。

$f_m(r) = (2m+r)\cdot r$ とすると、$f_m$ は $r\ge 0$ で単調増加である。 $f_m(0) = 0$ かつ $f_m(\tfrac12) = m+\tfrac14\gt 1$ より、$f_m(r') = \tfrac12$ なる $r'\in (0\lldot\tfrac12)$ が存在する。

よって、$r''\in(0\lldot r']$ が存在して $f(r'') = \|f(r'')\| = \delta$ が成り立つ。 この $r''$ に対し、 $$ \begin{aligned} r &\ge r'' \\ &\ge \frac{\delta}{2m+r''} \\ &\ge \frac{\delta}{2m+\tfrac12} \end{aligned} $$ が成り立つ。$\qed$

考察

制約の範囲で $\roundcirc{a} = a$, $\roundcirc{b} = b$, $\roundcirc{c} = c$ が成り立つ。

$\sqrt a+\sqrt b\in\N$ が成り立つとき $\sqrt a, \sqrt b\in\N$ であり、$\roundcirc{\sqrt a} = \sqrt a$ かつ $\roundcirc{\sqrt b} = \sqrt b$ が成り立つ。 $\roundcirc{\sqrt a}+\roundcirc{\sqrt b}\le 2^{53}$ であるから、$\sqrt a+\sqrt b\in\N$ となるとき $$ \begin{aligned} \sqrt a+\sqrt b\le c &\iff \roundcirc{\sqrt a}+\roundcirc{\sqrt b}\le c \\ &\iff \roundcirc{\sqrt a}\oplus\roundcirc{\sqrt b}\le c \\ \end{aligned} $$ が成り立つ。

以降、$\sqrt a+\sqrt b\notin\N$ の場合を考える。直感的には、$\sqrt a+\sqrt b$ が整数から十分遠いことを示せばよい。

note: これを示すパートでは浮動小数点型のことは考える必要はなく、ただの数学をすることになる。

$a$, $b$ の上限を $n$ とし、ある $\delta_n$ に対して $\|\sqrt a+\sqrt b\| \ge \delta_n$ が示された後は、 $$ \begin{aligned} &\phantom{{}\le{}} |(\roundcirc{\sqrt a}\oplus\roundcirc{\sqrt b}) - (\sqrt a + \sqrt b)| \\ &\le |(\roundcirc{\sqrt a}\oplus\roundcirc{\sqrt b}) - (\roundcirc{\sqrt a} + \roundcirc{\sqrt b})| + |(\roundcirc{\sqrt a} + \roundcirc{\sqrt b}) - (\sqrt a + \sqrt b)| \\ &\le (\roundcirc{\sqrt a} + \roundcirc{\sqrt b})\cdot 2^{-53} + (\sqrt a+\sqrt b)\cdot 2^{-53} \\ &\le (\sqrt a + \sqrt b)\cdot(1+2^{-53})\cdot 2^{-53} + (\sqrt a+\sqrt b)\cdot 2^{-53} \\ &\le (\sqrt a + \sqrt b)\cdot(2+2^{-53})\cdot 2^{-53} \\ &\le 2\sqrt n\cdot(2+2^{-53})\cdot 2^{-53} \end{aligned} $$ より、$2\sqrt n\cdot(2+2^{-53})\cdot 2^{-53} \lt \delta_n$ であれば $\|{\roundcirc{\sqrt a}\oplus\roundcirc{\sqrt b}}\|\gt 0$ となるため、 $$ \roundcirc{\sqrt a}\oplus\roundcirc{\sqrt b} \le c \iff \sqrt a+\sqrt b\le c $$ が成り立つことが言える。ここでは $n = 2\cdot 10^6$ であり、$\delta_n \gt 6.281\cdot 10^{-13}$ を示せば十分。

証明

Lemma 1: 非負整数 $n$ を任意に固定する。任意の整数 $a\in[n^2+1\lldot (n+1)^2-1]$ に対し、$\|\sqrt a\| \ge \tfrac1{2(n+1)}$ が成り立つ。

Proof

$$ n\lt \sqrt{n^2+1} \lt \dots \lt \sqrt{(n+1)^2-1} \lt n+1 $$ であるから、$\|\sqrt{n^2+1}\|$ と $\|\sqrt{(n+1)^2-1}\|$ を押さえれば十分。

$$ \begin{aligned} \sqrt{n^2+1} - n &= \frac{(n^2+1)-n^2}{\sqrt{n^2+1}+n} \\ &= \frac1{\sqrt{n^2+1}+n} \\ &\lt \tfrac12 \end{aligned} $$ より、$\|\sqrt{n^2+1}\| = \sqrt{n^2+1} - n$ であり、 $$ \begin{aligned} \sqrt{n^2+1} - n &= \frac1{\sqrt{n^2+1}+n} \\ &\gt \frac1{2\sqrt{n^2+1}} \\ \end{aligned} $$ が成り立つ。また、同様にして $$ \begin{aligned} (n+1) - \sqrt{(n+1)^2-1} &= \frac{(n+1)^2 - ( (n+1)^2-1)}{(n+1)+\sqrt{(n+1)^2-1}} \\ &= \frac1{(n+1)+\sqrt{(n+1)^2-1}} \\ &\lt \tfrac12 \end{aligned} $$ より $\|\sqrt{(n+1)^2-1}\| = (n+1) - \sqrt{(n+1)^2-1}$ であり、 $$ \begin{aligned} (n+1) - \sqrt{(n+1)^2-1} &= \frac1{(n+1)+\sqrt{(n+1)^2-1}} \\ &\gt \frac1{2(n+1)} \\ \end{aligned} $$ が成り立つ。$\sqrt{n^2+1}\le n+1$ より、 $$ \|\sqrt a\| \ge \frac1{2(n+1)} $$ が成り立つ。$\qed$

Corollary 2: 任意の非負整数 $a$ に対し、$\sqrt a\notin\Z$ ならば $\|\sqrt a\|\ge \tfrac1{2\ceil{\sqrt a}}$ が成り立つ。

Proof. Lemma 1 より従う。

Lemma 3: 非負整数 $n$ を任意に固定する。任意の非負整数 $a, b\in[1\lldot n]$ に対し、$\sqrt a+\sqrt b \notin\Z$ ならば $\|\sqrt a+\sqrt b\| \ge \tfrac1{16}\cdot (n+1)^{-3/2}$ が成り立つ。

Proof

$m\in\Z$ および $|r|\in (0\lldot \tfrac12]$ を用いて $\sqrt a+\sqrt b = m+r$ とおく。 両辺を $2$ 乗して $$ \begin{aligned} % (\sqrt a+\sqrt b)^2 &= m^2+2mr+r^2, \\ a+b+2\sqrt{ab} &= m^2 + (2m+r)\cdot r, \\ a+b-m^2 &= (2m+r)\cdot r - \sqrt{4ab} \end{aligned} $$ を得る。また、$\sqrt a+\sqrt b\le 2\sqrt n$ より、$m\le \ceil{2\sqrt n}$ である。

$\sqrt{4ab}\in\N$ ならば $$ r = \frac{a+b-m^2+\sqrt{4ab}}{2m+r} $$ であり、$r\ne 0$ に注意して $$ \begin{aligned} |r| &\ge \frac1{2m+\tfrac12} \\ &\ge \frac1{2\ceil{2\sqrt n}+\tfrac12} \\ &\ge \frac1{2(2\sqrt n+1)+\tfrac12} \\ &\ge \frac1{4\sqrt n+\tfrac52} \\ &\gt \tfrac14\cdot (n+1)^{-1/2} \end{aligned} $$ を得る。

$\sqrt{4ab}\notin\N$ ならば、 $$ a+b-m^2 = (2m+r)\cdot r - \sqrt{4ab} $$ より $$ \|(2m+r)\cdot r\| = \|\sqrt{4ab}\| $$

であり、Lemma 0.2 と Corollary 2 より、 $$ \begin{aligned} \|r\| &\ge \frac{\|\sqrt{4ab}\|}{2m+\tfrac12} \\ &\ge \frac1{2m+\tfrac12} \cdot \frac1{2\ceil{\sqrt{4ab}}} \\ &\ge \frac1{2\ceil{2\sqrt n}+\tfrac12} \cdot \frac1{4n} \\ &\ge \frac1{2\cdot(2\sqrt n+1)+\tfrac12} \cdot \frac1{4n} \\ % &= \frac1{8\cdot(2\sqrt n+1)+2} \cdot \frac1n \\ &= \frac1{16\sqrt n+10} \cdot \frac1n \\ &\gt \tfrac1{16}\cdot (n+1)^{-3/2} \end{aligned} $$ を得る。$\qed$

Corollary 4: 上記の解法は正当である。

Proof. $$ \tfrac1{16}\cdot (2\cdot 10^6)^{-3/2} \gt 2.209\cdot 10^{-11} \gg 6.281\cdot 10^{-13}. \quad\qed $$

おまけ

ざっくり $\tfrac1{16}\cdot n^{-3/2} \gt 2^{-51}\cdot n^{1/2}$ が成り立てばよいという話になります。すなわち、$n\lt 2^{47/2}\approx 1.186\times 10^7$ くらいです。

$n^2\pm 1$ の形に絞って探してみたところ、次の例が見つかりました。

>>> n = 5171
>>> sqrt(n**2-1) + sqrt(n**2+1)
10342.0
>>> n**2
26739241

> n = 5171;
> (n^2-1)^.5 + (n^2+1)^.5;
10341.9999999999981919251912771649254807294027797372

小さいケースで試した感じだと、この形が最適とは限らないようなので、もっと小さい例はあるんじゃないかなぁと思っています。

（追記）11863283 から順に全探索して、下記のケースが見つかりました。たぶん最小なんじゃないかなぁと思っています。

>>> sqrt(16740665) + sqrt(16912362)
8204.0

> 16740665^.5 + 16912362^.5;
8203.999999999999094484527497898279483192632706274

参考文献

• [1] Steinerberger, Stefan. “Sums of square roots that are close to an integer.” Journal of Number Theory 262 (2024): 45–57.
  • ほぼ本質はこれ（の中で引用されている [2] の文献）。
• [2] Angluin, Eisenstat. “How close can $\sqrt a+\sqrt b$ be to an integer?” Yale Technical Report 1279 (2004).
  • [1] の論文から引用されていましたが、見つけられませんでした。どこかで見られますか？

あとがき

Twitter で人々が浮動小数点型で AC して悩ましげにしているのを見つけて記事が発生するシリーズでした。 人々がもっとそういうツイートをしてくれるとうれしいです。

平方根の和ということで、式の形は下記と似ているところもあります。今になって読み返すとだいぶ拙いところがあるなと思います。気が向いたら直すかもしれません。

rsk0315.hatenablog.com

この手の記事が久々だったのと、ここ数日は調子がよくなかったので、あまりうまくできていない気がします。特に Lemma 0.2 や Lemma 3 はもっとまともになる気がしています。

この手の記事を書くたびに「思考停止で eps を使えばいいですよ」と思考停止で言ってくる人について考えてしまいます。お気持ち表明を述べようか迷いながら公式解説を見に行ったところ、そういう旨が書かれていてどうでもよくなって投げ出してしまいました。12 年以上前なのでそういう風潮が今よりも色濃かったのだろうと思います。

おわり

おわりです。

Vim や grep の起動コマンドに関する tips

Vim というエディタや、grep というコマンドがあります。

導入

read-only で Vim を起動するにあたっては、view というコマンドが用意されています。 vi との掛詞だなあというのを感じて、うまいなあと思っています。いちいち言及するのは野暮かもしれません。

また、正規表現ではなく固定文字列 (fix string) での検索するにあたっては、grep の代わりに fgrep というコマンドが用意されています。grep の re の部分は regular expression のことなので、固定文字列での検索なら gfsp などと名乗るべきでは？という気持ちもなくはありません。 あるいは、正規表現として BRE ではなく ERE を使うために egrep というコマンドも用意されています。 egrep や fgrep は後方互換性のために残されているだけの deprecated なものなので、grep -E や grep -F を使うのが好ましいでしょう。

疑問

さて、これらはどのように実装されているのでしょうか？

disclaimer: バージョンなどによっては、ここで紹介したものと異なるものもあるかもしれません。

たとえば、cat $(which egrep) を実行すると、次の出力が得られます。

#!/bin/sh
cmd=${0##*/}
exec grep -E "$@"

一方、diff -s $(which vim) $(which view) を実行すると、次の出力が得られます。

Files /usr/bin/vim and /usr/bin/view are identical

どうやら、exec vim -R "$@" などをしているわけではないようです。

note: これ以降、grep の話は出てきません。{bz,e,f,ptar,r,xz,ze,zf,z}grep はいずれもテキストファイルでした。

予想

ということで、argv[0] を見て判断しているとかなのかな？という予想がある程度自然に出てきます。 ln -s $(which vim) view をして ./view $(mktemp) を実行すると、次のように表示されました。

"/tmp/tmp.4Htfopv74I" [readonly] 0L, 0B 

予想が当たっていそうだな〜ということで、実装を見に行きます。

答え合わせ

github.com

static void parse_command_name(mparm_T *parmp) に関して、次のコメントがついています。

Check for: [r][e][g][vi|vim|view][diff][ex[im]] (sort of)

各文字列と対応するモード・オプションは次の通りです。

文字列	モード	オプション
r	restricted mode	-Z
e	easy mode	-y
g	run using GUI	-g
view	readonly mode	-R
diff	diff mode	-d
ex	Ex mode	-e
exim	improved Ex mode	-E

vi や vim は特に意味を持たないようです。 vimex は Ex mode になりますが、viex だと Ex mode にはならないとか、そういう差異はあります。

処理を追うと r?(e(?=[vg]))?g?(view|vim)?(diff)?(ex(im)?)? 的なものに相当しそうでしたが、わざわざそこまで細かく言う必要もないということでしょう。

おまけ

bash などの alias の機能を用いた場合は argv に渡る文字列は展開後の文字列であることに注意が必要です。 たとえば alias diff=vim のようにして diff を叩いた場合は、vim -d 相当のものではない vim が起動されることになります。 ~/.local/bin/ 配下など、適当な場所に symlink を置くなどが必要です。

たとえば、regex として Vim を起動すると vim -Zyge 相当のものが起動することになります。 evil や ev により vim -y が起動しますが、emacs や editor では vim -y にはなりません。 egrep で Vim を起動した場合は vim -yg になりますね。vim -ygZ にはならないことに注意が必要です*1。

あとがき

easy mode (vim -y) は Vim に慣れている人にとってはびっくりモードだと思います。 <ESC> を押しても自動で -- INSERT -- になるのは実質 virus だと思いますね。 Vim を閉じられない人の気持ちを味わえるかもしれません。 ふつうの vim であれば、<CTRL-C> を押せば “Type :qa and press <Enter> to exit Vim” のメッセージが出てきますが、easy mode ではそれすらありません。

今回の件を調べながら、自分で Vim をビルドして遊んでいたのですが、bin/ex を実行しようとして bi/nex と叩いたとき、Zsh が次のサジェストをしてきて驚きました。$PATH から探せるコマンドか、関数たちくらいしか出してくれないと思っていました。

zsh: correct bi/nex to bin/ex (n/y/a/e)?

おわり

おわりです。

*1:そもそも考える必要がないというのはそう。

Writeup for True or False 2, Daily AlpacaHack 2026/8/13

Daily AlpacaHack 2026/8/13–2026/8/15 の write-up です。 alpacahack.com

True or False の続編です。

考えたこと

続編あるあるとして、まずは diff を見ます。

% diff true-or-false{,-2}/chal.py

4c4
< MAX_EVALS = 28
---
> MAX_EVALS = 17 # No more ternary search
9c9
<     "+-*/()<>="
---
>     "+-*()<>=" # No more division-by-zero errors

おいおいおいという感じです。得られる出力が $3$ 通りしかなく、$3^{17} \lll 2^{44}$ なので困ります。 $6.013 \lt 2^{44/17} \lt 6.014$ なので $6^{17} \approx 2^{44}$ とわかります。$6^{17}$ の方がわずかに小さいため困りますが、何回か試す前提で無視できる範囲だと思いました。

$6 = 3\times 2$ なので、timing attack によって「すぐに終わる 3 択」と「ゆっくり終わる 3 択」をすればよさそうです。 $\{0, 1, 2, 3, 4, 5\}$ の値を取る変数を $z$ とし、$x = z \ge 3$ かつ $y = z\bmod 3$ とします。取りうる値をわかりやすくするため、コード上ではそれぞれ z012345, x01, y012 とします。

sleep() などは使えないしなぁと思いつつ ALLOWED_CHARS の * を見ていると 10**10000000 という気分になります。 一生待たされるのは困るので適宜チューニングしていると 10**8**7 とかがちょうどよさそうだなぁとなりました。 よって、x01 の値によって待ち時間を生じさせる gadget として ((x01*10)**8**7)*0+... ができあがります。

次に、3 択の値から Error を生じさせる方法について考えます。 Error を出せないなら 2 択を 3 つ作って $8^{17} \ggg 2^{44}$ にするか？という気持ちにもなりつつ ALLOWED_CHARS を見ながら考えていると、シフト演算の幅を負数にすることを思いつきます。

>>> 1 >> -1
Traceback (most recent call last):
  File "<python-input-0>", line 1, in <module>
    1 >> -1
    ~~^^~~~
ValueError: negative shift count

よーしよしということで、3 択を行う gadget として 1>>(y012-1) ができあがります。 上記と合わせて、((x01*10)**8**7)*0+(1>>(y012-1)) の形になりました。Error が 0 で True が 1 で False が 2 です。 評価順序の関係で、ゆっくり gadget を左に置いて、エラー gadget を右に置く必要があることに一応注意しておきます。

あとは $z$ を表す式について考えればよいです。 ということで、a を $6$ 進法で表したときの $i$ 桁目がわかればうれしいなとなります。前回は $3^{28} \gt 2^{44}$ だったので $3$ 進法での $i$ 桁目を下記のようにして求めました。整数 $x$, $y$ ($y\gt 0$) に対して $x\bmod y = x - \floor{x/y}\cdot y$ が成り立つことを用いています。

# b = a // 3**i % 3
# 1 / b < 1: [0, 1, 2] => [Error, False, True]
code = f"1/((a//3**{i})-(a//3**{i})//3*3)<1"

/ を使わずに除算がしたいがちょっと大変そうということで、上位桁について適当に三分探索しながら下位ビットを決めていくというようなことも思いつきましたが、なんか面倒そうだし心がときめかなかったので捨てました。 コメントにも “No more ternary search” と書かれていたので忖度です（？）。

note: たとえば f"(a-((a>>{i+1})<<{i+1}))>>{i}" とすることで $i$ ビット目を返せると思います。

さて、/ を使わない除算といえば Barrett reduction です。 過去に示したもの を思い出しながら雰囲気で端数合わせをします。条件分岐はしないでできるようにしたいです（condition*ifTrue+(1-condition)*ifFalse のようにすれば別に分岐はできると思いますが）。

雰囲気.py

def div(num, den):
    m = (~(~0 << 128) + den) // den
    res = (num * m) >> 128
    assert res == num // den, f"{num} // {den}, {res}"
    return res


for num in range(2, 1000):
    for den in range(2, 1000):
        div(num, den)

というわけで整ったので、全体のコードを書きます。

solve.py

from time import time

from rsk0315.remote import nc

MAX_EVALS = 17
ALLOWED_CHARS = "0123456789a+-*()<>="


def div(a, k):
    m = (~(~0 << 128) + k) // k
    return f"(({a}*{m})>>128)"


def mod(a, k):
    return f"({a}-({div(a, k)})*{k})"


guess = 0
with nc("nc 34.170.146.252 5440") as p:
    for i in range(MAX_EVALS):
        z012345 = mod(div("a", 6**i), 6)
        x01 = f"({z012345}>=3)"
        y012 = mod(z012345, 3)

        code = f"(({x01}*10)**8**7)*0+(1>>({y012}-1))"
        p.sendlineafter(b"Eval > ", code.encode())

        tic = time()
        resp = p.recvline(drop=True)
        toc = time()
        x01 = toc - tic > 1
        y012 = {b"Error": 0, b"True": 1, b"False": 2}[resp]
        cur = x01 * 3 + y012

        guess += cur * 6**i

    p.sendlineafter(b"Guess > ", f"{guess}".encode())
    print(p.recvall())

これをサーバに投げればおしまいです。一発で動くか不安でしたが、ローカルで特にテストもせず一発でフラグが出たので気持ちよかったです。

Well done! Here's your flag: Alpaca{truth_dare_double_dare_torture_kiss_or_promise}

あとがき

ところで、write-up を書きながら ALLOWED_CHARS を見返していて下記に気づきました。

>>> 0**-1
Traceback (most recent call last):
  File "<python-input-1>", line 1, in <module>
    0**-1
    ~^^~~
ZeroDivisionError: zero to a negative power

0**0 と 0**1 がそれぞれ 1 (True) と 0 (False) になるのでエラー gadget として使えます。 コメントに “No more division-by-zero errors” と書いてあるので控えておきましょう（？）。

思いつきパートと実装うまくいきパートがいくつかあり、気持ちよかったです。

おわり

おわりです。

ABC 誤差ジャッジまとめ

<2000-rated として開催されている ABC（通称 A6C、A8C、A7C）、すなわち ABC 126 以降の誤差ジャッジのまとめです。執筆時点では ABC 470 までが開催されたところです。更新は気まぐれになると思います。

一覧

出力内容の分類はお気持ちです。「長さ」や「高さ」などはすべて「距離」にまとめています。

表

問題	出力内容	基準	出力規定
ABC 126 C	確率	（なし）	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 130 C	面積	（なし）	絶対誤差あるいは相対誤差が $10^{-9}$ 以下
ABC 130 F	面積	ジャッジプログラムの出力	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 138 B	総和	ジャッジの出力	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 138 C	その他	ジャッジの出力	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 139 F	距離	実際の答え	相対誤差または絶対誤差が $10^{-10}$ 以内
ABC 142 A	確率	ジャッジの出力	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 144 D	角度	ジャッジの出力	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 144 F	期待値	ジャッジ	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 145 C	平均値	ジャッジの出力	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 151 F	円の半径	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 154 D	期待値	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 157 F	時間	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 159 C	その他	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 163 A	円の周長	想定解答	絶対誤差または相対誤差が $10^{-2}$ 以下
ABC 168 C	距離	正しい値	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 180 B	距離	正しい値	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 181 F	円の半径	想定解答	絶対誤差または相対誤差が $10^{-4}$ 以下
ABC 183 B	座標	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 184 D	期待値	正しい値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 189 F	期待値	想定解答	絶対誤差または相対誤差が $10^{-3}$ 以下
ABC 193 A	比率	想定解答	絶対誤差または相対誤差が $10^{-2}$ 以下
ABC 193 D	確率	想定解答	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 194 D	期待値	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 197 D	座標	想定解答	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 205 A	比率	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 211 A	その他	想定解答	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 223 C	距離	想定解答	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 224 G	期待値	想定解答	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 231 A	その他	想定解答	絶対誤差または相対誤差が $10^{-3}$ 以下
ABC 234 B	距離	想定解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 236 E	平均値	正しい値	相対誤差または絶対誤差が $10^{-3}$ 以下
ABC 239 A	距離	想定解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 242 A	確率	想定解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 246 B	座標	想定解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 255 B	円の半径	想定解	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 259 B	座標	解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 263 Ex	距離	想定解答	絶対誤差または相対誤差が $10^{-4}$ 以下
ABC 266 E	期待値	真の解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 274 E	時間	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 275 G	極限値	想定解答	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 279 D	時刻	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 286 Ex	距離	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 291 B	平均値	真の値	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 292 F	距離	真の値	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 292 Ex	平均値	真の値	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 294 F	比率	真の値	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 313 F	期待値	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 314 E	期待値	真の値	相対誤差もしくは絶対誤差が $10^{-5}$ 以下
ABC 314 Ex	円の半径	真の値	相対誤差もしくは絶対誤差が $10^{-5}$ 以下
ABC 315 F	その他	真の値	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 319 C	確率	真の値	絶対誤差が $10^{-8}$ 以下
ABC 324 F	その他	真の値	相対誤差もしくは絶対誤差が $10^{-9}$ 以下
ABC 327 E	その他	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 332 E	分散	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 334 F	距離	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 341 G	平均値	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 342 F	確率	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 350 E	期待値	真の解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 356 G	時間	正答の真の値	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 374 D	時間	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 375 B	その他	真の値	相対誤差または絶対誤差が $10^{-6}$ 以下
ABC 382 E	期待値	真の答え	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 385 F	距離	真の解	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 392 D	確率	真の解	相対誤差または絶対誤差が $10^{-8}$ 以下
ABC 393 G	その他	（特殊）	（特殊）
ABC 401 G	時間	真の値	相対誤差が $10^{-6}$ 以下
ABC 402 E	期待値	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 404 F	確率	真の解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 407 B	確率	真の値	絶対誤差が $10^{-9}$ 以下
ABC 418 B	比率	真の値	絶対誤差が $10^{-9}$ 以下
ABC 421 E	期待値	真の解	相対誤差または絶対誤差が $10^{-5}$ 以下
ABC 424 E	距離	真の解	絶対誤差または相対誤差が $10^{-9}$ 以下
ABC 426 E	距離	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 434 B	平均値	真の解	絶対誤差または相対誤差が $10^{-5}$ 以下
ABC 448 G	確率	真の値	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 449 A	面積	真の解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 456 B	確率	真の解	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 469 E	確率	真の答え	絶対誤差または相対誤差が $10^{-6}$ 以下
ABC 470 E	期待値	真の解	絶対誤差または相対誤差が $10^{-5}$ 以下

分析？

基準は「真の値」が一番多く、次点で「想定解答」でした。

出力規定は、「絶対誤差または相対誤差が $10^{-6}$ 以下」が一番多く、次点の「絶対誤差または相対誤差が $10^{-5}$ 以下」と比べて 3 倍以上の個数でした。 確率のように真の値が $1$ を超えないものについては相対誤差への言及がない問題もいくつかありました。

閾値としては $10^{-6}$ が一番多く、$10^{-5}$ や $10^{-9}$ はその半数ほどでした。 接続詞としては「または」が一番多く、「もしくは」「あるいは」が少しだけあります。 また、「絶対誤差」が先に書かれるものが多数派ですが、たまに「相対誤差」が先に書かれているものもあります。

ABC 144 F の「出力は、ジャッジと出力との絶対誤差または相対誤差が $10^{-6}$ 以下のとき正解と判定される。」は「ジャッジの出力との〜」の typo かもしれないし、そうでないかもしれません。

ギャラリー

Twitter の古のオタクの方々を紹介します。

2e-3と書くといいですよ（ここにきゅうりさんのclarのスクショのツイートを入れる）

— かならい (@sugarknri) 2026年8月13日

2e-3 を思い出したけどそういうのじゃなかった（？） https://t.co/YFIV4GsjoD

— Kojima (@t33f) 2026年8月13日

昔 こういう問題 があり、許容誤差として $2e-3$ と書かれていました。

あとがき

合わせて読みたい

259-momone.hatenablog.com

多少誤差が大きくても AC とする仕様については、AtCoder のような full-feedback 形式であれば特に問題ないと思いますが、Codeforces のような hack を前提としたシステムだとうれしくない気もします。 許容誤差が $10^{-6}$ の問題で、defender の出力の相対誤差が $1.01\times 10^{-6}$ となる（真の値は $1$ 以上）ような入力を与えて Unsuccessful hacking attempt が返されたら、お気持ち表明記事が発生すると思います。

エイプリルフールコンで、「出力の相対誤差が $0.10^{-6}$ 以上のときに正答となる」とか書いてみるのもありかもしれません*1。

おわり

おわりです。こんなことをしている場合ではない。

*1:$0.10^{-6}$ と $10^{+6}$ だったらどっちの方が読み飛ばしやすそうですか？

ABC 470 C についての雑談

atcoder.jp

えびちゃんは、先日述べた事情 やそれ以外の事情でここ数ヶ月 ABC から離れていたのですが、今回久々に参加しました。 直前の練習では、以前のえびちゃんではしないようなミスを散々して自信を失くしていましたが、本番でも C で散々詰まったのでしょんぼりになりました。一応コンテスト中には通せましたし、内容としても面白かったです。複数の解法で実装したのでいろいろと書きます。

おはなし

諸々のトピックについて述べます。

そういうデータ構造を用いる解法には特有のキャッチーさ（？）があり、惹かれてしまう気がするのですが、まずは基本を押さえるのが大事だと思います。 計算量解析をできるようになりましょう。そういうデータ構造のお勉強をするのも楽しいと思うので、両方やりましょう。

ならし解析

データ構造について何らかの処理を行う際、一回のクエリの最悪計算量は大きくなってしまう場合でも、一連の操作全体の計算量はそこまで大きくならないというシチュエーションはしばしばあります。そうした際には、最悪計算量の代わりに 償却計算量 あるいは ならし計算量 (amortized complexity) というのを考えます。

各 $i$ ($0\le i\lt Q$) について $i$ 回目のクエリの実際の計算量を $t_i$ とします。任意の $i$ ($0\le i\lt Q$) について、$\sum_{j=0}^i t_j \le \sum_{j=0}^i a_j$ となる $a_i$ ($0\le i\lt Q$) を定められるとき、$i$ 回目のクエリの償却計算量を $a_i$ と呼びます。 追加と削除など複数の種類のクエリがある場合には、どのような順序でそれらを行った場合でも $\sum_j t_j \le \sum_j a_j$ の条件が満たされている必要があります。

たとえば、$Q$ 回クエリを行った際に $t_i = 1$ ($0\le i\lt Q-1$) かつ $t_{Q-1} = Q$ となるようなデータ構造があったとして、$a_i = 2$ ($0\le i\lt Q$) と定めると上記の条件を満たします。このデータ構造を使った際の計算量を見積もるにあたって、一回あたりの計算量として $t_i$ の代わりに $a_i$ を用いても全体としては困らず、かつ $a_i$ の方が小さく見積もれているのでうれしいことを示しやすいわけです。 動的配列（C++ の vector や Rust の Vec のようなもの）に対して末尾に新しい要素を追加する際の計算量が、償却計算量として $O(1)$ 時間であることなどが身近な例です。

こうしたことを示すための解析を ならし解析 (amortized analysis) などと言います。 ABC でよく見る論法の例としては、「各要素に着目すると、その要素を消す処理を行う前にその要素を入れる処理をしている必要がある。その要素が消される回数は高々 $1$ 回なので、$n$ 個まとめて消す処理を $O(n)$ 時間でできるのであれば削除処理は $1$ つあたり $O(1)$ 時間と見なせる」といったものがあります。

keywords: banker’s method, physicist’s method

今回の想定解法はこの手法によるものです。他の出題例（C 問題とは限らず、網羅的でもない）としては下記があります。

• ABC 413 C
• ABC 446 C
• ABC 451 C
• ABC 459 C
• ABC 217 E

今回の問題への提出コードは 提出 #78230021 です。

種類数

さて、要素数 $n$ の非負整数列 $a = (a_0, a_1, \dots, a_{n-1})$ が $a_0 + a_1 + \dots + a_{n-1} = S$ を満たすとき、$a$ に含まれる整数の種類数は $O(\sqrt S)$ 個であるという話があります。 すなわち、今回の問題でいう $A$ は $O(\sqrt Q)$ 種類の値しか入っておらず、これを平衡木などで管理すればよさそうということになります。hiro1729 による ユーザ解説 でも触れられています。

コンテスト中は頭が終わっていて「$A$ に含まれる値を平衡木で管理するなら log がつくんだから $O(N+Q^{1.5}\log(Q) )$ 時間で、$Q\le 5\times 10^5$ でそれは無茶だろ〜 🤪」となっていました。冷静になるとクエリ 1 回ごとの処理は平衡木への追加・削除で $O(\log(Q) )$ 時間と平衡木の走査で $O(\sqrt Q)$ 時間であり、$O(\log(Q)+\sqrt Q) = O(\sqrt Q)$ なので問題ないわけですね。

平衡木に関して、要素数を $n$ として全要素を順に走査するのが $O(n)$ 時間でできるのも、ならし解析によるものだと思います。

AtCoder に限らない出題例や記事としては次のものがあります。

• ABC 215 G
• ABC 269 G
• HUPC 2019 Day 2 D
  • 関連記事

今回の問題への提出コードは 提出 #78265187 です。

ビットごとにカウント

XOR といえばビットごとに数える典型というのはまぁあって、それに固執してうまくいかなかった人も多いかもしれません。 うまくいく解法について述べます。SSRS によるものです。

https://t.co/0XhJSR0oCo やってみた

— SSRS (@SSRS_cp) 2026年8月9日

正整数の多重集合 $S$ について、$T_k = \{\!\{ x \bmod 2^{k+1} \mid x\in S\}\!\}$ を考えて、$T_k$ に含まれる $2^k, 2^k+1, \dots, 2^{k+1}-1$ の個数の偶奇を考えて、奇数なら $2^k$ が答えへの寄与になります。 Dec クエリに対しては、$1$ から $0$ になる要素（$2^{k+1}$ で割ったあまりではなく）をまず除外します。$T_k$ に関しての差分は、$x \equiv 0 \pmod{2^{k+1}}$ または $x\equiv 2^k \pmod{2^{k+1}}$ なる $x$ に限られることがわかるので、$O(1)$ 種類の要素について更新すればよいです。 更新にあたっては、Dec クエリの個数を覚えておくなり deque を使うなりするのがよさそうです。個数の管理に適切なデータ構造を用いれば、Inc クエリが一般の Add クエリだった場合でも対応できそうでう。

ビットごとに数える問題と、特定のクエリの個数を覚えておく問題の例です。

• ARC 092 B
• CPSCO2019 Session 3
• ABC 389 C
• ABC 410 C
• ABC 425 C

今回の問題への提出コードは 提出 #78266354 です。

Binary trie

$\gdef\symdiff{\operatorname{\triangle}}$

別の解法についての noshi91 のツイートです。

Cのクエリ1が A[x] += 1 の代わりに A[x] += y だった場合

— 熨斗袋 (@noshi91) 2026年8月8日

y ≤ 10¹⁸ で

— 熨斗袋 (@noshi91) 2026年8月8日

$5\cdot 10^5$ 回 $A_1 \xgets+ 10^{18}$ で更新させることで 64-bit 整数信者を落とすことができる（？）

想定解は下の桁から分岐する binary trie で O(Q log A) でした

— 熨斗袋 (@noshi91) 2026年8月8日

これを実装して面白いな〜となったので書きます。 非負整数の集合 $S$ について、下記を処理できるデータ構造を作れます。任意の二項演算 $\circ$ と引数 $T$ について、$S\xgets\circ T$ は $S$ を $S\circ T$ で更新することを意味するとします。

• 与えられた非負整数 $x$ について $x\in S$ を判定する。
• 与えられた非負整数 $x$ について $S \xgets{\cup} \{x\}$ で更新する。
  • $S$ に $x$ を追加する。
• 与えられた非負整数 $x$ について $S \xgets{\smallsetminus} \{x\}$ で更新する。
  • $S$ から $x$ を削除する。
• 与えられた非負整数 $x$ について $S \xgets{\symdiff} \{x\}$ で更新する。
  • $S$ に $x$ が含まれるか否かを反転させる。
  • あるいは、$\{x\}$ との対称差で更新する。
• $0\notin S$ を事前条件とし、$S \gets \{x-1\mid x\in S\}$ で更新する。
• $\bigoplus_{x\in S} x$ を出力する。
  • 全部の要素の XOR を求める。

Add クエリ $a_x \xgets+ y$ は、$S \xgets{\symdiff} \{a_x\}$ と $S \xgets{\symdiff} \{a_x+y\}$ で処理できます。 Dec クエリは、$S \gets \{x-1\mid x\in S\}$ と $S \xgets{\smallsetminus} \{0\}$ で処理できます。

以下、$S \gets \{x-1\mid x\in S\}$ の処理を説明します。 $x\gt 0$ を非負整数 $q$, $k$ を用いて $x = (2q+1)\cdot 2^k$ と表せるとき、$x-1 = 2q\cdot 2^k + (2^k-1)$ です。すなわち、$x\xgets-1$ の更新は下位 $k+1$ bits の反転と見なせます。 $$ q\cdot 2^{k+1} + 1\underbrace{00\ldots 0}_{k~\text{bits}}{\;\!}_{(2)} \mapsto q\cdot 2^{k+1} + 0\underbrace{11\ldots 1}_{k~\text{bits}}{\;\!}_{(2)} $$ これを binary trie に含まれるすべての整数に対して行うのは、$0$ の枝と $1$ の枝を交換する操作を（元々の）$0$ の枝に沿って行うことに相当します。 これは $O(\log(\max A) )$ 時間で処理できることがわかります。

この処理に相当する図を下記に示します。破線で $0$ の枝、実線で $1$ の枝を表します。また、三角形は（空でもよい）任意の部分木とします。

$\{x-1\mid x\in S\}$ に相当する binary trie

$S = \{1, 3, 4, 6, 7\}$ と $\{x-1\mid x\in S\}$ に対応する binary trie の図を下記に示します。 変更される箇所を赤で塗っています。

$S = \{1, 3, 4, 6, 7\}$ に対する例

Xor クエリに関しては、部分木が持つ値たちの XOR への寄与や、部分木が持つ要素数の偶奇を管理することで、$O(1)$ 時間で答えられます。

ふつう binary trie を使うときは上位ビットから分岐させがちな気がしますが、これは大小関係をうまく扱いたいからで、$\pm 1$ による一括更新を扱いたいときは下位ビットから分岐させるのがいいのかな〜と思いました。

• ABC 241 D
• ABC 308 G

今回の問題への提出コードは 提出 #78251019 です。

適当な二項演算としての XOR

特にいい性質があることを期待していない適当な二項演算（可換モノイド程度？）として XOR が使われることはしばしばあります。

• ABC 197 C
• ABC 390 D

FFT をするときだけ $998244353$ で割ったあまりを求めさせるとバレちゃう的な話同様、XOR 特有の性質を使うときだけ XOR を使うとバレちゃう的な見方もあるかもしれません。

あとがき

どうせ unrated で参加しているし、C を飛ばして D を解いて順位を上げても特にうれしいことはなく、解けない問題を投げ出さずに根気強くやるのが（現時点での）えびちゃんへの訓練としてはいいんだろうな〜という気持ちがあります。結果としてきちんと解けましたし、D も 5 分くらいで通せたのでよかったな〜と思っています。 E 以降もそのうち読もうと思っています。

記事中の図を描くにあたっては TikZ を使っているのですが、やっぱりなかなか曲者でして、ドキュメントや Stack Overflow を読みながらがんばっています。非公式の HTML 版 もあるらしいです。過去の記事 で NP-complete な問題に関してのおえかきをしたときのことを思い出しました。これも楽しかったです。

おわり

おわりです。

いつまでもあると思うなという話

あるいは、終わりがまだ先だろうという油断について。

今回は、競プロも CTF も（少なくとも直接的には）関係ない話で、感情のまま書き散らすレア回です。 というのも、えびちゃんが約 9 年間続けていたゲームが終わりを迎えたことに伴い、いろいろと感じるところがあったためです。

老人語り

えびちゃんがリステップを始めたのは 2017 年の 8 月 22 日で、3240 日ログインしていました。ちょこちょこ忘れている日がありますね。 当時は、ソシャゲあるあるの AP 制でキャンディというアイテムがあったり、譜面のレベルが☆ 5 つで示されていたりしていました。 また、難易度も EXPERT がなくて HARD が一番上で、Stage of Star の HARD が一番難しいものでした。楽曲数も当時はあまり多くなかったので物足りなくなってきて、画面上半分を隠してプレイしたりしていました。 その後、宣誓センセーションの HARD が追加され、明確に「むずかしい」という感覚が芽生えました。それでも何時間かプレイしていると見えるようになってきて、リステップからしか得られない栄養素がないと生きられない身体になっていきました。

あらそいに関しては周回があまりにも大変だったので敬遠することも多かったですが、フルコンチャレンジやハイスコアチャレンジは楽しんでやっていました。 プリズムダービーや tap only などが出てきたりなくなったり、EXPERT が追加されたり、さまざまな変化があったなあと思い出します。メドレーも好きだったなあ。 EXPERT が追加されるまでの間、ある程度慣れてきてまた物足りない期になっていましたが、それでもリステップから離れられなかったので片手プレイに勤しんだりしていました。たしかカナリアの HARD を片手でやっていたと思います。

何度かのオンゲキコラボも印象深いです。当時最大ノーツ数だった宣誓センセーション EXPERT の 948 を 1 超える 949 ノーツの Splash Dance!! も、新しい時代を感じさせるものの一つでした。その後は当然のように 1000 ノーツを超える譜面が出てきて、物足りなさを感じることは少なくなっていきました。 ところで Flavor Youth の EXPERT のラストはなんですか？ 結局一度しかフルコンできませんでした。シンプルに音ゲーが弱いだけという気もします。

物足りなさを感じることが少なくなっても身体が縛りプレイを求めていて、グレースケールにしてプレイするのを最近はやっていました。私たち、四季を遊ぶんです!! がわりとやりやすくて、譜面職人の気持ちを信じながらパズルをすることで色が見えないのになぜかコンボが繋がる快感には、驚きを隠せませんでした。クリア後、色を戻したときに「世界に色がある...！」と感じたのも面白かったです。直近は、遡行的インサイドやレーイレーイの EXPERT もグレースケールで all perfect できました。黄色はグレースケールでも比較的見やすいのでずるいです（？）。

そういえば、当時はタイトル画面の楽曲が Do it!!PARTY!! だったのですが、懐かしさからか Do it!!PARTY!! のイントロを聴くだけで泣きそうな気持ちになります。あれ別に泣き曲ではなくないですか？

えびちゃんはこういう懐古話が好きなんだろうということをしばしば思います。老人適性がある（？）。

音ゲー側の話とは別で、陽花ちゃんの声優が変わったり、環ちゃんが加わったり、陽花ちゃんが海外に行かれたり、苑ちゃんやアルシュトーンの皆さま方が加わったりといろいろなことがありました。正直な話をすると、花守ゆみりさんが陽花ちゃんを演じていた時代に心を置き去りにされているえびちゃんもいます。もちろん新しく入ってきてくださる方々のことも応援していて、そこに嘘はないのですが、忘れがたいものもあるということですね。

アルシュトーンの皆さま方は本当にすごくて、遡行的インサイドや WHITE ADDixiON に STAND BY YOU、リメンバーズ! のカバーなど好きなものがたくさんあります。リステの楽曲は名曲しかないのですが、そんな中でもやはり KiRaRe が実家という感じがあり、「やっぱこれなんだよなあ〜〜」という気持ちになります。

WHITE ADDixiON の好きなところ発表オタクやります
「逃がしはしないわ散らした火花」で「イヤイヤ」とたくさん韻を踏んでいるところ

— えびちゃん🚑🐿️☄️ (@rsk0315_h4x) 2025年5月24日

キャラとしては（えびちゃんはお姉さんが好きなので）環ちゃんが好きなのですが、環ちゃんのソロ曲やユニット曲などが作られるご予定はありますでしょうか...？ 新衣装もお麗しいことですのに 🥺 中学生アイドルコンテンツであるところに高校生が入るのが異端とされているのか、全体集合絵でも環ちゃんがご不在であられることがしばしばあり、かなしい気持ちになることもあります。 すみっコぐらしでも同様にえびふらいのしっぽちゃんがご不在なことがしばしばあり、似たような気持ちになります。

思い出話パートはこのくらいにいたしましょう。

より広くコンテンツの話

えびちゃんのリステップへの総課金額はあまり少なくないと思いますが、リステップからしか得られない栄養素はリステップからしか得られないのであり、リステップが生まれなかった世界線で同じだけのお金を費やしても得られない体験を得ることができたと思っています*1。 こう思えるようなコンテンツに出会えたこと自体が幸福だと感じます。

リステップが終わって唯一無二のゲーム性が失われることは人類にとっての多大な損失だと思うわけですが、リステップのゲームスタイルが唯一無二であったこと自体も寂しいものという気もします。似たタイプの思考型リズムアクションゲームは今後出てくるのでしょうか。

そのコンテンツを好きであり続ける前提で、コンテンツの終了と同時に自決しないのであれば、コンテンツを最後まで見届けられずに自分が死ぬか、コンテンツが終わる悲しみに耐えながら生きるかの二択しかありません。どちらの択であれ後悔は生じるものと思います。 あるいはコンテンツが終わらないうちにそのコンテンツから離れるというのもありますが、そういう離れ方自体が悲しいなぁとも感じます。

えびちゃんと相容れない教えとして「自立とは依存先を増やすこと」というものがありますが、依存先のそれぞれがかけがえのないものなので、ただ単一障害点を増やしているだけということになりがちです*2。 コンテンツを好きになるたびに終わったときの悲しみを想像するような生き方が幸福か？というと、そうではないというのは自覚しています。 自覚していることと実践できるかは別の話です。

他にもえびちゃんを救わないフレーズとして「止まない雨はない」というものがありますが、陰らない日もまたないことであるなぁと思うわけです。 あるいは、雨が止む瞬間の存在性だけを示して満足されても困るという気持ちにもなります。雨が止む前に死んでしまう場合もあり、主観的には止まない雨と同じです。 という話を書いていて “Life is a mosaic of pleasure and pain – grief is an interval between two moments of joy. [...]” のことを思い出しました。えびちゃんが以前よく遊んでいた Getting Over It の中でも引用されているフレーズです。

お見送り

今の会社に入社してから数年経ち、先輩や先輩以外などを見送る機会が多くありました。 会社以外でも、Twitter で見ていて尊敬していた人の更新がもう止まってしまったりして、名前を見る機会があるたびに気持ちが込み上げます。昔の写真を見ていたら、その方とお食事したときのものが出てきて、同様の気持ちになりました。

追記：何人かの方が名前を挙げてくださっていました。その方であっています。やはり想っているのはえびちゃんだけではないみたいです。

数年前、狩生かりゅというゲーム実況者がおられました。目隠しでポケモンルビーを攻略する動画が特に好きでした。 消えた動画が戻ってきてまた観られるようになる夢を見たのは、一度や二度ではありません*3。 キャモメやワンリキーの鳴き声、ポケモンルビーの BGM や効果音を聞くたびに記憶が蘇り、どうしていなくなってしまったのかという気持ちに襲われます。 心構えができていないかった別れは、特有の苦しみを伴うものです。 上で言及した Getting Over It についても彼の動画がきっかけで始めたもので、馬の鳴き声が聞こえるたびに切なくなります。

大学に入って最初にお世話になっていた宿では宿側の事情で 1 年経たずに退去することになったり、研究室時代は B3 から M2 まで 1 年ごとに指導教官が変わったり（おめでたい事情のことが多かったので、これはそういうものかなという気がしていますが）、「お見送り」という観点で思い返すといろいろあったかなぁという気持ちになったりします。

そういえば、歌丸師匠が旅立たれた後、録画していた笑点を見返してなにか虚しい気持ちになっていた時期もあったなあと思い出しました。

他にも惜しまれつつ幕を閉じたコンテンツとして、Google Code Jam もありました。Meta Hacker Cup はいつまで続いてくれるのでしょうか。

ぽかいこちゃんが Twitter から去ってしまったことについては、「どうして...」となっていますが、今でもえびちゃんのことを見守ってくださる（今日も記事が上がっていました。どうして？ いつもありがとうございます）ので、これに関しては泣かずに済んでいます。

最近の話

最近は、ちょっとしたきっかけから VTuber の方を何人か応援していますが、これもいわゆる卒業が起こりがちな業界なので、心が弱っているえびちゃんには厳しいものがあるかもしれません*4？ 卒業して数ヶ月・数年経った方に対してのロスを抱えたまま生き続けている人をしばしば見かけ、（時期的に、その方のことはえびちゃんはあまり知らないのですが）やはりそうした感情は普遍的に生じうるものだよなぁと思ったりもしました。 えびちゃんは、大空スバルさん、星街すいせいさん、白銀ノエルさん、雪花ラミィさん、儒烏風亭らでんさんを応援しています。

これは V ではないのですが、TL で見かけてたまたま観た動画で memento mori について言及があり、えびちゃんが思っていたのと似たような部分があるかなぁと思いました。 memento mori は remember (that you have) to die のこと^(ref) ですが、えびちゃんが抱えているものは you ではなく特定の第三者なので、少し違った側面があるなとも思っています。 他にも、carpe diem, quam minimum credula postero. や Gaudeamus igitur や De brevitate vitae などの言葉を知りました。 brevitas は abbreviation の真ん中あたりの部分と同根で、brevis は短いという意味です。しばしば “for the sake of brevity” などの言い回しも見ますが、その brevity も同様です。ラテン語のお勉強を始めてから、こういうところに意識が向くようになりました。

あとがき

えびちゃんだけではなくフォロヮの皆さま方も何かのロスに苦しんでおられることでしょうか？ あるいは、えびちゃんがツイートや記事たちを全部消していなくなる可能性も否定はできないわけで、そうした状況への準備はできていますか？ あとで読もうと思っている記事があるなら、URL をブックマークするのではなくローカルに保存しておく方が安心だと思います。

そういえば、びーとくんは数年前に実行していましたが、余裕を持って予告をなさっていてえらかったなぁと思いました。

おわり

おわりです。土日だっていつまでもあると思ってはいけません。あっという間に夕方です。

*1:音ゲーの部分が好きで、それ自体は無料で遊べるものではあります。

*2:このような教訓は各々の解釈によるところが大きいだろうので、えびちゃん以外の人にとって救いであるなら特に言うことはありません。

*3:三度か四度だったと思います。

*4:いま応援している人が卒業しそうとかそうでないとか、そういう話には言及していません。