<p>(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.)</p>
<p>The problem is solvable in linear time and logarithmic space using sums of logarithms. In more detail, the algorithm is as follows:</p>
<blockquote>
<ol>
<li>Using binary counters, count the numbers of occurrences of each possible input number in both lists.</li>
</ol>
</blockquote>
<p>This takes time <span class="math-container">$O(n)$</span>, and the counters use space <span class="math-container">$O(\log n)$</span>, as each counter is bounded by <span class="math-container">$n$</span> in value.</p>
<p>Let <span class="math-container">$p_1,\dots,p_k$</span> be the primes below the <span class="math-container">$O(1)$</span> bound. By distributing each counter for a number <span class="math-container">$a$</span> to the prime factors of <span class="math-container">$a$</span> (with appropriate multiplicity), and subtracting the counts for one list from the other list, we obtain the following in time <span class="math-container">$O(\log n)$</span>:</p>
<blockquote>
<ol start="2">
<li><p>Compute integers <span class="math-container">$\beta_1,\dots,\beta_k$</span> with <span class="math-container">$O(\log n)$</span> bits such that the problem is equivalent to determining the sign of <span class="math-container">$\Lambda:=\sum_{i=1}^k\beta_i\log p_i$</span>.</p>
</li>
<li><p>If <span class="math-container">$\beta_1=\dots=\beta_k=0$</span>, answer that the products are equal.</p>
</li>
</ol>
</blockquote>
<p>Otherwise <span class="math-container">$\Lambda\ne0$</span>. By <a href="https://en.wikipedia.org/wiki/Baker%27s_theorem" rel="noreferrer">Baker’s theorem</a>, we can lower bound
<span class="math-container">$$|\Lambda|&gt;2^{-C\log n}$$</span>
for a certain constant <span class="math-container">$C$</span>. Thus, the following correctly computes the sign of <span class="math-container">$\Lambda$</span>:</p>
<blockquote>
<ol start="4">
<li>Output the sign of <span class="math-container">$\sum_{i=1}^k\beta_i\pi_i$</span>, where <span class="math-container">$\pi_i$</span> is an approximation of <span class="math-container">$\log p_i$</span> to <span class="math-container">$m:=C\log n+k+1$</span> bits of accuracy.</li>
</ol>
</blockquote>
<p>Let <span class="math-container">$M(m)$</span> be the cost of multiplication of two <span class="math-container">$m$</span>-bit integers. The current best bound is <span class="math-container">$M(m)=O(m\,\log m\,2^{O(\log^* m)})$</span>, but here it would not make much difference even if we use the trivial <span class="math-container">$O(m^2)$</span> multiplication algorithm. We can compute <span class="math-container">$\log p_i$</span> to <span class="math-container">$m$</span> bits of accuracy in time <span class="math-container">$O(M(m)\log m)$</span> using AGM iteration (see e.g. <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations" rel="noreferrer">here</a>), and then evaluating <span class="math-container">$\sum_i\beta_i\pi_i$</span> takes time <span class="math-container">$O(M(m))$</span>. Overall, step 4 takes time <span class="math-container">$O(M(m)\log m)\subseteq O(\log n\,\mathrm{poly}(\log\log n))$</span>.</p>
<p>Thus, the running time of the algorithm is dominated by <span class="math-container">$O(n)$</span> of the first step.</p>

CC BY-SA 3.0
2017-05-30T17:56:53.200Z
Thanks! I'll have to work through the details later, but this seems very promising!
user168715
CC BY-SA 3.0
2017-05-30T17:44:14.797Z
2017-05-30T17:44:14.797Z
2020-06-17T09:38:08.363Z
Emil Jeřábek
<p>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?</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2017-05-29T20:46:23.833Z
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.
Phylliida
CC BY-SA 3.0
2017-05-29T23:06:49.177Z
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
xavierm02
CC BY-SA 3.0
2017-05-29T23:32:49.147Z
There may be some way to extend the method in https://math.stackexchange.com/a/1081989/10385
xavierm02
CC BY-SA 3.0
2017-05-30T08:55:24.397Z
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.
Emil Jeřábek
CC BY-SA 3.0
2017-05-30T08:57:49.733Z
I will think about the needed accuracy for log's. It may actually be more efficient.
Emil Jeřábek
<time-complexity><nt.number-theory>
Comparing two products of lists of integers?
user168715
# Comparing two products of lists of integers?

(Asked by: username_0 on 2017-05-29)

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?

**Tags:** time-complexity, nt.number-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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  
> **username_2**: There may be some way to extend the method in https://math.stackexchange.com/a/1081989/10385  
> **username_3**: 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.  
> **username_3**: I will think about the needed accuracy for log's. It may actually be more efficient.  

---

## 1 answers

### Answer by username_3 on 2017-05-30. Score: 6 | Accepted answer

(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)$:

> 2. 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$.
> 3. If $\beta\_1=\dots=\beta\_k=0$, answer that the products are equal.

Otherwise $\Lambda\ne0$. By [Baker’s theorem](https://en.wikipedia.org/wiki/Baker%27s_theorem), we can lower bound
$$|\Lambda|>2^{-C\log n}$$
for a certain constant $C$. Thus, the following correctly computes the sign of $\Lambda$:

> 4. 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](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations)), 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.

> **Comments:**
> **username_0**: Thanks! I'll have to work through the details later, but this seems very promising!  

---

