Consider the "sum" of two intervals of natural numbers $\sigma_i = \langle n_i, k_i \rangle := \{ n_i,n_i+1,\dots,n_i + k_i\} $ being the set of numbers $\sigma = \sigma_1 \oplus \sigma_2 $ with $m \in \sigma$ iff there are $m_i \in \sigma_i$ with $m = m_1 + m_2$. We easily find that $\sigma = \langle n_1 + n_2, k_1 + k_2 \rangle$. This is nothing but the set of possible sums of two natural numbers $N_i = n_i + \frac{k_i}{2}$ which are known only with some confidence $\pm \frac{k_i}{2}$.
Calculating this set requires two additions: $n_1 + n_2$ and independently $k_1 + k_2$. I'd like to propose a way which only needs one addition. I requires a specific kind of ternary logic and usage of a ternary number system. In the beginning it is restricted to a small subset of allowed number intervals. I hope the approach can be generalized to arbitrary intervals.
Consider natural numbers $n$ that are multiples of powers of $2$, i.e. that can be written in binary as
$$n = m\underbrace{0\dots0}_p$$
with $m$ any binary number. Consider further the number $k = 2^p - 1$. Then the interval $\langle n, k \rangle := \{ n,n+1,\dots,n + k\}$ can compactly be written in the form
$$\sigma = m\underbrace{\_\dots\_}_p$$
with the extra symbol $\_$ being the third symbol in the ternary alphabet (the blank symbol), indicating that the corresponding digit is unknown and can be either $0$ or $1$.
Now consider two intervals
$$\sigma_1 = m_1\underbrace{\_\dots\dots\_}_{p_1}$$
$$\sigma_2 = m_2\underbrace{\_\dots\_}_{p_2}$$
My claim is:
$$\sigma_1 \oplus \sigma_2 = m_3\underbrace{\_\dots\_}_{p_3} + \underbrace{\_\dots\dots\_}_{p_4}$$
with $p_3 = \min\{p_1,p_2\}$, $p_4 = \max\{p_1,p_2\}$. Note that $p_3 + p_4 = p_1 + p_2$.
The binary number $m_3$ is calculated by adding the two ternary sequences starting at index $p_3= \min\{p_1,p_2\}$, treating $\_$ like $0$ (which happens when $p_1 \neq p_2$). For our restricted set of numbers $n,k$ this reduces the number of binary additions to one. Even more, the numbers to be added are smaller than the original ones. The rest is counting.
Examples:
$1\_\_ + 11\_ = 101\_ + \_\_$
$10\_ + 11\_ = 101\_ + \_$
$11\_ + 11\_ = 110\_ + \_$
My question are:
Is the claim correct?
If so: Is it trivial or something trivial in an obfuscating disguise?
If not so: Has this approach already been taken? Under which name? What could I google for?
Does it seem feasible to generalize it to arbitrary intervals $\langle n_i, k_i \rangle$?
Generalization for arbitrary $\langle n, k\rangle$ could go like this:
Choose an interval of size $2^p -1$ closest to $k$.
Choose the number $n_0 = m\underbrace{0...0}_{p}$ closest to $n$.
Shift the interval $m\underbrace{\_...\_}_{p}$ by adding $n - n_0$:
$$\sigma = m\underbrace{\_...\_}_{p} + n - n_0.$$
Now we have to perform two additions again, but in both cases with smaller addends than the original ones.