/* corestep.c Author: Jay Han (jayhan@cs.washington.edu) The non-simulating optima number calculator. After an idea by Michael Constant. Run this program without parameters for help. Usage ----- There are three possible uses: 1. Test a single step: -s # 2. Test all mod-N: -m # 3. Test all steps: (default) For each type, you may specify or not a selection criterion: -cc classic formula -ca alternate formula -cf find-X (with up to FINDS numbers) If a criterion is specified, you may choose how many will be shown: -b # shows the # best steps In any case, you may ask to display the scores and find number for the chosen numbers by using -dc show classic score -da show alternate score -df with up to FINDS numbers Other options: -l # limit to steps <= # -v verbose -q quiet -o alternate output (don't know how to use this yet...) Notes ----- 1. Find-X numbers are displayed in percent. 100% is perfect, 200% means it takes twice as long as perfect (e.g. 1600 iterations to find 10 in small core). 2. If you specify two or more find-numbers as the criterion, the compound score is the average of the specified find-numbers. However, if you specify -df parameters, each find number will be dispayed separately. 3. All sorted scores (best scores) are displayed best-to-worst. For the classic formula, higher score is better. For the alternate formula and the find numbers, lower score is better. 4. In general, the display has been programmed to be tight, so as to give as much information as possible in the smallest space. However, the results are tabulated to allow easy browsing and character-based sorting. Examples -------- Find all mod-4 numbers: corestep -m 4 -c Find 5 best mod-4 numbers using classic formula: corestep -m 4 -cc Same, display their find-20 and find-100 numbers: corestep -m 4 -cc -df 20 100 Find 10 best mod-1 numbers for 10-sized opponents: corestep -m 1 -cf 10 -b 10 Same, display their find-50 and find-200: corestep -m 1 -cf 10 -b 10 -df 50 200 Find 20 best numbers for 10- and 20-sized opponents: (this takes some time, so we'll have the verbose mode on) corestep -cf 10 20 -b 20 -v Same, display their classic score: corestep -cf 10 20 -b 20 -dc Compiling --------- The program uses log(), which should be included in libm.a, the math library. Usually, it can be linked in with the compiler option -lm, as in: gcc -O2 -o corestep corestep.c -lm (Don't forget to turn on all optimization options!) This program should compile without problems on any OS with an ANSI C compiler, provided that uint is 16 bit wide. Feedback -------- I'd be happy to hear from you. Tell me if you find this program useful, interesting, or totally unsuited to your needs. Bug-reports are always welcome, even if they prove false! :-) If you have new ideas you'd like to see incorporated into the program, let me know also. I'm particularly looking for other alternate scoring formulas that give meaningful/useful results. *************************************************************************/ #define DATE "5/13/1994" #define VERSION "3" /************************************************************************/ #include #include #include typedef unsigned int uint; #define DISP_CLASSIC 0x1 #define DISP_ALTERNATE 0x2 #define DISP_FIND 0x4 #define BANNER \ "corestep v%s: Non-simulating optimal step finder by Jay Han, %s.\n" char banner[100]; #define FINDS 10 #define NBEST 5 #define CORESIZE 55440 uint coresize = (uint)CORESIZE; int verbose=1, printer=0, display=0; char tformat[10], rformat[5], lformat[5]; uint critfind[FINDS], dispfind[FINDS]; int size, nbest=NBEST, ncrit=0, ndisp=0; uint maxstep=0, mod=0; char criterion='c'; uint modsize (uint s) { uint r, b=s, a=coresize; if (s == 0 || s == 1) return s; while (r=a%b) { a = b; b = r; } return b; } double classic (uint m, uint s) { uint t, u; if (s == 0) return 0; t = m % s; u = m / s; if (t == 0) return (double) s * (u - 1); if (t < s - t) return classic (s, t) * u + classic (t, s % t) + (double) (u - 1) * s + (double) t; else return classic (s, s - t) * u + classic (t, s - t) + (double) (u - 1) * s + (double) t; } double alternate (uint m, uint s) { uint t, u; if (s == 0) return (double) 0; t = m % s; u = m / s; if (t == 0) return (double) (u - 2) * 0.5 * m + (double) s - (double) (u - 1) * 0.25 * u * s; if (t < s - t) return alternate (s, t) * u + alternate (t, s % t) + (double) (u - 2) * 0.5 * m + (double) s - (double) (u - 1) * 0.25 * u * s; else return alternate (s, s - t) * u + alternate (t, s - t) + (double) (u - 2) * 0.5 * m + (double) s - (double) (u - 1) * 0.25 * u * s; } double compute (uint s, double (*fn)()) { double score; score = fn (coresize, s) / ((double) coresize / modsize (s) - 1); if (score > 999.9) return 999.9; return score; } uint rec (uint m, uint s, uint x) { uint t, u; if (m <= x) return 0; if (s == 0) return 0; if (s <= x) return (m - x - 1) / s + 1; u = m / s; t = m % s; if (t == 0) return coresize / modsize (s); if (t < s - t) return rec (s, t, x) * u + rec (t, s % t, x) + u; else return rec (s, s - t, x) * u + rec (t, s - t, x) + u; } double find (uint s, uint x) { double score; if (modsize (s) > x) return 999.9; else { score = 100.0 * (rec (coresize, s, x) + 1) * x / coresize; if (score > 999.9) score = 999.9; } return score; } double findmany (uint s, int nfind, uint findl[]) { double score=0.0; int i; for (i=0; i < nfind; i++) score += find (s, findl[i]); return score / nfind; } double makescore (uint step) { switch (criterion) { case 'c': return compute (step, classic); case 'a': return compute (step, alternate); case 'f': return findmany (step, ncrit, critfind); } } #define printtext(t,x) printf (tformat, t, x) #define printright(x) printf (rformat, x) #define printleft(x) printf (lformat, x) void printscore (uint step, double score, int dodisplay) { int i; if (score < 0.0 && !dodisplay) return; if (printer) printtext (";", step); else printtext ("Step", step); if (!mod) { printf (" Mod"); printleft (modsize (step)); } if (score >= 0.0) { if (score < 1000.0) printf (" Score: %6.2lf", score); else printf (" Score: 999.99"); } if (dodisplay) { if (display & DISP_CLASSIC) printf (" Classic: %6.2lf", compute (step, classic)); if (display & DISP_ALTERNATE) printf (" Alternate: %6.2lf", compute (step, alternate)); for (i=0; i < ndisp; i++) { printf (" Finds"); printleft (dispfind[i]); printf (" %5.1f%%", find (step, dispfind[i])); } } printf ("\n"); } void printsettings (void) { int i; if (verbose) { if (printer) printf ("; "); printf ("Coresize %u.", coresize); if (mod) printf (" Mod-%u.", mod); if (maxstep) printf (" Maximum %u.", maxstep); if (nbest) printf (" Best %d.", nbest); if (criterion) { printf (" Scoring: "); switch (criterion) { case 'c': printf ("classic"); break; case 'a': printf ("alternate"); break; case 'f': printf ("find"); for (i=0; i best[i] * sign || beststep[i] == 0) { if (verbose == 2) printscore (step, score, 0); for (j=nbest-1; j>i; j--) { best[j] = best[j-1]; beststep[j] = beststep[j-1]; } best[i] = score; beststep[i] = step; break; } } } } else printscore (step, -1.0, 1); } if (criterion) { if (verbose == 2) { if (printer) printf ("; "); printf ("Best:\n"); } for (i=0; i