Re: Microsecond support in java.time.Duration/Instant?

[Alan Eliasen]

I'm not sure I want to bring this into the discussion, but there's a proposal 
(pushed largely by Facebook) for a timescale called the "flick" which is 
exactly  1/70560 second.

Quote:

   "This unit of time is the smallest time unit which is LARGER than a 
nanosecond, and can in integer quantities exactly represent a single frame 
duration for 24hz, 25hz, 30hz, 48hz, 50hz, 60hz, 90hz, 100hz, 120hz, and also 
1/1000 divisions of each. This makes it suitable for use via 
std::chrono::duration and std::ratio for doing timing work against the system 
high resolution clock, which is in nanoseconds, but doesn't get slightly out of 
sync when doing common frame rates."

I can see useful properties of this when doing multimedia playback.   They have 
C++ libraries implementing this unit.  I'm not affiliated with this effort in 
any way, but saw it recently.

https://github.com/OculusVR/Flicks/blob/master/README.md

On January 23, 2018 7:54:13 AM MST, Roger Riggs  wrote:
>Hi Kurt,
>
>I created an enhancement request in the Jira and linked the core-libs 
>emails in.
>     https://bugs.openjdk.java.net/browse/JDK-8196003
>
>Thanks for the frequency usage info.  Its hard to guess whether if
>micro 
>APIs were
>available whether they would have been used instead of millis.
>
>Roger
>
>
>On 1/23/2018 12:23 AM, Kurt Alfred Kluever wrote:
>> Thanks for the responses, Stephen + Roger,.
>>
>> As noted, a line definitely has to be drawn somewhere. In case anyone
>
>> is looking for some data, here are current relative usage stats
>inside 
>> of Google for the various APIs, grouped by functionality 
>> (creating/decomposing Instants/Durations):
>>
>>   Instant.ofEpochMilli(long): 67%
>>   Instant.ofEpochSecond(long): 29%
>> *  Instants.ofEpochMicros(long): 4%
>> *
>>
>>   Instant.toEpochMilli(): 83%
>>   Instant.getEpochSecond(): 10%
>> *  Instants.toEpochMicros(Instant): 7%*
>>
>>   Duration.ofSeconds(long): 30%
>> Duration.ofDays(long): 24%
>>   Duration.ofMillis(long): 21%
>> Duration.ofMinutes(long): 18%
>> Duration.ofHours(long): 7%
>>   Duration.ofNanos(long): < 1%
>> *  Durations.ofMicros(long): < 1%*
>>
>>   Duration.toMillis(): 73%
>> Duration.getSeconds(): 16%
>>   Duration.toMinutes(): 3%
>>   Duration.toNanos(): 3%
>> Duration.toDays(): 3%
>> *Durations.toMicros(Duration): 2%*
>> Duration.toHours(): 1%
>>
>> So yea, it's definitely towards the bottom of the usage stats, but 
>> that also might be partially because of the discoverability issue 
>> (people are much more likely to find an instance method directly on 
>> the type than a static method on our Durations class). Anyway, I'm
>not 
>> claiming these numbers motivate any sort of change, but given a 
>> proposal to add microsecond support directly to the APIs, I think I'd
>
>> be in favor :-) Or perhaps Google is unique in it's usage of 
>> microsecond precision (many of our storage systems have timestamps 
>> using microsecond precision).
>>
>> PS - and thanks for the ".NET ticks" reference, I hadn't heard of
>that 
>> before. And maybe here's a new one for you that just popped up in the
>
>> news --- a Flick  (1/70560 of
>
>> a second).
>>
>> On Mon, Jan 22, 2018 at 10:00 AM, Stephen Colebourne 
>> mailto:scolebou...@joda.org>> wrote:
>>
>> On 22 January 2018 at 02:58, Kurt Alfred Kluever > > wrote:
>> > I'm curious how these sets of units were chosen or decided
>upon? I
>> > understand that the line must be drawn somewhere (or else
>> someone may come
>> > along asking for centisecond support), but I'm curious as to
>the
>> rational.
>>
>> Nanos have to be supported as they are the smallest available.
>> Millis are supported as they are the historic form.
>>
>> Micros is only one of the other possible ones - .NET ticks might
>be
>> another. A line has to be drawn somewhere...
>>
>> Stephen
>>
>>
>>
>>
>> -- 
>> kak

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Re: JDK 9 RFR of JDK-8035279: Clean up internal deprecations in BigInteger

[Alan Eliasen]

> On Feb 26, 2014, at 8:55 PM, Brian Burkhalter
>  wrote:
>> If it looks worth doing, I'll file another issue to track the idea.
>> I already have it on my list anyway to follow up on Alan Eliasen's
>> comment in the BigInteger code:
>>
>> * This could be changed to a more complicated caching method using
>> * {@code Future}. */
>> private static BigInteger getRadixConversionCache(int radix, int
exponent) {


On 02/26/2014 02:53 PM, Paul Sandoz wrote:
> Not quite sure what that would entail.
>
> Paul.

   See, for example, p. 108 of "Java Concurrency in Practice," if one of
the guys there has a copy.  ;)

   I started writing a version of that cache using Future but it got
looking a bit hairy.  I submitted the very-simple version I did (which
is not the one that was in the final release) because I thought
anything more complex would hold up review too much.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: JDK 8 RFR 8029514: java/math/BigInteger/BigIntegerTest.java failing since thresholds adjusted in 8022181

[Alan Eliasen]

> On 12/4/2013 1:34 PM, Brian Burkhalter wrote:
>> Hello,
>>
>> Issue:https://bugs.openjdk.java.net/browse/JDK-8029514
>> Webrev:http://cr.openjdk.java.net/~bpb/8029514/webrev/
>>
>> The problem causing this failure is that the method getLower() used by
>> Karatsuba multiplication is expected to return an unsigned value but
>> instead returns 'this' if the parameter 'n' is not greater than the
>> int-length of the BigInteger on which it is invoked. For
>> multiplications in which there is a negative factor this could result
>> in an incorrect product being obtained.
>>
>> The BigIntegerTest is also updated to reflect the modified thresholds
>> (should have been in the patch for 8022181 but was not …).

   Hmmm... it looks like that patch is correct and necessary if
getLower() is receiving negative numbers.  I'm not quite sure what
happened there.  My vague recollection was that at one point the
arguments to Karatsuba multiply were conditioned to always be positive
in the multiply() dispatching function, but that's apparently not the
case in the current code.

   Thanks for letting me know about this.  I didn't see the earlier bug
report or the report that the thresholds were being changed.  It would
seem to me that the new thresholds are quite a bit higher than is
optimal for the architectures I tested on (Linux 64-bit and Windows 32
bit, and a bit of Raspberry Pi Arm); I intentionally set my thresholds
to be quite high and conservative.  Is there a particular architecture
that requires the thresholds to be set that high?  What performance
effect do those higher thresholds have on the most common architectures?

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: 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
  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-

Re: Various Random things (Was: Java 8 RFC 7189139: BigInteger's staticRandom field can be a source of bottlenecks)

[Alan Eliasen]

On 09/04/2013 05:26 PM, Brian Burkhalter wrote:
> I have updated the webrev
> 
> http://cr.openjdk.java.net/~bpb/7189139/
> 
> to add the two-parameter version of isProbablePrime() which was
> discussed. Naturally a CCC request would be needed in the event this
> were to go forward.

   The change to pass in the random number generator appears fine.
There's probably no need for a strong random number generator in this
case, though.  Rabin-Miller is a robust algorithm and the probability of
its failure can be easily made so that it's far more probable that the
computer's hardware fails while running the test.  (I wrote an article
about this if you're interested.)  The particular random numbers that it
chooses are not terribly crucial as long as there's enough margin, and
as long as random numbers aren't repeated pathologically.

   However, the primality tests could be made more efficient and more
certain.  For smallish numbers, the Rabin-Miller test performs a large
number of random tests, with some low probability of failure.

   It's known, however, for numbers less than 341,550,071,728,321, (or
larger, see references below,) that there are minimal sets of bases we
need to test with a Rabin-Miller test to *prove* primality.  (This would
also allow us to eliminate generating random numbers entirely, in these
cases, to perform a much smaller number of Rabin-Miller rounds, and let
us skip the Lucas test entirely as well, and enable a *proof* of
primality for numbers smaller than this.)

   For example, if the number n is less than 4,759,123,141 (this
encompasses all ints) then you only need to test that n is a strong
probable prime to bases 2,7, and 61 to *prove* primality.  This would be
much faster than the code now (which may do 50 rounds, and won't do
*more* than 50 rounds, no matter what certainty you request, which is
almost certainly a bug in the current code.)  It would also be more
correct than the current code, which admits a low probability of failure.

   There are references which show the exact bases to test for smaller
numbers in a Rabin-Miller test to *prove* primality here:

 http://primes.utm.edu/prove/prove2_3.html#quick
 http://priv.ckp.pl/wizykowski/sprp.pdf
 http://math.crg4.com/primes.html
 http://www.gpgpgpu.com/gecco2009/6.pdf

   Further, to *prove* primality of everything that will fit into an
unsigned long (2^64), you only need to test all prime bases <= 37.  See:
 http://oeis.org/A014233

   There could be a fast path to do the tests for smallish numbers in a
long or an int.  You'll want a modPow function.  Here's one for ints:

   /** Compute x^y mod m.  Assumes m >= 2. */
   public static int modPow(int x, int y, int m)
   {
  long acc = 1;
  long z = x % m;
  while (y != 0)
  {
 if ((y & 1) != 0)
acc = (acc * z) % m;
     z = (z * z) % m;
 y >>= 1;
  }
  return (int) acc;
   }

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: [PATCH] 4851444: Exposing sun.reflect.Reflection#getCallerClass as a public API in Java 8

[Alan Eliasen]

On 09/01/2013 09:50 AM, Nick Williams wrote:
> Interesting. I can access HTTPS in all of my browsers. OT, to help my
> figure out what's up with my HTTPS, what browsers and versions are
> y'all using, Jörn and Alan?

   I get the same problems with Firefox 23 on Linux.  This will help you
debug some of your problems:

https://www.ssllabs.com/ssltest/analyze.html?d=java.nicholaswilliams.net

   As you can see, it won't work with most browsers.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: RFR: 7057785 : (xs) Add note to hashCode() that support for self referential is optional

[Alan Eliasen]

On 08/28/2013 04:47 PM, Guy Steele wrote:
>  *ahem* Y'know, Common Lisp had a good solution for
> printing self-referential structures (by a user-extensible print
> function) back in 1984.
> 
> It leaned on the solution that had been provided in Interlisp in
> 1974.  On a machine with one megabyte of main memory and a speed of 1
> MIPS.
> 
> This is not rocket science. 

   Hehe.  So could you please describe the solution?

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: RFR 4641897: Faster string conversion of large integers

[Alan Eliasen]

On 06/25/2013 12:13 PM, Peter Levart wrote:
> else { // resizing
> // increase by factor of 1.5 (like ArrayList)
> int newLength = oldLength + (oldLength >> 1);

   We probably don't ever want to extend any row of this cache any more
than we need to.  The entries in each row of the cache, say for base 10,
are 10^(2^n) which obviously grows super-exponentially with n.  (And the
time to perform each squaring to get successive terms will grow
quadratically or at least subquadratically on top of that, along with
memory usage which squares with each additional term.)  So we should
never resize to more entries in that table than we need, and we should
try to avoid recalculating entries in that table in multiple threads, as
the cost to calculate them can be high.

   As I noted years ago, the caching behavior is certainly going to be
one of the most controversial parts of BigInteger improvements.  :)

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: RFR 4641897: Faster string conversion of large integers

[Alan Eliasen]

On 06/21/2013 06:42 PM, Brian Burkhalter wrote:
> I think
> the main open problem for this patch and the Karatsuba one just
> integrated this week is to determine algorithm crossover thresholds
> which are not going to provoke performance degradations for certain
> intermediate bit lengths on the platforms of interest. Any
> suggestions on this topic would also be appreciated.

   I'll send along some of the simple programs I used to tune the
thresholds for Karatsuba and Toom-Cook multiplication.  I posted these
 As has been stated before, tuning of these thresholds is as much of an
art as it is a science, as results will vary greatly for different bit
patterns.  You have to kind of weight toward the bit patterns that occur
most often in real-world programs (e.g powers of 2 +/-1, factorials, etc.)

   It would be great to have some sort of auto-tuner as part of the
build process, but of course that doesn't work when we're building
binary distributions that just get downloaded by end-users.
Arbitrary-precision math packages like GMP have a bunch of hard-coded
thresholds that are selected when your processor architecture is
detected, but if you want to work harder, you can run their autotune
programs to build headers that work well on your specific computer with
its unique cache sizes, memory speeds, etc.  Of course, you'll sometimes
see very different thresholds found when you run the tuning program
multiple times!  It's easy in C/C++ to do conditional #defines based on
detected processor architecture to get good performance, but I know
that's not the Java way.

   The thresholds I chose for the running program were found to work
well on a variety of Linux/Intel and Windows architectures, all the way
back to an 800 MHz Pentium III.  (Unfortunately, it's impossible to
build JDK 8 on those older systems due to its memory requirements.  One
of my semi-fast AMD-64 Linux systems still takes 21 hours to build JDK 8
due to excessive swap.  It could build JDK 7 much faster.)

I set the thresholds intentionally conservative to work well on all
the architectures I have access to.  The thresholds could have been
moved lower on modern architectures, but with a slight possible impact
to older architectures.  In any case, the performance of the various
algorithms is nearly the same in the crossover regions, so it usually
doesn't matter all that much.

   However, I can see that it's quite possible that JVMs which have very
expensive memory allocation overhead, or where allocation contention is
high, could be impacted more severely, and might have to have their
thresholds adjusted.  It's probably impossible to find a fixed set of
thresholds that perform optimally on all platforms.

   My tuning programs require a fair amount of re-running and changing
of the arguments tested, and keeping track of the thresholds that work
well for all arguments.  Again, more of an art than a science.

   Here's what you have to do:

   1.)  In your JDK code, in BigInteger.java, make KARATSUBA_THRESHOLD
and TOOM_COOK_THRESHOLD "public" instead of "private final".  This
allows the tuning program to tweak them.  (Be sure to change this back
when you're done tuning!)

   2.) Recompile JDK

   3.) Compile BigIntTiming.java

javac BigIntTiming.java

   4.) Run BigIntTiming to see which thresholds are fastest.  Keep track
of these.  Times are in milliseconds.  Smaller numbers are faster.  The
first column is the Karatsuba threshold, second column is the Toom-Cook
threshold.  (Note that these may need to be modified again when we add
Schoenhage-Strassen multiplication.)

java BigIntTiming

   I usually start with multiplications of two (small) large numbers,
say 2^20 * 3^11, and then change the code to work with much
bigger numbers, e.g. 2^200 * 3^100 to exercise larger arguments.
  (That is, repeat steps 3) and 4) many times.)  Larger arguments will
test many smaller powers as the recursive algorithms break down the
multiplications into smaller and smaller numbers.   You will want to
change the bounds of the

   for (int i=1; i<20 ...

loop to adjust to the time spent in various number sizes.  You want
the timings to be significant but not so long as to take forever.


The code for the tuning program is available at:

http://futureboy.us/temp/BigIntTiming.java

   Let me know what sort of thresholds you find to work best on various
architectures.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: RFR 4641897: Faster string conversion of large integers

[Alan Eliasen]

On 06/21/2013 10:23 PM, Dmitry Nadezhin wrote:
> Brian,
> 
> This patch significally enhances performance of string conversion  for
> large numbers.
> 
> I suggest to create also a fast path for power-of-two radices: 2, 4, 8, 16,
> 32 .
> It is a simple linear algorithm that is suitable both for large and small
> numbers.
> Can it be attached to this bug activity ?
> Or should it be filed as another bug ?

   I'd file it as another bug.

   As you'll see if you run profiling tests, and the power-of-two
radices are already *much* faster than the other powers, as would be
expected.  It's possible to do the power-of-two conversions completely
with bit operations in BigInteger and not relying on Long, but the
improvement may be small as these cases are already relatively fast.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: RFR 4641897: Faster string conversion of large integers

[Alan Eliasen]

On 06/21/2013 09:04 AM, Brian Burkhalter wrote:
> 
> On Jun 21, 2013, at 2:49 AM, Alan Bateman wrote:
> 
>> One part that might need attention is getRadixConversionCache as I
>> could imagine cases where the synchronization could lead to
>> contention. Have you (or Alan) considered alternatives that would
>> limit the synchronization to only when the powers cache needs to be
>> expanded?
> 
> I have not but will do so. I cannot speak for Alan E.

   Yes, as noted in the code comments and in my comments on this list,
it would be possible to do something fancier, perhaps using Future.
This code was intended to be as simple and understandable as possible,
to rapidly give an asymptotically much faster algorithm that would have
minimal review impact but significant performance improvement.  Other
design goals were to not duplicate work in the case that two threads
attempted to convert the same large number and calculate the same cache
value at the same time (this used to be a big problem before the pow()
function got much faster.  Some of those cache expansions required
hours, and you didn't want to do them twice.)

   There was also potential room for argument about the need for a cache
at all.  However, it became clear that keeping a cache significantly
improved performance at the cost of holding on to some memory with the
idea that if you print one big number, you're likely going to print
another big number at some time during the life of the VM.

   It was also a goal at one point in the 11-year-history of this bug to
produce code that could be backported to previous Java versions, thus no
use of Future, etc.  That may no longer be necessary.  I don't know
about other Java profiles that might use this code.  I was asked for
small, simple patches that could be reviewed in stages, so that's
somewhat reflected in the simplicity of that code.  The caches are
extended rarely, so although that method may block, it should not block
for too long.  I'm willing to review any rewrites that people might
suggest.  Frankly, when I started looking at rewriting the cache using
Future, the code complexity and data structures got quite unwieldy very
quickly.  Especially when trying to eliminate duplicated effort.

   If profiling shows that this is a bottleneck, we can revise it, but I
didn't see evidence of that.  It was suggested to make some of these
algorithms multi-threaded, but that was soundly rejected on this list
for this phase.  Perhaps in a later phase when the algorithms become
multi-threaded, the cache can be revised.

   The Schoenhage recursive base conversion code is not triggered unless
numbers are already significantly largish, so it won't affect
performance of smaller numbers, but the algorithm's much-improved
efficiency will make it faster for the larger numbers that trigger it.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Final RFR 4837946: Faster multiplication and exponentiation of large integers

[Alan Eliasen]

On 06/18/2013 06:13 PM, Brian Burkhalter wrote:
> This RFR was initially posted last month:
> 
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-May/016999.html
>
>  I hope that this is the final re-post. The issues in question are
> 
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
> 
> and the webrev as before is at
> 
> http://cr.openjdk.java.net/~bpb/4837946/

   Brian,

   Thanks for pushing this improvement.  As I've said before, I'm more
than willing to put my personal e-mail address on this patch to support
the Karatsuba and Toom-Cook and pow() and radix conversion fixes.  I'll
put my reputation on the line.  You're free to let people e-mail me
personally if their multiplications are incorrect.  I want to support
this.  It makes Java, and pure math, implemented in Java, better.

  If there's a problem, yo, I'll solve it.  (Sorry, I channeled Vanilla
Ice there.)

   After all, I've been publishing many of these improvements for 11+
years, and I'm the person whose e-mail address comes up when someone
searches about these issues.  To be frank, I'm personally involved much
more than Sun/Oracle employees whose e-mail addresses are hidden.  I
field a *lot* of questions about making BigInteger and BigDecimal
faster.  I've helped a lot of people for many years integrate these
changes into their JVMs, which isn't easy.  I try hard.  I have many
examples of fundamental problems in BigInteger being broken for 3+ years
while I've fixed them in my own language within the day.  I am willing
to support this and fix it fast.

   I think my optimizations are simple and obvious;  after all, I posted
a list of links to undergraduate classes who are expected to implement
Karatsuba or Toom-Cook multiplication in a day or a week.  I don't want
to present myself as a genius.  I'm no better than a typical
undergraduate.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: 4646474 : BigInteger.pow() algorithm slow in 1.4.0

[Alan Eliasen]

On 05/14/2013 07:11 PM, Brian Burkhalter wrote:
> The test in this issue report
> 
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
> 
> is pretty much useless for comparative purposes after applying
> 4837946 as the computed value is just a power of two which will be
> handled very quickly by the new algorithm.
> 
> As a single alternate data point I modified the test instead to
> compute 17^13466917. The execution time on my MacBookPro5,3 before
> applying the 4837946 patch was 2336.975514 seconds and afterwards
> 79.202646 seconds: an improvement of about a factor of 30. I am sure
> that there are much more extreme examples than this but the result is
> good to see.

   Yes, the extreme examples are ones like in the original bug report,
which are literally millions of times faster.  If the base contains a
power of 2, (which is by far the most common case I see in numeric
algorithms,) then performance can be be so drastically improved that
it's hard to measure the actual ratio.  For example, you've seen the
workarounds in BigDecimal for slow 10^x calculations, which will be
greatly improved by this patch and the toString() changes in the next phase.

   Note that when Schoenhage-Strassen multiplication is included, the
ratio will be even better.  On an eight-core (using just one core) AMD
FX-8350 at 4 GHz, the time for your example of 17^13466917 drops from
1412.522 seconds to 15.233 seconds, an improvement of a factor of about 93.

> I linked this issue to 4837946 as a duplicate so it will be closed
> out at the same time.

   That'll be great to see.  Combined, these two bug reports are old
enough to buy us drinks.  I'm so proud of them.  :)

   Is there any plan to backport these to earlier JVMs?

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: RFR : 8007398 : (S) Performance improvements for Int/Long toString() at Radix 2, 8, 16

[Alan Eliasen]

On 05/15/2013 07:17 PM, Mike Duigou wrote:
> Hello all;
> 
> This issue was originally part of JDK-8006627 (improve performance of
> UUID parsing/formatting) but was split out because it could be split
> out. I've been working incrementally on pieces of 8006627 as my time
> permits.
> 
> http://cr.openjdk.java.net/~mduigou/JDK-8007398/1/webrev/
> 
> Since the last rev I have made a separate implementation
> Integer.formatUnsignedInteger for use by Integer rather than sharing
> the Long implementation because it's about 30% faster. I suspect the
> benefits would be even greater on a 32-bit VM or 32-bit native
> platform.

   Mike,

   Do your changes affect performance for all radices, or for certain
radices as implied in some issue titles?

   It might be beneficial to coordinate with Brian Burkhalter who is
working on integrating my patches to make BigInteger.toString() much
faster.  As you know, BigInteger.toString() partially uses
Long.toString().  Improving the performance of Long.toString() will
improve the performance of BigInteger, which is great.  However, there
is an empirically-found threshold in BigInteger that might benefit from
re-tuning if Long.toString becomes significantly faster, though.  The
threshold is intentionally chosen to be a bit conservative for cases
like this, so re-tuning may not have a huge effect.

   I don't use different thresholds based on the radix, but that's
something to consider in the future if it could improve performance.
Radices that are powers of 2 shouldn't need the recursive improvements
in BigInteger.toString.

   If you let me know if these changes get checked in, I can see if
re-tuning the threshold for BigInteger.toString() can improve
performance even further.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: RFR: 4837946 - Faster multiplication and exponentiation of large integers

[Alan Eliasen]

On 05/14/2013 01:54 PM, Brian Burkhalter wrote:
> This is the first of an eventual four phases of performance
> improvement of BigInteger for large integers.
> 
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946
> 
> Webrev:
> 
> http://cr.openjdk.java.net/~bpb/4837946/
> 
> This contains Alan Eliasen's implementation of Karatsuba and 3-way
> Toom-Cook multiplication and squaring, and pow() accelerated by power
> of two shifting and accelerated exponentiation by squaring.
> 
> I have reviewed this code including verifying all algorithms against
> the references suggested in the code as well as other sources in the
> literature. It all looks to be entirely correct and very clean and
> clear.

   Thanks very much for looking this over, Brian!

   One minor revision to this revision that I must have missed is that
the added import for java.util.ArrayList is not actually used until
Phase 2, which is improving toString().  (ArrayList is used in the cache
for improving toString radix conversion.  I didn't use it anywhere in
multiply() or pow(). )

   More below.

> One change which I have *not* made and which seems appropriate to add
> to this patch is to modify multiply() to use square() if the
> parameter is the BigInteger instance on which the method is invoked,
> i.e., to change this snippet
> 
> public BigInteger multiply(BigInteger val) { if (val.signum == 0 ||
> signum == 0) return ZERO;
> 
> to this
> 
> public BigInteger multiply(BigInteger val) { if (val.signum == 0 ||
> signum == 0) return ZERO;
> 
> if (val == this) return square();

   That seems like a lightweight but acceptable change to me.  I have
discussed this optimization before, and thought it might improve a small
number of cases, but could make the base case of very small non-equal
numbers slightly slower.  I haven't benchmarked it; I'd doubt that the
change would even be detectable in most programs, and if it were
triggered, would somewhat improve the performance of certain programs.

   I was initially concerned that it might create an infinite loop if
any of the square() functions called multiply() to do the dirty work but
none of them seem to at the moment.  The identity comparison is be
reasonably fast and lightweight and constant time.  This optimization
wouldn't catch the case where two identical numbers are passed in but
don't point to the same place in memory.  It would be more general to
call .equals(Object) but that would have more overhead (in the worst
case, it's O(n) where n is the number of ints in the BigInteger.)  I
would probably avoid the latter.

   If you perform .pow(2) it will automatically square the numbers
efficiently and rapidly, but the users won't know that without looking
at the implementation, and there is some slight overhead to using pow()
compared to a public square() method.  In the future, the various
squaring routines could benefit from some of the tricks that pow() uses
(that is, detecting powers of two in the number and handling those via
left-shifts.)  This behavior would probably want to be factored out into
separate private functions, as it would be useful in pow(), square(),
and potentially in division, as I was recently discussing with Tim Buktu.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

On 05/10/2013 03:19 PM, Brian Burkhalter wrote:
> 
> On May 9, 2013, at 5:28 PM, Brian Burkhalter wrote:
> 
>> I just went ahead and filed 8014319 and 8014320 for phases 3 and 4, 
>> respectively. They will show up onhttp://bugs.sun.com/bugdatabase after some 
>> unspecified delay, probably about a day. Verbiage may be updated as needed.
> 
> Indeed these showed up:
> 
> Phase 3: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8014319
> Phase 4: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8014320

   Thanks, Brian!

   Another minor note is that you might want to correct "reminder" to
"remainder" in MutableBigInteger.java .  I can revise the patches if you
want.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

On 05/09/2013 03:02 PM, Brian Burkhalter wrote:
>> First you have:
>>
>>/**
>> * The threshold value for using 3-way Toom-Cook multiplication.
>> * If the number of ints in both mag arrays are greater than this number,
>> * then Toom-Cook multiplication will be used.   This value is found
>> * experimentally to work well.
>> */
>>private static final int TOOM_COOK_THRESHOLD = 75;
>>
>> but then:
>>
>>public BigInteger multiply(BigInteger val) {
>>if (val.signum == 0 || signum == 0)
>>return ZERO;
>>
>>int xlen = mag.length;
>>int ylen = val.mag.length;
>>
>>if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD))
>>{
>>
>>}
>>else
>>if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD))
>>return multiplyKaratsuba(this, val);
>>else
>>   return multiplyToomCook3(this, val);
>>}
>>
>> So, is it *both* numbers or *any* of them great than the constant
>> that the Toom-Cook algotithm will be used?

   You're right that the actual code will use Toom-Cook if 1.) both of
the numbers are greater than the Karatsuba threshold *and* 2.) at least
one of the numbers is greater than the Toom-Cook threshold.  That test
could go either way (with "and" or "or".)  When the sizes of the numbers
are in between Karatsuba and Toom-Cook sizes, both algorithms perform
approximately equally well.  You might choose Karatsuba as it has a
somewhat lower constant factor, but as the efficiency of Toom-Cook
multiplication increased, (say, with my fast exactDivideBy3 routine and
the choice of an optimal Toom-Cook formulation,) it became slightly
advantageous to choose Toom-Cook in this vague situation.  But it varies
with the precise bit patterns of the arguments.

   The thresholds were tuned to take this into account.  I'm not saying
that it always makes an optimal choice, but it's hard to make an optimal
choice without performing potentially expensive tests.

   At one point, I had fiddled with "unbalanced" Toom-Cook
multiplication where the numbers are of different sizes, but the added
code complexity wasn't worth the effort.

   Note that this logic and the description will change again when
Schoenhage-Strassen (SS) multiplication is added back in.  The SS
multiplication routines have a rather complicated stairstep of
thresholds, and describing the thresholds in comments will be difficult.

   If you want to change the comment to something like my first sentence
in the first paragraph, that would be fine.  Alternately, we could
change the logic to match the comment, but that would probably mean that
we should re-tune the thresholds.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

On 05/07/2013 12:53 PM, Brian Burkhalter wrote:
> To recapitulate in one place, I think we agree on the following sequence:
> 
> Phase 1: Faster multiplication and exponentiation of large integers
> * Karatsuba and Toom-Cook multiplication and squaring; revised pow() function.
> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 (update 
> synopsis/description)
> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
> 
> Phase 2: Faster string conversion of large integers
> * Recursive Schoenhage toString() routines.
> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897
> 
> Phase 3: Faster division of large integers
> * Burnickel-Ziegler division routines.
> * Issue to be filed.
> 
> Phase 4: Faster multiplication and division of very large integers
> * Barrett division and Schoenhage-Strassen multiplication.
> * Issue to be filed.

   Okay, I've created a set of patches that implement these 4 phases.
(They're not actually patches, but the entire source file for each
phase, as Brian requested.)

   These are available at:
http://futureboy.us/temp/BigIntegerPatch.zip

   In this zipfile, the file(s) to use for each phase are marked with
the ".phaseX" suffix.  If there is no change in a file for a given
phase, there is no file included for that phase, but you should make
sure that you are still using the BigDecimal and MutableBigInteger
file(s) applied in the previous phases.

   So, to be very clear, the files that make up each phase are:

Phase 1:
   BigInteger.java.phase1
   BigDecimal.java.phase1   (since BigInteger.pow is accelerated, the
workaround in BigDecimal is removed.)

Phase 2:
   BigInteger.java.phase2

Phase 3:
   BigInteger.java.phase3
   MutableBigInteger.java.phase3   (to use Burnikel-Ziegler divide)

Phase 4:
   BigInteger.java.phase4

   For your reference, the final versions of each file are contained
with the ".final" suffix.  These will be identical to previous phases
applied, and you don't have to apply them, but if someone wants to
quickly drop in the best improvements to their own JDK, just use the 3
files with the ".final" suffix.

   Let me know if you have any issues with these.

   Tim and Brian, you might decide amongst yourselves who wants to file
the issues for phases 3 and 4.  I don't know if Brian has any magical
powers to make the issues skip the QA process.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

> On May 4, 2013, at 5:13 AM, Alan Eliasen wrote:
>> If you're feeling overwhelmed by the magnitude of the changes to 
>> BigInteger, I would very strongly suggest that you review it in
>> stages. This e-mail proposes stages for the review of this patch.

On 05/06/2013 02:47 PM, Brian Burkhalter wrote:
> It is indeed rather a lot, especially given that the Barrett plus SS
> code alone accounts for more lines of changes than do all the
> previously proposed changes combined.

   I agree that the complexity and volume of code needed to implement
Barrett division and SS multiplication are significantly larger than
Karatsuba and Toom-Cook.

> My rationale for attempting a larger review was that if these new
> changes were not examined now, then they will likely miss the JDK 8
> train altogether. On the other hand if time were to run out on a
> large review then there would be a risk of nothing getting in.

   Yes, I understand that concern, which is why I think a staged review
makes sense.  I've noted before that the leading researcher in Toom-Cook
multiplication, Marco Bodrato, and his colleagues reviewed my Karatsuba
and Toom-Cook patches, and called them "very clean."  This review was
performed to a level of subtlety that they suggested a slighty different
proven-optimal Toom-Cook formulation that came from their research.
This allowed me to remove one shiftLeft from the routine.  This should
give some confidence and reduce review concerns for Karatsuba and
Toom-Cook multiplication.  (Believe me, I've tried to do everything I
can to simplify the review effort!)

   Since first posting these patches, I have had a large number of Java
users contact *me* and use these routines in their JDK.  I know that
these improvements are in good demand and have been widely tested.  I
have used these in very large computational efforts for years, and
tested them against

>> Today, I finished porting my recursive Schoenhage toString
>> routines that I've been using for years in my programming language
>> "Frink" ( http://futureboy.us/frinkdocs/ ).  They are drastically,
>> stunningly faster than the existing BigInteger.toString
>> algorithms.
> 
> The Schoenhage here is unrelated to SS multiplication?

   As you noted later, yes, the routines were both described by (I
believe) the same Schoenhage, but the algorithm has nothing to do with
the Fourier transforms that make up SS multiplication.  The Schoenhage
base conversion is quite simple; it's a recursive divide-and-conquer
that breaks each number approximately in half and then formats each half
separately, which can be done faster.

>> Step 3) would involve faster division:  The Burnickel-Ziegler and 
>> Barrett division routines that Tim wrote.  They are complicated.
> 
> Based on Tim's subsequent comment ("[…] Barrett, especially because
> it is only useful in combination with Schoenhage-Strassen"), it seems
> that Barrett division should be moved to Step 4.

   Yes, that's a good point.  I agree that Barrett division should be
moved to the same timeframe as SS multiplication.  If it makes it more
likely that we get an improved division routine (in Burnickel-Ziegler)
then it's more likely to give a useful combination of features in Java 1.8.

> If this approach were taken, probably we should file three new issues
> for Burnickel-Ziegler division, Schoenhage-Strassen multiplication,
> and Barrett division, respectively. I can take care of this if it
> sounds reasonable.

   That's fine with me.  There are several bugs involved that you can
close after this:

4228681:  Some BigInteger operations are slow with very large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681

   (this was closed but never fixed.)

4837946: Implement Karatsuba multiplication algorithm in BigInteger
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

4646474: BigInteger.pow() algorithm slow in 1.4.0
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

   This is improved in many ways:

   * Rewrote pow() to use Karatsuba and Toom-Cook multiplication
   * Implemented Karatsuba squaring
   * Immplemented 3-way Toom-Cook squaring
   * Found good threshholds for Karatsuba and Toom-Cook squaring
   * Added an optimization to use left-shifting for multiples of 2 in
the base.  This improved speed by thousands of times for things like
Mersenne numbers, and may be one of the most significant improvements
for practical programs.


4641897: BigInteger.toString() algorithm slow for large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

> Also helpful to the process would be to have (four) staged patches
> available. I could take on this task as well, i.e., derive patches
> from the code provided thus far, but it might be safer if those more
> intimately fam

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

r end-users to write algorithms that performed
notably faster.  If not, a possible (much less optimal) optimization
would be for multiply to detect that its arguments are equal (either
using == which would be fast or .equals or .compareTo which may be much
slower if the numbers are large) and call squaring routines instead of
doing the naive multiply.

   If reviewing time is limited, I might suggest performing the reviews
and integration in a few steps:

   Step 1) would be integrating the simple, high-benefit, low-risk
changes that I made:

   * Karatsuba multiplication
   * 3-way Toom-Cook multiplication
   * Karatsuba squaring
   * Toom-Cook squaring
   * Revised pow() function

   these require the helper functions:
   * getLower(int)  and
   * getUpper(int)  for Karatsuba which do efficient slices of numbers
   * getToomSlice() for Toom-Cook slicing to do efficient slicing of
  numbers.
   * exactDivideBy3:  A function to do divisions by modular
multiplication, which is at least 17 times faster on most architectures.
 Used in Toom-Cook3 multiplication.

   It should be noted that the pow() function performs some arguments
(e.g. when the base is a power of 2) millions or billions of times
faster than current Java and would alone drastically improve the
performance of many programs.

   Step 2) incorporating my toString changes.  It's useless to work with
these very big numbers if you can't output them in reasonable time.  And
right now toString() will be the bottleneck for most programs as it's
approximately O(n^2.0634) in my tests.  With the improved division
routines that Tim Buktu wrote, and my recursive base conversion
algorithms, I can make these perform in O(n^1.3596) or better.  This
means, as a practical matter, that printing the largest known Mersenne
number in base 10 is reduced from 18 hours to 150 seconds.  (I can
provide constants to the asymptotes if desired.)

   The bug for improving toString is:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

   I considered toString() slightly more controversial because to
perform repeated conversions efficiently it is very useful to allocate a
cache of "helper" values of 10^2^n to speed up calculations.  This had
memory usage implications, synchronization implications, and questions
about conversions to different bases (say, to convert to base 5, you
also need a cache of 5^2^n, etc.)  I didn't want this to delay the
acceptance of the simple and noncontroversial multiplication and pow
routines which had no external impact and didn't touch other files like
MutableBigInteger, SignedMutableBigInteger, etc.

   My complete patch contains very much faster, simple Schoenhage
recursive base conversion routines for toString.

   By the way, the synchronization for the new toString() routines could
be rewritten to use Future and other synchronization mechanisms.  In any
case. the current mechanism will almost always be faster.

   While I have been using Tim's Schönhage-Strassen multiplication and
Burnickel-Ziegler division routines in my daily work, and have not
detected failures, I have not written explicit tests for division at
all, and my number of very large integer divisions has been small.  My
multiplication tests were written to test general multiplication, but
also to very strongly test around the regions at which Karatsuba and
Toom-Cook have edge cases.  Since I don't know the Schönhage-Strassen
algorithms, I don't know where they might have particular edge cases, so
I haven't written any specific tests for them.

   Brian, would it be possible to make BigInteger.square() public?  It
would make it possible for end-users to write algorithms that performed
notably faster.  If not, a possible (much less optimal) optimization
would be for multiply() to detect that its arguments are equal (either
using == which would be fast or .equals or .compareTo which may be much
slower if the numbers are large) and call squaring routines instead of
doing the naive multiply.

   Step 3) would involve faster division:  The Burnickel-Ziegler and
Barrett division routines that Tim wrote.  These are important for
making base conversion faster, and making division reasonably fast.
(For many programs, division speed is the limiting factor.  This limits
the performance of BigDecimal too.)  They are complicated.

   Step 4) integrating what I believe are the most tricky
routines:  Schoenhage-Strassen (SS) multiplication.  I respect Tim
Buktu's programming skills, but I also know that SS multiplication is
hard to get right, even for super-geniuses.  The GMP team historically
released versions of SS multiplication that were wrong for a small
subset of arguments.  This stuff is hard.

   My latest best version of all of these routines is located at:

   http://futureboy.us/temp/BigInteger.java

   This passes all of my regression tests for multiply in the Karatsuba
and Toom-Cook regions, and all base conversion test.  It does not test
multiplication in the Schoenhage-Strassen regions, nor does it test
large division.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review: 7032154 - Performance tuning of sun.misc.FloatingDecimal/FormattedFloatingDecimal

[Alan Eliasen]

On 03/06/2013 11:55 AM, Brian Burkhalter wrote:
> The link below has been updated with a few minor changes, notably to
> use constants from {Double,Float}Consts and to include the link to
> the OpenJDK issue report. A formatting issue resulting from an awk
> failure during webrev script execution was also fixed.
> 
> B.
> 
> On Feb 28, 2013, at 1:34 PM, Brian Burkhalter wrote:
> 
>> I forgot that the attachment is not redistributed and that I can
>> now post on cr.openjdk.java.net so here's the webrev:
>> 
>> http://cr.openjdk.java.net/~bpb/7032154/
>> 
>> Begin forwarded message:
>> 
>>> This concerns the issue
>>> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7032154.

   I notice that the solution introduces yet another version of
BigInteger to add to BigInteger, MutableBigInteger,
SignedMutableBigInteger, and whatever other proprietary classes are
lurking.  That should give The Fear to anyone who has to maintain this
code.  The comments for the new class don't contain a justification for
yet another class other than "A really, really simple bigint package
tailored to the needs of floating base conversion."  I'm not quite sure
what that means.  The algorithms are drastically inefficient for large
numbers.

   (To give an order of magnitude estimate, a BigInteger calculation
that takes more than 18 hours (that's 64800 seconds) in JDK 1.7 takes
less than 200 seconds with the BigInteger patches that we've posted.)

   I would posit that all of the work that has been done improving the
algorithms in BigInteger by several orders of magnitude are vastly more
significant than introducing yet another BigInteger class with only
small percentage increases in speed for some small arguments with
another sun-namespace, non-supported class.

   The comments don't even describe the point of methods.  For example,
what does multByPow52 do?  Comments like "hope it fits!" don't exactly
inspire confidence either.

   It should be noted that the multiplication algorithms are O(n^2) and
will certainly be orders of magnitude slower than the new BigInteger
algorithms for large numbers.  (Which are stunningly faster than this
class could ever be.)  This class is unnecessary, and adds huge
maintenance costs, and is demonstrably orders of magnitude slower for
large numbers.  If it contains faster algorithms for some small number
sizes, they should be carefully merged with the pending patches for
BigInteger that have been posted by Timothy Buktu and myself, otherwise
they will just make things much slower, harder to maintain, non-portable
to open projects, and decidedly inferior.  Also, swearing and stuff in
the comments should be filtered out, along with typos like "Chache" etc.

   The algorithms for base conversions that I have developed, along with
the drastically faster multiplication and division and exponentiation
routines that Timothy Buktu and I have developed and posted, will blow
these timings out of the water for perhaps all but small number sizes.
If the new class contains algorithms are more efficient for small number
sizes, that code should be merged into BigInteger, rather than
introducing yet another limited BigInteger class and all of its
liabilities and bugs and maintenance effort.

   MutableBigInteger and SignedMutableBigInteger should probably also be
eliminated.  There is little that they do that couldn't be done
approximately as efficiently in BigInteger for small numbers, and vastly
faster for large numbers.  This would also improve the performance of
BigDecimal by orders of magnitude for large numbers.  (BigDecimal uses
O(n^2) algorithms from MutableBigInteger which makes division of large
numbers very slow.)

   This new class is 1252 lines of new code, compared to, say 400 lines
of well-tested code for my multiplication improvements to BigInteger
which are orders of magnitude faster for large numbers.  Timothy Buktu's
stunning FFT multiplication algorithms (added to the existing BigInteger
class) could add more lines that would turn Java into a best-of-class
language for large integer work.  That work should be done first.

   Summary:  It would be a drastic mistake to add yet another BigInteger
class with demonstrably inefficient algorithms for large numbers.  The
new proprietary and inefficient class sun.misc.FDBigInteger should be
rejected summarily until the BigInteger algorithm improvements have been
accepted.  All reviewers should reject a patch that includes this class.
 After that point, any improvements in the algorithms of FDBigInteger
should be merged into the existing BigInteger class, and tested against
the vastly faster algorithms that would then exist, not against the slow
code in JDK 1.7.  If my code isn't 100 times faster for large numbers,
(not 100 percent, 100 *times*,) I'll eat my head.  (My tests on big
numbers are 330 *times* faster easily.  And that's without Timothy
Buktu's magic FFT routines.)

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

Alan Eliasen wrote:
>> Brian, as you may also not know, I have further patches to 
>> drastically improve the toString behavior of BigInteger using 
>> Schoenhage-Strassen recursive decomposition.  This makes toString
>> orders of magnitude faster for large numbers and will likely
>> improve the performance of some of the stuff you're doing in
>> BigDecimal as well.  I will polish those up and submit them when
>> you've reviewed the multiplication and pow fixes.

On 03/04/2013 05:09 PM, Brian Burkhalter wrote:
> Thanks for the additional information and suggestions. While not
> based on anything substantive about the various additional changes
> you suggest, my initial reaction is first to try to review and
> integrate the patches already in the queue and then deal with these
> other improvements afterwards, preferably using patches against the
> current repository tip. These other ideas should have issues filed
> for them as well.

   There are issues filed about the inefficient algorithms used in
toString and pow:

4641897: BigInteger.toString() algorithm slow for large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

4646474: BigInteger.pow() algorithm slow in 1.4.0
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

   Unfortunately, because of the destruction of all the user-submitted
fixes in bug reports (when are those coming back?) you can't see the
further comments about these.  You have my much faster pow() routines in
Tim Buktu's combined patch for BigInteger, I believe, and you should be
able to close the latter bug if you merge that entire patch.  My way
faster toString patch is not included in that combined patch.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

On 03/04/2013 03:37 PM, Dr Heinz M. Kabutz wrote:
> Whilst we're at it, could we also add an option, perhaps via
> environment variable, to parallelize Karatsuba and other calculations?
> 
> Here's an article I wrote about the inefficiencies of BigInteger and
> working out large numbers:
> 
> http://www.javaspecialists.eu/archive/Issue201.html

   That's an interesting article, thanks.

   When I first made the patches for faster multiplication, I was asked
to generate small, simple patches so that they would be reviewed more
rapidly.  I didn't make any attempt to use multiple threads, although
these recursive divide-and-conquer algorithms would seem to be good
candidates for such algorithms

   Brian, as you may also not know, I have further patches to
drastically improve the toString behavior of BigInteger using
Schoenhage-Strassen recursive decomposition.  This makes toString orders
of magnitude faster for large numbers and will likely improve the
performance of some of the stuff you're doing in BigDecimal as well.  I
will polish those up and submit them when you've reviewed the
multiplication and pow fixes.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

On 03/04/2013 11:04 AM, Brian Burkhalter wrote:
> Probably a good idea.
> 
> But seriously this patch is #5 in my queue. We do intend to get to it
> this spring.
> 
> Brian
> 
> On Mar 2, 2013, at 4:41 AM, Tim Buktu wrote:
> 
>> It's been over a year since my original patch, and it's been over 3
>> years since Alan posted his patch. I think I'll stop holding my
>> breath.

   That's good to hear.  By the way, in case you didn't know the history
of this bugfix, the leading researcher in the world in Toom-Cook and
other techniques for high-performance multiplication, Marco Bodrato, and
his colleagues, reviewed my parts of the patch (Karatsuba and Toom-Cook
multiplication, Karatsuba and Toom-Cook squaring) and said they were
"very clean."  I also ran hundreds of gigabytes of test cases through it
(repeatedly,) taking many days, and cross-checked my multiplication
routines against several other packages including GMP and previous
versions of BigInteger.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Are the faster versions of HashMap and BigInteger going into jdk7?

[Alan Eliasen]

On 10/27/2009 01:12 AM, Alan Eliasen wrote:
> On 10/23/2009 11:01 AM, Andrew John Hughes wrote:
>> 6622432 is the one of the ones I just pointed to i.e. it's in JDK7.
>> If Alan has a further patch and hasn't even submitted it for
>> inclusion, it's obviously not in.
> 
>I had just queried Joe Darcy at Sun about reviewing my patches for
> Karatsuba and Toom-Cook multiplication in BigInteger again last week.
> His reply was:
> 
>"Yes, I apologize again for the repeated delays; I want to get your
> Karatsuba work reviewed and integrated within this JDK 7 milestone (the
> next few weeks)."

  How's this going?  (2 years later.)

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: How can I get all emails from this mailing list

[Alan Eliasen]

On 03/02/2011 01:46 AM, David Holmes wrote:
> You can try something like this on google:
> 
> site:mail.openjdk.java.net core-libs-dev AsynchronousDatagramChannel
> 
> there are probably better ways.

   That won't work because the pages are marked



   so nobody will be able to do a web search for any content here.  I
reported this months ago.  It's a pretty big issue for all of these
forums because you can't search for existing solutions, discussions, etc.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Mercurial repositories no longer work?

[Alan Eliasen]

On 11/09/2010 03:13 AM, Alan Bateman wrote:
> The web-discuss mailing list is the place for infrastructure discussion.
> As it happens, someone started a discussion about this issue just a few
> days ago:
>  
> http://mail.openjdk.java.net/pipermail/web-discuss/2010-November/000139.html

   Since this is an issue that affects every single OpenJDK contributor,
that may or may not be subscribed to every list, (I doubt most of us
are,) it is critical that information about accessing the central
repository (which is now effectively broken to anyone that uses current
versions of Mercurial, especially because the Forest extension is no
longer maintained) is pushed to contributors, and the solutions to that
problem get actively published to every list, and are published to the
official pages that explain how to check out and update OpenJDK as soon
as possible, which they haven't been.  (This is critical for an
open-source project.)

   Is there a contact at Oracle that is responsible for making the
OpenJDK open and accessible?  Who is the maintainer of the pages that
discuss how to check out and update OpenJDK?  Those pages are obsolete
and broken.  Mercurial's forest extension is apparently obsolete and
officially unmaintained.  What is the strategy to move OpenJDK forward?

   I'm not subscribed to the web-discuss list, and its archive pages are
marked as "nofollow" for web robots, so nobody will find it with a web
search.  You are asking that web robots do not follow links to any
messages in the archive.  I searched but couldn't find it for this
reason.  The thread posted above is not a solution; the only reply is a
dreadful hardcoded large program that kludges around the real problem
and will break again in the future if any subdirectory is added.  It
does not fix the problem that the official instructions to check out and
update OpenJDK sources no longer work, and that the official way to
check out (the unsupported Forest extension) is no longer usable.

   This is a major issue that must be addressed on all lists.  I hope
that paid Oracle employees will communicate the necessary fix to all
contributors on all lists, who try to contribute value to their products
for free.  Please forward this to the web-discuss list.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Mercurial repositories no longer work?

[Alan Eliasen]

   When attempting to update my working copy of JDK 1.7, I attempted to
perform a "hg fpull" and got the error:

   TypeError: transaction() takes exactly 2 arguments (1 given)

   A little research indicates a few things:

   * The mercurial "forest" extension is no longer maintained.
   * It is incompatible with Mercurial 1.6.
   * Forest maintainers suggest you switch to subrepos.
   * No updated version of the "forest" extension exists.
   * OpenJDK documents contain no information about this issue and point
to outdated, broken extensions:
 http://openjdk.java.net/guide/repositories.html
   * This giant repository was built on an untested, unmaintained
experimental third-party extension.
   * It appears to be impossible for developers to update their
repositories with the information given.

   So how does one update a working repository?  And what is being done
about the problem?  This would appear to have major implications for the
viability of the OpenJDK project.

-- 
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Math project or subproject

[Alan Eliasen]

On 01/29/2010 02:02 AM, Dmitry Nadezhin wrote:

In my previous post I discussed choice criteria for performance
enhancements in math libraries.

I guess that in production projects Jdk 1.6 and Jdk 1.7 the main choice
criteria is stability.
This explains why changes to math stuff in Java are almost impossible.
Here is a pair of examples:
1) The Karatsuba multiplication in BigInteger
http://mail.openjdk.java.net/pipermail/core-libs-dev/2008-January/000225.html


   I'm the submitter of these patches which are almost two years old in 
a couple of weeks, with still no approval.  And these multiplication 
patches are only a small part of the work that needs to be done on 
BigInteger.  I also have orders-of-magnitude improvements for pow() and 
toString(), both of which use extremely slow algorithms.  I was asked to 
make patches as small as possible so they could be reviewed quickly, so 
my submitted patches have just been for multiplication.


   Joe Darcy, what is your current status on reviewing these patches? 
Can you delegate this to Dmitry or Xiaobin if you don't appear to have 
time to do it?



I respect our "Java Floating-Point Czar" for keeping stability of
mainstream Java.
However, I suspect that some OpenJdk users prefer enhancements and bug
fixes of old bugs in math libraries in exchange for a small risk of

> new bugs.

   I think OpenJDK *contributors* need some evidence that their 
contributions are being looked at, or they'll stop contributing, and/or 
move to other platforms with better numerics.  Some of us have spent 
literally weeks of unpaid work improving performance, getting 
world-class outside reviewers to look over them and reduce Sun's 
workload, etc.  It's very depressing to wait over two years for approval 
of a well-known algorithm that is usually assigned as a homework 
assignment in undergrad courses.



What about more rapid enhancement of OpenJdk math in some project
related to but separate from OpenJDK 6 and (Open) JDK 7 ?
This may be a new Math project or a subproject of the Da Vinci Machine
Project.


   I'm all for improving Java's numerics.  Please keep me informed. 
I've already implemented a lot of missing algorithms.


--
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

Re: Are the faster versions of HashMap and BigInteger going into jdk7?

[Alan Eliasen]

On 10/23/2009 11:01 AM, Andrew John Hughes wrote:

6622432 is the one of the ones I just pointed to i.e. it's in JDK7.
If Alan has a further patch and hasn't even submitted it for
inclusion, it's obviously not in.


   I had just queried Joe Darcy at Sun about reviewing my patches for 
Karatsuba and Toom-Cook multiplication in BigInteger again last week. 
His reply was:


   "Yes, I apologize again for the repeated delays; I want to get your 
Karatsuba work reviewed and integrated within this JDK 7 milestone (the 
next few weeks)."


So I'm hopeful.  So far, I haven't heard of any substantive issues 
with the patches.  They were mostly stylistic.


As I've stated before, I also have patches that greatly improve the 
performance of pow() and toString() (by orders of magnitude) that I have 
been holding on to for a long time, and hoping to submit after the 
multiplication patches are approved.  (I was asked by Joe Darcy to 
submit in smaller patches.)  Hopefully these might get in JDK 7 too.


--
  Alan Eliasen
  elia...@mindspring.com
  http://futureboy.us/

[UPDATED PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

 Attached is an UPDATED patch for bug 4837946, (and others) for
implementing asymptotically faster algorithms for multiplication of
large numbers in the BigInteger class (which also improves the
performance of large numbers BigDecimal, etc.)

   This patch slightly modifies the patch I sent before, primarily by
removing an unused method that I let slip through when editing the patch
file.  It also adds comments and links to further information about the
algorithms, and in one place renames a variable in one of my functions
for pedagogical correctness.  It also slightly changes a signum test to
follow the new convention set elsewhere by Xiaobin Lu, which will be
slightly more efficient.

   This patch supersedes any others.  As always, if you just want to
drop in my whole BigInteger class with other proposed fixes for pow(),
it's available at:

http://futureboy.us/temp/BigInteger.java

   I'd also like to put out a call for volunteers to help Sun review
this patch and get it into JDK 1.7.  The Karatsuba and Toom-Cook
multiplication algorithms are well-understood and straightforward, and
have been written in as simple and direct way as possible, building on
existing methods in Java.  If you are able to review this patch, please
contact me.  Thanks!  From all the e-mails I get, I know this is very
important to a lot of people.


Alan Eliasen wrote:
>   Attached is an UPDATED patch for bug 4837946, (and others) for
> implementing asymptotically faster algorithms for multiplication of
> large numbers in the BigInteger class:
> 
>  http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946
> 
>This also affects other bugs:
> 
> 4228681:  Some BigInteger operations are slow with very large numbers
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681
> 
>(This was closed but never fixed.)
> 
> 
> 4837946: Implement Karatsuba multiplication algorithm in BigInteger
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946
> 
> This is done, along with Toom-Cook multiplication.  My
> implementation is intended to be easy to read, understand, and check.
> It significantly improves multiplication performance for large numbers.
> This bug will be able to be closed with this patch.
> 
>This patch now also implements 3-way Toom-Cook multiplication and
> 3-way Toom-Cook squaring in addition to the Karatsuba squaring.  3-way
> Toom-Cook multiplication has an asymptotic efficiency of O(n^1.465),
> compared to O(n^1.585) for Karatsuba and O(n^2) for the "grade-school"
> algorithm, making it significantly faster for very large numbers.
> 
> 
>This patch is almost identical to the ones posted earlier, but I've
> merged Xiaobin Lu's recent changes to BigInteger with my code.  The
> other change was removing an unnecessary carry check from the
> exactDivideBy3 routine.
> 
>I have again run tuning tests with Xiaobin's changes (no changes were
> made to the thresholds as a result; the previous combinations worked
> well.)
> 
>This has been extensively tested.  My regression tests are probably
> significant overkill for Sun's purposes.  They take about 30 hours to
> run and produce about 232 gigabytes of output.  (Multiply each of those
> numbers by 2 because you have to run it twice to compare the outputs of
> different VMs, and then compare output.)
> 
>This patch contains only multiplication- and squaring-related
> patches.  I will be submitting another patch of my changes to make the
> pow() function very much faster, but that will be a separate patch.  Sun
> has requested patches as small as possible.
> 
>I will also have patches for pow() (see
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474 ) and for
> toString ( http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897 )
> once these are approved and I'm informed that I'm working in the right
> direction.
> 
>This patch now also implements 3-way Toom-Cook multiplication and
> 3-way Toom-Cook squaring in addition to the Karatsuba squaring.  3-way
> Toom-Cook multiplication has an asymptotic efficiency of O(n^1.465),
> compared to O(n^1.585) for Karatsuba and O(n^2) for the "grade-school"
> algorithm, making it significantly faster for very large numbers.
> 
> 
>For those who'd rather just replace their BigInteger with my much
> faster version, that also contains my patches for pow(), it's available at:
> 
> http://futureboy.us/temp/BigInteger.java
> 
>These patches are designed to be as easy to read as possible, and are
> implemented in terms of already-existing methods in BigInteger.  Some
> more performance might be squeezed out of them by doing more low-level
> bit-fiddling, but I wanted to get a working ver

[UPDATED PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

   Attached is an UPDATED patch for bug 4837946, (and others) for
implementing asymptotically faster algorithms for multiplication of
large numbers in the BigInteger class:

 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

   This also affects other bugs:

4228681:  Some BigInteger operations are slow with very large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681

   (This was closed but never fixed.)


4837946: Implement Karatsuba multiplication algorithm in BigInteger
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

This is done, along with Toom-Cook multiplication.  My
implementation is intended to be easy to read, understand, and check.
It significantly improves multiplication performance for large numbers.
This bug will be able to be closed with this patch.

   This patch now also implements 3-way Toom-Cook multiplication and
3-way Toom-Cook squaring in addition to the Karatsuba squaring.  3-way
Toom-Cook multiplication has an asymptotic efficiency of O(n^1.465),
compared to O(n^1.585) for Karatsuba and O(n^2) for the "grade-school"
algorithm, making it significantly faster for very large numbers.


   This patch is almost identical to the ones posted earlier, but I've
merged Xiaobin Lu's recent changes to BigInteger with my code.  The
other change was removing an unnecessary carry check from the
exactDivideBy3 routine.

   I have again run tuning tests with Xiaobin's changes (no changes were
made to the thresholds as a result; the previous combinations worked
well.)

   This has been extensively tested.  My regression tests are probably
significant overkill for Sun's purposes.  They take about 30 hours to
run and produce about 232 gigabytes of output.  (Multiply each of those
numbers by 2 because you have to run it twice to compare the outputs of
different VMs, and then compare output.)

   This patch contains only multiplication- and squaring-related
patches.  I will be submitting another patch of my changes to make the
pow() function very much faster, but that will be a separate patch.  Sun
has requested patches as small as possible.

   I will also have patches for pow() (see
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474 ) and for
toString ( http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897 )
once these are approved and I'm informed that I'm working in the right
direction.

   This patch now also implements 3-way Toom-Cook multiplication and
3-way Toom-Cook squaring in addition to the Karatsuba squaring.  3-way
Toom-Cook multiplication has an asymptotic efficiency of O(n^1.465),
compared to O(n^1.585) for Karatsuba and O(n^2) for the "grade-school"
algorithm, making it significantly faster for very large numbers.


   For those who'd rather just replace their BigInteger with my much
faster version, that also contains my patches for pow(), it's available at:

http://futureboy.us/temp/BigInteger.java

   These patches are designed to be as easy to read as possible, and are
implemented in terms of already-existing methods in BigInteger.  Some
more performance might be squeezed out of them by doing more low-level
bit-fiddling, but I wanted to get a working version in and tested.

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  elia...@mindspring.com|for understanding."
  http://futureboy.us/  |   --H.H. Williams
diff --git a/src/share/classes/java/math/BigInteger.java 
b/src/share/classes/java/math/BigInteger.java
--- a/src/share/classes/java/math/BigInteger.java
+++ b/src/share/classes/java/math/BigInteger.java
@@ -93,6 +93,7 @@
  * @see BigDecimal
  * @author  Josh Bloch
  * @author  Michael McCloskey
+ * @author  Alan Eliasen
  * @since JDK1.1
  */
 
@@ -173,6 +174,38 @@
  */
 final static long LONG_MASK = 0xL;
 
+/** 
+ * The threshold value for using Karatsuba multiplication.  If the number
+ * of ints in both mag arrays are greater than this number, then
+ * Karatsuba multiplication will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_THRESHOLD = 50;
+
+/** 
+ * The threshold value for using 3-way Toom-Cook multiplication.  
+ * If the number of ints in both mag arrays are greater than this number,
+ * then Toom-Cook multiplication will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int TOOM_COOK_THRESHOLD = 75;
+
+/** 
+ * The threshold value for using Karatsuba squaring.  If the number
+ * of ints in the number are larger than this value,
+ * Karatsuba squaring will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_SQUARE_THRESHOLD = 90;
+
+/** 
+ * The threshold value for using Toom-Cook squaring.  If the number
+ * of ints in the numb

Re: Further BigInteger performance improvements

[Alan Eliasen]

Alan Eliasen wrote:
>Note that my optimizations for the pow() function give vastly better
> performance at even small bit sizes for many operands, as they factor
> out powers of 2 in the exponent and perform these very rapidly as
> bit-shifts.

   Oops.  I mean powers of 2 in the *base*, of course.  The
exponentiation of these can be done extremely rapidly as left-shifts,
and the remaining portion of the number can be exponentiated more
rapidly because it's smaller.

   Otherwise, exponentiation is done by repeated squaring as before, but
with much better algorithms that take advantage of new implementations
of Karatsuba and Toom-Cook squaring for larger operands.

--
   Alan Eliasen
   elia...@mindspring.com
   http://futureboy.us/

Re: Further BigInteger performance improvements

[Alan Eliasen]

ovements to multiplication,
but I may run yet another set of exhaustive tuning tests to see if the
thresholds can be again improved after my massive regression test
finishes, hopefully in the next 24 hours.

   Note that my optimizations for the pow() function give vastly better
performance at even small bit sizes for many operands, as they factor
out powers of 2 in the exponent and perform these very rapidly as
bit-shifts.

--
   Alan Eliasen
   elia...@mindspring.com
   http://futureboy.us/

Further BigInteger performance improvements

[Alan Eliasen]

it separately, if I can get Sun to review the multiply and pow
patches first.

   My patches are designed to be as readable and simple as possible.
They all build on existing functions, and eschew lots of low-level
bit-fiddling, as those types of changes are harder to understand and
debug.  I think it's best to get working algorithms with better
asymptotic efficiency, as those will vastly improve performance
for large numbers, and tune them by doing more low-level bit fiddling
later if necessary.  Even without being tuned to the nth degree, the new
algorithms are vastly faster for large numbers, and identical for small
numbers.

   I've been asked by Sun to submit my patches in small chunks, so I
plan to submit just the multiplication and squaring patch, and leave the
patches for pow() for later unless I hear otherwise.  I'd rather they
had it *all* and got it tested and integrated as soon as possible, after
all this waiting, and the work it takes to separate out working code to
make a smaller patch.

   I will be submitting a patch in the next day or two.  I'm running my
*huge* regression tests which produce about 250 GB of output and take at
least a day to run.  (And you have to run it twice against a known good
platform to have something to compare to... luckily I've done that.)

   For those who'd just like to replace their file with my improved
version (includes Xiaobin's patches), it's available at:
http://futureboy.us/temp/BigInteger.java

   From the queries I get, this is important to a lot of people.  The
performance of BigInteger can be improved by tens or hundreds or
thousands of times (or even more in the case of certain arguments of
pow()), and should be done to make Java a more viable platform for numerics.

   This work has been in Sun's hands for a long time, and really needs
to get into 1.7.

--
   Alan Eliasen
   elia...@mindspring.com
   http://futureboy.us/

[UPDATED PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

   Attached is an UPDATED patch for bug 4837946, for implementing
asymptotically
faster algorithms for multiplication of large numbers in the BigInteger
class:

   http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

   This patch supersedes all previous patches, and contains all of their
changes.  The difference between this patch and the one posted
previously are small, and consist of the following:

   * Changed a line in getToomSlice() to fix a problem that will affect
the future work I'm doing on the pow() function (which I have not yet
released.)

   * Changed threshhold constants from public to private final.  These
had been made public for tuning of threshholds, and they were
accidentally left as public in the last patch.

   For those who'd rather just replace their BigInteger with my much
faster version, that also contains my patches for pow(), it's available at:

 http://futureboy.us/temp/BigInteger.java

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams
diff --git a/src/share/classes/java/math/BigInteger.java 
b/src/share/classes/java/math/BigInteger.java
--- a/src/share/classes/java/math/BigInteger.java
+++ b/src/share/classes/java/math/BigInteger.java
@@ -172,6 +172,38 @@ public class BigInteger extends Number i
  */
 private final static long LONG_MASK = 0xL;
 
+/** 
+ * The threshold value for using Karatsuba multiplication.  If the number
+ * of ints in both mag arrays are greater than this number, then
+ * Karatsuba multiplication will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_THRESHOLD = 45;
+
+/** 
+ * The threshold value for using 3-way Toom-Cook multiplication.  
+ * If the number of ints in both mag arrays are greater than this number,
+ * then Toom-Cook multiplication will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int TOOM_COOK_THRESHOLD = 85;
+
+/** 
+ * The threshold value for using Karatsuba squaring.  If the number
+ * of ints in the number are larger than this value,
+ * Karatsuba squaring will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_SQUARE_THRESHOLD = 100;
+
+/** 
+ * The threshold value for using Toom-Cook squaring.  If the number
+ * of ints in the number are larger than this value,
+ * Karatsuba squaring will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int TOOM_COOK_SQUARE_THRESHOLD = 190;
+
 //Constructors
 
 /**
@@ -530,7 +562,8 @@ public class BigInteger extends Number i
 if (bitLength < 2)
 throw new ArithmeticException("bitLength < 2");
 // The cutoff of 95 was chosen empirically for best performance
-prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
+prime = (bitLength < SMALL_PRIME_THRESHOLD 
+? smallPrime(bitLength, certainty, rnd)
 : largePrime(bitLength, certainty, rnd));
 signum = 1;
 mag = prime.mag;
@@ -1043,6 +1076,16 @@ public class BigInteger extends Number i
 private static final BigInteger TWO = valueOf(2);
 
 /**
+ * The BigInteger constant -1.  (Not exported.)
+ */
+private static final BigInteger NEGATIVE_ONE = valueOf(-1);
+
+/**
+ * The BigInteger constant 3.  (Not exported.)
+ */
+private static final BigInteger THREE = valueOf(3);
+
+/**
  * The BigInteger constant ten.
  *
  * @since   1.5
@@ -1188,10 +1234,21 @@ public class BigInteger extends Number i
 if (val.signum == 0 || signum == 0)
 return ZERO;
 
-int[] result = multiplyToLen(mag, mag.length,
- val.mag, val.mag.length, null);
-result = trustedStripLeadingZeroInts(result);
-return new BigInteger(result, signum*val.signum);
+   int xlen = mag.length;
+   int ylen = val.mag.length;
+
+   if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD))
+   {
+   int[] result = multiplyToLen(mag, xlen,
+val.mag, ylen, null);
+   result = trustedStripLeadingZeroInts(result);
+   return new BigInteger(result, signum*val.signum);
+   }
+   else
+   if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD))
+   return multiplyKaratsuba(this, val);
+   else
+   return multiplyToomCook3(this, val);
 }
 
 /**
@@ -1229,6 +1286,242 @@ public class BigInteger extends Number i
 }
 
 /**
+ * Multiplies two BigIntegers using the Kara

[UPDATED PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

   Attached is an UPDATED patch for bug 4837946, for implementing
asymptotically
faster algorithms for multiplication of large numbers in the BigInteger
class:

 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

   The difference between this patch and the one posted earlier are:

   * This patch now also implements 3-way Toom-Cook multiplication and
3-way Toom-Cook squaring in addition to the Karatsuba squaring.  3-way
Toom-Cook multiplication has an asymptotic efficiency of O(n^1.465),
compared to O(n^1.585) for Karatsuba and O(n^2) for the "grade-school"
algorithm, making it significantly faster for very large numbers.

   * Thresholds for various multiplications were slightly modified for
better performance.  The lower limit for Karatsuba multiplication is now
45 ints (1440 bits), and the lower limit for 3-way Toom-Cook
multiplication is now 85 ints (2720 bits).

   * Threshholds for squaring were changed.  Karatsuba squaring is used
at 100 ints (3200 bits) and 3-way Toom-Cook squaring is at 190 ints
(6080 bits.)

   This has been extensively tested.  My regression tests are probably
significant overkill for Sun's purposes.  They take about 30 hours to
run and produce about 232 gigabytes of output.  (Multiply each of those
numbers by 2 because you have to run it twice to compare the outputs of
different VMs, and then compare output.)

   Again, my question is:  how much time and space is acceptable for
regression tests?  I posed this before, but didn't get an answer.

   This patch contains only multiplication- and squaring-related
patches.  I will be submitting another patch of my changes to make the
pow() function very much faster, but that will be a separate patch.

   For those who'd rather just replace their BigInteger with my much
faster version, that also contains my patches for pow(), it's available at:

http://futureboy.us/temp/BigInteger.java

   Note that my version of pow() will probably change somewhat before
submission, but this current version works perfectly and is faster for
most arguments.  It's gotten slightly slower for some mid-size
arguments, which is what I will be fixing.

   Previous patch report follows:

>This patch implements Karatsuba multiplication and Karatsuba squaring
> for numbers above a certain size (found by experimentation).  These
> patches are designed to be as easy to read as possible, and are
> implemented in terms of already-existing methods in BigInteger.  Some
> more performance might be squeezed out of them by doing more low-level
> bit-fiddling, but I wanted to get a working version in and tested.
> 
>This is quite a bit faster for large arguments.  The crossover point
> between the "grade-school" algorithm and the Karatsuba algorithm for
> multiplication is set at 35 "ints" or about 1120 bits, which was found
> to give the best crossover in timing tests, so you won't see improvement
> below that.  Above that, it's asymptotically faster. (O(n^1.585),
> compared to O(n^2)) for the grade-school algorithm.  Double the number
> of digits, and the "grade school" algorithm takes about 4 times as long,
> Karatsuba takes about 3 times as long.  It's vastly superior for very
> large arguments.
> 
>I'd also like to create another RFE for implementing even faster
> multiplication algorithms for yet larger numbers, such as Toom-Cook.
> 
>Previously, I had indicated that I'd submit faster algorithms for
> pow() at the same time, but the number of optimizations for pow() has
> grown rather large, and I plan on working on it a bit more and
> submitting it separately.  Many/most combinations of operands for pow()
> are now vastly faster (some hundreds of thousands of times,) but I'd
> like to make it faster (or, at the least, the same performance for all
> arguments, a few of which have gotten slightly slower.)  Unfortunately,
> these optimizations add to the size and complexity of that patch, which
> is why I'm submitting it separately.
> 
>I have created regression tests that may or may not be what you want;
> they simply multiply a very large bunch of numbers together and output
> their results to a very large file, which you then "diff" against known
> correct values.  (My tests produce 345 MB of output per run!)  I
> validated the results by comparing them to the output of both JDK 1.6
> and the Kaffe JVM, which was compiled to use the well-known and
> widely-tested GMP libraries for its BigInteger work.  All tests pass.  I
> haven't submitted these tests, but am awaiting getting a copy of the
> existing regression tests that Joseph Darcy discussed on this list.
> 
>Please let me know if there's a problem with the patch.  I had to
> hand-edit a few lines to remove the work I'm doing

Further BigInteger performance improvements

[Alan Eliasen]

   A few weeks ago, I posted some performance numbers for the
improvements I'm making to the BigInteger class.  Those performance
numbers were for the Karatsuba multiplication algorithm that I
implemented.  I've now implemented 3-way Toom-Cook multiplication (and
Toom-Cook squaring) which has better asymptotic performance than
Karatsuba multiplication.  (Karatsuba is O(n^1.585), 3-way Toom Cook is
O(n^1.465).  Compare this to Java 1.6 which used only O(n^2)
algorithms.)  One of the three algorithms are then chosen according to
the size of the numbers.

   There's also a lot of room for doing asymmetrical Toom-Cook
multiplication, with, say, one side being broken into 4 parts, and the
other into 2 parts, but that's lower on my priority list.

   Since I haven't heard of any progress on including my previous patch,
I'll be submitting a revised patch with Toom-Cook multiplication
included soon.  Below, interspersed among my previous statements, are
some updated performance numbers with the Toom-Cook algorithm:

Alan Eliasen wrote:
>But some numbers.  For multiplying the numbers 3^100 * 3^101,
> (with my fixes to do the exponentiation hundreds of thousands of times
> faster factored out; without these, JDK 1.6 would be thousands of times
> slower,) the times for 20 iterations are:
> 
>JDK 1.6OpenJDK1.7 with my patches  Kaffe w/GMP
>292987 ms  28650 ms866 ms

With Toom/Cook: 18054 ms
Performance improvement over Java 1.6:  16.2x

>For multiplying numbers 3^1400 * 3^1401, the time for 1
> iteration is:
> 
>JDK 1.6OpenJDK1.7 with my patches  Kaffe w/GMP
>3499115 ms 89505 ms910 ms

With Toom/Cook: 43636 ms

Performance improvement over Java 1.6:  80.18x

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams

Regression tests for BigInteger

[Alan Eliasen]

   Attached is the code for regression test for multiply() and pow() in
BigInteger.  It produces a lot of text (approximately 345 MB) to
standard output.  You will need to save this output and diff it against
known good results.  I have provided a file of known good results tested
against a variety of platforms, including the Kaffe JVM using the GMP
libraries for BigInteger.

   It tests a lot of different size arguments, including arguments
around many powers of 2, which are the places that one would expect
problems to occur.

   The known good results are available at:
   http://futureboy.us/temp/BigIntegerGood.txt.bz2

   This is a 56 MB download compressed with bzip2.

   I'd appreciate it if others could test this on other platforms.  I
don't anticipate any problems, though.

   I haven't had much time to finish the changes to the pow() function,
but there are some more optimizations I'd like to put in.

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams

import java.math.BigInteger;

public class BigIntegerRegressionTest
{
   public static void main(String args[])
   {
  BigInteger exp,b,c,r,r1,r2,bb2;

  for (int ee=0; ee<=1000; ee++)
  {
 for (int bb=-10; bb <= 10; bb++)
 {
 b = BigInteger.valueOf(bb);
 r = b.pow(ee);
 System.out.println("(" + bb + ")" + "^" + ee + "=" + r);
 }
  }


  for (int bb=-10; bb <= 10; bb++)
  {
 b = BigInteger.valueOf(bb);
 for (int ee=0; ee<=100; ee++)
 {
r1 = b.pow(ee);
for (int b2=-10; b2 <= 10; b2++)
{
   bb2 = BigInteger.valueOf(b2);
   for (int e2=0; e2<100; e2++)
   {
  r2 = bb2.pow(e2);
  r = r1.multiply(r2);
  System.out.println("(" + bb + ")" + "^" + ee + " * (" + b2 + 
")" + "^" + e2 + "=" + r);
   }
}
 }
  }
   }
}

Re: [PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

 Attached is a *revised* patch for bug 4837946, for implementing
asymptotically
faster algorithms for multiplication of large numbers in the BigInteger
class:

 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

   It only differs from my patch posted yesterday in one respect--the
new methods getLower() and getUpper() now call
trustedStripLeadingZeroInts() which has two effects:

   * Helps preserve the invariant expected by BigInteger that zero has a
signum of zero and a mag array with length of zero (due to the way that
the private constructor BigInteger(int[] mag, int signum) works.)

   * Optimizes some cases like multiplying 2*100, where the bit
string has a large number of zeroes in a row.

   Please use this patch instead of the one I posted yesterday.

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams
diff --git a/src/share/classes/java/math/BigInteger.java 
b/src/share/classes/java/math/BigInteger.java
--- a/src/share/classes/java/math/BigInteger.java
+++ b/src/share/classes/java/math/BigInteger.java
@@ -172,6 +172,22 @@ public class BigInteger extends Number i
  */
 private final static long LONG_MASK = 0xL;
 
+/** 
+ * The threshhold value for using Karatsuba multiplication.  If the number
+ * of ints in both mag arrays are greater than this number, then
+ * Karatsuba multiplication will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_THRESHHOLD = 35;
+
+/** 
+ * The threshhold value for using Karatsuba squaring.  If the number
+ * of ints in the number are larger than this value,
+ * Karatsuba squaring will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_SQUARE_THRESHHOLD = 100;
+
 //Constructors
 
 /**
@@ -530,7 +546,8 @@ public class BigInteger extends Number i
 if (bitLength < 2)
 throw new ArithmeticException("bitLength < 2");
 // The cutoff of 95 was chosen empirically for best performance
-prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
+prime = (bitLength < SMALL_PRIME_THRESHOLD 
+? smallPrime(bitLength, certainty, rnd)
 : largePrime(bitLength, certainty, rnd));
 signum = 1;
 mag = prime.mag;
@@ -1043,6 +1060,11 @@ public class BigInteger extends Number i
 private static final BigInteger TWO = valueOf(2);
 
 /**
+ * The BigInteger constant -1.  (Not exported.)
+ */
+private static final BigInteger NEGATIVE_ONE = valueOf(-1);
+
+/**
  * The BigInteger constant ten.
  *
  * @since   1.5
@@ -1188,10 +1210,19 @@ public class BigInteger extends Number i
 if (val.signum == 0 || signum == 0)
 return ZERO;
 
-int[] result = multiplyToLen(mag, mag.length,
- val.mag, val.mag.length, null);
-result = trustedStripLeadingZeroInts(result);
-return new BigInteger(result, signum*val.signum);
+   int xlen = mag.length;
+   int ylen = val.mag.length;
+
+   if ((xlen < KARATSUBA_THRESHHOLD) || (ylen < KARATSUBA_THRESHHOLD))
+   {
+   
+   int[] result = multiplyToLen(mag, xlen,
+val.mag, ylen, null);
+   result = trustedStripLeadingZeroInts(result);
+   return new BigInteger(result, signum*val.signum);
+   }
+   else
+   return multiplyKaratsuba(this, val);
 }
 
 /**
@@ -1229,6 +1260,82 @@ public class BigInteger extends Number i
 }
 
 /**
+ * Multiplies two BigIntegers using the Karatsuba multiplication
+ * algorithm.  This is a recursive divide-and-conquer algorithm which
+ * is more efficient for large numbers than what is commonly called the
+ * "grade-school" algorithm used in multiplyToLen.  If the numbers to
+ * be multiplied have length n, the "grade-school" algorithm has
+ * an asymptotic complexity of O(n^2).  In contrast, the Karatsuba
+ * algorithm has complexity of O(n^(log2(3))), or O(n^1.585).  It achieves
+ * this increased performance by doing 3 multiplies instead of 4 when
+ * evaluating the product.  As it has some overhead, should be used when
+ * both numbers are larger than a certain threshhold (found 
+ * experimentally).
+ *
+ */
+private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y)
+{
+int xlen = x.mag.length;
+int ylen = y.mag.length;
+   
+// The number of ints in each half of the number.
+int half = Math.max(xlen, ylen) / 2;
+   
+BigInteger xl = x.getLower(half);
+BigInteger xh = 

Re: [PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

Anonymous member wrote:
> Out of curiousity, how does the Java implementation compare to GMP in
> terms of speed?

   (Note:  These numbers apply to the *revised* patch that I'll be
posting in a few minutes.)

   It depends on the size of the numbers.  When I run the regression
tests that I wrote, my updated Java version runs in about 2 minutes.
When I run the same regression test in Kaffe using GMP, it takes about 2
*hours*.  (Some of the same tests using Java 1.6 take many, many hours
without my optimizations for the pow() function).

   But those are a lot of small numbers.  There is a lot of overhead in
converting from Java to C types and back, and in Kaffe's relative
slowness.  And currently, only multiply() has been improved in my Java
patches that I've submitted.  Kaffe is about 25 times slower on the
average program anyway.  When you run Kaffe/GMP for very large numbers,
Kaffe/GMP starts being very much faster.  OpenJDK still can't compete
for numbers that are on the cutting edge of number theory.   But we'll
be much better than we were before.

   If I were to write the same code in pure C using GMP, then GMP would
be much faster.  But I haven't done that.  So it's hard to compare GMP
to Java exactly.

   But some numbers.  For multiplying the numbers 3^100 * 3^101,
(with my fixes to do the exponentiation hundreds of thousands of times
faster factored out; without these, JDK 1.6 would be thousands of times
slower,) the times for 20 iterations are:

   JDK 1.6  OpenJDK1.7 with my patches  Kaffe w/GMP
   292987 ms28650 ms866 ms

   Thus, for numbers of this size, my algorithms are more than 10 times
faster than JDK 1.6, but 33 times slower than Kaffe/GMP.

   For multiplying the somewhat special form 2^100 * 2^101, (the
arguments of this in binary are a 1 followed by a million zeroes)

   JDK 1.6  OpenJDK1.7 with my patches  Kaffe w/GMP
   117298 ms386 ms  474 ms

   So, my algorithm is 303 times faster than JDK, and just slightly
faster than Kaffe/GMP.

   For multiplying numbers 3^1400 * 3^1401, the time for 1
iteration is:

   JDK 1.6  OpenJDK1.7 with my patches  Kaffe w/GMP
   3499115 ms   89505 ms910 ms

   Thus, for numbers of this size, my patches make it 38.9 times faster,
but still 99 times slower than GMP.  Sigh.  Well, to be expected.

   If you work with large numbers, GMP becomes ridiculously faster.
Kaffe with GMP becomes only slightly slower than pure GMP as the portion
of time in Java gets small.  GMP includes 3-way Toom-Cook
multiplication, and the much faster FFT multiplication (which is O(n))
for very large numbers, and hand-crafted assembly language that uses
64-bit instructions and limbs on my 64-bit architecture (as opposed to
the 32-bit ints used in BigInteger.  Hopefully some day in the future,
BigInteger will be rewritten to use longs internally instead of ints.
Multiplying two 64-bit longs does 4 times as much work as multiplying
two 32-bit ints, and will thus likely be significantly faster,
especially on 64-bit architectures.)

   So GMP is still very much faster for very large numbers.  It is also
*much* faster in turning numbers into strings, and in exponentiation.
The algorithms in BigInteger are horrible for pow() and toString().  See
the following bugs:

4641897: BigInteger.toString() algorithm slow for large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

4646474: BigInteger.pow() algorithm slow in 1.4.0
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

   I have several fixes for both of these.   My JVM-based programming
language Frink ( http://futureboy.us/frinkdocs/ ) implements many of
these improvements, and is much faster for a variety of arguments.  I
just need to finish improving these for a variety of different
arguments, and considering the threading and memory-size-vs-speed
tradeoffs in implementing toString efficiently.

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams

[PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

[Alan Eliasen]

   Attached is a patch for bug 4837946, for implementing asymptotically
faster algorithms for multiplication of large numbers in the BigInteger
class:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

   This patch implements Karatsuba multiplication and Karatsuba squaring
for numbers above a certain size (found by experimentation).  These
patches are designed to be as easy to read as possible, and are
implemented in terms of already-existing methods in BigInteger.  Some
more performance might be squeezed out of them by doing more low-level
bit-fiddling, but I wanted to get a working version in and tested.

   This is quite a bit faster for large arguments.  The crossover point
between the "grade-school" algorithm and the Karatsuba algorithm for
multiplication is set at 35 "ints" or about 1120 bits, which was found
to give the best crossover in timing tests, so you won't see improvement
below that.  Above that, it's asymptotically faster. (O(n^1.585),
compared to O(n^2)) for the grade-school algorithm.  Double the number
of digits, and the "grade school" algorithm takes about 4 times as long,
Karatsuba takes about 3 times as long.  It's vastly superior for very
large arguments.

   I'd also like to create another RFE for implementing even faster
multiplication algorithms for yet larger numbers, such as Toom-Cook.

   Previously, I had indicated that I'd submit faster algorithms for
pow() at the same time, but the number of optimizations for pow() has
grown rather large, and I plan on working on it a bit more and
submitting it separately.  Many/most combinations of operands for pow()
are now vastly faster (some hundreds of thousands of times,) but I'd
like to make it faster (or, at the least, the same performance for all
arguments, a few of which have gotten slightly slower.)  Unfortunately,
these optimizations add to the size and complexity of that patch, which
is why I'm submitting it separately.

   I have created regression tests that may or may not be what you want;
they simply multiply a very large bunch of numbers together and output
their results to a very large file, which you then "diff" against known
correct values.  (My tests produce 345 MB of output per run!)  I
validated the results by comparing them to the output of both JDK 1.6
and the Kaffe JVM, which was compiled to use the well-known and
widely-tested GMP libraries for its BigInteger work.  All tests pass.  I
haven't submitted these tests, but am awaiting getting a copy of the
existing regression tests that Joseph Darcy discussed on this list.

   Please let me know if there's a problem with the patch.  I had to
hand-edit a few lines to remove the work I'm doing for pow().

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams
diff --git a/src/share/classes/java/math/BigInteger.java 
b/src/share/classes/java/math/BigInteger.java
--- a/src/share/classes/java/math/BigInteger.java
+++ b/src/share/classes/java/math/BigInteger.java
@@ -172,6 +172,22 @@ public class BigInteger extends Number i
  */
 private final static long LONG_MASK = 0xL;
 
+/** 
+ * The threshhold value for using Karatsuba multiplication.  If the number
+ * of ints in both mag arrays are greater than this number, then
+ * Karatsuba multiplication will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_THRESHHOLD = 35;
+
+/** 
+ * The threshhold value for using Karatsuba squaring.  If the number
+ * of ints in the number are larger than this value,
+ * Karatsuba squaring will be used.   This value is found
+ * experimentally to work well. 
+ */
+private static final int KARATSUBA_SQUARE_THRESHHOLD = 100;
+
 //Constructors
 
 /**
@@ -1043,6 +1059,11 @@ public class BigInteger extends Number i
 private static final BigInteger TWO = valueOf(2);
 
 /**
+ * The BigInteger constant -1.  (Not exported.)
+ */
+private static final BigInteger NEGATIVE_ONE = valueOf(-1);
+
+/**
  * The BigInteger constant ten.
  *
  * @since   1.5
@@ -1188,10 +1209,19 @@ public class BigInteger extends Number i
 if (val.signum == 0 || signum == 0)
 return ZERO;
 
-int[] result = multiplyToLen(mag, mag.length,
- val.mag, val.mag.length, null);
-result = trustedStripLeadingZeroInts(result);
-return new BigInteger(result, signum*val.signum);
+   int xlen = mag.length;
+   int ylen = val.mag.length;
+
+   if ((xlen < KARATSUBA_THRESHHOLD) || (ylen < KARATSUBA_THRESHHOLD))
+   {
+   
+   int[] result = multiplyToLen(mag, xlen,
+val.mag, ylen, null);

Re: BigInteger performance improvements

[Alan Eliasen]

Joseph D. Darcy wrote:
> Yes, this is the right group :-)  As "Java Floating-Point Czar" I also
> look after BigInteger, although I haven't had much time for proactive
> maintenance there in a while.  I think using faster, more mathematically
> sophisticated algorithms in BigInteger for large values would be a fine
> change to explore, as long as the performance on small values was
> preserved and regression tests appropriate for the new algorithms were
> developed too.

   My last step for this patch is improving performance of pow() for
small numbers, which got slightly slower for some small arguments.  (But
some arguments, like those containing powers of 2 in the base, are
*much* faster.)  The other functions like multiply() are basically
unchanged for small numbers.  The new code, as you might expect,
examines the size of the numbers and runs the old "grade-school"
algorithm on small numbers and the Karatsuba algorithm on larger numbers
(with the threshhold point being determined by benchmark and experiment.)

   As to the matter of regression tests, I would presume that Sun
already has regression tests for BigInteger to make sure it gets correct
results.  Can you provide me with these, or are they in the OpenJDK
distribution already?  I can check these to make sure that they use
numbers big enough to trigger the threshholds, and if not, extend them
in the same style.  Regression tests should hopefully be a no-op,
assuming you have some already.  I'm not adding any new functionality
and no results should change--they should just run faster, of course.
It should of course be impossible to write a regression test that
"succeeds with the patch applied, and fails without the patch" like is
requested on the OpenJDK page, unless it is time-limited.

   Of course, I could extend the regression tests to test *huge* numbers
which may or may not be desired if you want the regression tests to run
in short time.  For example, a single exponentiation that takes
milliseconds in my new version takes on the order of 15 minutes with JDK
1.6.  How long are you willing to let regression tests take?  How many
combinations of arguments do you currently test?  Do you think more are
necessary?

> I'd prefer to process changes in smaller chunks rather a huge one all at
> once; however, I may be a bit slow on reviews in the near future due to
> some other openjdk work I'm leading up

   I will be submitting a patch addressing the three functions:
multiply(), pow() and (the private) square().  These are intertwined and
it would be more work and testing for both of us to separate out the
patches and apply them in 3 phases.  The patch will definitely not be huge.

   My patches are designed to be as readable and simple as possible for
this phase.  They all build on existing functions, and eschew lots of
low-level bit-fiddling, as those types of changes are harder to
understand and debug.  I think it's best to get working algorithms with
better asymptotic efficiency, as those will vastly improve performance
for large numbers, and tune them by doing more low-level bit fiddling
later.  Even without being tuned to the nth degree, the new algorithms
are vastly faster for large numbers, and identical for small numbers.

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams

BigInteger performance improvements

[Alan Eliasen]

   I'm planning on tackling the performance issues in the BigInteger
class.  In short, inefficient algorithms are used for
multiplication, exponentiation, conversion to strings, etc.  I intend to
improve this by adding algorithms with better asymptotic behavior that
will work better for large numbers, while preserving the existing
algorithms for use with smaller numbers.

   This encompasses a lot of different bug reports:

4228681:  Some BigInteger operations are slow with very large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681

   (This was closed but never fixed.)


4837946: Implement Karatsuba multiplication algorithm in BigInteger
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

I've already done the work on this one.  My implementation is
intended to be easy to read, understand, and check.  It significantly
improves multiplication performance for large numbers.


4646474: BigInteger.pow() algorithm slow in 1.4.0
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

   This will be improved in a couple ways:

   * Rewrite pow() to use the above Karatsuba multiplication
   * Implement Karatsuba squaring
   * Finding a good threshhold for Karatsuba squaring
   * Rewrite pow() to use Karatsuba squaring
   * Add an optimization to use left-shifting for multiples of 2 in the
base.  This improves speed by thousands of times for things like
Mersenne numbers.


4641897: BigInteger.toString() algorithm slow for large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

This algorithm uses a very inefficient algorithm for large numbers.
 I plan to replace it with a recursive divide-and-conquer algorithm
devised by Schoenhage and Strassen.  I have developed and tested this in
my own software.  This operates hundreds or thousands of times faster
than the current version for large numbers.  It will also benefit from
faster multiplication and exponentiation.


   In the future, we should also add multiplication routines that are
even more efficient for very large numbers, such as Toom-Cook
multiplication, which is more efficient than Karatsuba multiplication
for even larger numbers.

   Has anyone else worked on these?  Is this the right group?

   I will probably submit the Karatsuba multiplication patch soon.
Would it be more preferable to implement *all* of these parts first and
submit one large patch?

-- 
  Alan Eliasen  |  "Furious activity is no substitute
  [EMAIL PROTECTED]|for understanding."
  http://futureboy.us/  |   --H.H. Williams