Below are the results of performance evaluation:
1) Performance improvement of specialized method bi.toHexString() against
general bi.toString(16).
2) Code ot hypothetical BigInteger.toHexString();
3) Code of benchmark.
-Dima
=== b.bitLength(); b.toString(16); b.toHexString();
bitLength=2047; 0.001458205 sec 3.11251E-4 sec
bitLength=4095; 0.003836644 sec 6.14027E-4 sec
bitLength=8191; 0.01112082 sec 0.001148153 sec
bitLength=16383; 0.009785916 sec 0.00256648 sec
bitLength=32767; 0.024226532 sec 0.005104734 sec
bitLength=65535; 0.040899736 sec 0.001239427 sec
bitLength=131071; 0.057398824 sec 0.002302767 sec
bitLength=262143; 0.13263946 sec 0.004272388 sec
bitLength=524287; 0.44488142 sec 8.64876E-4 sec
bitLength=1048575; 1.628629919 sec 0.001423972 sec
bitLength=2097151; 6.399754105 sec 0.002084977 sec
bitLength=4194303; 25.052650526 sec 0.004460035 sec
bitLength=8388607; 100.974373978 sec 0.009238686 sec
bitLength=16777215; 407.2107094 sec 0.018795085 sec
===
=== The code of BigInteger.toHexString()
public String toHexString() {
if (signum == 0) {
return "0";
}
int highestLimb = mag[0];
int digitsInHigherLimb = 8 -
Integer.numberOfLeadingZeros(highestLimb) / 4;
int len = (mag.length - 1) * 8 + digitsInHigherLimb;
if (signum < 0)
len++;
StringBuilder buf = new StringBuilder(len);
if (signum<0)
buf.append('-');
for (int i = digitsInHigherLimb - 1; i >= 0; i--) {
buf.append(Character.forDigit((highestLimb >> (i * 4)) & 0xF,
16));
}
for (int i = 1; i < mag.length; i++) {
int m = mag[i];
buf.append(Character.forDigit((m >> 28) & 0xF, 16));
buf.append(Character.forDigit((m >> 24) & 0xF, 16));
buf.append(Character.forDigit((m >> 20) & 0xF, 16));
buf.append(Character.forDigit((m >> 16) & 0xF, 16));
buf.append(Character.forDigit((m >> 12) & 0xF, 16));
buf.append(Character.forDigit((m >> 8) & 0xF, 16));
buf.append(Character.forDigit((m >> 4) & 0xF, 16));
buf.append(Character.forDigit(m & 0xF, 16));
}
return buf.toString();
}
===
=== The benchmark program
public class TestToString {
public static void main(String[] args) {
int n = 1;
BigInteger bi = BigInteger.ONE;
System.out.println("b.bitLength(); b.toString(16);
b.toHexString();");
for (int i = 0; i <= 23; i++) {
long time0 = System.nanoTime();
String s1 = bi.toString(16);
long time1 = System.nanoTime();
String s2 = bi.toHexString();
long time2 = System.nanoTime();
assert s1.equals(s2);
if (i >= 10) {
System.out.println("bitLength=" + bi.bitLength() + ";\t" +
(time1 - time0) / 1e9 + " sec\t" + (time2 - time1) / 1e9 + " sec");
}
n *= 2;
bi = bi.shiftLeft(n).add(bi);
}
}
}
====
On Sat, Jun 22, 2013 at 8:37 AM, Alan Eliasen <elia...@mindspring.com>wrote:
> 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/
>
