Java's BigInteger class provides truncated division (quotient and remainder). Given this as a starting point, what's the simplest and most efficient way to implement floored and Euclidean division (quotient and remainder)?
Based on the answer of Soronbe, here are the implementations (excluding the second variant of floored divison) in correct Java syntax:
public BigInteger euclidianDivision(BigInteger a, BigInteger b) {
return
a.subtract(
a.compareTo(BigInteger.ZERO) < 0 ?
b.subtract(BigInteger.ONE) :
BigInteger.ZERO
).divide(b)
}
public BigInteger flooredDivision(BigInteger a, BigInteger b) {
return
a.add(
(a.compareTo(BigInteger.ZERO) < 0) != (b.compareTo(BigInteger.ZERO) < 0) ?
b.subtract(BigInteger.ONE) :
BigInteger.ZERO
).divide(b);
}
Update:
For computing the remainder according to the three division algorithms, two of them are already implemented in BigInteger
(mod
for the Euclidean division and remainder
for the truncating division). To obtain the remainder for flooring division, you can use the following implementation:
public BigInteger flooredRemainder(BigInteger a, BigInteger b) {
return
a.mod(b).subtract(
b.compareTo(BigInteger.ZERO) < 0 ? BigInteger.ONE : BigInteger.ZERO
);
}