Whats the fastet way in Java to multiply or divide with 1.6-CodePudding

I want to multiply or divide big numbers(BigIntegers) with 1.6.

Currently I use:

Divison:

BigDecimal dez = new BigDecimal("1.6");

BigDecimal bigd = new BigDecimal(big);

return bigd.divide(dez,10000, RoundingMode.FLOOR).toBigInteger();

Multiplication:

BigDecimal dez = new BigDecimal("1.6");

BigDecimal bigd = new BigDecimal(big);

return bigd.multiply(dez).toBigInteger()

Usually my numbers have 1000 <= x <= 10000 Bytes. Caching doesnt help numbers are not repeating.

Exists there a Bithack to do this faster?

CodePudding user response：

For dividing by 1.6, absolutely there's a bit hack. Mathematically, x ÷ 1.6 = x ÷ 2 x ÷ 8

So you can write this as

myBigInteger.shiftRight(1).add(myBigInteger.shiftRight(3))

There is no similar hack for multiplying by 1.6.

You will have to worry about rounding errors, of course, as bits disappear off the right hand end of the number. You'll have to think about what to do with these.

In particular, this expression is "off by one" if the last three bits of the original number are 101 or 111. So a better expression would be

myBigInteger.shiftRight(1).add(myBigInteger.shiftRight(3))   (myBigInteger.testBit(0) && myBigInteger.testBit(2) ? 1 : 0)

CodePudding user response：

Multiplication by 1.6 is equivalent to multiplication by ¹⁶⁄₁₀ or ⁸⁄₅, and division by 1.6 is equivalent to multiplication by ⁵⁄₈ or ¹⁰⁄₁₆

So to multiply you can do like either of this

big.shiftLeft(4).divide(BigInteger.TEN);
big.shiftLeft(3).divide(BigInteger.valueOf(5));

No need to use BigDecimal

Since the division is constant you can even convert it into a multiplication by the inverse although it might not worth it in this case

Similarly division can be done like this

big.multiply(BigInteger.TEN).shiftRight(4);
big.multiply(BigInteger.valueOf(5)).shiftRight(3);

If the value is negative you'll need a small change though because right shift rounds down instead of rounding towards zero

But if you need to do this millions of times then Java is probably the wrong choice. There are many excellent native big integer libraries, just call them using Java NDK. They're fast because they're native, but some can utilize SIMD so they'll significantly faster. For example y-cruncher can use AVX-512 for multiplication. See also Fast Multiple-Precision Integer Division Using Intel AVX-512

If you have multiple independent BigIntegers then you can also do then in parallel using multiple threads