n / a / b = n / (a * b)は常に真でしょうか？

Question

これまで何となく使ってきたのですが、
n / a / b = n / (a * b)は常に真でしょうか？

試しに以下を実行したが反例がないので、やはり常に真な気がするのですが
どうでしょうか？

(1..501).each{|n|
  (1..n).each{|a|
    (1..n).each{|b|
      p [a, b] if !((n / a / b) == (n / (a * b)))
    }
  }
}

Comments

[argius]

KiyoshiMotokiさんのおっしゃるとおり、プログラミング言語によると思いますが、もしRubyに限った質問であれば、タグにRubyをつけたほうが良いと思います。

[manman]

タグを「プログラミング言語」から「Ruby」に変更しました。

Answer 1

Rubyで整数の範囲では、真でしょう。
Rubyの整数は無限精度なので。

浮動小数点の場合は、有限精度なので真とは限らない。
偽となる例を1つ挙げておきます。

puts 2.0/0.1/7.0==2.0/(0.1*7.0) #=> false

Comments

[manman]

盲点を突かれました。

Answer 2

プログラミング言語タブなので、C/C++の場合で回答してみます。

CやC++言語のように整数型演算のオーバーフローを無視するような言語ですと、常に真にはなりません。
今は少ないですが、整数型(int)が-32768～32767の範囲しか表現できない処理系だった場合、
信じがたいと思いますが(32767*2)=-2となってしまう処理系が多く、10/(32767*2)=-5となるものがあります。10/32767/2=0なので結果が異なります。
今でもint型だけの演算で、int型の上限を超える計算をさせると同じような問題が起きます。

---

【追記】
げっ、タブがRubyに変わっちゃいました。私が回答した時はプログラミング言語だったので許してください。

Answer 3

言語仕様によるのではないでしょうか？

以下のリンクの"プログラミング言語"という項によると、

多くのプログラミング言語では、算術におけるそれと同じ優先順位である。しかし、中にはAPLやSmalltalkのように演算子の優先順位を持たない言語もある（APLではなんでも右から左へと評価していく。Smalltalkでは、なんでも左から右へと評価していく）。

https://ja.wikipedia.org/wiki/%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D

とありますので、少なくともAPLという言語では異なる結果になりそうです。

あとは、aまたはbをnに比べて非常に大きい値にした場合も、誤差が発生するかもしれません。

Answer 4

コンピュータでの計算では,桁数が有限だということに注意する必要があります。

極端な例として int を 2 bit で表している 言語で考えてみます。

この言語では 2/2/2 は 0 になります。
2/(22) は 22 の計算時にこの言語であらわせる整数の範囲を超えてしまいます。
言語によっては此処でエラーが発生して値は得られないことになります。
エラーが発生せず単に下の桁だけを取り出すようになっている場合は 2*2 は 0 となるかもしれません。
そして、計算を続けようとすると 2/0 となり、今度は 0 での割り算でのエラーとなるでしょう。

つまり、数学上では n / a / b = n / (a * b) ですが、
コンピュータでの計算では これが成り立たない例があるのです。

桁が有限な事の影響は掛け算だけで起こるわけではありません。
n == m と (n + 1) == (m + 1) は、判定結果が異なるケースもあります。
n + 1 の計算時に桁があふれたら、言語によってはエラーが発生するからです。

int でなく、double での場合でもいろいろな問題が発生することあります。
２次方程式の解の公式の数式をそのまま計算したのでは、実際の値は大きく異る値になってしまうことがあります。(これは数値計算系の教科書でよく出てくる例です)

Answer 5

基本的には真ですが、a * bがオーバーフローを起こした場合は結果が変わります。また、浮動小数点の場合は丸め誤差によって結果が変わる可能性があります。

Answer 6

(証明)以下、積は*記号を用いず文字を並べて表現する。
n = pa + q, p = rb + s(ただし、p, q, r, sは0以上の整数で、q < a, s < b)とする。
この時、n / a / b = rである。
n = (rb + s)a + q = rab + (sa + q)

ここでsa + q < abが示せれば、nをabで割った商がr,余りがsa + qということになり、
n / ab = rとなる。

sa + q - ab = a(s - b) + q
s, bは0以上の整数でs < bなのでs - bは-1以下の整数
よってa(s - b) <= -a
a(s - b) + q <= q - a < 0(∵q < a)
よってsa + q < ab
したがってsa + qは、nをabで割った余りに相当する。
つまり、n / ab = r = n / a / b (証明終了)

Comments

[swordone]

見返してみるとn,a,bが正の時しか証明してませんね…
整数全体で証明できるかな…？