Hi Brian, thanks for the update.

This patch differs from the code in https://github.com/tbuktu/bigint.git. Notably I observed that Schonhage-Strassen multiplication and Barrett division are not present. Is this intentional and if so why would that be? Are the implementations of these additional algorithms not quite ready for contribution or is there a licensing issue perhaps? Schönhage-Strassen and Barrett have been tested by me. I believe Alan Eliasen also ran tests. There are no known bugs and there shouldn't be any licensing issues because I wrote the code myself.

The reason why I didn't include these two algorithms in the patch I posted here is because I wasn't sure if it was too much code to review. If that is not a problem and you'd rather use the full implementation, the four patched files are at https://raw.github.com/tbuktu/bigint/master/src/main/java/java/math/BigInteg... https://raw.github.com/tbuktu/bigint/master/src/main/java/java/math/MutableB... https://raw.github.com/tbuktu/bigint/master/src/main/java/java/math/BigDecim... https://raw.github.com/tbuktu/bigint/master/src/test/java/BigIntegerTest.jav... Let me know if there are any more questions. Thanks, Tim

On Apr 29, 2013, at 11:00 AM, Brian Burkhalter wrote:

How much additional code is there for these two algorithms?

To answer my own question, there are apparently about 1,000 more lines.

Unless it is some daunting amount, then if you think that the code is of sufficient quality, my opinion would be that we might as well go ahead and review the most recent version. This would take longer of course, but I think less total time than doing it in two separate passes. Also, if these are not addressed now, it could be some time before separately reviewing the other two algorithms percolated to the top of the list.

...

Let me know if there are any more questions.

Are the patched files listed above with respect to the current tip of the JDK8 repository?

It looks to me as if they are, i.e., the only changes versus the JDK8 repo are those intended for this patch. Thanks, Brian

On 02/05/2013 02:34, Tim Buktu wrote:

:

Alan is working on an improved BigInteger.toString() that should be dramatically faster for large numbers. What's the deadline for getting this in? Thanks,

Tim Here's the latest milestone dates:

http://openjdk.java.net/projects/jdk8/milestones Given the size of the patch then it would be great to get it in as early as possible. With the review effort then I assume Feature Complete is too tight although I know Brian Burkhalter is anxious to get it in as soon as possible. I can't comment on the BigInteger.toString work to know how big this is. -Alan.

On 05/02/2013 06:37 PM, Brian Burkhalter wrote:

On May 2, 2013, at 5:02 AM, Alan Bateman wrote:

...

On 02/05/2013 02:34, Tim Buktu wrote:

...

:

Alan is working on an improved BigInteger.toString() that should be dramatically faster for large numbers. What's the deadline for getting this in? Thanks,

Tim Here's the latest milestone dates:

http://openjdk.java.net/projects/jdk8/milestones

Given the size of the patch then it would be great to get it in as early as possible. With the review effort then I assume Feature Complete is too tight although I know Brian Burkhalter is anxious to get it in as soon as possible. I can't comment on the BigInteger.toString work to know how big this is.

I think that's the best answer that can be given: as soon as possible. The 4837946 patch is far from simple to comprehend to say the least and then there is the testing so it's not going to be fast. If the toString() work is ready early enough to review then perhaps we can handle it, but I don't want to make anyone hurry to complete something and then say we cannot do it.

Brian: 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. Since I first posted these patches over 5 years ago, we were asked to make patches as small as possible so they would get reviewed more quickly. That's why my patches focused on what was a minimal but necessary subset: making multiply and pow work *much* faster with very simple, understandable, well-known, hard-to-get-wrong routines and simple optimizations that built on existing routines but gave very significant performance increases. (Implementing Karatsuba and Toom-Cook multiplication routines in Java is often given as a homework problem in undergrad Algorithms courses. Understanding their correctness requires nothing more than first-year Algebra.) 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. I have run these through my enormous regression tests which produce over 232 GB of output with no differences. I ram these (very large) regression tests which test multiplication and pow and toString functions in BigInteger. (They produce about 232 gigabytes of output, which I compare against known good output that was produced by previous versions of Java and by the Kaffe VM which used the GMP library. This tells you how long I've been working on this; Kaffe removed support for GMP over 4 years ago.) It should be known that I would need to further increase the size of these tests to make a significant test of the very large numbers that trigger Schönhage-Strassen (SS) multiplication. Currently, the smallest numbers that will trigger SS multiplication are both operands >247,000 bits, or about 7718 ints. SS multiplication is used at all times when both operands are 1,249,000 bits or more. These are biggish numbers, and my tests currently don't go out that far. I can vouch strongly for the correctness of Karatsuba and Toom-Cook multiplication, though. Keep in mind that torture-testing Schönhage-Strassen multiplication and comparing against the runs of Java 1.7 or earlier might take a *very* long time because the earlier versions of BigInteger.multiply(BigInteger) are so slow in multiplications of the size where SS multiplication is used. I can personally vouch for having very strongly tested the parts of multiplication and pow that I wrote, which include: * Karatsuba multiplication * 3-way Toom-Cook multiplication * Karatsuba squaring * Toom-Cook squaring * Revised pow() function 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. I have implicitly used his division routines in my base conversion routines for large numbers, and have found no errors. 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. 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 eliasen@mindspring.com http://futureboy.us/

Replying to myself:

I will run the latest version of BigIntegerTest (which tests the above mentioned numbers around powers of two) for a day or so and report back.

The test ran successfully. Tim

Hi Alan, Thank you for the detailed, thoughtful message. 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.

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.

Since I first posted these patches over 5 years ago, we were asked to make patches as small as possible so they would get reviewed more quickly.

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.

That's why my patches focused on what was a minimal but necessary subset: making multiply and pow work *much* faster with very simple, understandable, well-known, hard-to-get-wrong routines and simple optimizations that built on existing routines but gave very significant performance increases. (Implementing Karatsuba and Toom-Cook multiplication routines in Java is often given as a homework problem in undergrad Algorithms courses. Understanding their correctness requires nothing more than first-year Algebra.)

Apparently - and fortunately - algebra as in pre-calculus not as in abstract (groups / rings / fields): something which I studied as an undergraduate but which has long since succumbed to brain rot.

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?

I can personally vouch for having very strongly tested the parts of multiplication and pow that I wrote, which include:

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

That is good to know.

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. I have implicitly used his division routines in my base conversion routines for large numbers, and have found no errors.

It looks like Tim has made some changes to BigIntegerTest which exercise the Burnickel-Ziegler code.

Brian, would it be possible to make BigInteger.square() public?

I am looking into it.

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

This is equivalent to http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 plus http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474.

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. The bug for improving toString is:

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

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

This and quick look at your code answers my question, i.e., it is unrelated to SS multiplication.

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.

Step 4) integrating what I believe are the most tricky routines: Schoenhage-Strassen (SS) multiplication. This stuff is hard.

I think that your proposal for a staged review is a good plan including in terms of the order in which the algorithms would be addressed. I would like to know what others think about it. 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. 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 familiar with the code helped out, especially as said patches might already exist somewhere. If I am not mistaken, the patch for Step 1 less the pow() improvements is this one: https://gist.github.com/tbuktu/1576025. For the time being I will start to look at this patch.

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

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

This is equivalent to the most recent version of TIm's repository https://github.com/tbuktu/bigint plus your changes for pow() and toString()? Thanks, Brian

Hi Tim, On May 6, 2013, at 5:16 PM, Tim Buktu wrote:

...

If I am not mistaken, the patch for Step 1 less the pow() improvements is this one: https://gist.github.com/tbuktu/1576025. For the time being I will start to look at this patch.

Note that it also includes Burnikel-Ziegler. I put it in there because BZ is kind of the division counterpart of Karatsuba/Toom-Cook, so I thought they should go together. If you go with Alan's proposal, we'd need to make a new patch with just Karatsuba, Toom-Cook, and pow(). Maybe Alan has that patch already.

You are correct: I realized that I was mistaken after leaving work.

...

...

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

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

This is equivalent to the most recent version of TIm's repository

https://github.com/tbuktu/bigint

plus your changes for pow() and toString()?

They're the same except for some formatting changes I did so the old and new code would match.

OK - thanks. Brian

Alan, On May 7, 2013, at 2:33 AM, Alan Eliasen wrote:

...

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.

Agreed.

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.

Definitely. I cannot by any stretch purport to being a domain expert at that level. My role is simply to apply due diligence in shepherding these improvements through final review, testing, and integration insofar as possible.

(Believe me, I've tried to do everything I can to simplify the review effort!)

I can see that.

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 [sic]

The demand and utility are clear which is why this is at the top of the list now.

...

...

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.

That was the idea.

...

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.)

It is marked "Resolved-Fixed" even though it is not but I am not sure it is worth re-opening it and re-marking it as resolved. I think it can be linked however to the following issue with an accompanying comment.

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

Assuming that such modification of an existing issue is acceptable, this one ought to be renamed to something like "Implement Karatsuba and Toom-Cook multiplication and squaring" with an appropriate update to the description.

...

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 familiar with the code helped out, especially as said patches might already exist somewhere.

Okay, I can provide patches for each of these phases if you'd like.

That would be very helpful and appreciated. Please see the summary at the end.

The patch for the first phase you're looking at (below) would be a good place to start.

As caught by Tim and myself, that patch is not really equivalent to the Phase 1 patch.

Do you want these as actual patches? Or just the whole file that you can drop into place? If you prefer patches, what format would you like them in?

Whole files are preferable; I can generate the diffs myself.

...

If I am not mistaken, the patch for Step 1 less the pow() improvements is this one: https://gist.github.com/tbuktu/1576025. For the time being I will start to look at this patch.

That seems like a good place to start. It doesn't include the pow() fixes, though.

And as noted elsewhere does include Burnickel-Ziegler so it is not apropos for Phase 1.

...

...

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

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

This is equivalent to the most recent version of TIm's repository

https://github.com/tbuktu/bigint

plus your changes for pow() and toString()?

Yes, Tim merged my toString changes into his github repository. The files there contain all of our known changes.

Good to know. 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. Thanks again for your comments and assistance. Brian

Out of curiosity (my major was math back in university), I take a look at BigInteger.java.phase1: 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? Thanks Max On 5/9/13 3:11 PM, Alan Eliasen wrote:

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.

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 eliasen@mindspring.com http://futureboy.us/

On May 13, 2013, at 11:57 AM, Brian Burkhalter wrote:

On May 11, 2013, at 8:35 PM, Alan Eliasen wrote:

...

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;

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. […] 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.

I would prefer simply to change the javadoc of the constant unless others have a strong preference otherwise.

For example: /** * The threshold value for using 3-way Toom-Cook multiplication. * If the number of ints in each mag array is greater than the * Karatsuba threshold, and the number of ints in at least one of * the mag arrays is greater than this threshold, then Toom-Cook * multiplication will be used. */ private static final int TOOM_COOK_THRESHOLD = 75; Brian

On May 9, 2013, at 10:44 AM, Brian Burkhalter wrote:

...

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.

Indeed if I file them it will streamline things. I will compose a draft summary and description for each of these issues and post it before filing so that if anyone has anything to add it may be done in one step for each.

I just went ahead and filed 8014319 and 8014320 for phases 3 and 4, respectively. They will show up on http://bugs.sun.com/bugdatabase after some unspecified delay, probably about a day. Verbiage may be updated as needed. Brian

On 10.05.2013 23:19, Brian Burkhalter wrote:

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

Brian

Excellent, thanks!

On May 13, 2013, at 4:26 AM, Alan Eliasen wrote:

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

Thanks, Alan, I will take care of it. Brian