Base Conversion

For more information, see Horner's method on Wikipedia.

This tutorial demonstrates how to convert between any two numerical bases with support for all real numbers. Common numeric bases include base 2 (binary), base 8 (octal), base 10 (decimal), and base 16 (hexadecimal). For the purposes of this tutorial, support will be provided for bases up to 36. Horner's method provides an efficient way to convert numbers between two arbitrary bases. This method, named after William George Horner, uses the properties of polynomial factorization and will be used in this tutorial to convert numbers into base 10.

An example implementation can be found here.

Explanation

For more information, see Radix on Wikipedia.

A numeric base, also referred to as a radix (plural radices) is the number of unique digits used to represent a numeric quantity. Base 10 is the most commonly used base, in which there are 10 unique digits (0 through 9).

As mentioned above, Horner's method evaluates polynomials in terms of $x$. It can be rewritten to represent a number as a polynomial as $({\text{digit}}_{n}...{\text{digit}}_{1}{\text{digit}}_{0})_{b_{1}}={\text{digit}}_{n}\cdot b_{2}^{n}+...+{\text{digit}}_{1}\cdot b_{2}^{1}+{\text{digit}}_{0}\cdot b_{2}^{0}$. Horner's method can optimize this calculation by factoring out the base, resulting in the following iterative formula:

$result=0$

$result=result\cdot b_{2}+{\text{digit}}_{i}{\text{ for }}i=n,n-1,...,0$

This tutorial utilizes a method that converts the input number to base 10 as an intermediary.

Base Implementation

Prerequisites

A list (digits::list) must be defined and contain all desired digits in order of value. A typical list contains the digits 0 through 9 and the letters A through Z, which adds up to 36 items.

Additionally, several variables must be defined:

• (i) — the loop counter
• (quotient) — a rolling quotient used in converting from base 10
• (output) — the output of the script

Scripts

define convert (number) from base (base) to base 10
set [output v] to (0)
set [i v] to (1)
repeat (length of (number))
    set [output v] to (((output) * (base)) + ((item # of (letter (i) of (number)) in [digits v]) - (1)))
    change [i v] by (1)
end

define convert (number) from base 10 to base (base)
set [output v] to []
set [quotient v] to (number)
repeat until <(quotient) = (0)>
    set [output v] to (join (item (((quotient) mod (base)) + (1)) of [digits v]) (output))
    set [quotient v] to ([floor v] of ((quotient) / (base)))
end

define convert (number) from base (base) to base (target base)
if <(number) = (0)> then
    set [output v] to (0)
else
    if <(base) = (target base)> then
        set [output v] to (number)
    else
        convert (number) from base (base) to base 10
        convert (output) from base 10 to base (target base)
    end
end

Extending Support

It is possible for base conversion to work with fractional parts of numbers as well as integer parts. This is because the exponent on the base continues to decrease by one past the decimal point. For example, consider the base 10 number 10.683. This number can be represented as:

$1\cdot 10^{1}+0\cdot 10^{0}+6\cdot 10^{-1}+8\cdot 10^{-2}+3\cdot 10^{-3}$

Alternative versions of the scripts shown above should be added that support fractions, as well as any modifications that should be made. As such, the input will need to be split into its integer and fractional parts which will be handled separately.

Some extra variables will also need to be defined:

• (integer part) — a variable containing the integer part of the input
• (fractional part) — a variable containing the fractional part of the input
• (decimal found?) — a variable used for splitting the input
• (divisor) — the divisor used when converting a fraction to base 10
• (digit index) — an index used when converting a fraction from base 10 to another base
• (decimal precision) — the number of digits to come after the decimal point. This should be set by the user.

Fractions

define split (number) by decimal
set [integer part v] to []
set [fractional part v] to []
set [decimal found? v] to (0)
set [i v] to (1)
repeat (length of (number))
    set [letter v] to (letter (i) of (number))
	if <(letter) = [.]> then
        set [decimal found? v] to (1)
    else
        if <(decimal found?) = (0)> then
            set [integer part v] to (join (integer part) (letter))
        else
            set [fractional part v] to (join (fractional part) (letter))
        end
    end
    change [i v] by (1)
end

define convert fraction (fraction) from base (base) to base 10
set [output v] to (0)
set [divisor v] to (base)
set [i v] to (1)
repeat (length of (fraction))
    change [output v] by (((item # of (letter (i) of (fraction)) in [digits v]) - (1)) / (divisor))
    set [divisor v] to ((divisor) * (base))
    change [i v] by (1)
end

define convert fraction (fraction) from base 10 to base (base)
set [output v] to (0)
set [digit index v] to (fraction)
repeat until <<(digit index) = (0)> or <(length of (output)) = (decimal precision)>>
    set [digit index v] to ((number) * (base))
    set [output v] to (join (output) (item (([floor v] of (number)) + (1)) of [digits v]))
    set [number v] to ((number) mod (1))
end

define convert (number) from base (base) to base (target base)
...
if <(base) = (target base)> then
    set [output v] to (number)
else
    split (number) by decimal
    convert (integer part) from base (base) to base 10:: custom
    convert (output) from base 10 to base (target base):: custom
    if <<not <(fractional part) = []>> and <not <(fractional part) = (0)>>>then
        set [integer part v] to (output)
        convert fraction (fractional part) from base (base) to base 10
        convert fraction (output) from base 10 to base (target base)
        set [output v] to (join (join (integer part) [.]) (output))
    end
end

Negatives

Adding support for negative numbers requires only two minor modifications to the code.

define split (number) by decimal
...
if <(decimal found?) = (0)> then
    if <not <(letter) = [-]>> then
        set [integer part v] to (join (integer part) (letter))
else
    ...
end

define convert (number) from base (base) to base (target base)
if <(number) = (0)> then
    ...
else
    ...
end
if <(letter (1) of (number)) = [-]> then
    set [output v] to (join [-] (output))
end