Math.floor(x / y) は常に期待する値になるか

数学

x, y は0以上2^32未満の整数とし、yは0でないとする。
数式上に ${...} と書いたらECMAScriptで...の部分を評価した結果の値を表すものとする。${...} の外で a + b のように何か演算を書いた場合、それは浮動小数点数の演算ではなく、数学的な実数の演算を表すものとする

${Math.floor(x / y)}} = floor(x / y) は常に成り立つか？

α = floor(x / y) とおくと α <= (x / y) < α + 1 が成り立つ

直近への丸め

ECMAScriptの四則演算は結果を直近の表現可能な値へ丸めることが定められている。すなわち ⊙を四則演算の記号(+,-,*,/)、aを任意の表現可能な値だとすると ${x ⊙ y} < a < (x ⊙ y) や (x ⊙ y) < a < ${x ⊙ y} が成り立つことはない。

α <= ${x / y} <= α + 1 を示す
  • α, α + 1 はともに表現可能な値である。
  • α <= (x / y) より ${x / y} < α となることはない。
  • 同様に (x / y) <= α + 1 より ${x / y} > α + 1 となることもない。
  • したがって α <= ${x / y} <= α + 1 である。
${x / y} != α + 1 ？

${x / y} != α + 1 の場合、α <= ${x / y} < α + 1 より${Math.floor(x / y)} = α が成り立つ。
よって、${x / y} = α + 1 となることがないことを示せばいい。

(整数) + 1 より小さい最大の浮動小数点数

1以上2未満の区間においては浮動小数点数は小数点以下の桁数が52桁の固定小数点数だと考えることができる。
同様に

  • 2以上4未満では51桁
  • 4以上8未満では50桁
  • ......

であるから

  • 2^n 以上 2^(n+1) 未満では (52 - n) 桁である (0<=n<=52)

したがって

  • nを自然数、aを整数とし、0<=n<=52, 2^n <= a < 2^(n+1) であるとすると
  • a + 1 より小さい表現可能な値の最大は a + ((1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n))) である

ここで

  • f(n) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n)) とおく
  • aを 0<=a<2^32 の整数として a + 1 より小さい表現可能な値の最大をa + g(a)とする
  • a != 0 のとき g(a) = f(floor(log2(a)))
  • a = 0 のとき g(0) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^53) であるから f(-1) に一致する
  • したがってg(a)は f(-1), f(0), f(1), ..., f(31) のいずれか
  • f(n)は単調減少であるから31以下のすべての整数nについて f(31) <= f(n) である
  • よって f(31) <= g(a) は常に成り立つ。
y = 3 で確かめる

ここで y = 3 とおいて ${x / 3} = α + 1 になることがあるかどうか確かめる

(x / 3) = α + (r / 3) と表すことができる。 (r = 0,1,2)

(x / 3)  = α + (r / 3)
        <= α + (2 / 3)
        <= α + f(31)
        <= α + g(α)
         < α + 1
  • よって (x / 3) <= α + g(α) < α + 1 であり α + g(α) は表現可能な値であるから ${x / 3} = α + 1 となることはない。
  • ここでは y = 3 としたが (y - 1) / y <= f(31) が成り立つならば ${x / 3} != α + 1 は常に成り立つ。
  • 関数 (y - 1) / y は y > 0 で単調増加し f(31) = (2^21 - 1) / 2^21 であるから y <= 2^21 であるとき ${x / y} != α + 1 は常に成り立つ。
yが大きいときについて考える

y <= 2^21 については示せたから、問題はyが2^21より大きいときである。
g(α)の下界としてf(31)を使ったが、yが大きいときにはαは小さくなるから下界をもっと大きくできるはずである。

ここでf(n) を変形しておく

f(n) = (1 / 2) + (1 / 2^2) + ... + (1 / 2^(52-n))
     = Σ[k=1,52-n] (1 / 2)^k  # 初項 1/2, 公比 1/2, 項数 52-n の等比数列の和
     = (1 / 2) * (1 - (1 / 2) ^ (52-n)) / (1 - (1 / 2))
     = 1 - (1 / 2) ^ (52-n)
     = (2 ^ (52-n) - 1) / (2 ^ (52-n))

y >= 2^n とする。 (0 <= n <= 32)

α  = floor(x / y)
   <= (x / y)
    < (2^32 / y)
   <= (2^32 / 2^n)
    = 2^(32-n)

よって α < 2^(32-n) すなわち α <= 2^(32-n) - 1
関数g(a)は単調減少をするから

g(α) >= g(2^(32-n) - 1)
       = f(32-n-1)
       = (2 ^ (52-(31-n)) - 1) / (2 ^ (52-(31-n)))
       = (2 ^ (21+n) - 1) / (2 ^ (21+n))

よって y <= (2 ^ (21+n)) ならば

(x / y) =  α + (r / y)  # rは0以上y未満の整数
        <= α + ((y - 1) / y)
        <= α + (2 ^ (21+n) - 1) / (2 ^ (21+n))
        <= α + g(α)
        <  α + 1

である。

  • よってnを0以上32未満の任意の整数とするとき 2^n <= y <= 2 ^ (21+n) であるすべての整数yで ${x / y} != α + 1 が成り立つ。
  • まず、y <= 2^21において常に ${x / y} != α + 1 が成り立つことは既に示した。
  • n = 21 とおいて 2^21 <= y <= 2^42 で常に ${x / y} != α + 1 が成り立つ。
  • よってyが1以上2^32未満のすべての整数において ${x / y} != α + 1 は常に成り立つ。
  • したがって ${Math.floor(x / y)} = floor(x / y) は常に成り立つ。
  • おわり

まとめ

数学難しいです！でも自分で問題を立てて考えるのは楽しいですね！
間違っているところや、ここをこうした方がいいといった指摘、もっとスマートな方法があればコメント欄に書き込んでくださるとありがたいです！