RFR: JDK-8323186: A faster algorithm for MutablebigInteger.divWord(long, int) [v3]

[Daniel Jeliński]

On Mon, 22 Jan 2024 18:52:32 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> As you note, that would probably require two divisions. I don't know if the JIT compiler can detect that the arguments are the same and emit just one division instead.
>> I think your code is good enough for the purpose of [Mutable]BigInteger, and better than the current one.
>
> @rgiulietti I've added a method to check the results of tests.

Hi @fabioromano1,
MutableBigInteger.divWord is not a part of the public JDK interface. If you're trying to optimize a method that's publicly available, please add a benchmark for that method. You can find the instructions for running benchmarks [here](https://github.com/openjdk/jdk/blob/master/doc/testing.md#microbenchmarks). You will need to tell configure where it can find JMH, instructions [here](https://github.com/openjdk/jdk/blob/master/doc/testing.md#configuration). If you aren't familiar with JMH, you can find some examples [here](https://github.com/openjdk/jdk/tree/master/test/micro/org/openjdk/bench/java/math).

If you check the context where `divWord` is called, you'll notice that it's only used when the dividend is a negative long. If you dig deeper, you'll also notice that dividend is only negative if the divisor is a negative int. With these constraints on the input arguments, the worst-case approximation error is much lower than what you presented in your earlier comment. The `divWord` method might not be worth optimizing.

If you take another look at the context where `divWord` is called, you'll probably also notice that the surrounding code can be simplified to `Long.divideUnsigned` and `Long.remainderUnsigned`. These methods are usually optimized by the CPU, so this change might actually improve the performance of some BigInteger operations.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/17291#issuecomment-1968511350