JDK 8 RFR 4891331: BigInteger a.multiply(a) should use squaring code

[Alan Eliasen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 10/23/2013 06:37 PM, Brian Burkhalter wrote:
> The results suggest that the effect of the equality test (val == 
> this) is insignificant. Significant performance improvement was 
> however observed for squaring of values with int array magnitude 
> length >= 8. The performance gain was up to 150-200% for the
> largest bit length tested (1536). Larger bit lengths were not
> tested as those would enter the current range of Karatsuba
> multiplication (>= 1600 bits).

   These look like good tests and the benefit of using squaring code
and is evident.  It should be noted that going into the Karatsuba and
Toom-Cook range should yield even greater improvements, as there are
special-case algorithms for Karatsuba and Toom-Cook squaring which
further increase the efficiencies.  This should allow users some real
performance increases without making square() public (as I think it
really should be, but I know that means API changes.)

> While not pertinent to this review per se, it should be noted that 
> the performance of pow(2) approaches that of square() as the bit 
> length increases. It might be worth a subsequent investigation to 
> determine whether there is a second threshold beyond which pow(2) 
> overtakes square() altogether.

   As Brian and I have discussed off-list, the improvements I made for
pow() are sensitive to the particular bit-pattern of the number being
exponentiated.  If the number contains powers of 2 as factors (that
is, if the number has trailing zeroes in binary, which is quick to
test) then the pow() function right-shifts the arguments to remove
trailing zeroes and operates on smaller numbers potentially *much*
faster, then left-shifts the result back quickly.  This improvement
made doing things like calculating Mersenne numbers hundreds of
thousands of times faster in JDK 8 than in previous releases.

   That powers-of-two optimization is highly dependent on the bit
pattern of the numbers, though.  It immensely speeds up the cases with
a lot of trailing binary zeroes, but doesn't help much otherwise.
It's not clear if applying this optimization to square() or even
multiply() would be valuable for the most common cases.  (Multiplying
or exponentiating powers of 2 is very common in my experience.  It
should be noted that Karatsuba and Toom-Cook multiplication make
multiplying numbers with lots of trailing zeros quite a bit faster by
their nature.)

   In short, these patches look good and effective, and will make many
cases faster for many users without slowing down existing cases
appreciably, and without users having to change their programs.  The
code impact is minor and easily understandable, and any slowdown is a
small constant-time (because of == check instead of .equals()).  It
just does the right thing automatically.  Thanks, Brian!

   If I could approve this patch, I would.  Officially signing this
message with my cryptographic key to indicate that it's me. :)

- -- 
  Alan Eliasen
  eliasen at mindspring.com
  http://futureboy.us/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)
Comment: See Alan's GPG guide at https://futureboy.us/pgp.html
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iEYEARECAAYFAlJovM8ACgkQ5IGEtbBWdrH7KgCcDRQRiG39o2wTcrlruOfXqs/W
PokAn0oDsgwsB+Z6wxabDBmAlbk30ENu
=BuMk
-----END PGP SIGNATURE-----