20
$\begingroup$

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 < n$ and $0 \le y < 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?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ I'll mention that it is possible to create a scheme that performs these operations in time $\Theta(n)$ on non-negative integers, where $n$ is the bitsize of the largest integer (assuming we know $n$ ahead of time). I wonder if we can do better, and do this in time proportional to the current integer(s) being computed. $\endgroup$ – Matt Groff Nov 12 '12 at 23:10
  • 5
    $\begingroup$ @TysonWilliams: Yes! Binary! $\endgroup$ – Jeffε Nov 13 '12 at 3:36
  • 2
    $\begingroup$ Instead of getting linear time for all of these operations, is there a representation of integers so that all of these operations have time $O(n\log n)$? $\endgroup$ – Emil Jeřábek Nov 13 '12 at 12:40
  • 4
    $\begingroup$ Actually, there is a trivial positive answer: represent integers in binary with $n^2$ bits of padding. Shouldn’t the statement include some condition to the effect that the representation should have length linear in the length of the binary representation? $\endgroup$ – Emil Jeřábek Nov 13 '12 at 13:03
  • 5
    $\begingroup$ @EmilJeřábek: I assume he wants the representation of any integer $n$ to use $f(n)$ bits, for some function $f(n)=\Theta(\log n)$. $\endgroup$ – Jeffε Nov 14 '12 at 14:12
14
$\begingroup$

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<\exp((1+\mathcal{o}(1) )n\log n)$. Since we can represent any $N<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)$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ see also chinese remainder theorem $\endgroup$ – vzn Nov 16 '12 at 16:33
  • 1
    $\begingroup$ @vzn: Yes, I was going to mention that for comparisons, but then it occurred to me that there might be a quicker comparison operation via a mixed radix representation. $\endgroup$ – Joe Fitzsimons Nov 16 '12 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.