Implementation of Base Conversion
This site offers several examples where representing a number in a base different from the customary 10 may have a great advantage. For example, binary representation is instrumental in solving Nim, Scoring, Turning Turtles and other puzzles. As every one knows nowadays, this is also the system underlying the modern computer technology.
Along with the binary, the science of computers employs bases 8 and 16 for it's very easy to convert between the three while using bases 8 and 16 shortens considerably number representations.
To represent 8 first digits in the binary system we need 3 bits. Thus we have,
Let's combine the first few conversion in a table:
For the sake of reference, representation of a number in a system with base (radix) N may only consist of digits that are less than N.
More accurately, if
|(1)||M = akNk + ak-1Nk-1 + ... + a1N1 + a0|
with 0 ≤ ai < N we have a representation of M in base N system and write
|M = (akak-1...a0)N|
If we rewrite (1) as
|(2)||M = a0 + N·(a1 + N·(a2 + N·...))|
the algorithm for obtaining coefficients ai becomes more obvious. For example,
Let's represent the algorithm mnemonically: (result is a string or character variable where I shall accumulate the digits of the result one at a time)
A few words of explanation.
- "" is an empty string. You may remember it's a zero element for string concatenation.
- Here we check whether the conversion procedure is over. It's over if M is less than N in which case M is a digit (with some qualification for N>10) and no additional action is necessary. Just prepend it in front of all other digits obtained previously. The '+' plus sign stands for the string concatenation.
- If we got this far, M is not less than N. First we extract its remainder of division by N, prepend this digit to the result as described previously, and reassign M to be M/N.
- This says that the whole process should be repeated starting with step 2.
I would like to have a function say called Conversion that takes two arguments M and N and returns representation of the number M in base N. The function might look like this
This is virtually a working Java function and it would look very much the same in C++ and require only a slight modification for C. As you see, at some point the function calls itself with a different first argument. One may say that the function is defined in terms of itself. Such functions are called recursive. (The best known recursive function is factorial:
Not all programming languages (Basic is one example) allow functions to call themselves recursively. Recursive functions may also be undesirable if process interruption might be expected for whatever reason. For example, in the Tower of Hanoi puzzle, the user may want to interrupt the demonstration being eager to test his or her understanding of the solution. There are complications due to the manner in which computers execute programs when one wishes to jump out of several levels of recursive calls.
Note however that the string produced by the conversion algorithm is obtained in the wrong order: all digits are computed first and then written into the string the last digit first. Recursive implementation easily got around this difficulty. With each invocation of the Conversion function, computer creates a new environment in which passed values of M, N, and the newly computed S are stored. Completing the function call, i.e. returning from the function we find the environment as it was before the call. Recursive functions store a sequence of computations implicitly. Eliminating recursive calls implies that we must manage to store the computed digits explicitly and then retrieve them in the reversed order.
In Computer Science such a mechanism is known as LIFO - Last In First Out. It's best implemented with a stack data structure. Stack admits only two operations: push and pop. Intuitively stack can be visualized as indeed a stack of objects. Objects are stacked on top of each other so that to retrieve an object one has to remove all the objects above the needed one. Obviously the only object available for immediate removal is the top one, i.e. the one that got on the stack last.
Then iterative implementation of the Conversion function might look as the following.
The function is by far longer than its recursive counterpart; but, as I said, sometimes it's the one you want to use, and sometimes it's the only one you may actually use.