How close can we get to linear multiply, add, and compare (on integers)? Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and comparision operations are computable in linear time:


  Does there exist a representation of integers so that addition, multiplication, and comparison are all doable in linear time? Basically, is there a linear time discretely ordered ring?


(1)  How close can we come to linear time multiplication and addition, without compares?  Here I assume that the problem sizes may vary, so that we may need a data structure/algorithm that allows for changing integer sizes.

(2)  For the complete problem, we can assume that we will find an optimum scheme for multiply, add, and compare on the integers.  How close can we get the slowest of these three operations (in the worst case) towards linear time?  And on that note, how fast would the other operations be?

FORMAL PROBLEM STATEMENT

As Emil Jeřábek mentions, we'd like to rule out trivial cases and concentrate on worst case behavior for this question.

So we ask, for non-negative integers $\forall x$ and $\forall y$ where $0 \le x &lt; n$ and $0 \le y &lt; n$, can we find a data structure/algorithm that can perform addition, multiplication, and compares with\between $x$ and $y$ in $O(n \log{(n)})$ time and $O(\log^2{(n)})$ space?
Probably not the best answer, but perhaps this is a useful starting point. If we wish to represent a non-negative integer, we can store it as a set of residues modulo sequential prime numbers starting from 2. In this form comparison is potentially hard, but multiplication and addition can be done pretty quickly. The product of the first $n$ primes is approximated by $$p_n\# =\exp((1+\mathcal{o}(1) )n\log n).$$
Hence to represent an integer $N$ you require residues modulo the first $n$ primes, where $N&lt;\exp((1+\mathcal{o}(1) )n\log n)$. Since we can represent any $N&lt;p_n\#$ using residues modulo the first $n$ prime residues, we can take $n \log n \propto \log(N)$. Addition and multiplication can be done directly between pairs of residues. There are $n$ such pairs, with the maximum prime being around $n\log(n)$. Thus addition should be in $O(n\log\log(N))$, while multiplication via Schonhage-Strassen should be in $O(n\log\log(N)\log\log\log\log(N)\log\log\log(N))$. Since $n \log n \propto \log N$, then a rough approximation gives $n$ in $O(\log N/\log\log N)$. This would give the complexity of addition and multiplication as approximately $O(\log N)$ and $O(\log N \log\log\log N \log\log\log\log N)$.