LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@hibit(hibit at)

軽い気持ちで負の整数を含む不等式を式変形して評価しない方がいい

Posted at

理由

  • 正確な挙動をさせるためには場合分けが必要である
  • 言語の仕様によって挙動が異なる

対策

　オーバーフローの問題がなければ、式変形して除算がない形にするのが一番確実。

前提

　先行研究によると、以下の事実が言えます。

　ある 正の 整数 $z,p,q$ について、

  • $z \cdot q \leq p \Longleftrightarrow z \leq \lfloor \frac{p}{q} \rfloor$
  • $z \cdot q \geq p \Longleftrightarrow z \geq \lceil \frac{p}{q} \rceil$
  • $z \cdot q < p \Longleftrightarrow z < \lceil \frac{p}{q} \rceil \Longleftrightarrow z \leq \lceil \frac{p}{q} \rceil - 1$
  • $z \cdot q > p \Longleftrightarrow z > \lfloor \frac{p}{q} \rfloor \Longleftrightarrow z \geq \lfloor \frac{p}{q} \rfloor + 1$

　まず、これが問題ないかをプログラムで網羅的にチェックします。理論的にはすべての整数をチェックする必要がありますが、とりあえず $1 \sim 100$ まで調べて問題がなかったらオーケーとします。

C++
#include <iostream>
#include <cassert>

int main() {
    const int zL = 1;
    const int zR = 100;
    const int pL = 1;
    const int pR = 100;
    const int qL = 1;
    const int qR = 100;

    for (int z = zL; z <= zR; ++z) {
        for (int p = pL; p <= pR; ++p) {
            for (int q = qL; q <= qR; ++q) {
                assert((z * q <= p) == (z <= p / q));
            }
        }
    }
    std::cout << "<= asserted" << std::endl;

    for (int z = zL; z <= zR; ++z) {
        for (int p = pL; p <= pR; ++p) {
            for (int q = qL; q <= qR; ++q) {
                assert((z * q >= p) == (z >= (p + q - 1) / q));
            }
        }
    }
    std::cout << ">= asserted" << std::endl;

    for (int z = zL; z <= zR; ++z) {
        for (int p = pL; p <= pR; ++p) {
            for (int q = qL; q <= qR; ++q) {
                assert((z * q < p) == (z < (p + q - 1) / q));
            }
        }
    }
    std::cout << "< asserted" << std::endl;

    for (int z = zL; z <= zR; ++z) {
        for (int p = pL; p <= pR; ++p) {
            for (int q = qL; q <= qR; ++q) {
                assert((z * q > p) == (z > p / q));
            }
        }
    }
    std::cout << "> asserted" << std::endl;

    return 0;
}

　このプログラムを走らせると、

<= asserted
>= asserted
< asserted
> asserted

　となり、恐らく上の式が問題ないだろうということが確認できます。

　Python でも同様です。

def main():
    zL = 1
    zR = 100
    pL = 1
    pR = 100
    qL = 1
    qR = 100

    for z in range(zL, zR + 1):
        for p in range(pL, pR + 1):
            for q in range(qL, qR + 1):
                assert (z * q <= p) == (z <= p//q)

    print("<= asserted")

    for z in range(zL, zR + 1):
        for p in range(pL, pR + 1):
            for q in range(qL, qR + 1):
                assert (z * q >= p) == (z >= (p + q - 1) // q)

    print(">= asserted")

    for z in range(zL, zR + 1):
        for p in range(pL, pR + 1):
            for q in range(qL, qR + 1):
                assert (z * q < p) == (z < (p + q - 1) // q)

    print("< asserted")

    for z in range(zL, zR + 1):
        for p in range(pL, pR + 1):
            for q in range(qL, qR + 1):
                assert (z * q > p) == (z > p // q)

    print("> asserted")

if __name__ == "__main__":
    main()

　これらの関係 負の数や $0$ に対しても 同様に成り立つのでしょうか？

負の数を割る

　$z$ と $p$ の範囲を拡張し、 $-100 \sim 100$ としてみます。

　すると、なんとエラーが出ます。

　具体的には、例えば $(z,p,q)=(-49,-99,2)$ でエラーが出ます。

  • $z \cdot q = -98 \leq p=-99 \quad (\text{FALSE})$
  • $z = -49 \leq \lfloor \frac{p}{q} \rfloor = \lfloor \frac{-99}{2} \rfloor = -50\quad (\text{FALSE})$

　になって、一致するから問題ないはずなのですが。

　これは、C++ の 除算の仕様 が原因です。

　突然ですが、ここで Python と C++ において、負の数を含む除算がどのような結果になるかをまとめた表を貼ります。

image.png

　本質をまとめると、以下のようになります。

image.png

　恐るべきことに、言語によって結果が異なります。これは仕様なので、どちらが正解とかはないですが、C++ は負の数の「切り捨て」は、絶対値を切り捨てる方向、つまり 数としては大きい方 に丸めます。C++ 的には、$\lfloor \frac{-99}{2} \rfloor$ は $-49$ になります。

　よって、場合分けが必要です。

C++
    for (int z = zL; z <= zR; ++z) { // [-100,100]
        for (int p = pL; p <= pR; ++p) { // [-100,100]
            for (int q = qL; q <= qR; ++q) { // [1,100]
                if(p < 0){
                    assert((z * q <= p) == (z <= (p - q + 1) / q));
                }else{
                    assert((z * q <= p) == (z <= p / q));
                }
            }
        }
    }
    std::cout << "<= asserted" << std::endl;

　デフォルトだと 切り上げ になっているものを 切り下げ にするため (p-q+1)/q という形でその処理をしています。

　ちなみに、Python だと、負の数でも数が小さい方に切り捨ててくれるので、$z$ や $p$ が負でも大丈夫です。

Python
for z in range(zL, zR+1): # [-100,100]
    for p in range(pL, pR+1): # [-100,100]
        for q in range(qL, qR+1): # [1,100]
            assert((z * q <= p) == (z <= p // q))

0 で割る

　次に、割る数の定義域を拡張して考えます。話がややこしくてなるので、$z$ または $p$ は正限定に戻します。

　まず、$0$ 除算は定義できないので自明に場合分けが必要です。

    for (int z = zL; z <= zR; ++z) { // [1,100]
        for (int p = pL; p <= pR; ++p) { // [1,100]
            for (int q = qL; q <= qR; ++q) { // [0,100]
                if (q == 0) {
                    assert((z * q >= p) == (0 >= p));
                } else {
                    assert((z * q >= p) == (z >= (p + q - 1) / q));
                }
            }
        }
    }

負の数で割る

　次に $q$ を拡張して負の数を含めてみると、エラーが出ます。

　そう、負の数で割ると不等号が逆転する のでした。ということで、場合分けの追加。

    for (int z = zL; z <= zR; ++z) { // [1,100]
        for (int p = pL; p <= pR; ++p) { // [1,100]
            for (int q = qL; q <= qR; ++q) { // [-100,100]
                if (q < 0){
                    assert((z * q <= p) == (z >= p / q));
                }else if (q == 0) {
                    assert((z * q <= p) == (0 <= p));
                } else {
                    assert((z * q <= p) == (z <= p / q));
                }
            }
        }
    }
    std::cout << "<= asserted" << std::endl;

負の数を負の数で割る

　ラスボスです。負の数を負で割った場合。当然ながら、割る数を負にすると、切り下げ、切り上げを切り替える必要があります。結論的には以下のようになります。

c++
    for (int z = zL; z <= zR; ++z) { // [-100,100]
        for (int p = pL; p <= pR; ++p) { // [-100,100]
            for (int q = qL; q <= qR; ++q) { // [-100,100]
                if (q < 0){
                    if(p < 0){
                        assert((z * q <= p) == (z >= (p + q + 1) / q));
                    }else{
                        assert((z * q <= p) == (z >= p / q));
                    }
                }else if (q == 0) {
                    assert((z * q <= p) == (0 <= p));
                } else {
                    if(p < 0){
                        assert((z * q <= p) == (z <= (p - q + 1) / q)); 
                    }else{
                        assert((z * q <= p) == (z <= p / q));
                    }
                }
            }
        }
    }
    std::cout << "<= asserted" << std::endl;

　切り下げの方法が q の正負によって変わっている点に注意です。

　ここまで場合分けして、やっと（負の数がある場合も含めて）$z \cdot q \leq p$ と同値な比較ができます。

　ちなみに Python だとこう。

Python
    for z in range(zL, zR + 1): #[-100,100]
        for p in range(pL, pR + 1): #[-100,100]
            for q in range(qL, qR + 1): #[-100,100]
                if q < 0:
                    assert (z * q <= p) == (z >= (p + q + 1)//q)
                if q == 0:
                    assert (z * q <= p) == (0 <= p)
                if q > 0:
                    assert (z * q <= p) == (z <= p//q)
    print("<= asserted")

　他の演算子についても、「これは切り捨てか？切り上げか？」「除算の仕様はどうか？」ということをミスらなければ、同様のことができます。ややこしすぎます。

　という訳で、冒頭の結論に至ります。除算が含まない形にするのが一番確実です。

式変形が役に立つかもしれない場面（正）

　ちなみに、式変形した形が役に立つかもしれないものとして、以下のような例が考えられます。

　ただし、以下の応用例は、与えられる数がすべて正である想定 であることに注意してください。

オーバーフロー

「$a \cdot b > 10^{18}$ か？」みたいなことを比較する場合、$a \cdot b$ が整数の型の範囲に収まりきらない場合、オーバーフローを引き起こします。よって、この場合は「$a > \frac{10^{18}}{b}$ か？」といった形で比較する方が安全です。

配列を変えないまま比較する

「$\lbrace 1,1,2,3,5,\cdots \rbrace$ という配列を $b$ 倍したものに対して $a$ より大きい境目はどこか？」ということを求める場合、全要素を $b$ 倍した配列を別に確保するのがわかりやすいですが、以下のように問題を言い換えることもできます。

「$\lbrace 1,1,2,3,5,\cdots \rbrace$ という配列に対して $\frac{a}{b}$ より大きい境目はどこか？」

　これにより、配列を変えないまま同じ判定ができます。

　なお、これを負の数でやろうとすると範囲が反転したりして頭がバグるのでオススメしません。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?