Bimonotone enumeration

Abstract:

Solutions of a diophantine equation $f(a,b) = g(c,d)$, with $a,b,c,d$ in some finite range, can be efficiently enumerated by sorting the values of $f$ and $g$ in ascending order and searching for collisions. This article considers functions $f \colon \mathbb {N} \times \mathbb {N}\to \mathbb {Z}$ that are bimonotone in the sense that $f(a,b) \le f(a’,b’)$ whenever $a \le a’$ and $b \le b’$. A two-variable polynomial with non-negative coefficients is a typical example. The problem is to efficiently enumerate all pairs $(a,b)$ such that the values $f(a,b)$ appear in increasing order. We present an algorithm that is memory-efficient and highly parallelizable. In order to enumerate the first $n$ values of $f$, the algorithm only builds up a priority queue of length at most $\sqrt {2n}+1$. In terms of bit-complexity this ensures that the algorithm takes time $O( n \log ^2 n )$ and requires memory $O( \sqrt {n} \log n )$, which considerably improves on the memory bound $\Theta ( n \log n )$ provided by a naïve approach, and extends the semimonotone enumeration algorithm previously considered by R.L. Ekl and D.J. Bernstein.