Discrete Mathematics/Number representations



You are already familiar with writing a number down, and having it mean a certain combination of tens, hundreds, and so on. This is one form of number representation, but there are others. We will look at number bases and continued fractions.

Number bases


You are already familiar with base-10 number representation. For example, the number 2818 is the same as


We can replace the number 10 here with any number and we obtain a different number. In general, we can represent an integer n in a base b by the following:


where the ai are all less than b.

We write a number base b as (akak-1...a0)b.

For example, if we have the numeral 243 in base 6, we write it (243)6. When we are in base 10 we simply write the number: for example the numeral 155 in base 10 is simply written 155.

However, given a number in a base b, how can we convert it to our natural base 10 system? Likewise, how can we convert a number from our base 10 system to base b?

The first is relatively easy, the other more difficult.

Converting base b to base 10


We simply use the definition of a base-b number to convert a base-b number to base 10 - that is we simply multiply out.

For example


Converting base 10 to base b


This task however is slightly more difficult, and there are several ways of performing this task.

One method is to write each step using the division algorithm from the Number theory section. For example, if we wish to convert 1317 to base 12:

1317 = 12 × 109 + 9
109 = 12 × 9 + 1
9 = 12 × 0 + 9

So in base 12, (919)12=1317.

Real numbers


We've just seen how we can convert integers from base to base, but how do we work with converting real numbers?

Recall in base 10 we write a number such as 11.341 as


and so we can extend our definition above of a base-b number to be


where the ai are all less than b, and the sum could terminate or go on indefinitely.

Again, how are we to convert these numbers from base to base? We can convert the integral part, but what about the fractional part (the part less than 1)?

Converting fractional n to base-b


Say we wish to convert .341 in base 10 to base 6.

We write a table, using the following rules

i      ci                   γii
0      0                   .341                2.046
1      2                   .046                0.276
2      0                   .276                1.656
3      1                   .656                3.936
4      3                   .936                5.616
5      5                   .616                3.696
6      3                   .696                4.176
7      4                   .176                1.056
8      1                   .056                0.336
9      0                   .336                2.016

It looks like this expansion will go on forever! We need to calculate for further values of i to see whether we hit a repeat value of γi to see whether we get a repetition.

So we have the approximation that .341 is near to (.20135341)6. (Calculate this using the definition. How close is our approximation?)

If we obtain a base-b representation for example, that looks something like (.18191819181918191819...)b we call the representation periodic. We often write this as


We use this same procedure to convert a fractional number to base-b by replacing the 6 above with b.

Converting fractional n to base 10


We have a nifty trick we can use to convert a fractional n in base-b to base 10 provided the representation repeats. Let us look at an example:

Consider  . Now then


And now


which is




And finally


On converting (3145)7 to base 10, we obtain the following


Continued fractions


In a sense, the base-b representation is nice, but it has a few shortcomings in respect to accuracy. We cannot reliably represent the number   using base-b representation. This is where the continued fraction representation comes in handy, which has some nice properties regarding quadratic irrationals.

A continued fraction is a number in the form


Since this notation is clearly rather cumbersome, we abbreviate the above to


Again we ask ourselves how can we convert from and to this number representation? Again converting from is simpler than converting to.

Converting from continued fraction representation


We simply use our definition of the continued fraction to convert from a continued fraction. This may look difficult, but in fact is quite simple depending on which end one starts with. Let's look at an example



Now, we work from right to left. We first have the fraction


The next digit 2 tells us to perform


and then take the reciprocal to get


Now the next digit 1 tells us to perform


and then to take the reciprocal to get


Now we must add q0 which is always greater than 1 and we get the result:


Converting to continued fraction representation


Again, we draw up a table.

Consider the fraction 12/22, and use the following rules in the table

i   θi      θi-1     qi
0   12/22   .       0
1   12/22   22/12   1
2   5/6     6/5     1
3   1/5     5/1     5

(stop since next row will be full of 0s)

So now the continued fraction for 12/22 is [0; 1, 1, 5].

Converting a periodic continued fraction to quadratic irrational


Firstly, we make note of a nice property of periodic continued fractions (where the sequence of qi repeat), that

every periodic continued fraction is a number in the form

For example, consider the continued fraction




which we can rewrite as


Now we can simplify to obtain


which is a quadratic equation and can be solved to obtain


Note that we can always roll up the continued fraction into the form (aα+b)/(cα+d)=α, which demonstrates the point that every quadratic irrational has a repeating continued fraction representation



Say we have a continued fraction [q0; q1, ... ] which represents a number n. Let us examine the following series of fractions [q0], [q0; q1], [q0; q1, q2] and so on. Each element of the series is known as a convergent. It turns out that the series of convergents provide the best rational approximations to n.

These can be calculated from the continued fraction representation, but also from the calculation table. Let us take  .

Continue as before, but place an extra -1 row, and set u-1=1, v-1=0. Iterate with the rules


and the sequence repeats and the continued fraction is [2; 2, 4, 2, 4, ... ]. We can continue the process to generate more convergents - the convergents are 2, 5/2, 22/9, 49/20, ...