当分子是2的幂的倍数时加速除法和余数

Question

我需要的形式的执行计算a 2^m / b,其中a/b接近1,a和b接近2^m和m较大(大于1000).我需要商和余数.我可以用Java做到这一点

BigInteger[] computeScaledRatio(BigInteger a, BigInteger b, int m) {
    return a.shiftLeft(m).divideAndRemainder(b);
}

成本大约是将2m位数除以m位数的成本.

有没有办法让这更快？

如果可能的话,我想将成本降低到大约分割两个m位数的成本.

我不在乎结果代码是否更复杂和/或是否需要一些外部库.

我绝望地尝试了以下代码.毫不奇怪,这种表现令人沮丧.

static final double LOG2_10 = Math.log(10) / Math.log(2);
static final BigDecimal TWO = BigDecimal.valueOf(2);
BigInteger[] computeScaledRatio(BigInteger a, BigInteger b, int m) {
    int percession = (int) Math.ceil((2 * m) / LOG2_10);
    BigDecimal t = new BigDecimal(a).divide(new BigDecimal(b),
            new MathContext(percession));
    t = t.multiply(TWO.pow(m));

    BigInteger q = t.toBigInteger();
    BigInteger r = t.subtract(t.setScale(0, RoundingMode.FLOOR))
            .multiply(new BigDecimal(b)).setScale(0, RoundingMode.HALF_UP)
            .toBigInteger();
    return new BigInteger[] { q, r };
}

Answer 1

首先，您可以进行以下明显的优化：

while (b is even) {
    b /= 2;
    m -= 1;
}

在乘法/除法之前。