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.
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.
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.
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 γ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)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
On converting (3145)7 to base 10, we obtain the following
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, ...