On Fri, 2010-11-19 at 17:28 -0500, Bob Copeland wrote: > On Fri, Nov 19, 2010 at 06:07:05PM +0900, Bruno Randolf wrote: > > Hmm, maybe I suck in mathemathics, but I don't see a way to do that given the > > formula: > > > > (((internal * (weight - 1)) + (val * factor)) / weight > > I was thinking something along the lines of: > > round = (1 << n) - 1; > (((internal * (weight - 1) + round) >> n) + val) * ((1 << n) / weight) > > where (1 << n) is the factor and ((1 << n) / weight) can be precomputed. > If you think about it, this is just reciprocal multiplication in fixed- > point math with n bits of decimal resolution. > > The problem is the shift of the older terms introduces roundoff error, but > there are some tricks you can do to maintain bounded error, e.g. shifting > by some smaller factor of n and scaling other terms -- in the limit you > reinvent floating point and then it's slower than division :) Sure, x/y := x/z * z/y, and by picking z := 2^n, we can pre-compute z/y and write x/z using a shift. The problem however is always range vs granularity, you chose to first /z and then *z/y, this avoids some overflow issues but truncates the lower n bits of x. If you first *z/y and then /z you keep your low bits but risk loosing the top bits to an overflow. I guess the question is do we really need weights outside of 2^n? If not, you can use the weight := 2^n version. If you do, you get to pick either of the previously mentioned options. Sadly gcc doesn't sanely support a u128 type, which would be very useful to avoid some of these overflow issues (like we used to use u64 mults for u32 fixed points mults). -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
