java - 大整数的底除法和欧几里得除法

Question

Java 的 BigInteger 类提供截断除法(商和余数)。以此为起点，实现底数和欧几里得除法(商和余数)的最简单和最有效的方法是什么？

Answer 1

基于Soronbe的回答，这里是正确的 Java 语法的实现(不包括 floored divison 的第二个变体):

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

更新: 根据三种除法算法计算余数，其中两种已经在BigInteger中实现(mod用于欧氏除法，remainder用于欧氏除法)截断除法)。要获取地板划分的余数，您可以使用以下实现:

public BigInteger flooredRemainder(BigInteger a, BigInteger b) {
    return
        a.mod(b).subtract(
            b.compareTo(BigInteger.ZERO) < 0 ? BigInteger.ONE : BigInteger.ZERO
        );
}