Floored and Euclidean division of big integers

Question

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)?

To clarify, you want the result to round toward negative infinity, not toward zero? — Oliver Charlesworth, Mar 22 '15 at 12:52
@SMA I'm implementing the TPTP specification for first-order logic with arithmetic, which prescribes all three kinds of integer division. BigDecimal solves a different problem, unless I'm missing something? — rwallace, Mar 22 '15 at 12:53
@OliverCharlesworth Yes, as in http://stackoverflow.com/questions/4102423/efficiently-implementing-floored-euclidean-integer-division — rwallace, Mar 22 '15 at 12:56
Have a look at Guava's [BigIntegerMath.divide](http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/math/BigIntegerMath.html#divide(java.math.BigInteger,%20java.math.BigInteger,%20java.math.RoundingMode)) — Louis Wasserman, Mar 22 '15 at 17:40
Can you not do something along the lines dividing and if the result isn't an integer, take the integer part, and correct negative numbers as needed? — childofsoong, Mar 25 '15 at 00:23

score 4 · Accepted Answer · edited May 23 '17 at 12:23

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
        );
}

score 3 · Answer 2 · edited May 23 '17 at 11:52

According to: https://stackoverflow.com/a/4110620/4701236 this should be quite efficient. Note this is tested for efficiency in C and not Java, yet seeing the differences are rather small, I dont expect them to be big in Java (differences between implementations, not between C and Java) as the current Java compiler optimizes a lot.

public BigInteger euclidianDivision(BigInteger a,BigInteger b){
    return (a - (a<0 ? b-1 : 0)).divide(b)
}

public BigInteger flooredDivision(BigInteger a,BigInteger b){
    return (a + ( ((x<0) != (y<0))? b-1 : 0)).divide(b)
}

public BigInteger secondFlooredDivision(BigInteger a,BigInteger b){
    return (a + ( ((a ^ b) < 0)? b-1 : 0)).divide(b)
}

The secondFlooredDivision makes assumptions about the binary representation of negative number, so I advise you use the other. Currently not able to test this code, so if someone could run it and correct possible syntax mistakes (I wrote it as pseudo-code).

Floored and Euclidean division of big integers

2 Answers2