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/
