## Overview

This article covers the algorithm for and methods, and the math for, converting numbers and strings from/to one number base to another number base.

This kind of function I use all the time in my software so that users have a choice of the kind of input they would like to feed into my programs. I like to build in flexibility for my input, while leaving the absolutely simplest possible so as not to make the software hard to use. This is the type of function I use in 80%-90% of my programs and even some DHTML web pages for input handling: I want users to have the flexibility of being able to put any type of input format they would like.

here is a question I answered about converting decimal fractions to binary used to drive meto distraction in college. now it's normal for me and I think about bitset fixed point arithmetic C++ classes.

## number base conversion - base to base

you can do this with a calculator if you have one. if you don't use TTCALC.

we are going to convert an unsigned binary number (base 2) 11100101011 to a new number base which we are going to invent. it could just as easily be hexadecimal (base 16) but I want you to not be stuck in a rut with canned ideas.

the new numbering system uses the numbering system of hexadecimal with the additional characters all the way through Z, for a total of 26 letters + 10 digits which is 36 characters, so the number base to convert TO is 36. The number base to convert FROM is binary, or 2.

The character set could just as well all be letters for that matter or even be punctuation, or symbols, the choice of the character set for representation of digits is entirely up to me, the inventor.

So our allowable digits character set is going to be `0123456789abcdefghijklmnopqrstuvwxyz`

Get a decent scientific calculator which can do number BASEs like an HP 33s if you are cheap, very functional and useful and lasts a long time on coin cells or Li-Ion built-in rechargeable batteries. I have listed some very nice calculators. the HP 48IIg and 50g is an excellent calculator, but there's a lot of things about it that drive me up the wall,and a lot of things I like, and it uses up AAA and CR2032 batteries fairly quickly with college use so buy them in bulk. Casio graphing calculators have always been nice feature-wise and easy to use for programmers, and so have HP 33s and HP 35s.

You can skip the following steps if the conversion can be done directly on your calculator, but you should still learn how to do this the hard way, since you will need to learn how to code this. This is the type of function I use 80%-90% of my programs and even some DHTML web pages for input handling: I want users to have the flexibility of being able to put any type of input format they would like.

- convert to base 10, or whatever base is native, using your calculator, or your program.
- after the number is fully converted to a native base, convert the number to the target base.

I just posted a feature request into ttcalc to handle bit shifts and rotates, it's a necessary part of programming work. until then, use ttcalc to multiply the from_digit positions of the by their appropriate base power.

## The Math

p=zero-based digit position right to left (base power index) d[p]=digit at position p b=base from n=number of digits in number to convert from

$\mathrm{number}=\sum _{p=0}^{n-1}{d}_{p}\times {b}^{p}=({d}_{0}\times {b}^{0})+({d}_{1}\times {b}^{1})+({d}_{2}\times {b}^{2})+...+({d}_{n-1}\times {b}^{n-1})$

You can ignore the zeros if you want to save calculator time.

for the example, let's look at the digit positions.

11100101011 ----------- 10000000000 09876543210

everything to the left that we don't see are zero digits, so we can ignore those.

we have 1's in position 0, 1, 3, 5, 8, 9, 10. using our equation above and pluggin in the appropriate stuff, we get $\mathrm{number}=\sum _{p=0}^{11-1}{d}_{p}\times {2}^{p}=(1\times {2}^{0})+(1\times {2}^{1})+(0\times {2}^{2})+(1\times {2}^{3})+(0\times {2}^{4})+(1\times {2}^{5})+(0\times {2}^{6})+(0\times {2}^{7})+(1\times {2}^{8})+(1\times {2}^{9})+(1\times {2}^{10})=1835$

You should memorize the powers of 2 and at least some of 16. you will use them a lot.

You should be able to write your own algorithm and think it out for yourself.

Usually it means working the number from left to right digit-wise, but according to its base power index (what I call p), it's exactly the opposite direction (base power index 0 is on the right and counts leftward).

To get the decimal answer (or native base) in the calculator converted back to binary (or any base), use the following algorithm:

## decimals

thing iofthe digitpositionss like a number line going in both directions,where the digit to the left of the desimal point is 0.

base 2 weightings are only different from base 10 weightings in that just to the left of the decimal point is 2^0 and to the right is 2^-1, to the right of that is 2^-2, to the right of that is 2^-3 and so on.

0 Σ digitValue*base^digitpos digitpos=-5

the digitvalue would be in the range 0..1 (the range of 0..base-1)

take 0.8515625 base 10-->base2 for instance.

work from left to right (larger values to smaller).

0. < 2^0 (1) so put 0 to left of decimal point.

.5 >= 2^-1 (0.5) so subtract 0.5 from 0.8515625 which gives 0.3515625 and put a 1 past 1st answer decimal point, 0.1

.04321 < 2^-2 (0.25) so subtract 0.25 from 0.3515625 which gives 0.1015625 and put a 1 past 1st answer decimal point, 0.11

.04321 < 2^-3 (0.125) so put a 0 past 3rd answer decimal point, 0.110

.04321 < 2^-4 (0.0625) so subtract 0.0625 from 0.1015625 which gives 0.0390625 and put a 1 past 1st answer decimal point, 0.1101

.04321 >= 2^-5 (0.03125) so subtract 0.03125 from 0.0390625 which gives 0.0078125 and put a 1 past 5th answer decimal point, 0.11011

.04321 < 2^-6 (0.015625) so put a 0 past 6th answer decimal point, 0.110110

.04321 >= 2^-7 (0.0078125) so subtract 0.0078125 from 0.0078125 which gives 0.0 and put a 1 past 7th answer decimal point, 0.1101101

some may be be irrational, a repeating decimal, or something else you will have to cut off, but a few like this one will be representable. the ones that won't will not end with 0.0 so early.

best case is you end up with a 0 for "gives".

## Number base conversion integer to string algorithm:

variables: base_to=base you are converting to last_to_digit_pos=last zero-based digit_to position, right-to-left last_from_digit_pos=last zero-based digit_from position, right-to-left digit_from_pos=current from_digit position digit_to_pos=current digit_to position number_from=initially, number to start with result=number_to power algorithm: function power(base, n) result = 1 for i = 1 to n result = result * base next return result end function algorithm #1: COMMENT: this algorithm skips directly to the correct digit. COMMENT: it *can* be used for for making strings, but not recommended, see latter lines. function integer_to_base_string(base_to, number_from, byreference result) base_charset = "0123456789abcdefghijklmnopqrstuvwxyz" result = 0 number_from = 0 if (0 == number_from) then result_string = "0" return success end if while number_from != 0 do COMMENT: powbase = find the next smallest/lesser power of base_to COMMENT: that is closest to number_from COMMENT: figure out what position that power of (base-to-convert-to) is COMMENT: for powbase for digit_to_pos = 0 to last_from_digit_pos powbase = power(base_to, digit_to_pos) if (powbase > number_from) then digit_to_pos = digit_to_pos - 1 powbase = power(base_to, digit_to_pos) exit this for loop else if (powbase == number_from) then exit this for loop end if next COMMENT: write a digit_to down in that position as part of the answer. digit_to = ToInteger(number_from / base_to) if (digit_to > base_to) then return failure end if number_from = number_from - (digit_to * powbase) put digit_to in its correct place in result at position digit_to_pos end while end function algorithm #2: COMMENT: we will assume zero-based indexes into strings function integer_to_base_string(base_to, number_from, byreference result_string) base_charset = "0123456789abcdefghijklmnopqrstuvwxyz" COMMENT: for Javascript, maximum usable integer digits is 17 (2^53). COMMENT: you will need a lot more powerful power function for this, one that does floating point. last_to_digit_pos = Math.floor(Math.pow(power(2,53),1/36.0)) result_string = "" if (0 == number_from) then result_string = "0" return success end if is_leading_zero_digits = true for digit_to_pos = last_to_digit_pos to 0 step -1 powbase = power(base_to, digit_to_pos) digit_to = ToInteger(number_from / powbase) if (digit_to > base_to) then COMMENT: number_from too large for conversion, return failure return failure endif number_from = number_from - (digit_to * powbase); if (is_leading_zero_digits and 0 != digit_to) then is_leading_zero_digits = false end if if (not is_leading_zero_digits) then COMMENT: if your strings are 1-based, then simply add 1 to digit_to result_string = result_string + base_charset.charAt(digit_to) endif next return success end function

## Number base conversion string to integer algorithm:

variables: base_to=base you are converting to last_to_digit_pos=last zero-based digit_to position, right-to-left last_from_digit_pos=last zero-based digit_from position, right-to-left digit_from_pos=current from_digit position digit_to_pos=current digit_to position number_from=initially, number to start with string_from=the number to convert from in base base_to in the form of a string number_to= power algorithm: function power(base, n) result = 1 for i = 1 to n result = result * base next return result end function COMMENT: we will assume zero-based indexes into strings function StringPos(string_to_search, char_to_find) is_found = false for index = 0 to string_to_search.length() - 1 if (char_to_find == string_to_search.charAt()) then is_found = true exit this for loop end if next if (is_found) then return index else COMMENT: return failure return -1 end if end function algorithm #1: COMMENT: we will assume zero-based indexes into strings function base_string_to_integer(base_from, string_from, byreference number_to) base_charset = "0123456789abcdefghijklmnopqrstuvwxyz" string_from_length = string_from.length() last_from_digit_pos = string_from_length - 1 MAX_from_digit_pos = Math.floor(Math.log(Math.pow(2,53))/Math.log(base_from)) number_to = 0 if (last_from_digit_pos > MAX_from_digit_pos) { return failure } for digit_from_pos = 0 to last_from_digit_pos COMMENT: the .toLowerCase is entirely optional. If your character set string is case sensitive, COMMENT: then use the string as it is without that function. digit_from = base_charset.indexOf(string_from.charAt(last_from_digit_pos - digit_from_pos).toLowerCase()); if (-1 == digit_from) { return failure } powbase = power(base_from, digit_from_pos) number_to = number_to + (digit_from * powbase) next return success end function

or you can simply in the display section put ttcalc's input and output base to whatever canned base you want, and then just type in the numbers. but I am sure this is not what your instructor is wanting you to do. I think he wants you to learn how to convert the numbers yourself. the reason why is sometimes in programming, you need to write number-string conversion routines and this requires the process I am outlining - breaking it down into powers of the base you want it in.

so you had better learn how to do this by hand now, or you will be up a creek when it comes time to do this in the real world over and over again programmatically and not with a calculator. sometimes you just need to build up your own library of routines, and this is one of them.

## Number of digits

Number of base N (64, 36, 16, 10, 8, 2) digits that this program is compatible with in Javascript because of floating point arithmetic and its 17 usable mantissa digits (without corruption).

Math.floor(Math.log(Math.pow(2,53))/Math.log(64))= (digits, upper and lower case, @ and _)

Math.floor(Math.log(Math.pow(2,53))/Math.log(62))= (digits, upper and lower case)

Math.floor(Math.log(Math.pow(2,53))/Math.log(36))= (digits, upper or lower case)

Math.floor(Math.log(Math.pow(2,53))/Math.log(16))= (hexadecimal, digits upper or lower case a-f)

Math.floor(Math.log(Math.pow(2,53))/Math.log(10))= (digits)

Math.floor(Math.log(Math.pow(2,53))/Math.log(8))= (digits 0-7)

Math.floor(Math.log(Math.pow(2,53))/Math.log(2))= (digits 0-1)