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, 0=000, 1=001, 2=010, 3=011, 4=100, 5=101, 6=110, 7=111. Assume M=(2065)₈. In order to obtain its binary representation, replace each of the four digits with the corresponding triple of bits: 010 000 110 101. After removing the leading zeros, binary representation is immediate: M=(10000110101)₂. (For the hexadecimal system conversion is quite similar, except that now one should use 4-bit representation of numbers below 16.) This fact follows from the general conversion algorithm and the observation that 8=2³ (and, of course, 16=2⁴.) Thus it appears that the shortest way to convert numbers into the binary system is to first convert them into either octal or hexadecimal representation. Now let see how to implement the general algorithm programmatically.

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 = a_kN^k+a_k-1N^k-1+...+a₁N¹+a₀

with 0 <= a_i < N we have a representation of M in base N system and write

M = (a_ka_k-1...a₀)_N

If we rewrite (1) as

(2)	M = a₀+N(a₁+N(a₂+N*...))

the algorithm for obtaining coefficients a_i becomes more obvious. For example, a₀=M modulo n and a₁=(M/N) modulo n, and so on.

Recursive implementation

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)

result = ""
if M < N, result = 'M' + result. Stop.
S = M mod N, result = 'S' + result
M = M/N
goto 2

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

1	String Conversion(int M, int N)	// return string, accept two integers
2	{
3	if (M < N)	// see if it's time to return
4	return new String(""+M);	// ""+M makes a string out of a digit
5	else	// the time is not yet ripe
6	return Conversion(M/N, N) + new String(""+(M mod N));	// continue
7	}

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: n!=n*(n-1)!.) The function calls (applies) itself to its arguments, and then (naturally) applies itself to its new arguments, and then ... and so on. We can be sure that the process will eventually stop because the sequence of arguments (the first ones) is decreasing. Thus sooner or later the first argument will be less than the second and the process will start emerging from the recursion, still a step at a time.

Iterative implementation

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.

1	String Conversion(int M, int N)	// return string, accept two integers
2	{
3	Stack stack = new Stack();	// create a stack
4	while (M >= N)	// now the repetitive loop is clearly seen
5	{
6	stack.push(M mod N);	// store a digit
7	M = M/N;	// find new M
8	}
9	// now it's time to collect the digits together
10	String str = new String(""+M);	// create a string with a single digit M
11	while (stack.NotEmpty())
12	str = str+stack.pop()	// get from the stack next digit
13	return str;
14	}

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.

34221051

Amazon.com Widgets