<p>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 <a href="https://math.stackexchange.com/questions/156509/product-of-all-prime-numbers-upto-some-prime-p">approximated</a> 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)$.</p>

CC BY-SA 3.0
2012-11-16T16:33:38.843Z
see also [chinese remainder theorem](http://en.wikipedia.org/wiki/Chinese_remainder_theorem)
vzn
CC BY-SA 3.0
2012-11-16T18:16:10.307Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2012-11-15T14:15:47.180Z
2012-11-16T09:02:42.347Z
2017-04-13T12:19:19.363Z
Joe Fitzsimons
<p>Accoring to <a href="http://rjlipton.wordpress.com/2012/07/02/connect-the-stars/">K. W. Regan's article "Connect the Stars"</a>, 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:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>(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.</p>

<p>(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?</p>

<p><strong>FORMAL PROBLEM STATEMENT</strong></p>

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

<p>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?</p>

CC BY-SA 3.0
2012-11-12T23:10:55.233Z
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.
Matt Groff
CC BY-SA 3.0
2012-11-13T01:39:46.083Z
Instead of getting linear time for all of these operations, is there a representation of integers so that all of these operations have sub-quadratic time?
Tyson Williams
CC BY-SA 3.0
2012-11-13T03:36:47.880Z
@TysonWilliams: Yes!  Binary!
Jeffε
CC BY-SA 3.0
2012-11-13T12:40:03.150Z
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)$?
Emil Jeřábek
CC BY-SA 3.0
2012-11-13T12:57:04.620Z
`mul(a, b)` via `add(log(a), log(b))` doesn't count as "linear" time for integers represented by their logarithms?
jnml
CC BY-SA 3.0
2012-11-13T13:03:42.173Z
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?
Emil Jeřábek
CC BY-SA 3.0
2012-11-14T04:36:06.633Z
@jnml: I don't believe it's totally trivial how you implement `add(a,b)` and `less_than(a,b)`.  If you believe you can do all three operations faster than $O(n \log n)$ I wouldn't mind having a rough idea of how you do this.
Matt Groff
CC BY-SA 3.0
2012-11-14T04:43:57.180Z
Such a representation is unlikely be a simple one since a simple representation is likely to be convertible to and from binary representation very efficiently and that would improve the upper-bound on the binary multiplication.
Kaveh
CC BY-SA 3.0
2012-11-14T11:49:05.190Z
How do you intend to formally state the question so that it “disallows padding”? How do you define that something is a padding? The question as it stands is ill-posed.
Emil Jeřábek
CC BY-SA 3.0
2012-11-14T14:12:06.927Z
@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)$.
Jeffε
CC BY-SA 3.0
2012-11-15T01:45:15.577Z
I asked about uses for this system here: http://cs.stackexchange.com/questions/6667/what-are-the-potential-uses-of-a-good-r-n-s-system
Matt Groff
CC BY-SA 3.0
2012-11-15T04:40:47.757Z
this seems similar to the question of whether [addition is faster than multiplication](http://cstheory.stackexchange.com/questions/12671/is-there-a-proof-that-addition-is-faster-than-multiplication). also intuition might suggestion that fourier analysis & convolution might have something to do with this or be a possible "lead", where multiplication is transformed into addition in the frequency domain etc.
vzn
<ds.algorithms><ds.data-structures><worst-case>
How close can we get to linear multiply, add, and compare (on integers)?
Matt Groff
# How close can we get to linear multiply, add, and compare (on integers)?

(Asked by: username_0 on 2012-11-12)

Accoring to [K. W. Regan's article "Connect the Stars"](http://rjlipton.wordpress.com/2012/07/02/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?

**Tags:** ds.algorithms, ds.data-structures, worst-case
> **Comments:**
> **username_0**: 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.  
> **username_1**: Instead of getting linear time for all of these operations, is there a representation of integers so that all of these operations have sub-quadratic time?  
> **username_2**: @TysonWilliams: Yes!  Binary!  
> **username_3**: 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)$?  
> **username_4**: `mul(a, b)` via `add(log(a), log(b))` doesn't count as "linear" time for integers represented by their logarithms?  
> **username_3**: 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?  
> **username_0**: @jnml: I don't believe it's totally trivial how you implement `add(a,b)` and `less_than(a,b)`.  If you believe you can do all three operations faster than $O(n \log n)$ I wouldn't mind having a rough idea of how you do this.  
> **username_5**: Such a representation is unlikely be a simple one since a simple representation is likely to be convertible to and from binary representation very efficiently and that would improve the upper-bound on the binary multiplication.  
> **username_3**: How do you intend to formally state the question so that it “disallows padding”? How do you define that something is a padding? The question as it stands is ill-posed.  
> **username_2**: @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)$.  
> **username_0**: I asked about uses for this system here: http://cs.stackexchange.com/questions/6667/what-are-the-potential-uses-of-a-good-r-n-s-system  
> **username_6**: this seems similar to the question of whether [addition is faster than multiplication](http://cstheory.stackexchange.com/questions/12671/is-there-a-proof-that-addition-is-faster-than-multiplication). also intuition might suggestion that fourier analysis & convolution might have something to do with this or be a possible "lead", where multiplication is transformed into addition in the frequency domain etc.  

---

## 1 answers

### Answer by username_7 on 2012-11-15. Score: 14

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](https://math.stackexchange.com/questions/156509/product-of-all-prime-numbers-upto-some-prime-p) 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

> **Comments:**
> **username_6**: see also [chinese remainder theorem](http://en.wikipedia.org/wiki/Chinese_remainder_theorem)  
> **username_7**: @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.  

---

