Representation of signed integers of base B

In summary: No, the representation is unique if the digits are all distinct, but it is possible for two different numbers in the representation to have the same value. In the case of our example, the number $200112$ has the value $-2\cdot 3^5+0\cdot 3^4-0\cdot 3^3+1\cdot 3^2-1\cdot 3+2=-478$.
  • #1
mathmari
Gold Member
MHB
5,049
7
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?
 
Technology news on Phys.org
  • #2
mathmari said:
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)

mathmari said:
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$? 🤔

mathmari said:
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? 🤔
 
  • #3
Klaas van Aarsen said:
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:
 
  • #4
mathmari said:
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)
 
  • #5
Klaas van Aarsen said:
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:
 
  • #6
First off, the answer to (a) was not correct. (Shake)

mathmari said:
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$? 🤔

mathmari said:
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. 🤔

mathmari said:
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... 🤔
 
  • #7
Klaas van Aarsen said:
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:
Klaas van Aarsen said:
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:
Klaas van Aarsen said:
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:
 
Last edited by a moderator:
  • #8
mathmari said:
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. 🤔
mathmari said:
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$. 🤔
mathmari said:
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? 🤔
 
  • #9
Klaas van Aarsen said:
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:
 
  • #10
mathmari said:
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. 🤔
 
  • #11
Klaas van Aarsen said:
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:
 
  • #12
mathmari said:
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. 🤔
 
  • #13
Klaas van Aarsen said:
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:
 
  • #14
mathmari said:
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. 🤔
 
  • #15
Klaas van Aarsen said:
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:
 
  • #16
mathmari said:
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. 🧐
 
  • #17
Klaas van Aarsen said:
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:
 
  • #18
mathmari said:
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)

mathmari said:
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). 🤔
 

1. What is the purpose of representing signed integers in base B?

Representing signed integers in base B allows for a more efficient and concise way of storing and manipulating numbers. It also allows for a wider range of numbers to be represented compared to traditional binary representation.

2. How are negative numbers represented in base B?

Negative numbers in base B are typically represented using a sign bit, where 0 represents a positive number and 1 represents a negative number. This sign bit is typically placed in the most significant bit (MSB) position.

3. What is the range of numbers that can be represented using base B for signed integers?

The range of numbers that can be represented using base B for signed integers depends on the number of bits used to represent the number. For example, using 8 bits, the range of numbers that can be represented is -128 to 127 for base 10. The range increases as the number of bits increases.

4. How does one perform arithmetic operations on signed integers represented in base B?

Arithmetic operations on signed integers represented in base B can be performed using the same rules as traditional binary representation. The only difference is that the sign bit must be taken into account when performing operations such as addition, subtraction, multiplication, and division.

5. What are the advantages of using base B for representing signed integers?

Using base B for representing signed integers allows for a more compact representation of numbers, which in turn saves memory space. It also allows for a wider range of numbers to be represented compared to traditional binary representation. Additionally, arithmetic operations can be performed more efficiently using base B representation.

Similar threads

Replies
9
Views
1K
  • Programming and Computer Science
Replies
1
Views
931
  • Computing and Technology
Replies
4
Views
740
  • Calculus and Beyond Homework Help
Replies
1
Views
500
  • Programming and Computer Science
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
506
  • Calculus and Beyond Homework Help
Replies
2
Views
244
  • Introductory Physics Homework Help
Replies
2
Views
321
Replies
27
Views
890
  • Introductory Physics Homework Help
Replies
12
Views
718
Back
Top