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
DOI: https://doi.org/10.1090/S0025-5718-08-02162-5
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?)

  • 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. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics, Addison-Wesley Publishing Co., Reading, Massachusetts, 1989. MR 1001562 (91f:00001)
  • 4. R. K. Guy, Unsolved problems in number theory, third 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, third ed., The Clarendon Press, Oxford University Press, New York, 1954. MR 0067125 (16,673c)
  • 6. D. E. Knuth, The art of computer programming, volume 1: fundamental algorithms, second ed., Addison-Wesley Publishing Co., Reading, Massachusetts, 1969. MR 0286317 (44:3530)
  • 7. -, The art of computer programming, volume 3: sorting and searching, second ed., Addison-Wesley Publishing Co., Reading, Massachusetts, 1998. MR 0445948 (56:4281)
  • 8. J. Leech, Some solutions of Diophantine equations, Proc. Cambridge Philos. Soc. 53 (1957), 778-780. MR 0090602 (19,837f)
  • 9. E. Rosenstiel, J. A. Dardis, and C. R. Rosenstiel, The four least solutions in distinct positive integers of the Diophantine equation $ s=x^3+y^3=z^3+w^3=u^3+v^3=m^3+n^3$, Bull. Inst. Math. Appl. 27 (1991), no. 7, 155-157. MR 1125858 (92i:11134)
  • 10. D. W. Wilson, The fifth taxicab number is $ 48\,988\,659\,276\,962\,496$, J. Integer Seq. 2 (1999), Article 99.1.9, HTML document (electronic). MR 1722364 (2000i:11195)

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
Email: Michael.Eisermann@ujf-grenoble.fr

DOI: https://doi.org/10.1090/S0025-5718-08-02162-5
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