* At each stage, we attampt to choose the guess which will give us the most
* information, regardless of the outcome. For each guess candidate, we
* count the remaining possible codes for each outcome, and choose the
- * candidate with the least square sum. There are wrinkles.
+ * candidate with the least maxmimum bin size. There are wrinkles.
*
* Firstly the number of possible guesses is large, and the number of
* possible codes is huge too; and our algorithm takes time proportional to
* Secondly, when the number of possible codes become small, we want to bias
* the guess selection algorithm towards possible codes (so that we win if
* we're lucky). Since the algorithm chooses the first guess with the lowest
- * sum-of-squares value, we simply run through the possible codes before
+ * max-bin-size value, we simply run through the possible codes before
* enumerating the prototype guesses.
*/
size_t ns; /* Number of remaining guesses */
dig *bg; /* k */ /* Current best guess */
dig *t; /* k */ /* Scratch-space for prototype */
- double bmax; /* Best guess least-squares score */
+ size_t bmax; /* Best guess max partition size */
dig x, bx; /* Next unused symbol index */
- size_t *v; /* (k + 1)^2 */ /* Bin counts for least-squares */
+ size_t *v; /* (k + 1)^2 */ /* Bin counts */
ratectx *r; /* Rate context for search */
} cpc;
unsigned k = c->m.k;
size_t *v = c->v;
size_t *vp;
- double max;
+ size_t max;
rate_init(c->r, g);
memset(v, 0, (k + 1) * (k + 1) * sizeof(size_t));
v[b * (k + 1) + w]++;
}
max = 0;
- for (i = (k + 1) * (k + 1), vp = v; i; i--, vp++)
- max += (double)*vp * (double)*vp;
- if (c->bmax < 0 || max < c->bmax) {
+ for (i = (k + 1) * (k + 1), vp = v; i; i--, vp++) {
+ if (*vp > max)
+ max = *vp;
+ }
+ if (!c->bmax || max < c->bmax) {
memcpy(c->bg, g, k * sizeof(dig));
c->bmax = max;
c->bx = x;
static void best_guess(cpc *c)
{
- c->bmax = -1;
+ c->bmax = 0;
if (c->ns < 1024) {
unsigned k = c->m.k;
const dig *s;