11
$\begingroup$

Suppose I have two lists of positive integers of bounded manitude, and I take the product of all elements of each list. What's the best way to determine which product is larger?

Of course I can simply compute each product, but I'm hoping there's a more efficient approach, as the number of digits in the products will increase linearly with the number of terms, so that the whole computation is quadratic.

If I were adding instead of multiplying, I could use a "zippering strategy" of incrementally adding entries from the first list and subtracting from the second, circumventing the need to compute the (large) overall sums. The analogous techniques for products would be to sum the logarithms of the entries, but the problem now is that computing the logs requires use of inexact arithmetic. Unless there's some way to prove the numerical error is irrelevant?

$\endgroup$
  • $\begingroup$ If we know the max integer value and that is independent of n (i.e., a constant k) then we can make a lookup table of the factors of all numbers from 1 to k. Now I think if you write everything in base [product of factors] it becomes linear since you can compute the products in linear time with that base then compare each digit (starting with highest order digit) in turn until one is greater than the other. The details there are a little tricky but I think that should work if k is a constant. $\endgroup$ – Phylliida May 29 '17 at 20:46
  • $\begingroup$ I'd rather say that the analogous technique for products is to keep a rational number equal to the first elements of the first list divided by the first elements of the second one (plus handling $0$s). But that's not really helpful because if all number are coprime, it will compute both products. | Also I'm not sure that the naive algorithm is quadratic. Computing a product of $n$ integers of size $m$ can take up to $C(m,m)+C(m,2m)+...+C(m,(n-1)m)$ where $C(x,y)$ is the cost of multiplying a $x$-bits integers with a $y$-bits integers.Unless you consider that the products also fit in the format $\endgroup$ – xavierm02 May 29 '17 at 23:06
  • 1
    $\begingroup$ There may be some way to extend the method in math.stackexchange.com/a/1081989/10385 $\endgroup$ – xavierm02 May 29 '17 at 23:32
  • $\begingroup$ An improvement on the naive approach: count the number of occurrences of each factor (in linear time), and only compute the product at the end, using an efficient powering algorithm. This works in time $O(M(n))$, which is $O(n\,\log n\,2^{O(\log^*n)})$ using the current asymptotically fastest method. $\endgroup$ – Emil Jeřábek May 30 '17 at 8:55
  • 2
    $\begingroup$ I will think about the needed accuracy for log's. It may actually be more efficient. $\endgroup$ – Emil Jeřábek May 30 '17 at 8:57
7
$\begingroup$

(I understand the description of the problem so that the input numbers are bounded by a constant, so I will not track dependence on the bound.)

The problem is solvable in linear time and logarithmic space using sums of logarithms. In more detail, the algorithm is as follows:

  1. Using binary counters, count the numbers of occurrences of each possible input number in both lists.

This takes time $O(n)$, and the counters use space $O(\log n)$, as each counter is bounded by $n$ in value.

Let $p_1,\dots,p_k$ be the primes below the $O(1)$ bound. By distributing each counter for a number $a$ to the prime factors of $a$ (with appropriate multiplicity), and subtracting the counts for one list from the other list, we obtain the following in time $O(\log n)$:

  1. Compute integers $\beta_1,\dots,\beta_k$ with $O(\log n)$ bits such that the problem is equivalent to determining the sign of $\Lambda:=\sum_{i=1}^k\beta_i\log p_i$.

  2. If $\beta_1=\dots=\beta_k=0$, answer that the products are equal.

Otherwise $\Lambda\ne0$. By Baker’s theorem, we can lower bound $$|\Lambda|>2^{-C\log n}$$ for a certain constant $C$. Thus, the following correctly computes the sign of $\Lambda$:

  1. Output the sign of $\sum_{i=1}^k\beta_i\pi_i$, where $\pi_i$ is an approximation of $\log p_i$ to $m:=C\log n+k+1$ bits of accuracy.

Let $M(m)$ be the cost of multiplication of two $m$-bit integers. The current best bound is $M(m)=O(m\,\log m\,2^{O(\log^* m)})$, but here it would not make much difference even if we use the trivial $O(m^2)$ multiplication algorithm. We can compute $\log p_i$ to $m$ bits of accuracy in time $O(M(m)\log m)$ using AGM iteration (see e.g. here), and then evaluating $\sum_i\beta_i\pi_i$ takes time $O(M(m))$. Overall, step 4 takes time $O(M(m)\log m)\subseteq O(\log n\,\mathrm{poly}(\log\log n))$.

Thus, the running time of the algorithm is dominated by $O(n)$ of the first step.

$\endgroup$
  • $\begingroup$ Thanks! I'll have to work through the details later, but this seems very promising! $\endgroup$ – user168715 May 30 '17 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.