New benchmarks


Posted by Ron Lenk , Oct 26,1999,14:00 Post Reply  Forum

Here are the new (and improved!) versions of the benchmarks.
The smaller arrays should (hopefully) make it possible for you
to run them in the limited amount of memory. I have made a few
cosmetic changes as well, such as adding a main() to quicksort.

-RL

ballclock.c
--
#include

#define QUEUE_SIZE 32

void bottomenqueue(int bottom[], int *btail, int i)
{
bottom[*btail] = i;
*btail = (*btail + 1) % QUEUE_SIZE;
}

int bottomdequeue(int bottom[], int *bhead)
{
int last;

last = bottom[*bhead];
*bhead = (*bhead + 1) % QUEUE_SIZE;
return last;
}

int numberofdays(int balls)
{
int lastball;
int done;
int halfdays;

int bottom[QUEUE_SIZE];
int bhead;
int btail;

int hour[12];
int five[12];
int minute[5];

int htop, ftop, mtop;

int i, h, f, m;

bhead = 0;
btail = 0;
mtop = 0;
ftop = 0;
htop = 0;
halfdays = 0;

for (i = 0; i < balls; i++)
bottomenqueue(bottom, &btail, i);

for (done = 0; !done; ) {
halfdays++;

for (h = 0; h < 12; h++) {
for (f = 0; f < 12; f++) {
for (m = 0; m < 5; m++)
minute[mtop++] = bottomdequeue(bottom, &bhead);

five[ftop++] = minute[--mtop];

for (m = 0; m < 4; m++)
bottomenqueue(bottom, &btail, minute[--mtop]);
}

hour[htop++] = five[--ftop];

for (f = 0; f < 11; f++)
bottomenqueue(bottom, &btail, five[--ftop]);
}

lastball = hour[--htop];

for (h = 0; h < 11; h++)
bottomenqueue(bottom, &btail, hour[--htop]);

bottomenqueue(bottom, &btail, lastball);

done = 1;

for (i = 0; i < balls - 1; i++)
if (bottom[(bhead + i + 1) % QUEUE_SIZE] -
bottom[(bhead + i) % QUEUE_SIZE] != 1)
done = 0;
}

return halfdays / 2;
}

int main()
{

int balls;

for (balls = 27; balls < QUEUE_SIZE; ++balls)
printf("%d balls cycle in %d days\n", balls, numberofdays(balls));

return 0;
}
--

cubes.c
--
/* Determine the minimal number of cubes that sum to a given number. */
/* 567 = 343 + 216 + 8 -> 3, 37 = 27 + 8 + 1 + 1 -> 4 */

#include

void go(int rest, int ix, int sofar, int *best, int cubes[]) {
int i;

if (ix == 1) {
sofar += rest;
if (*best > sofar)
*best = sofar;
}
else
for (i = 0; i <= rest / cubes[ix]; i++)
go(rest - i * cubes[ix], ix - 1, sofar + i, best, cubes);
}

void doit(int n) {
int best, cubes[16], nc;

nc = 0;
cubes[nc] = 0;

while (cubes[nc] <= n) {
nc++;
cubes[nc] = nc * nc * nc;
}

nc--;
best = n;

go(n, nc, 0, &best, cubes);

printf("%d can be expressed as the sum of %d cubes\n", n, best);
}

int main(void) {
int i;
for (i = 1; i < 32; i++)
doit(i);

return 0;
}
--

quicksort.c
--
#include

void quicksort(int a[], int l, int r) {
int p, i, j, t;

while (r - l > 0) {
p = a[l];
i = l - 1;
j = r + 1;
for (;;) {
while (a[++i] < p);
while (a[--j] > p);
if (i >= j)
break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
if (j - l + 1 < r - j) {
quicksort(a, l, j);
l = j + 1;
}
else {
quicksort(a, j + 1, r);
r = j;
}
}
}

int main(void) {
int array[] = { 0, 15, 1, 14, 2, 13, 3, 12, 4, 11, 5, 10, 6, 9, 7, 8 };
int i;

quicksort(array, 0, 15);

for (i = 0; i < 16; ++i)
printf("array[%d] = %d\n", i, array[i]);

return 0;
}
--