Discrete Mathematics/Number representations

Introduction

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

2×10³+8×10²+1×10¹+8×10⁰

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:

a_kb^k+a_k-1b^k-1+...+a₀b⁰

where the a_i are all less than b.

We write a number base b as (a_ka_k-1...a₀)_b.

For example, if we have the numeral 243 in base 6, we write it (243)₆. 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

(919)₁₂=9×12²+12¹+9=1317.

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)₁₂=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

1×10¹+1×10⁰+3×10^-1+4×10^-2+1×10^-3

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

a_kb^k+a_k-1b^k-1+...+a₀b⁰+a_-1b^-1+...

where the a_i 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

$c_{i}=\lfloor {6\gamma _{i-1}}\rfloor$

$\gamma _{i}=6\gamma _{i-1}-c_{i}$

i      ci                   γi                6γi
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)₆. (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

$(.{\overline {1819}})_{b}$

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 $(.{\overline {3145}})_{7}=\alpha$. Now then

$(3145.{\overline {3145}})_{7}=7^{4}\alpha$

And now

$(3145)_{7}+(.{\overline {3145}})_{7}=7^{4}\alpha$

which is

$(3145)_{7}+\alpha =7^{4}\alpha$

Then

$(3145)_{7}=7^{4}\alpha -\alpha$

$(3145)_{7}=(7^{4}-1)\alpha$

And finally

${(3145)_{7} \over 7^{4}-1}=\alpha$

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

$\alpha =1111/2400$

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 ${\sqrt {2}}$ 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

$q_{0}+{1 \over q_{1}+{1 \over q_{2}+{1 \over q_{3}+\ldots }}}$

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

$[q_{0};q_{1},q_{2},q_{3},\ldots ]$

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

Consider

$\alpha =[3;1,2,5]$

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

${1 \over 5}$

The next digit 2 tells us to perform

$2+{1 \over 5}=11/5$

and then take the reciprocal to get

${5 \over 11}$

Now the next digit 1 tells us to perform

$1+{5 \over 11}={16 \over 11}$

and then to take the reciprocal to get

${11 \over 16}$

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

$\alpha ={59 \over 16}$

Converting to continued fraction representation

Again, we draw up a table.

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

$\theta _{i}=\theta _{i-1}^{-1}-q_{i-1}$

$q_{i}=\lfloor \theta _{i}^{-1}\rfloor$

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 q_i repeat), that

every periodic continued fraction is a number in the form

${a\pm {\sqrt {b}} \over c}\ \mathrm {for} \ a,b,c\in \mathbb {Z}$

For example, consider the continued fraction

${\begin{matrix}\alpha &=&[2;2,1,2,2,1...]\\&=&[2;{\overline {2,1,2}}]\end{matrix}}$

Now

$[2;{\overline {2,1,2}}]=[2;2,1,{\overline {2,2,1}}]$

which we can rewrite as

$\alpha =2+{1 \over {2+{1 \over {1+{1 \over \alpha }}}}}$

Now we can simplify to obtain

$\alpha =2+{1 \over {2+{1 \over {\alpha +1 \over \alpha }}}}$

$\alpha =2+{1 \over {2+{\alpha \over \alpha +1}}}$

$\alpha =2+{1 \over {3\alpha +2 \over \alpha +1}}$

$\alpha =2+{\alpha +1 \over 3\alpha +2}$

$\alpha ={7\alpha +5 \over 3\alpha +2}$

$\alpha {(3\alpha +2)}={7\alpha +5}$

$\alpha {(3\alpha +2)}-5=7\alpha$

$3\alpha ^{2}+2\alpha -5=7\alpha$

$3\alpha ^{2}+2\alpha -7\alpha -5=0$

$3\alpha ^{2}-5\alpha -5=0$

which is a quadratic equation and can be solved to obtain

$\alpha ={\frac {5+{\sqrt {85}}}{6}}$.

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

Convergents

Say we have a continued fraction [q₀; q₁, ... ] which represents a number n. Let us examine the following series of fractions [q₀], [q₀; q₁], [q₀; q₁, q₂] 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 ${\sqrt {6}}$.

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

$u_{i+1}=q_{i+1}u_{i}+v_{i-1}$

$v_{i+1}=q_{i+1}v_{i}+v_{i-1}$

${\begin{matrix}i&\theta _{i}&\theta _{i}^{-1}&q_{i}&u_{i}&v_{i}\\-1&&&&1&0\\0&{\sqrt {6}}&&2&2&1\\1&2-{\sqrt {6}}&1+{\sqrt {3/2}}&2&5&2\\2&-1+{\sqrt {3/2}}&2+{\sqrt {6}}&4&22&9\\3&-2+{\sqrt {6}}&1+{\sqrt {3/2}}&2&49&20\\\end{matrix}}$

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, ...