Program to Convert Number Bases

Date: 07/12/99 at 11:02:43
From: Mike Manson
Subject: Easier way to convert base systems of numbers

Hi, 

I've learned that you can convert the base system of a number using 
the following method:

12461 base 10 --> base 4
     
     4|12461
        3115 r 1
         778 r 3
         194 r 2
          48 r 2
          12 r 0
           3 r 0
           0 r 3

then you take the remainders and read them backwards. So 12461 in base 
4 = 3002231.

This way works and I do understand the basic concepts of raising to 
whatever power involved in base conversions. I just need an easier way 
to do this. I am writing a computer program that will incorporate this 
function, and while I can use something similar to the above inside a 
programming loop, it would be easier if there were a way to do it 
using some type of equation expression. Someone suggested that there 
is an equation using log functions that can be used for base 
conversion. Any ideas?

Date: 07/12/99 at 12:45:01
From: Doctor Peterson
Subject: Re: Easier way to convert base systems of numbers

Hi, Mike.

The method you've demonstrated is by far the easiest method I know, 
and is exactly what I would use for a computer program. Any method you 
use will give you one digit at a time in a loop. There is a way that 
starts out by using the logarithm to find how many digits you need, 
then works from left to right rather than right to left; but logs are 
much slower then the divisions this method uses. If you want to get 
the digits of a number N from left to right, I would first just 
multiply 1 by the base repeatedly until the result, A, passes the 
number to be converted (this gives how many digits you will need); 
then get each digit by dividing this number A by the base to make it 
less than N, and divide N by A. The quotient is the digit to print and 
the remainder takes the place of N for the next step. For example, to 
convert 123 to base 4,

      1 * 4 = 4
      4 * 4 = 16
     16 * 4 = 64
     64 * 4 = 256 > 123

     256 / 4 = 64; 123 / 64 = 1 rem 59  ---> digit 1
     64  / 4 = 16;  59 / 16 = 3 rem 11  ---> digit 3
     16  / 4 = 4;   11 /  4 = 2 rem 3   ---> digit 2
     4   / 4 = 1;    3 /  1 = 3 rem 0   ---> digit 3

The answer is 1323 base 4.

As you can see, that takes the same amount of work for each step as 
your method, and a little extra work at the start. Both ways are 
equally easy to program.

Perhaps if you tell me what programming language you are using, I can 
help you see how to write these algorithms. Let me know if you need 
more help.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/12/99 at 21:48:30
From: (anonymous)
Subject: Re: Easier way to convert base systems of numbers

Thanks for the reply. I'm using C++ and based on the first way, I've 
come up with a program fragment that doesn't seem to work at this 
time. If you have any suggestions or examples, it would be extremely 
useful.

Much appreciation,
Matt

Date: 07/13/99 at 08:49:19
From: Doctor Peterson
Subject: Re: Easier way to convert base systems of numbers

Hi, Mike.

I'll try to put together a quick program for this, but what might be 
more useful (and quicker) is for you to send me your program (or at 
least the fragment that isn't working) so I can see what's wrong with 
it. That way we can help you correct your own thinking (or maybe just 
typing) rather than merely copy mine. I'll be waiting.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/13/99 at 17:50:03
From: (anonymous)
Subject: Re: Easier way to convert base systems of numbers

Yeah, I thought that would be the best way and I wanted to send it to 
you but the only problem is that the computer I have Turbo C++ 
installed on doesn't have any Internet connection and it has one of 
those old 5 1/4" floppy drives (*ouch*). Don't laugh, I do have a very 
good computer but it's a family one and I barely get enough time to 
work on it without someone else needing it. I'll see if I can just 
recopy for you. Otherwise, if you don't have enough time to write the 
actually code, a program outline, pseudocode type outline would be 
helpful.

Thank you,
Matt

Date: 07/13/99 at 22:30:08
From: Doctor Peterson
Subject: Re: Easier way to convert base systems of numbers

Hi, Matt.

You sound like my son, who has Turbo C++ on our old computer, and 
before that used our yet older 286 with only a 5 1/4" drive. We have 
managed to network him with our Pentium, but it's still limiting. All 
you have to send me should be the main loop that does the actual 
conversion, so don't try to copy the whole thing by hand. What I have 
in mind would be only a few lines, unless you're doing more than just 
converting. I did start writing my own version, and I'll probably send 
it after I see yours, once I get it done.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/16/99 at 17:09:20
From: Doctor Peterson
Subject: Re: Easier way to convert base systems of numbers

Hi, Matt. Since I haven't heard back from you, I wanted to send my 
code for converting bases, so you can see what I did. I suspect you 
may be taking a different approach, and I'd still like to see it.

Here are my two versions, based on the algorithm you first sent me and 
the one I sent back. Each has its advantages:

// right-to-left algorithm
 while (n > 0)
 {   // extract rightmost digit, convert to ASCII
  char digit = '0' + n % base;
  if (digit > '9')
   digit += ('A' - '9' - 1);
    // add digit to right of string
  string = digit + string;
    // remove digit from number
  n = n / base;
 }

// left-to-right algorithm
 int divisor = 1;
 while (divisor <= n)
 {   // find first power of base above number
  divisor *= base;
 }
 while ((divisor /= base) >= 1)
 {   // extract leftmost digit, convert to ASCII
  char digit = '0' + n / divisor;
  if (digit > '9')
   digit += ('A' - '9' - 1);
    // add digit to left of string
  string = string + digit;
    // remove digit from number
  n = n % divisor;
 }

In both cases, n is the number to be converted to a text string in the 
given base. I extract one digit at a time, and put the digit into 
ASCII form so that alphabetic characters follow numeric, as in hex; 
this can handle any base up to 36! I used a string object to hold the 
results; for the left-to-right version, you could just print out one 
character at a time.

By the way, my first version of the l-to-r version didn't work right 
for some numbers, because I got the second while wrong. It is a little 
tricky.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/