Archived

This topic is now archived and is closed to further replies.

RapidStunna

Averaging Numbers "On The Fly"

Recommended Posts

This is probobly a really simple math technique, but I''ve never been taught it because I havn''t had any formal classes with probobility yet. Anyhow, I was looking for a way to find the average amount of times a certain function was being called each frame. Regular averaging (being when you add all your values together and divide by the total amount) didn''t seem to work in this situation. The problem to me was: 1.) If my program terminates randomly, I still want the output of function calls. Regular averaging wouldn''t work because the averaging must occur when all the values are known, which wouldn''t occur until the application was ready to quit. 2.) I needed an extendable number of frames to work with. In other words, If one application took 44 frames, and the next took 3333333, regular averaging techniques would become a problem. For example, using regular averaging, I would need to extend an array of values each frame or allocate a HUGE buffer to store all the possible frame values. In order to solve this, I took a nice shower and thought that if I weighted the number for the new frame and mixed it with the previously-figured-frame-average, then I could find a dynamic average for each frame. Let me show you it in psuedo code: If my values end up being 2,4,6, and 8, regular averaging would find an average of 5. (2+4+6+8=20/4=5). Using dynamic averaging, I use this formula for each frame -- Let a = previous average Let n = new number of mix in Let w1 and w2 be weight values Let s = number of values CURRENTLY averaged in w1=s/(s+1) w2=1-s a=a*w1+n*w2 -- By doing that each frame, you get a dynamic average. It''s pretty simple, but just thought I''d share it with the forums since it''s my new tidbit to work with. Doing some simple tests, I found it to be just about 100% accurate. Some rare cases it ended up being .1 off when using all integers. The only real downfall is that compared to regular averaging, it''s rougly 66% slower. If you compare that to the memory you''d be allocating though, it seems well worth the use. Tell me what you think of it, or insult me for wasting my time thinking of something that''s already been thought of. In either case, post back . ---
Brent Gunning | My Site

Share this post


Link to post
Share on other sites
Let a1 be the previous frame's average, a2 be this frame's average, n be the number of frames, and x be the current frame's value.

a2 = (a1 / (n - 1) + x) * n
= a1 * n / (n - 1) + x * n

Looks right to me. I wouldn't call them "weight" values, however.

You could just add up the x for each frame, then divide that by n when you want output, that would be faster by eliminating the divide and multiply ops each frame. If you're worried about abnormal termination, you could just output the sum and frame count values, and calculate the average by hand (final sum/final frame count).

EDIT: Damn spelling. "your" != "you're"

Image loads when I'm online!The following statement is true. The previous statement is false.
Shameless promotion:
FreePop: The GPL Populous II clone.

[edited by - doc on July 28, 2003 9:30:36 PM]

Share this post


Link to post
Share on other sites
You could keep a running tally of the total number of times the function has been called and the total number of frames that have occured. Then each frame, divide total calls by total frames, and you''ve got your average. Each frame would need one addition, one increment (frames increased by one, which you''re probly already doing) and one divide.

Another way would be to multiply the previous average by the previous number of frames, add the newest number of calls, then divide by the new number of frames. This is basically the same as above, except your store the previous average, not the previous number of calls. I don''t see any advantage to this, but you might. Each frame would need one multiply, one add, one increment and one divide.

I think both of these would be faster than your add, divide, subtract, multiply, multiply and add. I don''t imagine the speed difference is enough to worry about though. The first suggestion might be more accurate however, in that 3333332/3333333 is very nearly 1, and prone to rounding, and you do that sort of divide every frame, so errors would accumulate and get worse over time, probly geometrically...

Share this post


Link to post
Share on other sites
quote:
You could just add up the x for each frame, then divide that by n when you want output, that would be faster by eliminating the divide and multiply ops each frame. If you're worried about abnormal termination, you could just output the sum and frame count values, and calculate the average by hand (final sum/final frame count).

quote:
You could keep a running tally of the total number of times the function has been called and the total number of frames that have occured. Then each frame, divide total calls by total frames, and you've got your average. Each frame would need one addition, one increment (frames increased by one, which you're probly already doing) and one divide.

Another way would be to multiply the previous average by the previous number of frames, add the newest number of calls, then divide by the new number of frames. This is basically the same as above, except your store the previous average, not the previous number of calls. I don't see any advantage to this, but you might. Each frame would need one multiply, one add, one increment and one divide.


Good points. I see one problem with that though. If I'm averaging a common function call (ie. AddVertex), that running total might get too high for the variable. Well, I'm not sure. Do you think that if you took a popular game and did this with an _int64, that it would overflow?

---
Brent Gunning | My Site

[edited by - RapidStunna on July 28, 2003 9:41:10 PM]

Share this post


Link to post
Share on other sites
2^64 = 18446744073709551616

10^8 AddVertex calls per frame at 1000 frames / second would take 184467441 seconds or 2135 days or 5.85 years.

Edit: According to:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/_langref_Data_Type_Ranges.asp

the range of __int64 is only –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 so you'll have to cut that running time in half. Shucks.

[edited by - Geoff the Medio on July 28, 2003 9:53:38 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by RapidStunna
Good points. I see one problem with that though. If I''m averaging a common function call (ie. AddVertex), that running total might get too high for the variable. Well, I''m not sure. Do you think that if you took a popular game and did this with an _int64, that it would overflow?



If the total is too large to fit in the variable, then your scheme of updating the average will also fail due to lack of precision.

I would use a 64-bit int to keep track of the total because:

2^31 / ( 100000 verts/frame * 100 frames/second ) = 215 seconds

Share this post


Link to post
Share on other sites