From: Bruno Randolf <br1@einfach.org>
To: Peter Zijlstra <peterz@infradead.org>
Cc: Bob Copeland <me@bobcopeland.com>,
Johannes Berg <johannes@sipsolutions.net>,
Jouni Malinen <j@w1.fi>,
linville@tuxdriver.com, randy.dunlap@oracle.com,
blp@cs.stanford.edu, linux-wireless@vger.kernel.org,
linux-kernel@vger.kernel.org, Lars_Ericsson@telia.com,
stefanr@s5r6.in-berlin.de, kosaki.motohiro@jp.fujitsu.com,
akpm@linux-foundation.org, kevin.granade@gmail.com
Subject: Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average
Date: Thu, 2 Dec 2010 17:12:49 +0900 [thread overview]
Message-ID: <201012021712.49377.br1@einfach.org> (raw)
In-Reply-To: <1290207715.2114.10.camel@laptop>
On Sat November 20 2010 08:01:55 Peter Zijlstra wrote:
> 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).
Thank you all for your help and sorry for following up so late!
I think we don't really need weights outside of 2^n and i'm going to post a
patch based on Peter Zijlstra's formula. Thanks again! Would it make sense to
have the factor 2^n too, so we can bitshift there too?
bruno
next prev parent reply other threads:[~2010-12-02 8:13 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-11-12 3:00 [PATCH v7 0/3] Generic exponentially weighted moving average (EWMA) Bruno Randolf
2010-11-12 3:00 ` [PATCH v7 1/3] Add generic exponentially weighted moving average (EWMA) function Bruno Randolf
2010-11-12 3:00 ` [PATCH v7 2/3] ath5k: Use generic EWMA library Bruno Randolf
2010-11-12 3:00 ` [PATCH v7 3/3] nl80211/mac80211: Report signal average Bruno Randolf
2010-11-16 9:37 ` Jouni Malinen
2010-11-17 8:28 ` Bruno Randolf
2010-11-17 16:16 ` Johannes Berg
2010-11-17 23:11 ` Bob Copeland
2010-11-19 8:49 ` Bruno Randolf
2010-11-19 14:04 ` Stefan Richter
2010-11-22 2:41 ` Bruno Randolf
2010-11-22 7:26 ` Stefan Richter
2010-11-19 17:52 ` Johannes Berg
2010-11-22 2:36 ` Bruno Randolf
2010-11-19 9:07 ` Bruno Randolf
2010-11-19 12:16 ` Peter Zijlstra
2010-11-19 22:28 ` Bob Copeland
2010-11-19 23:01 ` Peter Zijlstra
2010-12-02 8:12 ` Bruno Randolf [this message]
2010-11-19 18:58 ` Johannes Berg
2010-11-22 18:46 ` John W. Linville
2010-11-20 16:45 ` Brian Prodoehl
2010-11-24 16:24 ` Johannes Berg
2010-11-24 19:05 ` Ben Greear
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=201012021712.49377.br1@einfach.org \
--to=br1@einfach.org \
--cc=Lars_Ericsson@telia.com \
--cc=akpm@linux-foundation.org \
--cc=blp@cs.stanford.edu \
--cc=j@w1.fi \
--cc=johannes@sipsolutions.net \
--cc=kevin.granade@gmail.com \
--cc=kosaki.motohiro@jp.fujitsu.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-wireless@vger.kernel.org \
--cc=linville@tuxdriver.com \
--cc=me@bobcopeland.com \
--cc=peterz@infradead.org \
--cc=randy.dunlap@oracle.com \
--cc=stefanr@s5r6.in-berlin.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).