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

On Sat, 2020-05-09 at 11:59 +0000, Costello, Roger L.
costello@xxxxxxxxx wrote:
> 
...
> 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.

At a rough guess, if you are doing hundreds of thousands of these
computations -- so, something on the order of 1.0E6, and not 1.0E9 or
1.0E12 or more -- then you probably spent more clock time writing your
email of inquiry than you would spend waiting for the calculations to
finish, even in the unluckiest possible formulation interpreted by the
least efficient of all possible implementations.

If you are in fact sitting drumming your fingers waiting for a
calculation like this to complete, then either there are a lot more
multiplications and additions to be performed than you say, or the
bottleneck is somewhere else.  (Or both: if you have hundreds of
millions or hundreds of thousands of millions of 'col' elements to go
through, you may be looking at an I/O bound computation, in which case
tweaking the way your arithmetic is expressed might not help much.)

In any case, as formulated, the question you ask seems unlikely to
have any useful answer. Since the speed of interpretation is a
function both of the formulation of the program and the language
processor used, there is never a "most efficient approach" in general,
only with respect to specific processors, or specific classes of
processor, and only with respect to specific resources.  In some
situations, for example, it is desirable to minimize use of CPU
cycles; in other situations, it is better to conserve space.  In some
situations, on the other hand, both the cost of CPU cycles and that of
space are dwarfed by the cost of programmer time.  In the latter
situations, the most efficient formulation will almost always be the
one which is simplest to write, simplest to read, and easiest to
confirm correct.  (And sometimes, miraculously, or as the result of
some very hard work, in some implementations of some languages those
formulations are also the ones most effectively optimized by the
language processor.  Win/win!)

I hope this helps.

Michael Sperberg-McQueen