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

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?)

  • 1. D. J. Bernstein, Enumerating solutions to $ p(a)+q(b)=r(c)+s(d)$, Math. Comp. 70 (2001), no. 233, 389-394. MR 2001f:11203
  • 2. R. L. Ekl, Equal sums of four seventh powers, Math. Comp. 65 (1996), no. 216, 1755-1756. MR 97a:11050
  • 3. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1989. A foundation for computer science. MR 1001562
  • 4. Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335
  • 5. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford, at the Clarendon Press, 1954. 3rd ed. MR 0067125
  • 6. Donald E. Knuth, The art of computer programming. Vol. 1: Fundamental algorithms, Second printing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR 0286317
  • 7. Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR 0445948
  • 8. John Leech, Some solutions of Diophantine equations, Proc. Cambridge Philos. Soc. 53 (1957), 778–780. MR 0090602
  • 9. E. Rosenstiel, J. A. Dardis, and C. R. Rosenstiel, The four least solutions in distinct positive integers of the Diophantine equation 𝑠=𝑥³+𝑦³=𝑧³+𝑤³=𝑢³+𝑣³=𝑚³+𝑛³, Bull. Inst. Math. Appl. 27 (1991), no. 7, 155–157. MR 1125858
  • 10. David W. Wilson, The fifth taxicab number is 48988659276962496, J. Integer Seq. 2 (1999), Article 99.1.9, 1 HTML document. MR 1722364

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.

American Mathematical Society