## Converting a base-x number Directly to a base-y number in 1880

Posted by mark schwartz on April 8, 2016

__Introduction:__

I have a collection of about 50 math text books dated from about 1850 to 1900. There are many algorithms in these texts that are the same as the algorithms (and rules) in today’s texts. However, many of these old texts have very interesting, insightful and utilitarian algorithms. There is no explanation for their no longer existing in current math texts.

__The Story:__

In 1880, Todhunter’s *Algebra for Beginners *(page 270) describes an algorithm for converting a non-base-10 number to another non-base-10 number. (It is to be noted that the algorithm works for base-10 to base-x and the converse as well!). In most texts of today, such a conversion is done in two steps: first, convert the given number to base-10 and second, convert that base-10 number to the desired base. For example, convert 321_{4 }to base-3.

First convert 321_{4 }to 57_{10} and then convert 57_{10 }to 2010_{3 }. There are several algorithms for converting the base-10 number to a base-x number. The most common one is to do a series of divisions of the base-10 number by the base-x number until the quotient is zero, which signals the end of the process and that remainder is the last digit in the new base-x number. The series of remainders of the divisions is the base-x number, building that number from right to left. The following steps demonstrate this process.

321_{4} = 3(4^{2}) + 2(4) + 1 = 57_{10} and then to convert this to base-3 …

__ __57 ÷ 3 = 19 r 0

19 ÷ 3 = 6 r 1

6 ÷ 3 = 2 r 0

2 ÷ 3 = 0 r 2

Result: 321_{4} = 2010_{3}

Mr. Todhunter, however, describes an algorithm which converts 321_{4} __directly__ to 2010_{3} without converting from base-4 to base-10 to base-3.

Take a look at the sequence of divisions below, the quotients look erroneous … but they are correct! A detailed explanation follows and is the essence of Mr. Todhunter’s algorithm. It may well be that in 1880 this was a common and well-known procedure, but Mr. Todhunter’s presentation is the only one I’ve seen so far. Here’s how he converts 321_{4} to base-3.

321 ÷ 3 = 103 r 0

103 ÷ 3 = 12 r 1

12 ÷ 3 = 2 r 0

2 ÷ 3 = 0 r 2

Again 321_{4} = 2010_{3}

Here’s how it works and why the quotients look so odd.

321 ÷ 3 = 103 because …

The division is the standard division algorithm with one exception. Normally, if the division of the first single digit in the dividend doesn’t work, the usual division algorithm says move on and divide a two digit number by the divisor. *But, in Mr. Todhunter’s algorithm, this first division must be done, not skipped.*

The next paragraph lays out the rules (in bold italics) for Mr. Todhunter’s algorithm, using the above example.

Dividing the 3 in 321 by 3 results in 1, with a subtraction remainder of 0, ‘bring down’ the 2. ** Recall that in Mr. Todhunter’s algorithm this first division must be done, not skipped. **In essence, the result of the first subtraction is 02, not 2. The purpose of including the zero remainder is that after the next digit in the dividend is ‘brought down’,

**The result of this (0•4 + 2) is 2.**

*the remainder digit is multiplied by the base of 4 (base of the given term) and then added to the digit that was brought down.*

*This calculated term is divided by the target base 3.*Continuing, this calculated term 2 divided by 3 is zero, with a subtraction remainder of 2. Bring down the 1 and the outcome is 21. Multiply 2 by 4 and add 1 (2•4 + 1) = 9. Again, it’s the calculated term divided by 3.

Now divide the calculated term 9 by 3, and the result is 3, remainder 0. This is the first remainder and therefore the first digit in the answer (as seen above).

Again, the key is: determine the calculated term and that *calculated term* is divided by the target base. One way to track this work is: after bringing down the next digit in the dividend, determine the calculated term, write the calculated term under the term brought down, scratch out the term bought down, and then proceed with dividing the calculated term by the target base. Most students worked out their own tracking system. This procedure has to be done slowly at first because it looks like long division but Mr. Todhunter introduces an important difference.

It is a very handy (and ingenious) algorithm for converting any base number to any other base. Practice, practice, practice and it will become as routine as the algorithm which includes the intervening base-10 number.

Below is another example to help you see how this works. Notice the first division.

Convert 242_{5 }to base 3.

242 ÷ 3 = 044 r 0 (the first calculated term is 2•5 + 4 = 14)

44 ÷ 3 = 13 r 0 (the calculated term is 1•5 + 4 = 9)

13 ÷ 3 = 02 r 2 (the calculated term is 1•5 + 3= 8)

2 ÷ 3 = 0 r 2

The answer: 242_{5} = 2200_{3} (72 base 10 if you must know)

I don’t know if Mr. Todhunter’s created or “borrowed” this method, but in any event, it’s a very interesting conversion algorithm and if you get comfortable with it, I believe it’s a little faster than the traditional base “x”, to base 10, to base “y”.

## Leave a Reply