- #1

- 5,053

- 7

Consider a representation of signed integers of base $B$, in which the digits are listed in descending order of importance, with the least significant digit corresponding to a positive, and the next digits to an alternate negative and positive value. Thus, a number of this representation of $n$ digits $A=A_{n-1}A_{n-2}\dots A_1A_0$ has a value $$T(A)=(-1)^{n-1}\cdot T(A_{n-1})\cdot B^{n-1}+(-1)^{n-2}\cdot T(A_{n-2})\cdot B^{n-2}+\ldots -T(A_1)\cdot B+T(A_0)$$ with each digit having a value from $0$ to $B-1$.

For example if $B=3$ the $6$-digit number $200112$ of the above reresentation has the value $-2\cdot 3^5+0\cdot 3^4-0\cdot 3^3+1\cdot 3^2-1\cdot 3+2=-478$.

a) What is the range of the above representation for random $B$ and $n$? What is the number with the maximum and what is the number with the minimum value?

b) Give an algorithm for converting a random constant decimal number of the decimal system to the above representation, and verify it for three random numbers.

c) Examine the uniqueness of the representation, ie examine whether it is possible for two different numbers in the representation to have the same value. Give a counter-example if such a thing is possible or otherwise prove mathematically the uniqueness. If you found that there is no uniqueness in the representation of a number what is the average number of different representations of the same value in the above representation?

d) Give an algorithm of conversion of the above representation to the complement representation with respect to B and verify it for three random numbers, one for $Β = 5$ and $n = 3$, one for $Β = 3$ and $n = 8$ and one for $Β = 2$ and $n = 13$.

e) Return to the original representation and give an addition / subtraction algorithm for representation numbers, including overflow control, and verify it for two random number pairs one for $Β = 3$ and $n = 5$ and one for $Β = 2$ and $n = 11$ for both operations per pair.

I have done the following :

a) The maximum value is when we all positive terms have the greatest coefficient and the negative ones zero. The minimum value is when we all negative terms have the greatest coefficient and the npositive ones zero.

For example for $B=10$ and $n=3$ we have that \begin{align*}T(max)&=(B-1)\cdot B^2-0\cdot B+(B-1)=B^3-B^2+B-1=10^3-10^2+10-1=909=9\cdot 100+9\\ & =(B-1)\cdot B^2+(B-1)=(B-1)\cdot (B^2+1) \\ T(min)&=0\cdot B^2-(B-1)\cdot B+0=-B^2+B=-10^2+10=-90=-90=-9\cdot 10\\ & =-(B-1)\cdot B=-B^2+B

\end{align*}

So for general $B$ and $n$ we have that the maximum is $(B-1)\cdot (B^{n-1}+1)$ and the minimumis $-(B-1)\cdot B^{n-2}$.

Is that correct? :unsure:

b) How does this algorithm look like?