schedule2021-04-19

【Rust】num-integerのdiv_mod_floor()とdiv_rem()の違い

引数が正の整数の場合はどちらも返り値が同じ。引数がどちらも負の数を渡した場合も返り値が同じ。

違いは２つの引数の符号が異なる場合に現れる。

どちらも正の整数

div_mod_floor() と div_rem() はどちらも (商, あまり) のタプルを返します。

// 11 わる 3 = 3 あまり 2
// Simultaneous floored integer division and modulus
assert_eq!(integer::div_mod_floor(11, 3), (3, 2));
// Simultaneous integer division and modulus
assert_eq!(integer::div_rem(11, 3), (3, 2));

どちらも正の整数の場合は二つの違いは特にない。

どちらも負の整数

負の整数を渡しても返り値に相違はない。

// -11 わる -3
assert_eq!(integer::div_mod_floor(-11, -3), (3, -2));
assert_eq!(integer::div_rem(-11, -3), (3, -2));

// -17 わる -5
assert_eq!(integer::div_mod_floor(-17, -5), (3, -2));
assert_eq!(integer::div_rem(-17, -5), (3, -2));

二つの引数の符号が異なる場合

ただし、２つの引数の符号が異なる場合には相違がある。

// -11 わる 3
assert_eq!(integer::div_mod_floor(-11, 3), (-4, 1));
assert_eq!(integer::div_rem(-11, 3), (-3, -2));

// 11 わる -3
assert_eq!(integer::div_mod_floor(11, -3), (-4, -1));
assert_eq!(integer::div_rem(11, -3), (-3, 2));

div_rem() の場合は div_rem(-11, 3) == div_rem(-11, -3)です。
div_mod_floor() の場合は div_mod_floor(-11, 3) != div_mod_floor(-11, -3)である。

div_mod_floor() と div_rem() のコード

なぜ、div_mod_floor()が上のようになっているかはコードを見るとわかる。 div_mod_floor()では符号が異なる場合に明示的な処理をしている。

https://github.com/rust-num/num-integer/blob/master/src/lib.rs

lib.rs

/// Calculates `div_floor` and `mod_floor` simultaneously
#[inline]
fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
    // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
    // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
    let (d, r) = self.div_rem(other);
    if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
        (d - 1, r + *other)
    } else {
        (d, r)
    }
}

/// Simultaneous truncated integer division and modulus.
#[inline]
fn div_rem(&self, other: &Self) -> (Self, Self) {
    (*self / *other, *self % *other)
}

コードのコメントの論文より抜粋。

F-division floors the quotient and effectively rounds toward negative infinity. This definition is described by Knuth (Knuth, 1972) and is used by Oberon (Wirth, 1988) and Haskell (Peyton Jones and Hughes (eds.), 1998). Note that the sign of the modulus is always the same as the sign of the divisor. F-division is also a sign-preserving division (Boute, 1992), i.e. given the signs of the quotient and remainder, we can give the signs of the dividend and divisor. Floored division can be expressed in terms of truncated division.

F-divisionは商をフロア化し、効果的に負の無限大に向かって丸めます。この定義は、Knuth (Knuth, 1972) によって記述され、Oberon (Wirth, 1988) および Haskell (Peyton Jones and Hughes (eds.), 1998) で使用されています。なお、モジュラスの符号は、常に除数の符号と同じです。F-divisionは符号保存除算でもあります(Boute, 1992)。すなわち、商と剰余の符号が与えられれば、配当と除数の符号を与えることができます。フロアー式除算は、切り捨て式除算で表現することができます。

Algorithm F:
$q_F = q_T − I \\ r_F = r_T + I · d$
where
$I = if signum(r_T) = −signum(d) then 1 else 0$