🦁

Lua 5.1/5.2/LuaJITの%演算子と浮動小数点数の罠

2023/02/11に公開1

Luaの % 演算子

整数型が導入される以前のLua(Lua 5.1/5.2/LuaJIT)の % 演算子は次のように定義されています:

a % b == a - math.floor(a/b)*b

これはおおよそflooring divisionに対する剰余を返します。整数除算の二つの流儀で言うところのmodです。

しかし、この定義は math.floor という語彙を使っていることから察せられるように、浮動小数点数演算を使っています。その結果、整数同士の剰余

(-9007199254740992) % 3

に対して間違った答え 0 を返してしまいます。-9007199254740992-2^{53}で、

-2^{53}\equiv -(-1)^{53}\equiv 1\mod{3}

と計算できて正しい(浮動小数点数を使わない)答えは 1 です。実際、浮動小数点数を使わないLua 5.3で同じ計算を実行すると 1 が得られます。

というわけで、Lua 5.1/5.2/LuaJITの % で絶対値が大きな整数の剰余を計算するのはやばそうだということがわかります。Lua 5.1や5.2の開発はもう終了していますし、LuaJITはLua 5.1準拠なので、この挙動が「修正」されることはないでしょう。仕様バグです。

安全に使える十分条件

Luaの % 演算子が全く使えないかというとそんなことはなく、絶対値が大きくないところだとか、% の右側が2の累乗だったりすれば安全に使える気がします。確かめてみましょう。

整数n, dについて n % d の計算を考えます。n, dの絶対値の範囲は\lvert n\rvert\le 2^{53}, 1\le\lvert d\rvert\le 2^{53}とします。

実数\mathbf{R}から倍精度浮動小数点数\mathbf{F}へ最近接丸めを行う関数をR\colon\mathbf{R}\to\mathbf{F}とします。

Luaの % 演算子の定義をRを使って書いたものは

n\mathbin{\%}d:=R(n-R(\lfloor R(n/d)\rfloor\cdot d))

となりますが、

に書いたようにこのndの範囲では\lfloor R(n/d)\rfloor\lfloor n/d\rfloorに一致します。また、浮動小数点数のfloor \lfloor\cdot\rfloorは浮動小数点数として正確に表現できます(なので\lfloor\cdot\rfloorの周りにR(\cdot)は書いていません)。

ということで、

n\mathbin{\%}d=R(n-R(\lfloor n/d\rfloor\cdot d))

という風に、丸めが問題になりうるのは掛け算の際と引き算の際の2回です。

仮に掛け算の正確な値(整数値)が浮動小数点数として正確に表現可能であれば

R(n-R(\lfloor n/d\rfloor\cdot d))=R(n-\lfloor n/d\rfloor\cdot d)

となり、n-\lfloor n/d\rfloor\cdot dは絶対値がd未満なので浮動小数点数として正確に表現可能で、

n\mathbin{\%}d=n-\lfloor n/d\rfloor\cdot d

を得ます。よって、「積\lfloor n/d\rfloor\cdot dが浮動小数点数として正確に表現できるのはどのような時か」が焦点となります。

nとdが同符号の場合

n/d\ge 0の場合は0\le\lfloor n/d\rfloor\le n/dなので、0\le\bigl\lvert\lfloor n/d\rfloor\cdot d\bigr\rvert\le \lvert n\rvertです。\lvert n\rvert\le 2^{53}と仮定しているので、整数\lvert\lfloor n/d\rfloor\cdot d\rvertは浮動小数点数で正確に表現できます。

よって、ndが同符号の場合はLuaの % 演算子を安全に使えます。

nの絶対値がd以下の場合

今度はndは異符号であること(n/d<0)と、nの絶対値がdの絶対値以下であること(\lvert n\rvert\le\lvert d\rvert)を仮定します。

この時、\lfloor n/d\rfloor=-1です。よって、積\lfloor n/d\rfloor\cdot dは浮動小数点数で正確に表現できます。

nの絶対値がdよりも大きいが、大きすぎない場合

今度はndは異符号であること(n/d<0)と、nの絶対値がdの絶対値よりも大きいこと(\lvert d\rvert<\lvert n\rvert)を仮定します。

\lfloor n/d\rfloor\cdot dはおおよそn付近であろうということは予想されるので、nの絶対値が大きすぎなければ\lfloor n/d\rfloor\cdot dは浮動小数点数として正確に表現可能でしょう。

まず、床関数の定義(と異符号であること)より

n/d-1<\lfloor n/d\rfloor\le n/d<0

です。絶対値を取って

\lvert n/d\rvert\le\bigl\lvert\lfloor n/d\rfloor\bigr\rvert<\lvert n/d-1\rvert

で、それぞれ\lvert d\rvertをかけて

\lvert n\rvert\le\bigl\lvert\lfloor n/d\rfloor\cdot d\bigr\rvert<\lvert n-d\rvert

を得ます。よって、\lfloor n/d\rfloor\cdot dの絶対値は最大で\lvert n-d\rvert-1程度になり得ます。ndが異符号であることを考慮すると\bigl\lvert\lfloor n/d\rfloor\cdot d\bigr\rvertの上限は\lvert n\rvert+\lvert d\rvert-1になります。

最初に\lvert d\rvert<\lvert n\rvertすなわち\lvert d\rvert\le\lvert n\rvert-1を仮定したので、\lvert n\rvert+\lvert d\rvert-1\le 2\lvert n\rvert-2となります。

よって、2\lvert n\rvert-2\le 2^{53}であれば安全に % 演算子を使えます。このnの範囲は-(2^{52}+1)\le n\le 2^{52}+1です。nの絶対値がdよりも小さい場合はさっき安全だとわかったので、この結論に関してnの絶対値の下限を設定する必要はありません。

dが2の累乗である場合

\lvert d\rvertが2の累乗d=2^kである場合は「d倍」は正確に計算できます。ここではndもそこまで大きくないので、オーバーフローの心配はありません。kの範囲は0\le k\le 53です。

よって\lvert d\rvert=2^k (0\le k\le 53)の場合は安全に % 演算子を使えます。偶数かどうかの判定が n % 2 == 0 でできるのは嬉しいですね。

十分条件まとめ

絶対値が2^{53}以下の整数n, dについて以下のいずれかが成り立てば、 % を安全に使えます:

  • ndが同符号
  • \lvert n\rvert\le\lvert d\rvert
  • \lvert n\rvert\le 2^{52}+1
  • \lvert d\rvert=2^k (0\le k\le 53)

回避策

一般の場合は、% 演算子を安全に使うことはできません。そこで、別の方法で剰余を計算することを考えます。

Luaの場合はtruncating divisionに関する剰余(整数除算の二つの流儀でいうrem)が math.fmod で利用できるので、整数除算の二つの流儀に書いた方法でmodをエミュレートすれば良いです。コード例を以下に載せます:

function mod(n, d)
  assert(d != 0)
  r = math.fmod(n, d)
  if r == 0 or n * d >= 0 then
    return r
  else
    return r + d
  end
end

コード例では、同符号かどうかの確認は n * d >= 0 で行いました。

おまけ:FMAが有効な場合

q=\lfloor n/d\rfloorとしてn-q\cdot dの計算にFMA (fused multiply add; この場合はfused multiply subtract)が使われた場合は乗算の際の丸めが起こらないので正しい答えが得られます。

具体的な環境の例を挙げると、AArch64(最初からFMAがある)のGCC(積極的にFMAを使う)でコンパイルされたLua 5.1は整数の % を正しく計算します。

関連記事

Discussion

紳士ぴんきー紳士ぴんきー

同じソースコードでもFMAが有効な条件では
正しく動作「してしまう」のですね。

環境によって出たり出なかったり……
バグはこれが恐ろしいです。