Date 25 Aug 2005 17:40:29 -0400 From linux@horizon ... Subject Re: Need better is_better_time_interpolator() algorithm
> (frequency) * (1/drift) * (1/latency) * (1/(jitter_factor * cpus))

(Note that 1/cpus, being a constant for all evaluations of this
expression, has no effect on the final ranking.)
The usual way it's done is with some fiddle factors:

quality_a^a * quality_b^b * quality_c^c

Or, equivalently:

a * log(quality_a) + b * log(quality_b) + c * log(quality_c)

Then you use the a, b and c factors to weight the relative importance
of them. Your suggestion is equivalent to setting all the exponents to 1.

But you can also say that "a is twice as important as b" in a
consistent manner.

Note that computing a few bits of log_2 is not hard to do in integer
math if you're not too anxious about efficiency:

unsigned log2(unsigned x)
{
unsigned result = 31;
unsigned i;

assert(x);
while (!x & (1u<<31)) {
x <<= 1;
result--;
}
/* Think of x as a 1.31-bit fixed-point number, 1 <= x < 2 */
for (i = 0; i < NUM_FRACTION_BITS; i++) {
unsigned long long y = x;
/* Square x and compare to 2. */
y *= x;
result <<= 1;
if (y & (1ull<<63)) {
result++;
x = (unsigned)(y >> 32);
} else {
x = (unsigned)(y >> 31);
}
}
return result;
}

Setting NUM_FRACTION_BITS to 16 or so would give enough room for
reasonable-sized weights and not have the total overflow 32 bits.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html