1. ## 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.

2. Which sort of average
- mean
- median
- mode

http://mathworld.wolfram.com

3. 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.

4. You might want to consider the mathematical relation log(x/y) = log(x)-log(y) (if x and y are both positive).

5. 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...

6. 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.

7. 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?

8. yeah, just take the number of numbers you have and a decimal place to it to the left.

9. 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.

10. 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.

11. 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;

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;
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");
Sleep (600);
cout << ".";
Sleep (600);
cout << ".";
Sleep (600);
}

cout << endl << endl << "The answer is: " << answer << endl;
cout << endl << "Press [ENTER] to close...";
cin.get();
return 0;
}```

12. 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

13. 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.

14. 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);
}```

15. 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>!