Representation of signed integers of base B

[mathmari]

Hey! :giggle:

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?

 

[I like Serena]

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*}

Hey mathmari!

Looks correct to me. (Nod)

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?

Suppose we consider an example with $n=4$, what do we get then?
And what if $n=5$?

b) How does this algorithm look like?

Suppose we have a random number $A$ and we are looking for its representation with respect to basis $B$ with $n$ digits.
We have $A=(-1)^{n-1}A_{n-1}B^{n-1}+\ldots-A_1 B + A_0$.
Suppose we calculate $A\bmod B$, what will we find?

 

[mathmari]

Suppose we have a random number $A$ and we are looking for its representation with respect to basis $B$ with $n$ digits.
We have $A=(-1)^{n-1}A_{n-1}B^{n-1}+\ldots-A_1 B + A_0$.
Suppose we calculate $A\bmod B$, what will we find?

We have that $A\bmod B=A_0$, right? :unsure:

 

[I like Serena]

We have that $A\bmod B=A_0$, right?

Indeed. (Nod)
That is assuming that we define $\bmod B$ such that the result is between $0$ and $B-1$ and not negative, which is also the constraint we have for $A_0$.

So now we have $A_0$.
Can we combine $A$, $A_0$, and $B$ in such a way that we can find $A_1$? (Wondering)

 

[mathmari]

now we have $A_0$.
Can we combine $A$, $A_0$, and $B$ in such a way that we can find $A_1$? (Wondering)

We calculate the expression modulo $B^2$ and solve for $A_1$, right? :unsure:
So in general we calculate the expression modulo $B^k$ to calculate $A_{k-1}$,right? :unsure:

So to give the algorithm we just give this description, right? :unsure: As for (c) doesn't a representation in general have to be unique? :unsure:

 

[I like Serena]

First off, the answer to (a) was not correct. (Shake)

We calculate the expression modulo $B^2$ and solve for $A_1$, right?
So in general we calculate the expression modulo $B^k$ to calculate $A_{k-1}$,right?

Suppose we do, then we find $-A_1 B + A_0 + kB$ with $k$ such that the result is between $0$ and $B-1$. That is assuming that is how we defined $\text{mod}$.
How will we find $A_1$ since we don't know $k$?

So to give the algorithm we just give this description, right?

We might, but I think the description is still a bit too fuzzy.
The question also asks to apply the algorithm to 3 random numbers.
We didn't do that yet, did we? If we do, and see what happens, perhaps we can improve the algorithm a bit.

As for (c) doesn't a representation in general have to be unique?

We don't know yet.
A proof is typically a proof by contradiction.
Suppose there are 2 different representations of the same number, then...

 

[mathmari]

First off, the answer to (a) was not correct. (Shake)

For $n=3$ :
\begin{align*}T(max)&=(B-1)\cdot B^2-0\cdot B+(B-1)=B^3-B^2+B-1=(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=-(B-1)\cdot B
\end{align*}
For $n=4$ :
\begin{align*}T(max)&=- 0\cdot B^{3}+(B-1)\cdot B^2 -0\cdot B+(B-1)=(B-1)\cdot B^2+(B-1)=(B-1)\cdot (B^2+1) \\ T(min)&=- (B-1)\cdot B^{3}+0\cdot B^2 -(B-1)\cdot B+0=- (B-1)\cdot B^{3} -(B-1)\cdot B=-(B-1)\cdot (B^3+B)\end{align*}

For $n=5$ :
\begin{align*}T(max)&=(B-1)\cdot B^4- 0\cdot B^{3}+(B-1)\cdot B^2 -0\cdot B+(B-1)=(B-1)\cdot B^4+(B-1)\cdot B^2+(B-1)\\ & =(B-1)\cdot (B^4+B^2+1) \\ T(min)&=0\cdot B^4- (B-1)\cdot B^{3}+0\cdot B^2 -(B-1)\cdot B+0=- (B-1)\cdot B^{3} -(B-1)\cdot B=-(B-1)\cdot (B^3+B)\end{align*}

So the maximum is $$T(\text{max})=(B-1)\left (\sum_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}B^{2i}\right )$$ and the minimum is $$T(\text{min})=-(B-1)\left (\sum_{i=1, odd}^{n-1}B^{i}\right )$$

Is that correct? :unsure:

Suppose we do, then we find $-A_1 B + A_0 + kB$ with $k$ such that the result is between $0$ and $B-1$. That is assuming that is how we defined $\text{mod}$.
How will we find $A_1$ since we don't know $k$?

I got stuck right now. How did we get the term $kB$ ? :unsure:

We don't know yet.
A proof is typically a proof by contradiction.
Suppose there are 2 different representations of the same number, then...

But how can that be if the coefficients are the digits of the number? :unsure:

 

[I like Serena]

So the maximum is $$T(\text{max})=(B-1)\left (\sum_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}B^{2i}\right )$$ and the minimum is $$T(\text{min})=-(B-1)\left (\sum_{i=1, odd}^{n-1}B^{i}\right )$$

Is that correct?

It looks correct now. (Nod)

For the record, those are geometric series, so we can simplify them.
And then we might also verify if the examples match.

I got stuck right now. How did we get the term $kB$ ?

The $\bmod B$ operation finds an equivalence class, which can be normalized to $0$ to $B-1$ by adding or subtracting $B$ until the result is in that interval.
As an example, consider $A=-2B$.
Then we have $A\pmod{B^2} \equiv - 2B \implies A\bmod{B^2} =-2B + kB^2$.
If we define $\bmod$ to have a result in the range $0$ to $B^2-1$, then we get $A\bmod{B^2}=B^2-2B$. (Worried)

For the record, many programming languages have a $\bmod$ that "keeps the sign".
In that case we have $-2\bmod 3=-2$ and $2\bmod 3=2$.

But how can that be if the coefficients are the digits of the number? :unsure:

As an example suppose we have $n=2$.
Then $A=-A_1 B+A_0$.
Suppose the representation is not unique.
Then there must be $A_1'$ and $A_0'$ with $(A_1',A_0')\ne(A_1,A_0)$, such that $A=-A_1' B+A_0'$.
Can we verify that this leads to a contradiction? Or if we can't, can we find an example with concrete numbers where the conditions are satisfied?

 

[mathmari]

As an example suppose we have $n=2$.
Then $A=-A_1 B+A_0$.
Suppose the representation is not unique.
Then there must be $A_1'$ and $A_0'$ with $(A_1',A_0')\ne(A_1,A_0)$, such that $A=-A_1' B+A_0'$.
Can we verify that this leads to a contradiction? Or if we can't, can we find an example with concrete numbers where the conditions are satisfied?

Then we have that $$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow (-A_1+A_1')B+(A_0-A_0')=0 \Rightarrow -A_1+A_1'=0 \ \text{ and } \ A_0-A_0'=0 \Rightarrow A_1=A_1' \ \text{ and } \ A_0=A_0'$$ so we get a contradiction.

Is that correct? :unsure:

 

[I like Serena]

Then we have that $$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow (-A_1+A_1')B+(A_0-A_0')=0 \Rightarrow -A_1+A_1'=0 \ \text{ and } \ A_0-A_0'=0 \Rightarrow A_1=A_1' \ \text{ and } \ A_0=A_0'$$ so we get a contradiction.

Is that correct?

How did you get that $(-A_1+A_1')B+(A_0-A_0')=0 \Rightarrow -A_1+A_1'=0 \ \text{ and } \ A_0-A_0'=0$?

Btw, for the algorithm I suggest to use $A_1 = -\frac{A - A_0}{B} \bmod B$.
With the minus sign in there, it does not matter whether the $\bmod$ operation "keeps the sign" or not.

 

[mathmari]

How did you get that $(-A_1+A_1')B+(A_0-A_0')=0 \Rightarrow -A_1+A_1'=0 \ \text{ and } \ A_0-A_0'=0$?

Ah can we do that in that way? Do we have to calculate the expression modulo $B$ ?
$$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow (-A_1 B+A_0)\pmod B=(-A_1' B+A_0')\pmod B \Rightarrow A_0=A_0'$$
Then we have that $$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow -A_1 B+A_0=-A_1' B+A_0 \Rightarrow -A_1 B=-A_1' B \Rightarrow B(A_1-A_1')=0 \Rightarrow A_1-A_1'=0 \Rightarrow A_1=A_1'$$

Do we do that in that way? :unsure:

 

[I like Serena]

Ah can we do that in that way? Do we have to calculate the expression modulo $B$ ?
$$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow (-A_1 B+A_0)\pmod B=(-A_1' B+A_0')\pmod B \Rightarrow A_0=A_0'$$
Then we have that $$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow -A_1 B+A_0=-A_1' B+A_0 \Rightarrow -A_1 B=-A_1' B \Rightarrow B(A_1-A_1')=0 \Rightarrow A_1-A_1'=0 \Rightarrow A_1=A_1'$$

Do we do that in that way?

I believe we should do it this way yes.
However, let's be careful to avoid mistakes.
We have:
$$(-A_1 B+A_0) \equiv (-A_1' B+A_0')\pmod B \implies A_0 \equiv A_0' \pmod B \implies A_0=A_0'+kB$$
Since $A_0$ and $A_0'$ are both defined to be in the range $0$ to $B-1$, it follows that $k=0$ and they must indeed be equal.

 

[mathmari]

I believe we should do it this way yes.
However, let's be careful to avoid mistakes.
We have:
$$(-A_1 B+A_0) \equiv (-A_1' B+A_0')\pmod B \implies A_0 \equiv A_0' \pmod B \implies A_0=A_0'+kB$$
Since $A_0$ and $A_0'$ are both defined to be in the range $0$ to $B-1$, it follows that $k=0$ and they must indeed be equal.

Ah ok! So we have a contradiction, and so it cannot be that two different representations correspond to the same number, right? To prove that formally mathematically, do we show that in the same way as here in the example for $n=2$ ? :unsure:

 

[I like Serena]

Ah ok! So we have a contradiction, and so it cannot be that two different representations correspond to the same number, right? To prove that formally mathematically, do we show that in the same way as here in the example for $n=2$ ?

We didn't check if $A_1=A_1'$ yet, did we? If they can be different, we have still found a different representation.

And yes, logically we do a proof by induction.

 

[mathmari]

We didn't check if $A_1=A_1'$ yet, did we? If they can be different, we have still found a different representation.

Do we not have $$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow -A_1 B+A_0=-A_1' B+A_0 \Rightarrow -A_1 B=-A_1' B \Rightarrow B(A_1-A_1')=0 \Rightarrow A_1-A_1'=0 \Rightarrow A_1=A_1'$$ Or can we not use that if $a\cdot b=0$ then either $a=0$ or $b=0$ ? :unsure:

 

[I like Serena]

Do we not have $$-A_1 B+A_0=-A_1' B+A_0' \Rightarrow -A_1 B+A_0=-A_1' B+A_0 \Rightarrow -A_1 B=-A_1' B \Rightarrow B(A_1-A_1')=0 \Rightarrow A_1-A_1'=0 \Rightarrow A_1=A_1'$$ Or can we not use that if $a\cdot b=0$ then either $a=0$ or $b=0$ ?

Yes we do. It's just that it wasn't proven yet. It should be proven, so now it is.

 

[mathmari]

Yes we do. It's just that it wasn't proven yet. It should be proven, so now it is.

So we have that in this specific case we have the uniqueness, and we have to prove that in the same way gor general $n$ by induction,right? :unsure:

Base case : For $n=1$ we have that $A=A_0$ and $A=A_0'$. Since $A_0=A_0'$, we are done.

Inductive Hypothesis : For $n=k$ we have that a $k$-digit number has a unique representation.

Inductive Step : For $n=k+1$ we have a $(k+1)$-digit number. Let $A=(-1)^{k}\cdot A_k\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0$ and $A=(-1)^{k}\cdot A_k'\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}'\cdot B^{k-1}+\ldots -A_1'\cdot B+A_0'$.
Then $$(-1)^{k}\cdot A_k\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0=(-1)^{k}\cdot A_k'\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}'\cdot B^{k-1}+\ldots -A_1'\cdot B+A_0'$$ Considering it modulo $B^k$ we get $$(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0=(-1)^{k-1}\cdot A_{k-1}'\cdot B^{k-1}+\ldots -A_1'\cdot B+A_0'$$ from which we get $A_{k-1}=A_{k-1}', \ \ldots , \ A_1=A_1', \ A_0=A_0'$ because of the inductive hypothesis.
Then we get \begin{align*}&(-1)^{k}\cdot A_k\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0=(-1)^{k}\cdot A_k'\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0 \\ & \Rightarrow (-1)^{k}\cdot A_k\cdot B^{k}=(-1)^{k}\cdot A_k'\cdot B^{k}\\ & \Rightarrow (-1)^kB^k(A_k-A_k')=0 \\ & \Rightarrow A_k-A_k'=0 \\ & \Rightarrow A_k=A_k'\end{align*} And so the two representations are the same, i.e. the representation is unique. Is that correct? :unsure: Could you give me a hint for (d) ? :unsure:

 

[I like Serena]

So we have that in this specific case we have the uniqueness, and we have to prove that in the same way gor general $n$ by induction,right? :unsure:

Base case : For $n=1$ we have that $A=A_0$ and $A=A_0'$. Since $A_0=A_0'$, we are done.

Inductive Hypothesis : For $n=k$ we have that a $k$-digit number has a unique representation.

Inductive Step : For $n=k+1$ we have a $(k+1)$-digit number. Let $A=(-1)^{k}\cdot A_k\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0$ and $A=(-1)^{k}\cdot A_k'\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}'\cdot B^{k-1}+\ldots -A_1'\cdot B+A_0'$.
Then $$(-1)^{k}\cdot A_k\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0=(-1)^{k}\cdot A_k'\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}'\cdot B^{k-1}+\ldots -A_1'\cdot B+A_0'$$ Considering it modulo $B^k$ we get $$(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0=(-1)^{k-1}\cdot A_{k-1}'\cdot B^{k-1}+\ldots -A_1'\cdot B+A_0'$$ from which we get $A_{k-1}=A_{k-1}', \ \ldots , \ A_1=A_1', \ A_0=A_0'$ because of the inductive hypothesis.
Then we get \begin{align*}&(-1)^{k}\cdot A_k\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0=(-1)^{k}\cdot A_k'\cdot B^{k}+(-1)^{k-1}\cdot A_{k-1}\cdot B^{k-1}+\ldots -A_1\cdot B+A_0 \\ & \Rightarrow (-1)^{k}\cdot A_k\cdot B^{k}=(-1)^{k}\cdot A_k'\cdot B^{k}\\ & \Rightarrow (-1)^kB^k(A_k-A_k')=0 \\ & \Rightarrow A_k-A_k'=0 \\ & \Rightarrow A_k=A_k'\end{align*} And so the two representations are the same, i.e. the representation is unique.Is that correct?

Looks correct to me. (Nod)

Could you give me a hint for (d) ?

What do they mean by "complement number"? (Wondering)

Btw, we didn't properly have an algorithm for (b) yet, did we?
Question (d) likely builds on the algorithm of (b).