On May 16, 2013, at 7:21 PM, Alan Eliasen wrote:
>> 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!
You're welcome. I really did not expect find any problems but I feel better
understanding the algorithms and the implementation insofar as possible.
> 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(). )
I have cleaned up the imports.
> 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.
A quick and dirty benchmark gave these results in operations per millisecond
(larger value is faster):
Before
o.s.m.g.t.MyBenchmark.multiplyLarge 1445.571
o.s.m.g.t.MyBenchmark.multiplySmall 8919.505
o.s.m.g.t.MyBenchmark.squareLarge 1462.645
o.s.m.g.t.MyBenchmark.squareSmall 9018.123
After: multiply(this) returns square()
o.s.m.g.t.MyBenchmark.multiplyLarge 1460.300
o.s.m.g.t.MyBenchmark.multiplySmall 8814.362
o.s.m.g.t.MyBenchmark.squareLarge 1518.695
o.s.m.g.t.MyBenchmark.squareSmall 8287.958
The base code was the current JDK 8 tip (sans phase 1 changes) and the only
change was to call square() if the parameter to multiply == this. In the above,
"small" indicates that everything will fit in a long and "large" that it will
not.
> 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.
I don't see that anywhere in the code either.
> 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.
I concur.
> 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.
Sounds like a good idea I would be inclined to leave these changes to some
later stage, perhaps a "phase 3.5" or some such.
Brian
