Subject: Re: [xsl] A superefficient way to compute the sum of A[i] * B[i] for i=1 to n? From: "Dimitre Novatchev dnovatchev@xxxxxxxxx" <xsllistservice@xxxxxxxxxxxxxxxxxxxxxx> Date: Sat, 9 May 2020 17:52:59 0000 
Hi Roger, > I need a superefficient way to compute the sum of A[i] * B[i] for i=1 to n. In case you have n cores / processors, and the compiler knows to optimize functions like map(), zipWith() (foreachpair() in XPath 3.0), then all processors can each do a corresponding multiplication in parallel in a single moment (computing cycle). Then what remains is the summing of the results of these multiplications. This essentially is the mapreduce technique. Interestingly enough, while not all reduce operations can be parallelized, in the case of sum() one can add together n numbers in Log2(n) summing steps  very similar to the DVC (DiVide and Conquer) technique, but doing it parallel  not sequentially. So, first there would be n/2 additions, then n/4 additions (of the results of the first step), then n/8 additions, and so on  in a total of ceiling(Log2(n)) steps. If for each steps we have sufficient number of processors (n/2 for the first step, less for the following steps), then the summing could be performed in Log2(n) computing cycles. So, it seems that the whole computation could be performed in something like ~ ceiling(Log2(n)) + 1 computing cycles. Or maybe I am being wrong here? :) Please, correct me. Cheers, Dimitre On Sat, May 9, 2020 at 4:59 AM Costello, Roger L. costello@xxxxxxxxx < xsllistservice@xxxxxxxxxxxxxxxxxxxxxx> wrote: > Hi Folks, > > I need a superefficient way to compute the sum of A[i] * B[i] for i=1 to > n. > > For example, suppose A is this: > > <row> > <col>0.9</col> > <col>0.3</col> > </row> > > and B is this: > > <row> > <col>0.2</col> > <col>0.8</col> > </row> > > I want to compute: > > (0.9 * 0.2) + (0.3 * 0.8) > > Here's one way to do it: > > sum(for $i in 1 to count($A/col) return number($A/col[$i]) * > number($B/col[$i])) > > I suspect that is not the most efficient approach. > > What is the most efficient approach? I will be doing hundreds of thousands > of these computations, so I want to use the most efficient approach. > > /Roger > >  Cheers, Dimitre Novatchev  Truly great madness cannot be achieved without significant intelligence.  To invent, you need a good imagination and a pile of junk  Never fight an inanimate object  To avoid situations in which you might make mistakes may be the biggest mistake of all  Quality means doing it right when no one is looking.  You've achieved success in your field when you don't know whether what you're doing is work or play  To achieve the impossible dream, try going to sleep.  Facts do not cease to exist because they are ignored.  Typing monkeys will write all Shakespeare's works in 200yrs.Will they write all patents, too? :)  Sanity is madness put to good use.  I finally figured out the only reason to be alive is to enjoy it.
Current Thread 


< Previous  Index  Next > 

Re: [xsl] A superefficient way to , Liam R. E. Quin liam  Thread  Re: [xsl] A superefficient way to , Dimitre Novatchev dn 
Re: [xsl] A superefficient way to , Liam R. E. Quin liam  Date  Re: [xsl] Joining list fragments, Michael MüllerHille 
Month 