3
$\begingroup$

I'm interested in balanced base $B$ representation for fixed point arithmetic. The paper Fixed-point arithmetic in SHE schemes (Costache, Smart, Vivek and Waller, in Proceedings of 23rd International Conference on Selected Areas in Cryptography (SAC 2016), Springer Lecture Notes in Computer Science, vol. 10532, pp. 401–422, 2016; PDF) provides two examples using balanced based $B=3$. However, I don't understand the 2nd second representation, i.e. $$\frac{8}{3}=10.\bar{1} $$ where $\bar{1}=-1$. More generally speaking, I'm also interested in balanced form representation $B=5, 7$. I believe this should be a well-known problem, though I was not able to google it. Do you know some relevant literature to this?

$\endgroup$
1
  • $\begingroup$ This seems like a pure math question, and so belongs to Mathematics. $\endgroup$ Dec 11 '18 at 20:26
2
$\begingroup$

$$\frac{8}{3}=3 - \frac13=1\cdot3^1 + 0\cdot3^0 +(-1)\cdot3^{-1}=(10.\bar{1})_3$$

Since $\frac83$ is not equal to $\dfrac p{5^i}$ for any integer $p$ and $i$, it cannot be expressed as a fixed-point balanced base-5 number. Instead, infinite periodical fraction part has to be used, where $\bar2=-2$.

$$\frac{8}{3}=5-2+\frac{-2}5+\frac2{25}+\frac{-2}{125}+\frac2{625}+\frac{-2}{3125}+\frac2{15625}+\cdots=(1\bar2.\bar{2}2\bar{2}2\bar{2}2\cdots)_5$$

Let us see it step by step.
$\frac{8}{3}\approx5$
$\frac{8}{3}-5=\frac{-7}3\approx -2$
$\frac{8}{3}-(5-2)=\frac{-1}3\approx \frac {-2}5$
$\frac{8}{3}-(5-2+\frac{-2}5)=\frac15\frac{1}3\approx \frac15\frac {2}5$
$\frac{8}{3}-(5-2+\frac{-2}5+\frac15\frac25)=\frac15\frac15\frac{-1}3\approx \frac15\frac15\frac {-2}5$
$\frac{8}{3}-(5-2+\frac{-2}5+\frac15\frac25+\frac15\frac15\frac{-2}5)=\frac15\frac15\frac15\frac{1}3\approx \frac15\frac15\frac15\frac {2}5$
$\frac{8}{3}-(5-2+\frac{-2}5+\frac15\frac25+\frac15\frac15\frac{-2}5+\frac15\frac15\frac15\frac25)=\frac15\frac15\frac15\frac15\frac{-1}3\approx \frac15\frac15\frac15\frac15\frac {-2}5$
$\vdots$

You can work out the the balanced base-7 number with periodical fraction for $\dfrac 83$.

For the case of base 3, you can take a look at balanced ternary at Wikipedia.

$\endgroup$
2
  • $\begingroup$ The section "3.1 Balanced Base-B Encoding" of that paper you mentioned can be considered as a nice introduction. $\endgroup$
    – John L.
    Dec 11 '18 at 20:55
  • $\begingroup$ There are 13 references near the end of that paper. You could read and trace some of them. $\endgroup$
    – John L.
    Dec 11 '18 at 22:43
2
$\begingroup$

The expression $10.\overline{1}$ should be interpreted as follows: $$ 1 \cdot 3^1 + 0 \cdot 3^0 + (-1) \cdot 3^{-1} = 3 - \frac{1}{3} = \frac{8}{3}. $$ The interpretation of balanced base $b=2d+1$ is the same, with the digits ranging from $-d$ to $d$.

$\endgroup$
1
  • $\begingroup$ Thank you for the answer. Do you know some relevant literature to this? I would like to learn how to represent generic floating number such as 0.72? $\endgroup$
    – dfine
    Dec 11 '18 at 20:46

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.