Hi Hans,
Giving some additional context, we'll occasionally get bug reports that
amount to an observation equivalent to the following:
"I have two Big{Foo} variables and in a loop I assign larger and larger
values to them. As the values get large, bigFoo1.add(bigFoo2) runs much
faster than bigFoo1.multiply(bigFoo2). This seems wrong."
With additional knowledge of the algorithmic complexities of add and
multiply for large values, the above is not a surprising result and the
intention of the note is to share some additional context with the
reader so they are not surprised by this result either. Additionally,
the note does describe what the JDK implementation has done for some
time, switching between algorithms based in input size, etc.
The new text in both classes appears under an apiNote, which means the
next text is informative without being normative. Therefore, the JDK is
not obliged to behave in the described way, but is free to do so.
The current BigInteger implementation is not written to be hardened
against timing side-channel measurements.
Thanks,
-Joe
On 10/23/2023 10:19 AM, Hans Boehm wrote:
Since I think this is about asymptotic complexity, which is determined
by behavior on large inputs, is there a reason to talk about switching
to other algorithms on smaller inputs? We certainly don't want to get
into the habit of listing "easy case" optimizations everywhere.
I'm unclear about the extent to which BigInteger is intended to
provide running times that depend only on the size of the inputs, or
whether they can vary with the actual bits in the input. Though hard
to state precisely, this does seem to matter to cryptographers. And it
sometimes seems to matter to others, since guarantees aimed at
cryptographers can slow down other code. Is it worth stating something
more in this area?
On Sat, Oct 21, 2023 at 2:14 AM Alan Bateman <al...@openjdk.org> wrote:
On Sat, 21 Oct 2023 00:56:21 GMT, Joe Darcy <da...@openjdk.org> wrote:
> Add informative notes to BigInteger and BigDecimal about
possible running times, etc.
The wording looks okay to me and I expect it will appear as an API
note in BigInteger.
However, for BigDecimal I suspect the h2 headings (for the next
heading and the existing heading for IEEE 754 Decimal Arithmetic)
means they won't look like they are part of the API note, instead
they will look like new sections after the API note. Do you see
what I mean in the generated javadoc?
-------------
Marked as reviewed by alanb (Reviewer).
PR Review:
https://git.openjdk.org/jdk/pull/16298#pullrequestreview-1691219200
