by Zoran Horvat

Nov 03, 2013

Given a string representing a number, base in which the number is written and new base to which number should be converted, write a function which produces a string representing the same number in new base. Digits higher than 9 should be represented by capital letters A, B, ..., Z. Together with decimal digits 0 to 9, this makes total of 36 digits that can be represented. Hence, both bases will be numbers between 2 and 36, inclusive.

Example: For number 1002 with base 3 and new base 8 (octal number) output value should be 35. Same number in new base 10 would produce output 29, and in new base 16 (hexadecimal number) it would produce output 1D.

This exercise deals with numbers written in positional system. This means that each position is associated with specific "weight", or a multiplier applied to the digit at that position. Take decimal numeric system as an example. Weights associated with positions are one, for lowest digit, ten, for the following digit, a hundred, a thousand, and so on.

In general case, when number is written in positional system with base b with total of n digits, weights of positions would grow exponentially with position number: b^0, b^1, b^2, ... , b^n-1. Actual value of the number, given the values of its digits, is then:

Now we can begin solving the problem. We are given a number in base b in form of a stream of digits. The task is to entail digits of another number in base d, so that values of two numbers are equal:

There are some oddities to note about this formula. First, bases of two numbers are different. Second thing is the consequence: number of digits differs in two numbers, in general case. Even more, although number of digits in the left-hand number (n) is known in advance, the length of the number on the right (m) is unknown. It could be deduced from n and number bases but, as will soon become obvious, we don't really need to know m.

It would be quite difficult to guess all the digits in the second number at once, given the number value (sum on the left side of the equation) and the target base d. This conclusion leads to the idea of entailing target number digits in some sort of an iterative process. One possibility is to build on the fact that lowest digit in the target number is solely determined by the overall number value. It is not affected by higher digits in any way (this is the core quality of all positional number systems). If we divide the left-hand sum by the base d, division remainder will be the value of lowest digit in the number on the right:

Now that we have decided the value of lowest digit, we can completely remove it from both sides of the equation:

Even more, both sides of the equation are now divisible by d after remainder has been subtracted from them:

Net result of this transformation is that now we have got a completely new number in base b on the left side. At the same time, number on the right side in base d has all digits left intact, with only the lowest digit missing - the lowest digit has been eliminated from the equation. What used to be the second lowest digit in the target number has now become the least significant digit in the new target number.

Way forward from this point is quite simple. Just repeat the process once more to extract the next lowest digit in the target number. And again, repeat the process to calculate the next digit and so on. Digits are deduced one at a time, until all m digits are calculated. The only difficulty is that m is not known. So we need a stopping condition.

If we observe the process described above, we will notice that the number on the left side of the equation is reduced in every step. This comes from dividing that number with base d. As the process continues, we can expect that at some point the whole number is going to become equal to zero. Th would be the point in which we stop looking for more digits on the right. Should we continue, all further digits would be zero - leading zeros, in fact - and they are not needed.

So the stopping criterion is to look when the source number drops to zero. This comes with a trap: the source number might already be zero at the beginning, even before we have extracted the first digit for the resulting number in base d. In that case, the resulting number should also be set to zero and the whole calculation skipped entirely.

The core function which converts number bases is now fairly simple, although dependant on a couple of helper functions:

```
function ConvertNumber(number, b, d)
begin
newNumber = ""
while number <> "0"
begin
number = Divide(number, b, d, out remainder)
newDigit = ValueToDigit(remainder)
newNumber = Concatenate(newDigit, newNumber)
end
if newNumber ="" then
newNumber = "0"
end
```

Most important helper function used is called Divide. It receives a number, its base and a divisor. On output, this function returns result of the division, which is a number in base which was specified as an argument. In addition, the function returns division remainder through an output parameter. Here is the pseudocode of this function:

```
function Divide(number, base, divisor, out remainder)
begin
remainder = 0
result = ""
for i = 0 to Length(number) - 1
begin
digitValue = DigitToValue(number[i])
remainder = base * remainder + digitValue
newDigitValue = remainder / divisor -- integer division
remainder = remainder mod divisor
if newDigitValue > 0 OR result <> "" then
newDigit = ValueToDigit(newDigitValue)
result = Concatenate(result, newDigit)
end
if result = "" then
result = "0"
return result
end
```

There are a few points to mention in this function. First of all, implementation is based on simple pencil-and-paper algorithm. But the catch is that division is performed in specified base, rather than in decimal number system. As a consequence, we only have current digit and current remainder converted to integers at any given time. This is simply because division and modulo operations in programming languages are defined for integers, rather than for numbers with arbitrary base.

Nevertheless, this pencil-and-paper process produces one output digit in every step, and these digits are appended to the resulting number from most significant position towards less significant ones. And again, there is a catch. If digit produced on the output is zero and resulting number is empty (this is the first digit), then the digit is dropped. It would be a leading zero anyway, and it serves no purpose in the number apart from needlessly growing it in length. But then, there is another catch: if no digits are appended to the result by the end of the loop, then one zero is still passed to it (this is the result of the final if statement in the function). This step resolves the situation where all digits in the result are leading zeros, meaning that the whole output number is zero.

Below is the complete implementation of console application in C# which converts number bases.

```
using System;
namespace ChangingBases
{
public class OperationResult
{
static int DigitToValue(char digit)
{
int value = 0;
if (digit >= '0' && digit <= '9')
value = digit - '0';
else // digit is between 'A' and 'Z'
value = digit - 'A' + 10;
return value;
}
static char ValueToDigit(int value)
{
char digit = '\0';
if (value < 10)
digit = (char)('0' + value);
else
digit = (char)('A' + (value - 10));
return digit;
}
static string Divide(string number, int numberBase, int divisor,
out int remainder)
{
remainder = 0;
string result = string.Empty;
for (int i = 0; i < number.Length ; i++)
{
int digitValue = DigitToValue(number[i]);
remainder = numberBase * remainder + digitValue;
int newDigitValue = remainder divisor;
remainder = remainder % divisor;
if (newDigitValue > 0 || result != string.Empty)
{
char newDigit = ValueToDigit(newDigitValue);
result = result + newDigit;
}
}
if (result == string.Empty)
result = "0";
return result;
}
static string ConvertNumber(string number, int numberBase,
int newBase)
{
string newNumber = string.Empty;
while (number != "0")
{
int reminder = 0;
number = Divide(number, numberBase, newBase, out reminder);
char newDigit = ValueToDigit(reminder);
newNumber = newDigit + newNumber;
}
if (newNumber == string.Empty)
newNumber = "0";
return newNumber;
}
static void Main(string[] args)
{
Console.Write("Enter number (empty to exit): ");
string number = Console.ReadLine();
while (!string.IsNullOrEmpty(number))
{
Console.Write(" Enter number base (2-36): ");
int numberBase = int.Parse(Console.ReadLine());
Console.Write("Enter new number base (2-36): ");
int newBase = int.Parse(Console.ReadLine());
string newNumber = ConvertNumber(number, numberBase, newBase);
Console.WriteLine("{0} ({1}) = {2} ({3})",
number, numberBase, newNumber, newBase);
Console.Write("Enter number (empty to exit): ");
number = Console.ReadLine();
}
}
}
}
```

When application is run, it produces output like this:

```
Enter number (empty to exit): 1002
Enter number base (2-36): 3
Enter new number base (2-36): 8
1002 (3) = 35 (8)
Enter number (empty to exit): 1002
Enter number base (2-36): 3
Enter new number base (2-36): 10
1002 (3) = 29 (10)
Enter number (empty to exit): 1002
Enter number base (2-36): 3
Enter new number base (2-36): 16
1002 (3) = 1D (16)
Enter number (empty to exit): 97ADSFKH32497GH2
Enter number base (2-36): 32
Enter new number base (2-36): 10
97ADSFKH32497GH2 (32) = 348659477389970058232354 (10)
Enter number (empty to exit):
```

If you wish to learn more, please watch my latest video courses

This course begins with examination of a realistic application, which is poorly factored and doesn't incorporate design patterns. It is nearly impossible to maintain and develop this application further, due to its poor structure and design.

As demonstration after demonstration will unfold, we will refactor this entire application, fitting many design patterns into place almost without effort. By the end of the course, you will know how code refactoring and design patterns can operate together, and help each other create great design.

More...

In four and a half hours of this course, you will learn how to control design of classes, design of complex algorithms, and how to recognize and implement data structures.

After completing this course, you will know how to develop a large and complex domain model, which you will be able to maintain and extend further. And, not to forget, the model you develop in this way will be correct and free of bugs.

More...

Zoran Horvat is the Principal Consultant at Coding Helmet, speaker and author of 100+ articles, and independent trainer on .NET technology stack. He can often be found speaking at conferences and user groups, promoting object-oriented development style and clean coding practices and techniques that improve longevity of complex business applications.

- From Dispose Pattern to Auto-disposable Objects in .NET
- What Makes Functional and Object-oriented Programming Equal
- Overcoming the Limitations of Constructors
- Does the Command Pattern Require Undo?
- What Makes while Loop a Poor Choice in Programming
- How to Wrap System.Random Into an Infinite IEnumerable<int> Sequence
- More...

- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Writing Purely Functional Code in C#
- Tactical Design Patterns in .NET: Creating Objects
- Tactical Design Patterns in .NET: Control Flow
- Tactical Design Patterns in .NET: Managing Responsibilities
- Advanced Defensive Programming Techniques
- Writing Highly Maintainable Unit Tests
- Improving Testability Through Design