0
$\begingroup$

Let $n \in 2 \mathbb{N} - 1$. I was wondering what sort of algorithms there are for converting (non-balanced) base-n to balanced base-n, where "balanced" is as is described in this article: http://en.wikipedia.org/wiki/Signed-digit_representation, and where the representation is as short as possible (for example, $7 = (1,1,1)_2$ with lower powers of the base being toward the right); in other words, base n with minimal residues for digits. For such a balanced ternary, two algorithms are given here: http://en.wikipedia.org/wiki/Balanced_ternary#Conversion_from_ternary.

Thank you for any help that you might give.

$\endgroup$
1
$\begingroup$

For an "ordinary" base-$n$ representation using digits $0,\ldots,n-1,$ a number $x$ with $k+1$ digits and no negative sign will have a leading digit $d$ (a $d$ in the "$n^k$" place) under exactly the following conditions:

$$ 0 \leq x - dn^k < n^k.$$

The greatest possible value of a number of $k+1$ digits is

$$ (n-1)n^k + (n-1)n^{k-1} + \cdots + (n-1)n^2 + (n-1)n + (n-1) = n^{k+1} - 1.$$

For a balanced base-$n$ representation where $n$ is odd, a number $x$ with $(k+1)$ digits will have a leading digit $d$ when

$$ -\frac{n^k}{2} < x - dn^k < \frac{n^k}{2}.$$

In this case there is no possibility of equality, since $x - dn^k$ is an integer and $\frac{n^k}{2}$ is not. The greatest possible value of a number of $k+1$ digits is

$$ \frac{n-1}{2}n^k + \frac{n-1}{2}n^{k-1} + \cdots + \frac{n-1}{2}n^2 + \frac{n-1}{2}n + \frac{n-1}{2} = \frac{n^{k+1} - 1}{2}$$

and similarly the least possible value is $-\frac{n^{k+1} - 1}{2}.$

For any odd $n,$ then, you can convert an ordinary base-$n$ number whose digits are $c_p\cdots c_2c_1c_0$ to a balanced base-$n$ number whose digits are $d_q\cdots d_2d_1d_0$ by working from right to left, much like the way you would convert ordinary ternary to balanced ternary. That is, if you have already converted the rightmost $k$ digits of a number $x$, you will have $$ x = (c_p\cdots c_{k+1}c'_k)n^k + (d_{k-1}\cdots d_1d_0) $$ where $-\frac{n^k}{2} < d_{k-1}\cdots d_1d_0 < \frac{n^k}{2}$ and $c'_k$ is either the original $c_k$ or $c_k + 1.$ (The number $d_{k-1}\cdots d_1d_0$ will be negative if its most significant non-zero digit is negative; it is possible for this number to have some leading zeros.)

Now write the number $x$ this way: $$x = (c_p\cdots c_{k+2})n^{k+2} + c_{k+1}n^{k+1} + c_kn^k + (d_{k-1}\cdots d_1d_0).$$ If $c_k < \frac n2,$ then $c_kn^k + (d_{k-1}\cdots d_1d_0) < \frac{n^{k+1}}{2}$, so you can set $d_k = c_k$ and write $$ x = (c_p\cdots c_{k+1})n^{k+1} + (d_kd_{k-1}\cdots d_1d_0). $$ If $c_k > \frac n2,$ then $c_kn^k + (d_{k-1}\cdots d_1d_0) > \frac{n^{k+1}}{2}$, so you will need to set $d_k = c_k - n$ so that you can write $$\begin{eqnarray} x &=& (c_p\cdots c_{k+2})n^{k+2} + (c_{k+1}+1)n^{k+1} + (d_kd_{k-1}\cdots d_1d_0)\\ &=& (c_p\cdots c_{k+2}c'_{k+1})n^{k+1} + (d_kd_{k-1}\cdots d_1d_0) \end{eqnarray}$$ where $c'_{k+1} = c_{k+1} + 1.$ That is, if you would "round up" from $c_k$ then you "carry $1$" to $c_{k+1}.$

For the rightmost digit, $c_0,$ of course, there are no digits to the right of it, so $c'_0=c_0$ and you can omit $d_{k-1}\cdots d_1d_0$ when you apply the formulas above. For the leftmost digit, $c_p,$ there is no digit $c_{p+1}$ to "carry" to, so if $c_p > \frac n2$ you simply set $d_p = c_p - n$ and $d_{p+1} = 1$ and you're done.

$\endgroup$

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.