Number Representations
Contents
Number Representations¶
A quantum computer and classic computer both needs some way to represent numbers. We need to be able to look at the result of our computation and relate it to a number. This means we need to understand how to represent numbers.
We will start by looking at representations on classical computers. This will build the conceptual framework needed to understand the Quantum Fast Fourier Transform.
Base Systems¶
We traditionally write numbers using decimal (base-10) notation. When we read 152, we are using the position of the digits to determine this means 1 hundred fifty two. The number is created by a combination of the digits and their position.
The digits available in a base-10 system are the values 0,1,2,3,4,5,6,7,8,9. We call the system base-10 because the location of the digits tell us the powers of two.
\( \begin{align} 152 =& 1*10^2 + 5*10^1 + 2*10^0 \end{align} \)
The digits available are also determined by the base. Since we are using base-10, we can use the digits from 0 to \(10-1=9\).
This process can be generalized to any base. Let us select 2 as our base. This means we can use digits from 0 to \(2-1=1\). A number is represented by a sequence of \(\{0,1\}\) digits. We can take \(110_{2}\) as our example.
Note
Many numbers can look like they belong to multiple bases. For example, our number here \(110\) is in base-2, but it is also a valid base-10 number. It could be one hundred ten. The subscript \(D_{2}\) is used to denote the base of the number. When not stated, it is assumed the number is in base-10.
What do these digits tell us? We still use the base and the position of the digits to read the number.
\( \begin{align} 110_{2} =& 1*2^2 + 1*2^1 + 0*2^0 \\ =& 4+2+0 \\ =& 6 \end{align} \)
The number \(110_{2}\) in base-2 is another representation of 6 in base-10. They both represent the same number. The number is just written in a different base. We take pick a third based and write 6 again, this time we use base-3.
\( \begin{align} 020_{3} =& 0*3^2 + 2*3^1 + 0*3^0 \\ =& 0 + 6 + 0 \\ =& 6 \end{align} \)
The three values \(6_{10}\), \(110_{2}\), and \(020_{3}\) are all representations of the same number. On an classical computer, the representation \(110_{2}\) is the most useful. Each physical wire on the computer can only transmit a high (1) or low (0) single. By representing a number using only two digit symbols, we can make a representation a processor can handle.
Converting to Non-Decimal Base¶
Since the base-10 (decimal) system is the most common for humans, we traditionally use it as the most common base. When we write numbers, we assume they are base-10 unless told otherwise.
There is an algorithm for converting a number from base-10 into any other base. It uses integer division and remainders.
When we divide two numbers, there are many ways to think about the answer. We can take a fraction like \(\frac{9}{2}\) and just leave it as a fraction. We could also use a decimal point to denote a partial value \(\frac{9}{2}=4.5\). In this case, we are saying that \(4\) is the closes whole number and we are off by \(0.5=\frac{5}{10}=\frac{1}{2}\).
We can also split the division up into two parts. The quotient, the whole number part of the result and the remainder. We use the division forward slash to mean quotient division. We have \(9/2=4\). The whole number part of the division results in \(4\), but this is not the entire answer. We know that \(2*4=8\). We are missing part of the number. The missing part is called the remainder.
We can use subtraction to find the remainder.
\( \begin{align} 9-2*4 =& 9-8 = 1 \end{align} \)
We use the precentage sign to denote the modulo, an operator that gives the remainder of a division. To get the remainder of 9 divided by 2, we would write \(9 \%2=1\).
To convert the number 28 to base-5, we compute remainders and quotients repeatedly. We stop when the quotient is zero.
\( \begin{align} 28/5 = & 5 \\ 28\%5 =& 3 \\ 5/5 =& 1 \\ 5\%5 =& 0 \\ 1/5 =& 0 \\ 1\%5 =& 1 \end{align} \)
The remainders we computed are \(3,0,1\). If we read these backwards, we get the base-5 value \(28_{10} = 103_{5}\).
We can implement this algorithm in Python. The digits are stored in a list.
#Convert a number from base-10 to given base
def toBase(num,base):
N=[]#place to store digits
while num > 0:
rem = num % base #remainder in python
num = num // base #quotient in python
N.append(rem)
#Digits are backward, reverse
N=N[::-1]
#Return array of digits
return N
We can convert a number to any base we want.
num=28
print(toBase(num,2))
print(toBase(num,3))
print(toBase(num,5))
The results are \(11100_{2}\), \(1001_{3}\), and \(103_{5}\).
Converting From Non-Decimal Base¶
To convert a number back, we just need to use the powers of the base. The number is a list. Let us call the list \(L\). The list \(L\) has \(n\) elements. The \(i\)-th element is in position \(L_{i}\) of the list. The first position in the list is \(L_{0}\). To convert a list stored in base-\(b\) back to base-10, we just need to compute a summation.
\( \begin{align} \sum_{i=0}^{n-1} L_{i} b^{n-1-i} \end{align} \)
We can confirm that \(103_{5}\) will compute to \(28_{10}\).
\( \begin{align} \sum_{i=0}^{2} L_{i} 5^{2-i} =& 1*5^2 + 0*5^1 + 1*5^0 \\ =& 25 + 3 \\ =& 28 \end{align} \)
The Python code for this conversion is given below.
#Convert from base given back to base-10
def fromBase(num,base):
result=0#Final Answer
n = len(num)
#Summation
for i in range(0,n):
#L_{i} * b^{n-1-i}
result=result+num[i]*(base**(n-1-i))
#return final answer
return result
We can test it as an inverse of the toBase function from the previous section.
A=toBase(num,2)
B=toBase(num,3)
C=toBase(num,5)
print(fromBase(A,2))
print(fromBase(B,3))
print(fromBase(C,5))
All three function calls return \(28_{10}\).
Polynomials¶
When we think of a number as being represented as an ordered list of digits and a base, we realize it looks like a polynomial. We can write \(103_{5}\) using a variable to represent the base instead of writing the \(5\).
\( \begin{align} f(b) =& 1*b^2 + 0*b^1 + 3*b^0 \\ =& 1*b^2 + 3 \end{align} \)
We have a polynomial function \(f(b)\) that evaluates to \(28\) when we use \(f(5)\).
We could also create a polynomial \(g(b)\) that represents \(28\) in base-10.
\( \begin{align} g(b) =& 2*b + 8 \end{align} \)
When we evaluate \(g(10)\) we get back \(28\).
Using bases to represent numbers are polynomials gives us an important tool to compute.
A practical computer processor has only so much space. Most modern computers have 64-bit processors. That means the processor can represent numbers between \(0\) and \(2^{64}-1\). The number 18,446,744,073,709,551,615 may seem impossibly large, but many problems in computation will require numbers larger than this. Applications in applied mathematics, chemisty, and physics often require significantly larger numbers.
For a simple experiment, let us imagine a retro 8-bit computer. It can only represent numbers from \(0\) to \(2^{8}-1=255\). When happens when we want to multiply \(900 * 350\)? The processor cannot handle numbers this big. Instead, we select our base as 256, the first number the system cannot handle.
\( \begin{align} b=& 256 \\ 900_{10} =& 3b + 132 \\ 172_{10} =& 1b + 94 \\ 315000_{10} =& 4b^2 + 206b + 120 \end{align} \)
By thinking of a number as a polynomial evaluated at a base, we can represent numbers larger than the processor can handle. This is called multiprecision arithmetic.
We can also develop algorithms for computing with numbers in this representation. We consider a number to be a list of coefficients and a base. When the polynomial coefficients are evaluated at the base, we get the base-10 number back.