1
$\begingroup$

We are currently looking for a fast, i.e. subquadratic, algorithm for the following equation: $z_m = \sum_{i,j :\, (i \cdot j) = m} x_i \cdot y_j$.

That is, we are given two finite input vectors $x$ and $y$ and are trying to calculate the full vector $z$, where each element $z_m$ in $z$ consists of the sum of the pairwise products of elements in the input vectors $x_i$ and $y_j$, whose indices $i$ and $j$ result in $m$ after multiplication.

A bit on the background: we are trying to efficiently multiply two probabilistic mass functions.

Since this problem is closely related to standard convolution (when changing product to sum): $z_m = \sum_{i,j :\, (i + j) = m} x_i \cdot y_j$,

we already found out that it would be possible to log-transform the indices of the input vectors and rediscretize/bin them. Then you could use FFT-convolve to get the log-transformed $z$ vector, which has to be exponentiated (on the indices) in the end. However, discretization most probably results in errors (depending on the resolution of the rediscretization) as well as increases the overall runtime because of the increasing length of the input vectors.

Does anyone know about an alternative solution to this problem (maybe with a hint to an existing implementation or on implementation details)? We have also looked at some theory on log-convolution/scale convolution (https://en.wikipedia.org/wiki/Logarithmic_convolution, with an implementation here) since it seems to be at least very closely related. However, we are not sure if and how the rather complex theory applies to our discrete problem directly.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

There is little room for improvement over brute force because the average number of collisions is a very slowly growing function.

The Erdős multiplication table problem asks how many numbers are products $ab$ with $1\le a,b \le n$. It is known that the count is $$\Theta\left(\frac{n^2}{(\log n)^c (\log\log n)^{3/2}}\right)$$ where $c=1-(1+\log\log 2)/\log 2 = 0.086$. So, if you multiply random variables with full support $\{1,...,n\}$, you get almost $n^2$ values with positive probability. The denominator is under $10$ for $n$ up to about $10^{18}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot for your concise answer. That makes a lot of sense. We came up with small strategies that seemed to reduce the theoretical runtime by a (hard-to-quantify) bit but not much (which is certainly related to the bound you mentioned). Runtime constants for non-brute-force approach might make it even slower in practice. I accepted this as the correct answer. $\endgroup$
    – julepf
    Commented Apr 1, 2016 at 10:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .