# Averaging Algorithm

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 04-15-2006
Mr207
Averaging Algorithm
Hi,

This is my first time posting here. I'm taking a programming class, and one of our assignments is to write a program that calculates the average of a group of numbers without the use of division. The code itself isnt so much the problem, but I am having trouble coming up with an algorithm to do it. I know this isnt so much a programming question but a math question, but I'm hoping theres a math whiz here who can give me a hand. Even a hint would help really.

• 04-16-2006
Salem
Which sort of average
- mean
- median
- mode

http://mathworld.wolfram.com
• 04-16-2006
Rashakil Fol
There's no way to compute a mean of an arbitrary number of elements without using division. If you end up thinking you've done so, then you've implemented a division algorithm. So let's pray your teacher meant median or mode. (But then why would the teacher bother specifying not to use division?)

If you know beforehand the size of the group of numbers, then you can just multiply. For example, if you know there will be ten numbers to average, you could just multiply the sum by 0.1.
• 04-16-2006
grumpy
You might want to consider the mathematical relation log(x/y) = log(x)-log(y) (if x and y are both positive).
• 04-16-2006
jafet
You don't need division to perform division! ;)

Using Newton-Rhapson with f(x) == 1/x - N, you can approximate 1/N like this:

X0 = first approximation, close to but smaller than 1/N
Xk+1 = Xk * (2 - Xk * N)

If Xk has z digits of precision, Xk+1 will have around 2*z digits of precision (ie it converges to 1/N quadratically), so complexity for z digits of 1/N is O(log z M(N)) where M(N) is multiplication cost.

Then take the sum, and multiply by this number to the required degree of precision!

I have no idea if this is cheating, though... :rolleyes:
• 04-16-2006
Salem
Gotta love these pointless homework questions which ask you to solve fairly trivial problems by restricting the allowed set of operators you can use.

Like the "how to do addition without using +" problem which happens every so often.
• 04-16-2006
bumfluff
Could he not just find out how many numbers there are in the list that he needs to find the average of? And then use Rashakil Fol's idea?
• 04-16-2006
c89c
yeah, just take the number of numbers you have and a decimal place to it to the left.
• 04-16-2006
grumpy
Quote:

Originally Posted by c89c
yeah, just take the number of numbers you have and a decimal place to it to the left.

That only works if the number is 10.
• 04-17-2006
bumfluff
Yeah I was trying to figure out ways around that after I posted.

Could you not just cheat and make sure that you can only have a number of values between a certain range.
• 04-17-2006
bumfluff
This is what I made that does that:

Code:

```#include <iostream.h> #include <windows.h> #include <cstdlib> using namespace std; int main() {       int numvalues;       int values [20];       int intermediary;       int x = 0;       float y;       float answer;       cout << "Please enter the number of values you have (1-20): ";       cin >> numvalues;       cout << endl;       for (int i = 0; i < numvalues; ++i)       {           cout << "Enter Value number " << i+1 << ": ";           cin >> intermediary;           values [i] = intermediary;       }       for (int j = 0; j < numvalues; ++j)       {           x += values [j];       }       cout << endl << "The total of your values is: "<< x << endl;       cout << endl << "Press [ENTER] to get your answer...";       cin.ignore();       cin.get();       switch (numvalues) {             case 1:                   y = 1;                   break;             case 2:                   y = 0.5;                   break;             case 3:                   y = 0.3333333333;                   break;             case 4:                   y = 0.25;                   break;             case 5:                   y = 0.2;                   break;             case 6:                   y = 0.1666666666;                   break;             case 7:                   y = 0.1428571428;                   break;             case 8:                   y = 0.125;                   break;             case 9:                   y = 0.1111111111;                   break;             case 10:                   y = 0.1;                   break;             case 11:                   y = 0.0909090909;                   break;             case 12:                   y = 0.0833333333;                   break;             case 13:                   y = 0.0769230769;                   break;             case 14:                   y = 0.0714285714;                   break;             case 15:                   y = 0.0051282051;                   break;             case 16:                   y = 0.0051282051;                   break;             case 17:                   y = 0.0588235294;                   break;             case 18:                   y = 0.0555555555;                   break;             case 19:                   y = 0.0526315789;                   break;             case 20:                   y = 0.5;                   break;             default:             cout << "You have entered too many values you will have to restart the program!"<<endl;             cout << endl;             cout << "Press [ENTER] to exit...";             cin.get();             return 1;       }       for (int k = 0; k < 4; ++k)       {           system("CLS");           cout << "Please wait while your answer is calculated.";           Sleep (600);           cout << ".";           Sleep (600);           cout << ".";           Sleep (600);       }       answer = x*y;       cout << endl << endl << "The answer is: " << answer << endl;       cout << endl << "Press [ENTER] to close...";       cin.get();       return 0; }```
• 04-17-2006
The Wazaa
I like the thing where you let the user wait 1.2 seconds for an operation performed in less than 5 milliseconds (probably even shorter time) ;)

But I don't really see the point in finding the average without using division, on the other hand I don't see any point in writing the programs we gets as assignment in my school. Although we are allowed to use division in our average-algorithms :)
• 04-17-2006
grumpy
bumfluf your approach won't work for number of values > 20.

I hinted at one approach earlier; looks like I need to spell it out;
Code:

```#include <cmath> #include <iostream> int main() {     double sum;     int n;         // somehow initialise previous two values ...     double average;     if (n > 0)     {         average = std::exp(std::log(std::fabs(sum)) - std::log((double)n)) * ((sum > 0) : 1 : -1);         std::cout << "Average is " << average << '\n';     }     else     {           std::cout << "Cannot compute average if number of values < 0\n";     }    }```
You might also wish to consider what the expression "sum*std::pow((double)n, -1.0)" yields.
• 04-17-2006
qqqqxxxx
as an approximation:
Code:

```#include<stdio.h> main(){  int a=35;  int b=46;  while((b-a)>1){   a++;   b--;  }  printf("%d",a); }```

Code:

```#include<stdio.h> main(){  float a=35;  float b=46;  while((b-a)>0.001){   a+=0.001;   b-=0.001;  }  printf("%f",a); }```
• 04-17-2006
Ideswa
Quote:

Originally Posted by grumpy
bumfluf your approach won't work for number of values > 20.

His program does work with values > 20! I compiled and ran it. It works perfect.

@ bumfluf: use <iostream> instead of <iostream.h>!
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last