# 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×10
^{3}+8×10^{2}+1×10^{1}+8×10^{0}

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*_{k}*b*^{k}+*a*_{k-1}*b*^{k-1}+...+*a*_{0}*b*^{0}

where the *a*_{i} are all less than *b*.

We write a number base *b* as (*a*_{k}*a*_{k-1}...*a*_{0})_{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×12^{2}+12^{1}+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×10
^{1}+1×10^{0}+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*_{k}*b*^{k}+*a*_{k-1}*b*^{k-1}+...+*a*_{0}*b*^{0}+*a*_{-1}*b*^{-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*[edit]

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

We write a table, using the following rules

ic_{i}γ_{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[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 *q*_{0} 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}q_{i}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 *q*_{i} 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 [*q*_{0}; *q*_{1}, ... ] which represents a number *n*. Let us examine the following series of fractions [*q*_{0}], [*q*_{0}; *q*_{1}], [*q*_{0}; *q*_{1}, *q*_{2}] 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, ...