Thread: Averaging Algorithm

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    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.

    Thanks in advance.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Which sort of average
    - mean
    - median
    - mode

    http://mathworld.wolfram.com
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    You might want to consider the mathematical relation log(x/y) = log(x)-log(y) (if x and y are both positive).

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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...
    Last edited by jafet; 04-16-2006 at 08:17 AM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    545
    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. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    22
    yeah, just take the number of numbers you have and a decimal place to it to the left.

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.

  10. #10
    Registered User
    Join Date
    Nov 2005
    Posts
    545
    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. #11
    Registered User
    Join Date
    Nov 2005
    Posts
    545
    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;
    }

  12. #12
    Registered User
    Join Date
    Jan 2006
    Location
    Sweden
    Posts
    92
    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. #13
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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. #14
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    as an approximation:
    Code:
    #include<stdio.h>
    main(){
     int a=35;
     int b=46;
    
    
     while((b-a)>1){
      a++;
      b--;
     }
    
     printf("%d",a);
    }







    for added accuracy:
    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);
    }
    Last edited by qqqqxxxx; 04-17-2006 at 04:35 AM.

  15. #15
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    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>!
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM