On Wednesday, March 12, 2003, at 02:16 PM, Geir Magnusson Jr. wrote:
If you could give a technical reason why you think BI/BD is overkill, that would be appreciated.
Gladly. BigIntegers/Decimals (hencefort, Bigs) are immutable objects but much, much heavier than Integers/Doubles (hencefort, Nums). So every operation on them has to construct and garbage collect a composite object whose interface is completely implemented in Java. Nums, on the other hand, undergo heavy optimization on the JVM's part.
Of course, Bigs are complicated beasts that implement complicated behavior. The operations on them don't map 1-1 on machine operations as native scalar types do: basically, they implement long hand arithmetic. Division, in particular, is horrible (for the interested, the definitive reference is Knuth, vol. II).
What all that cost afford you isn't really never having to worry about overflow, but integer/rational math, as opposed as math modulo a power of two. I want to stress this: it's another whole set of operations. Packages like Mathematica and Maple use Big math internally to provide sophisticated mathematical reasoning.
I made a simple test suite, computing all Pythagorean triples (that is, integer-sided right triangles) up to 10^2 + 1 (it sounds more complicated than it is, actually). The results are these:
[puma:~/Desktop] mgiovann% java NumbersTest
A battery of tests that times 10000 iterations of NumbersTest$Test00, NumbersTest$Test01, NumbersTest$Test02.
Baseline integer test (uses native int's):
PASSED in 0.09 s -- 8.6 us/it
Boxed integer test (uses java.lang.Integer):
PASSED in 0.77 s -- 77.2 us/it
Big integer test (uses java.lang.BigInteger):
PASSED in 6.81 s -- 681.2 us/it
As you can see, Nums are an order of magnitude slower than native ints, and Bigs are an order of magnitude slower than Nums, even if the code looks "simpler". I attach the Java source for the interested.
I was planning on a similar Double/BigDecimal shootout, but the numbers for Integer/BigInteger made me think that the case is compelling enough as it is.
If you need further clarification, I'd be delighted to elaborate.
Mat�as.
import java.math.BigInteger; import java.math.BigDecimal;
public final class NumbersTest {
public interface Test {
String getDescription();
boolean test();
}
public static final class TestSuite implements Test {
private Test[] battery;
private int iterations;
public TestSuite(Test[] battery, int iterations) {
this.battery = battery;
this.iterations = iterations;
}
public void setIterations(int iterations) {
this.iterations = iterations;
}
public int getIterations() {
return iterations;
};
public String getDescription() {
StringBuffer buf = new StringBuffer();
buf.append("A battery of tests that times ");
buf.append(getIterations());
buf.append(" iterations of ");
for (int i = 0; i < battery.length; i++) {
if (i > 0)
buf.append(", ");
buf.append(battery[i].getClass().getName());
}
buf.append(".");
return buf.toString();
}
public boolean test() {
for (int i = 0; i < battery.length; i++) {
Test test = battery[i];
System.out.println(test.getDescription());
long lap = System.currentTimeMillis();
for (int j = getIterations(); j > 0; --j) {
if (!test.test()) {
System.out.println("FAILED");
return false;
}
}
lap = System.currentTimeMillis() - lap;
System.out.println("PASSED in "
+(Math.floor(lap / 10.0 + 0.5) / 100.0)
+" s -- "
+(Math.floor((double)lap / (double)
getIterations() * 10000.0 + 0.5)/10.0)
+" us/it");
}
return true;
}
}
private static abstract class IntegerTest implements Test {
public String getDescription() {
return "Compute all primitive Pythagorean pairs with r up to
"+getLimit()+" (see, e.g. Niven & Zuckerman).";
}
public int getLimit() {
return 10;
}
}
private final static class Test00 extends IntegerTest {
public String getDescription() {
return "Baseline integer test (uses native int's):
"+super.getDescription();
}
/**
* Compute the GCD of the arguments, using the Euclidean algorithm.
* @param p the first number
* @param q the second number
* @return the GCD of both arguments.
*/
private static final int gcd(int p, int q) {
int r;
if (p < q) {
r = p;
p = q;
q = r;
}
if (q == 0)
return 0;
while (q != 0) {
r = p % q;
p = q;
q = r;
}
return p;
}
public boolean test() {
for (int r = getLimit(); r > 1; --r) {
for (int s = 1 + (r & 1); s < r; s += 2) {
if (gcd(r, s) != 1)
continue;
int r2 = r * r, s2 = s * s;
int x = r2 - s2;
int y = 2 * r * s;
int z = r2 + s2;
int test = x*x+y*y-z*z;
if (test != 0)
return false;
}
}
return true;
}
}
private final static class Test01 extends IntegerTest {
public String getDescription() {
return "Boxed integer test (uses java.lang.Integer):
"+super.getDescription();
}
/**
* Compute the GCD of the arguments, using the Euclidean algorithm.
This
* implementation unboxes the integers, computes the GCD and boxes
back the result.
* @param pp the first number
* @param qq the second number
* @return the GCD of both arguments.
*/
private static final Integer gcd(Integer pp, Integer qq) {
if (pp == null || qq == null)
throw new IllegalArgumentException("gcd");
int p = pp.intValue(), q = qq.intValue();
int r;
if (p < q) {
r = p;
p = q;
q = r;
}
if (q == 0)
return new Integer(0);
while (q != 0) {
r = p % q;
p = q;
q = r;
}
return new Integer(p);
}
/**
* Assume no optimization of unboxing on any expression, either atomic
or in sequence.
* That is, this is a worst-case scenario.
*/
public boolean test() {
for (Integer r = new Integer(getLimit());
r.intValue() > 1;
r = new Integer(r.intValue() - 1)) {
for (Integer s = new Integer(1 + (r.intValue() & 1));
s.compareTo(r) < 0;
s = new Integer(s.intValue() + 2)) {
if (gcd(r, s).intValue() != 1)
continue;
Integer r2 = new Integer(r.intValue() *
r.intValue());
Integer s2 = new Integer(s.intValue() *
s.intValue());
Integer x = new Integer(r2.intValue() -
s2.intValue());
Integer y = new Integer(2 * r.intValue() *
s.intValue());
Integer z = new Integer(r2.intValue() +
s2.intValue());
Integer test = new Integer(
x.intValue()*x.intValue() +
y.intValue()*y.intValue() -
z.intValue()*z.intValue()
);
if (test.intValue() != 0)
return false;
}
}
return true;
}
}
private final static class Test02 extends IntegerTest {
public String getDescription() {
return "Big integer test (uses java.lang.BigInteger):
"+super.getDescription();
}
/**
* Assume no optimization of unboxing on any expression, either atomic
or in sequence.
* That is, this is a worst-case scenario.
*/
public boolean test() {
BigInteger TWO = BigInteger.valueOf(2L);
for (BigInteger r = BigInteger.valueOf((long) getLimit());
r.compareTo(BigInteger.ONE) > 0;
r = r.subtract(BigInteger.ONE)) {
for (BigInteger s =
r.and(BigInteger.ONE).add(BigInteger.ONE);
s.compareTo(r) < 0;
s = s.add(TWO)) {
if (r.gcd(s).compareTo(BigInteger.ONE) != 0)
continue;
BigInteger r2 = r.multiply(r);
BigInteger s2 = s.multiply(s);
BigInteger x = r2.subtract(s2);
BigInteger y = r.multiply(s).shiftLeft(1);
BigInteger z = r2.add(s2);
BigInteger test =
x.multiply(x).add(y.multiply(y)).subtract(z.multiply(z));
if (test.compareTo(BigInteger.ZERO) != 0)
return false;
}
}
return true;
}
}
public static void main(String[] args) {
TestSuite tests = new TestSuite(
new Test[] { new Test00(), new Test01(), new Test02() },
10000
);
System.out.println(tests.getDescription());
tests.test();
}
}
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
