# Compute a commutative and associative operation on n-2 arguments efficiently

Considering a function $$f$$ such that: $$f(x_1, x_2, x_3) = f(f(x_1, x_2), x_3) = f(x_1, f(x_2, x_3))$$ and $$f(x_1, x_2) = f(x_2, x_1)$$

and a set $$X = \{ x_1, \dots, x_n \}$$; how to compute $$f(x_1, \dots, x_{i - 1}, x_{i + 1}, \dots, x_{j-1}, x_{j+1}, \dots, x_n)$$ for all pairs $$i, j \in 1, \dots, n$$, $$i < j$$ while minimizing the number of calls to $$f$$?

• Only $$f(x)$$ and $$f(x, y)$$ can be computed
• $$f^{-1}$$ is not defined

For example, let $$f$$ be addition, i.e, $$f(x_1, x_2, \cdots, x_n)=x_1+x_2+\cdots+x_n$$. However, only calls to $$f$$ with one or two arguments are allowed, i.e $$f(x)=x$$ and $$f(x_1,x_2)=x_1+x_2$$. In particular, neither subtraction nor negation is allowed. The problem is to compute all sums of $$n-2$$ numbers among the given $$n$$ numbers with the least number of additions. There are $$n(n-1)/2$$ such sums.

• Is $f^{-1}(x)$ known and about as costly to compute as $f(x)$? Jun 19 at 20:20
• (yoseville is right about improving the question rather than commenting comments.) This was more promising if $f(f(x_1, x_2), x_3) = f(x_1, f(x_2, x_3))$. Oh wait, there's another comment think it is associative. Jun 19 at 20:57
• Please edit the question to include all relevant information. Don't just put it in the comments. We want questions to read well for someone who encounters it for the first time, and so people can understand what is being asked without having to read the comments.
– D.W.
Jun 20 at 0:23
• Formally, the problem is either undefined or not answerable. Mathematically, it is entirely possible that the behavior of $f$ on 4 or more arguments is completely unrelated to its behavior on 3 or less arguments, so the information you have given us is not sufficient. I suspect $f$ has additional structure that you have not presented in the question. Perhaps your intention is that $f(x_1,\dots,x_n) = f(f(x_1,\dots,x_{n-1}),x_n) = f(x_1,f(x_2,\dots,x_n))$ for all $n$? What does it mean to say $f(x)$ can be computed (on a single argument?) and how is that relevant?
– D.W.
Jun 20 at 4:01
• Perhaps you mean that it is a binary operation that is commutative and associative? Does it have any other properties? e.g.: is it idempotent? Is it over a semigroup, monoid, or group? Is there an identity? What is the domain of it? Does it have inverse elements?
– D.W.
Jun 20 at 4:07

(1) You can compute $$f(x_1,\dots,x_{i-1})$$ for all $$i$$ with $$n-2$$ calls to $$f$$. (Simply iterate over $$i:=1,\dots,n$$.)

(2) Then, using (1), you can compute $$f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{j-1})$$ for all $$i,j$$ with $$n(n-1)/2$$ more calls to $$f$$. (For each $$i$$, iterate over $$j:=i+2,\dots,n$$.)

(3) You can also compute $$f(x_{j+1},\dots,x_n)$$ for all $$j$$ with another $$n-2$$ calls to $$f$$. (Iterate over $$j:=n,\dots,1$$.)

(4) Finally, using (2) and (3), you can compute $$f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{j-1},x_{j+1},\dots,x_n)$$ for all $$i,j$$ with another $$n(n-1)/2$$ calls to $$f$$.

In all, this uses about $$n^2+n$$ calls to $$f$$.

This is within a factor of 2 of the best possible, as you need to output $$n(n-1)/2$$ different values, so obviously you'll need to make at least $$n(n-1)/2$$ calls to $$f$$.

(Motivation: let $$h = n/2$$.
Given $$f_{ih} = f(x_i\dots x_{h-1}) \text{ and } f_{hj} = f(x_h\dots x_j)$$ (precomputed in about $$n$$ evaluations of $$f$$),
$$f(x_{i+1}\dots x_{j-1})$$ can be computed as $$f(f_{(i+1)h}, f_{h(j-1)})$$ for all $$i\lt h\lt j$$.
This saves ?$$\frac{(n-2)(n-3)} 2 - n$$? evaluations.
Similarly for $$q = n/4, 3q = h+q, o = n/8, 3o = q+o, 5o = h+o, 7o = 3q+o, \dots$$.)

The above promises to be a bookkeeping headache.
Instead, pre-compute $$f(x_{k2^l}\dots x_{(k+1)2^l-1}), 0 in about n evaluations of $$f$$:
Any $$f_{ij}$$ can be computed in less than $$2\lg_2(n)$$ evaluations.

## An example

Let $$f_{\boxed {lk}} := f(x_{k2^l}\dots x_{(k+1)2^l-1})$$

Suppose $$n = 13$$, then $$\lg_2(n) \approx 3.7$$. Since $$l$$ is an integer and $$0 < l \leq 3.7...$$), this means $$l$$ iterates through $$1, 2, 3$$.

## $$l = 1,\quad 2^l = 2$$

$$0 < k < \frac n {2^l} = \frac {13} 2 = 6.5$$

So $$k$$ iterates from $$1$$ to $$6$$ inclusive

$$k=1,\quad f_{\boxed {11}} = f(x_2, x_3)\\ k=2,\quad f_{\boxed {12}} = f(x_4, x_5)\\ k=3,\quad f_{\boxed {13}} = f(x_6, x_7)\\ k=4,\quad f_{\boxed {14}} = f(x_8, x_9)\\ k=5,\quad f_{\boxed {15}} = f(x_{10}, x_{11})\\ k=6,\quad f_{\boxed {16}} = f(x_{12}, x_{13})\\$$

## $$l = 2,\quad 2^l = 4$$

$$0 < k < \frac n {2^l} = \frac {13} 4 = 3.25$$

So $$k$$ iterates from $$1$$ to $$3$$ inclusive

$$k=1,\quad f_{\boxed {21}} = f(x_4 \dots x_7)\\ k=2,\quad f_{\boxed {22}} = f(x_8 \dots x_{11})\\ k=3,\quad f_{\boxed {23}} = f(x_{12} \dots x_{15})\\$$

## $$l = 3,\quad 2^l = 8$$

$$0 < k < \frac n {2^l} = \frac {13} 8 = 1.625$$

So $$k$$ iterates from $$1$$ to $$1$$

$$k=1,\quad f_{\boxed {31}} = f(x_8 \dots x_{15})$$

• (The mechanism is much the same joseville was getting at, just usefulness of the results is guaranteed rather than unlikely.) Jun 20 at 6:14
• Added an example using the limits on $k$ and $l$ you set, but they produce invalid ranges. Either I made a mistake or the limits on 𝑘 and 𝑙 (probably just 𝑘) need to be tweaked slightly. I think the right limit for 𝑘 might be 0≤𝑘<⌊ $\frac n {2^l}$ ⌋ with $f_{\boxed {lk}}$ defined as $f_{\boxed {lk}} := f(x_{k2^l + 1} \dots x_{(k+1)2^l})$. The +1 in $x_{k2^l + 1}$ is due to the $x_i$ being 1-indexed. Jun 21 at 18:57
• But I get the overall concept and I like it. Using "sum" as the operator, basically you want to precompute all non-overlapping $2$-sums, all non-overlapping $4$-sums, all non-overlapping $8$-sums, ..., all non-overlapping $2^l$-sums, etc. Jun 21 at 18:57

Count how many times each $$x_i$$ occurs in the argument list.

Suppose $$X_1$$ is the set of $$x_i$$ that occur once, $$X_2$$ is the set of $$x_i$$ that occur twice, ..., $$X_m$$ is the set of $$x_i$$ that occur $$m$$ times, ... etc.

Suppose $$y \in X_j$$, eventually you will have to evaluate $$f(y)$$ $$j$$ times. So instead of computing $$f(y)$$ $$j$$ times, just compute it once and save the result (in a dictionary, map, w/e).

Suppose $$X_j = \{a, b, c\}$$. You will have to evaluate $$f(a, b, c)$$ $$j$$ times. Instead of computing it $$j$$ times, evaluate it once and save the result.

Suppose $$d \in X_{2^p}$$ for some integer $$p$$. Let

• $$d_0 := f(d)$$
• $$d_1 := f(d, d) = f(f(d), f(d)) = f(d_1, d_1)$$
• $$d_2 := f(d, d, d, d) = f(f(d, d), f(d, d)) = f(d_1, d_1)$$
• ...
• $$d_p := f(\underbrace{d, d, ..., d}_{2^p\ \text{times}}) = f(d_{p-1}, d_{p-1})$$
• I don't understand your answer. Is it clear that the goal is to compute $n(n - 1)$ values? Jun 19 at 16:17
• Not at all. You should read through How to Ask. I think the above makes sense w.r.t. to what you asked. Jun 19 at 16:27
• I don't understand how this answers the question. I don't see an algorithm here that produces the desired output. I don't understand how computing $f(y)$ helps. I don't understand why we would evaluate $f(a,b,c)$ more than once. I don't understand how the $d_i$ help or how they are relevant.
– D.W.
Jun 20 at 4:08
• I think I get the idea. In the light of $x_i$ are not necessarily unique, but are likely to be in practice, it doesn't look helpful. Jun 20 at 4:37