77 lines
1.6 KiB
Java
77 lines
1.6 KiB
Java
// DIVITER -- Benchmark which divides by 2 using lists of n ()'s.
|
|
|
|
class Pair {
|
|
|
|
// A Java compiler ought to generate inline code for these.
|
|
|
|
public static Pair cons (int n, Pair y) { return new Pair(n, y); }
|
|
public static int car (Pair x) { return x.hd; }
|
|
public static Pair cdr (Pair x) { return x.tl; }
|
|
|
|
// If it doesn't, then we'll inline them by hand.
|
|
// That's why the following are public.
|
|
// (But Sun's Java 1.2 does the inlining ok.)
|
|
|
|
public Pair (int n, Pair y) { hd = n; tl = y; }
|
|
public int hd;
|
|
public Pair tl;
|
|
|
|
}
|
|
|
|
class divrec {
|
|
static Pair ll;
|
|
|
|
static Pair create_n (int n) {
|
|
Pair result = null;
|
|
while (n > 0) {
|
|
n = n - 1;
|
|
result = Pair.cons ( 0, result );
|
|
}
|
|
return result;
|
|
}
|
|
|
|
static Pair iterative_div2 (Pair l) {
|
|
Pair a = null;
|
|
for (l = l; l != null; l = Pair.cdr (Pair.cdr (l)))
|
|
a = Pair.cons(Pair.car(l), a);
|
|
return a;
|
|
}
|
|
|
|
static Pair recursive_div2 (Pair l) {
|
|
if (l == null)
|
|
return null;
|
|
else {
|
|
Pair y = recursive_div2 (Pair.cdr(Pair.cdr( l )));
|
|
return Pair.cons ( Pair.car(l), y );
|
|
}
|
|
}
|
|
|
|
static int list_length (Pair l) {
|
|
int n = 0;
|
|
while (l != null) {
|
|
l = Pair.cdr(l);
|
|
n++;
|
|
}
|
|
return n;
|
|
}
|
|
|
|
/*===========================================================================*/
|
|
|
|
public static void main (String args[])
|
|
{
|
|
int i;
|
|
Pair result;
|
|
Pair ll;
|
|
ll = create_n (200);
|
|
|
|
result = recursive_div2 (ll);
|
|
for (i=1; i<400000; i++) {
|
|
result = recursive_div2 (ll);
|
|
}
|
|
|
|
if (list_length (result) != 100)
|
|
System.out.println ("*** wrong result ***");
|
|
}
|
|
|
|
}
|