Speeding up division and remainder when numerator is a multiple of power of two

Question

I need to perform computation of the form a 2^m / b where a/b is near 1, a and b are near 2^m and m is large (greater than 1000). I need both quotient and the remainder. I can do this in Java with

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

The cost is approximately the cost of dividing a 2m-bit number by an m-bit number.

Is there a way to make this faster?

If possible, I'd like to reduce the cost to approximately the cost of dividing two m-bit numbers.

I don't care if the resulting code is more complex and/or if some external libraries are needed.

I tried the following code out of desperation. The performance, not surprisingly, is dismal.

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

For a start, you can do the following obvious optimization:

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

before multiplication/division.

Answer 2

A bit-twiddling solution could grow out of this observation.

If a is na bits wide and b is nb bits wide then you could begin by dividing a * 2^nb by b. After that the trailing bits are just a repeating pattern. Think about it from your old long-division days - once you have shifted right your divisor far enough you are just bringing down zeros from your dividend.

E.g. a = 53 & b = 42 (both 6 bits wide)

a * 2^6 / b = 110101000000 / 101010 = 1010000

from now on the pattern 110000 repeats every 6 bits:

a * 2^12 / b = 110101000000000000 / 101010 = 1010000110000

a * 2^18 / b = 110101000000000000000000 / 101010 = 1010000110000110000

It remains to discover how to find the repeating pattern but it must repeat because it is derived from only the remainder of a * 2^6 / b because the only contribution that a * 2^m has after that is the bringing down of more zeros.

I suspect the final remainder is also calculable.