Re: asking suggestions on the algorithm in compution.Thanks.

From: Yan ZHANG (buaanupt_at_sina.com)
Date: 11/01/04

  • Next message: James H. Power: "Is there a "taxonomy" of statistical analysis approaches?" 
    Date: Mon, 1 Nov 2004 11:38:59 +0800

    It is so great. Thank you very much for your very helpful comments. 

    -- 
Yan ZHANG
Wireless Communications Laboratory, NICT Singapore
National Institute of Information&Communications Technology (NICT)
Science Park II, Singapore
http://www.ntu.edu.sg/home5/pg01308021
"Paul A. Rubin" <rubin@msu.edu> wrote in message
news:clueej$1p9q$1@msunews.cl.msu.edu...
> ZHANG Yan wrote:
> > Thank you very much for your comments. I am very sorry that I have not
> > stated the questions very clearly. Hope that the following is more
> > clear.
> >
> > //////////////////////////////////////////////////////////////////////
> > Input: k,A,b
> > //k is integer; A is integer; b is integer
> > Output:X
> >
> > X = 0.0
> > for k = 1..A
>
> You're contradicting yourself here.  Either k is an input or k is a loop
> index; it cannot be both.  I'll assume you meant it to be a loop index.
>
> >   for all possible set (m_1,m_2,...,m_k) satisfying m_1+m_2+...+m_k =
> > b
> >      X = X + f_1(m_1) * f_2(m_2) * ... * f_k(m_k)
> >   end
> > end
> >
> > //in this algorithm, f_i(m_i) is a function with m_i as input.
> >
> >
> > The difficulty lies in the fact that there are too many possible
> > combination of set (m_1,m_2,...,m_k) satisfying m_1+m_2+...+m_k = b.
> > So, the number of cycle is ver high.
> >
> > Can you plz give some suggestions in reduce the computation time and
> > complexity? Thank you very much.
> > --
> > Y.ZHANG
>
> I assume that you want the m_j to be either positive or nonnegative
> integers as well (?).
>
> The first thing to do is to tabulate f_1(x) for x=0,...,b and save that,
> then tabulate f_2(x) for x=0,...,b, etc.  That way you won't be wasting
> time recomputing them each time they are used.  (This assumes you have
> enough memory to retain the tables.)
>
> To do the summation, use recursion.  Define a function g(bb,kk) (where
> bb is the right hand side of the constraint, and kk is the index of the
> last f function being used), as follows:
>
> g(bb,kk) = sum {x=0...bb} f_kk(x)*g(bb-x,kk-1)
>
> g(bb,1) = f_1(bb)
>
> Your k-th sum then should be g(b,k).  To get additional speed reductions
> (at the cost of increased memory use), you can put each computed value
> of g in a table, so that you can look it up if/when it is used again
later.
>
> How much total work is this?  We have A*(b+1) function evaluations
> f_j(x) up front.  After that, we tabulate g(bb,kk) for bb=0...b and
> kk=2...A, so we compute (A-1)(b+1) values of g().  Computing g(bb,kk)
> involves bb+1 multiplications, bb+1 additions (assuming you initialized
> the running total to 0), and 2*(bb+1) lookups.  So the total work for
> g(bb,kk) is proportional to bb+1, which means the work to tabulate
> g(bb,kk) for all bb=0...b is O(b^2), and so the work to tabulate all
> values of g is O(A*b^2).
>
> -- Paul
>
>
****************************************************************************
**************
> Paul A. Rubin                                                    Phone:
>     (517) 432-3509
> Department of Management                                Fax:      (517)
> 432-1111
> The Eli Broad Graduate School of Management    E-mail:   rubin@msu.edu
> Michigan State University
> http://www.msu.edu/~rubin/
> East Lansing, MI  48824-1122  (USA)
>
****************************************************************************
**************
> Mathematicians are like Frenchmen:  whenever you say something to them,
> they translate it into their own language, and at once it is something
> entirely different.                                    J. W. v. GOETHE
  • Next message: James H. Power: "Is there a "taxonomy" of statistical analysis approaches?"

    Relevant Pages
    • Quantcast