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: Sun, 10 May 2020 18:53:34 0000 
For reference on fast sequential algorithms for computing the dot product, see this: https://lemire.me/blog/2018/07/05/howquicklycanyoucomputethedotproductbetweentwolargevectors/ On Sat, May 9, 2020 at 10:52 AM Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote: > 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. > >  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 , Dimitre Novatchev dn  Thread  Re: [xsl] A superefficient way to , Dimitre Novatchev dn 
Re: [xsl] Joining list fragments, Michael MüllerHille  Date  [xsl] Nested foreachgroup and cur, Rick Quatro rick@xxx 
Month 