xsl-list
[Top] [All Lists]

Re: [xsl] A super-efficient way to compute the sum of A[i] * B[i] for i=1 to n?

2020-05-09 12:53:07
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(_at_)mitre(_dot_)org 
<
xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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.
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--
<Prev in Thread] Current Thread [Next in Thread>