Re: A super-efficient way to compute the sum of A[i] *

For reference on fast sequential algorithms for computing the dot product,
see this:

https://lemire.me/blog/2018/07/05/how-quickly-can-you-compute-the-dot-product-between-two-large-vectors/


On Sat, May 9, 2020 at 10:52 AM Dimitre Novatchev <dnovatchev@xxxxxxxxx>
wrote:

> Hi Roger,
>
>   > I need a super-efficient 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() (for-each-pair() 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 map-reduce 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 <
> xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
>
>> Hi Folks,
>>
>> I need a super-efficient 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.