-----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 elia...@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-----
