Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Bimonotone enumeration

Author: Michael Eisermann
Journal: Math. Comp. 78 (2009), 591-613
MSC (2000): Primary 68P10; Secondary 11Y50, 68W10, 11Y16, 11D45
Published electronically: June 16, 2008
MathSciNet review: 2448723
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68P10, 11Y50, 68W10, 11Y16, 11D45

Retrieve articles in all journals with MSC (2000): 68P10, 11Y50, 68W10, 11Y16, 11D45

Additional Information

Michael Eisermann
Affiliation: Institut Fourier, Université Grenoble I, France

Keywords: Sorting and searching, diophantine equation, bimonotone function, sorted enumeration, semimonotone enumeration, bimonotone enumeration
Received by editor(s): July 27, 2005
Received by editor(s) in revised form: June 22, 2007
Published electronically: June 16, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.