Ealdwulf Wuffinga wrote: > > For git-bisect, Sam and H Peter are proposing a heuristic to trade off > between information gained and likelihood of testing a bad commit. For > bbchop, I am already doing calculating the information gain directly, > so if I can incorporate the probability that a commit is broken - has > to be skipped - then the trade-off will happen automatically. > Therefore it would be useful to have some plausible theory as to how > the probability of a broken commit should be calculated, given some > known-broken and known-not-broken commits. > Again, given a bisection, the information gain by "bisecting" at point x where 0 < x < 1 is: -(x log2 x)-((1-x) log2 (1-x)) At x = 0.5 this gives the optimal 1 bit, but the curve is rather flat near the top. You don't drop to 1/2 bit of information until x = 0.11 or 0.89, and it doesn't drop to 1/4 bit of information until x = 0.04 or 0.96. Thus, the lack of optimality in searching away from a skip point is much smaller than the potential cost of having to having to skip multiple nearby points. -hpa -- H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html