Results 1 to 7 of 7

Math Help - Algorithm help

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    21

    Algorithm help

    I am terrible with algorithms but here goes

    Suppose one wants to find, for a given list of distinct numbers, the sum of the products of every pair of different numbers in the list. For example, if the list consists of 4, 10, 20, 100 then we would compute 4*10 + 4*20 + 4*100 + 10*100 + 20*100 = 3720

    The task is to write out an algorithm for the above calculation for an arbitrary list of n distinct numbers.

    I am lost and don't know where to begin
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by minkyboodle View Post
    I am terrible with algorithms but here goes

    Suppose one wants to find, for a given list of distinct numbers, the sum of the products of every pair of different numbers in the list. For example, if the list consists of 4, 10, 20, 100 then we would compute 4*10 + 4*20 + 4*100 + 10*100 + 20*100 = 3720

    The task is to write out an algorithm for the above calculation for an arbitrary list of n distinct numbers.

    I am lost and don't know where to begin
    Why didn't you have 10*20?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    21
    because I missed it
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by minkyboodle View Post
    because I missed it
    Algo Hint

    For i = 1 to n-1
    For j = (i+1) to n
    sum = sum + a_i*a_j

    Can you complete?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    Suppose there were n numbers in the list. Then if you simply multiply all the pairs together, which seems to be what aman_cc is suggesting you have to do n*(n-1)/2 multiplications. So for 10 numbers that would be 45 multiplications. But you can do it with only 11 multiplications and one division like this:
    Add all the numbers together, and square the result
    Add the squares of all the numbers together.
    Subtract the second number from the first and divide by 2.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2009
    Posts
    21
    Quote Originally Posted by alunw View Post
    Suppose there were n numbers in the list. Then if you simply multiply all the pairs together, which seems to be what aman_cc is suggesting you have to do n*(n-1)/2 multiplications. So for 10 numbers that would be 45 multiplications. But you can do it with only 11 multiplications and one division like this:
    Add all the numbers together, and square the result
    Add the squares of all the numbers together.
    Subtract the second number from the first and divide by 2.

    so to write that it would be?

    I get what you are saying but I can't figure out how to put it into math writing
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    I think you should try to do a little more work yourself now. In any case I don't know what system you are supposed to be using for writing down your algorithm. I've used a form of the binomial theorem here, or whatever its equivalent for more than two terms is called.
    Why not try to use the same kind of language aman_cc used, but to describe my algorithm instead.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 19th 2010, 02:46 AM
  2. Algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: November 22nd 2009, 07:11 AM
  3. algorithm
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: July 16th 2008, 01:29 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2008, 01:02 PM
  5. gcd algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2007, 11:47 PM

Search Tags


/mathhelpforum @mathhelpforum