Discrete Mathematics/Number representations

Introduction edit

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 edit

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

2×103+8×102+1×101+8×100

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:

akbk+ak-1bk-1+...+a0b0

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 edit

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)12=9×122+121+9=1317.

Converting base 10 to base b edit

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 edit

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×101+1×100+3×10-1+4×10-2+1×10-3

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

akbk+ak-1bk-1+...+a0b0+a-1b-1+...

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 edit

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 edit

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

 

Then

 
 

And finally

 

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

 

Continued fractions edit

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 edit

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

 

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 edit

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 edit

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

 

Now

 

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

Convergents edit

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