Bimonotone enumeration

Details Bimonotone enumeration Bimonotone enumeration

2008-03-22

arxiv.org/abs/0803.3273v1

Mathematics

Combinatorics

22 pages, 7 figures. The algorithms presented here have been implemented as class templates in C++ and are available on the au

Scientific paper

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 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 naive approach, and extends the semimonotone enumeration algorithm previously considered by R.L. Ekl and D.J. Bernstein.

Affiliated with

Also associated with

No associations

Rating

Bimonotone enumeration does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bimonotone enumeration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bimonotone enumeration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-597043