What's the fastest way in Java to multiply or divide with 1.6?

Question

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

Currently I'm using:

Division:

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 doesn't help numbers are not repeating.

Exists there a bithack to do this faster?

It works nicely but its too slow, creating Bigdezimal, converting back, etc, I need to do this million times with BigInteger its getting slow. — TTho Einthausend, Aug 30 '22 at 20:25
Let me rephrase my question. If you're using BigDecimal instead of Double, it's because you are ok to lose some speed in exchange of precision. So I assume that precision is a must, and if that's the case, then the BigDecimal.divide is already the quickest offer from the JVM to handle that kind of operation. Also, do you observe a real bottleneck or you're just assuming that doing this million times will be too time consuming? — Matteo NNZ, Aug 30 '22 at 20:29
Note that BigDecimal/BigInteger classes are not about "bigness" but about precision. You can handle the same number with the standard double or the BigDecimal, if you choose the second is because you want the operation to be precise and not because the number you're handling is too big — Matteo NNZ, Aug 30 '22 at 20:33
I think Handling Byte 100Byte Integer precise you need BigInteger, double will simply not work.... — TTho Einthausend, Aug 30 '22 at 20:35
For dividing by 1.6, have you tried multiplying your `BigInteger`s by `BigInteger.TEN` then shifting right by `4`? — rgettman, Aug 30 '22 at 20:37
1.6 is ratio 16/10 or 8/5. You don't need to use BigDecimal's here, use: big.multiply(BigInteger.valueOf(8)).divide(BigInteger.valueOf(5)) or big.multiply(BigInteger.valueOf(5)).divide(BigInteger.valueOf(8)) — Maxim Butov, Aug 30 '22 at 20:40
If your numbers are really so huge that they can't fit into a long (2^64!!), then yes you are forced to use BigInteger. But in the odd case this is true (never happened to see numbers that big in real life), then I don't think you have any faster option than what you're doing already. You can surely declare the 1.6 static final instead of creating it each time, but not much more. However my question stands by: do you observe a real performance degradation or you're just guessing it may happen? — Matteo NNZ, Aug 30 '22 at 20:41
`BigInteger` is faster than `BigDecimal`. You state you have the former but you are using the latter in your code. Which is it? — user207421, Aug 31 '22 at 00:27
@user207421 the OP is converting their BigInteger to BigDecimal just to multiply by `BigDecimal(1.6)` then convert back to BigInteger — phuclv, Aug 31 '22 at 03:28

Dawood ibn Kareem · Accepted Answer · 2022-08-31T01:38:28.537

2

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)

edited Aug 31 '22 at 01:38

answered Aug 30 '22 at 23:51

Dawood ibn Kareem

77,785
15
98
110

Just curious, what does this accomplish? Is it demonstrably more performant? – CollinD Aug 30 '22 at 23:58
2

I would expect it to be MUCH more performant than converting everything to `BigDecimal`, doing the division, then converting back. But since OP is doing this a million times, that would be a good question for them to answer, if they try out this solution. I haven't done any kind of performance test on this. – Dawood ibn Kareem Aug 31 '22 at 00:00

phuclv · Answer 2 · 2022-08-31T03:27:59.023

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

What's the fastest way in Java to multiply or divide with 1.6?

2 Answers2