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 that are bimonotone in the sense that

f (a, b) l e f (a^{'}, b^{'})

whenever

a l e a^{'}

and

b l e 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

s q r t 2 n + 1

. In terms of bit-complexity this ensures that the algorithm takes time

O (n l o g^{2} n)

and requires memory

O (s q r t n l o g n)

, which considerably improves on the memory bound

T h e t a (n l o g n)

provided by a naive approach, and extends the semimonotone enumeration algorithm previously considered by R.L. Ekl and D.J. Bernstein.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Bimonotone enumeration