Speed up BigInteger gcd with one small argument
gcd() goes out of its way to provide constant running time. This
has unfortunate performance consequences for
x.gcd(BigInteger.valueOf(2)). In such lopsided cases, compute the
remainder of dividing one by the other first, and then use that in
the binary gcd computation.
It is unclear that such a point solution is the best way to address
BigInteger performance issues. But fixing this obvious hole is
probably useful in comparing strategies, even if this CL doesn't
end up sticking.
Added a BigInteger.gcd() test, since presubmit testing missed an
earlier bug.
Bug: 140780742
Test: Treehugger
Change-Id: I9777b84b230497a22d632dff283866bcb5d1dc23
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
2 files changed