In Technical Informatics, number systems are important. I mean, just like in any other field. You must know how to represent your numbers. A Number Representation is when you take a set of numbers and make it into a set and do operations with it. Sounds awfully like groups in abstract algebra (we talked about this in the computer science post).
Anyways, you take a set of numbers or symbols and you number them. The set of these symbols is called an alphabet. An example of an alphabet for the decimal system is:
With this alphabet base 10 we represent our numbers in our day-today lifes.
Now, this is not the only useful numeric system to exist. We have also:
So we denote any system of numbers with base "b" as
Fun Fact!
Each of this systems have their own use and obviously benefits and downsides. For Informatics an Hexadecimal system is a very useful way of compacting a large amount of combinations within a very small set of characters.
For example, when using the Hexadecimal system we can pack 256 numbers in two characters. While that would take us 128 characters if we speak about bits or in the binary system. Now, we use binary in computers because we need a way to convey signals through electrical current. Theoretically we could have more than two signals, but that is not good. This is because even small fluctuations in the electromagnetic fields around or your environment can make a bit with intermediate states "flip" so we try to keep them as far apart as possible, so that even with small fluctuations, our computers do not crash. This is critical and it was one of the failures of early computers. Basically reliability and cost is the main driver for using only 0 and one.
The ENIAC computer used 10 signal levels! Which obviously requires a very high level of precision and basic operations like addition are very complicated to perform...
Numbers with a finite lenght
Yep, in maths you can do whatever you want. And therefore you can have numbers that have a set length. We normally always ignore the zeros to the left in a number. But a number with a finite length n and a base b can be denoted as:
So the number 183 would be denoted as
**This is not necessarily the correct way of representing the numbers**
Natural Number Representation
Warning: This will get very mathematical and complicated!
Let b ∈ N where b>1 , then every natural number Z where 0 ≤ z ≤ b^n -1 is representable as a word of the length n via
through [eq 1.]
And
Where i= 0,1,....., n-1
Ok now what? That is put in mathematical words. In human readable words look at eq. 1 . You have a sum to represent any number z in any system starting at n-1 and ending at i=0. We discussed n earlier as the maximum length. b is the base so base 10 or base 2 for example. This is kind of scientific notation. Let us see an example for base 10:
We replace n-1 from eq. 1 to 3, because there are 4 digits on the number. So n= 4-1 = 3.
So for a binary number 111011
Explained simpler and with less math:
Maximum numbers you can represent
We add the -1 because we also want to represent Zero because we are talking about positive integers. So in hexadecimal with 2 symbols we can represent:
From Zero up to 31.
Reverse Conversion
Ok nice, Now I know how to convert into any other number from decimals. Now how do I convert decimal into binary (base 2) or into base b?
Let us convert 47 into binary
47/2 = 23 | Rest 1 |
23/2=11 | Rest 1 |
11/2 = 5 | Rest 1 |
5/2 = 2 | Rest 1 |
2/2 = 1 | Rest 0 |
1/2 = 0 | Rest 1 |
You start basically dividing the number by the base. Until you reach a result that is equal to zero. Now that you have the table you read it from bottom to the top! So the result is 101111 in base 2. All of this can be described through the Horner-schema or Horner's method, a very very complex equation that help us convert from any base to any base without middle steps. But that is indeed very very complicated, so we will just keep to the basics.
Horners Method
Because computers have hard times with polynomials, there had to be a method for converting from hexadecimal or binary into decimal right? Yes absolutely. As we saw, any conversion can also be made into a polynomial. Let us check our first equation:
Which we can simplify right? As every single z is being multiplied by a b. And then instead of solving a complex polynomial we are just kind of multiplying times x. Let us first reorder the equation into something like:
Now Horner's method is very complex but it is used to solve polynomials of high degrees! And if we look at our equation, our polynomial is of the degree i. So using the Horner's method helps computer's save time and generalize. As we want any equation to be as general as possible.