Skip to content

Base 10 to Base R Conversion

While the conversion from base R to decimal is straightforward and appear uniform, there are actually two different operations in the computation of the weight. Note that we start counting from the first digit to the left of the decimal point (i.e., the dot) and that we count from 0. As we move to the left, we increment the power by one and as we move to the right, we decrement the power by one.

If we are not dealing with power, we should instead multiply the weight by the base as we move to the left and divide the weight by the base as we move to the right. Thus, we actually have two different treatment depending on whether we are on the left or the right of the decimal point.

To start our explanation, we will first mention the terminologies used. We call the sequence of numbers to the left of the dot as the whole_number and the sequence of numbers to the right of the dot as the fraction.

Terminologies

Real Number
1
<whole number> . <fraction>
Where <whole number> and <fraction> are both integers.

We have two different treatment for the conversion depending on whether the number is part of the whole_number or the fraction. To convert to a number of base R:

Kind Method Explanation
Whole Numbers Repeated division by R Number to the left of dot; weight is multiplied by R when convert from base 10 ⇝ base R; the reverse is division by R
Fractions Repeated multiplication by R Number to the right of dot; weight is divided by R when convert from base 10 ⇝ base R; the reverse is multiplication by R

For now, we will only cover positive number. In other words, the number n > 0. We do not consider n = 0 because it is simply 0 in any base.

Repeated Division by R

This method is used to convert a decimal whole number to any other base R. The method is as follows:

Repeated Division Algorithm

We start with the given number and will perform two operations:

  • Integer Division: Truncate the values after the dot.
  • Remainder: Compute the remainder after integer division.

We will repeatedly divide the number by R until we reach 0. For each number produced by this repeated division (starting from the first original number), we compute the remainder when divided by R. This remainder is then appended to the beginning of the result.

Symbol

Do note that the remainder may need to be converted to the proper symbol especially when the base is greater than 10. We typically use alphabets A-Z to represent the symbol corresponding to 10 onwards. Thus, we should be able to easily represent numbers until base 36 (26 alphabets + 10 digits).

Repeated Division by R
1
2
3
4
5
6
7
8
# input : number num in base 10
#         base R
# output: number num in base R as a string res
res := ""
while (num > 0) do
  res := (num % R) ++ res # repeated division (concatenate to result)
  num := num / R          # integer  division
end

In this example, we convert 43 to base 2. The result should be (101011)2. You can check yourself that indeed (101011)2 = (43)10.

R num Division Remainder
2 43 43/2 = 21 43%2 = 1 ← LSB
2 21 21/2 = 10 21%2 = 1
2 10 10/2 = 5 10%2 = 0
2 5 5/2 = 2 5%2 = 1
2 2 2/2 = 1 2%2 = 0
2 1 1/2 = 0 1%2 = 1 ← MSB
2 0 STOP

The result can be obtained by reading from bottom-up (simulating moving left-to-right from dot): (101011)2.

Termination

Do we actually need to stop after we reach 0? Actually no! Let's look at what happens if we continue.

R num Division Remainder
2 43 43/2 = 21 43%2 = 1 ← LSB
2 21 21/2 = 10 21%2 = 1
2 10 10/2 = 5 10%2 = 0
2 5 5/2 = 2 5%2 = 1
2 2 2/2 = 1 2%2 = 0
2 1 1/2 = 0 1%2 = 1 ← MSB
2 0
2 0
2 0
:
2 0

Notice how we get all zeroes on the left side. This means, insted of getting (101011)2, we get (00...00101011)2. If we look at the conversion again, it does not change the value.

Repeated Multiplication by R

This method is used to convert a decimal fraction to any other base R. The method is as follows:

Repeated Multiplication Algorithm

We start with the given number and will perform two operations:

  • Multiplication: Multiply two real numbers. We assume an infinite precision.
  • Truncate: We truncate the fraction part.

We will repeatedly multiply the number by R until we reach 0. For each number produced by this repeated multiplication (starting from the number after the first multiplication), we find the truncation of the number and look at the whole number part. This whole number is then appended to the end of the result.

Symbol

Do note that the remainder may need to be converted to the proper symbol especially when the base is greater than 10. We typically use alphabets A-Z to represent the symbol corresponding to 10 onwards. Thus, we should be able to easily represent numbers until base 36 (26 alphabets + 10 digits).

Repeated Multiplication by R
1
2
3
4
5
6
7
8
# input : number num in base 10
#         base R
# output: number num in base R as a string res
res := ""
while (num > 0) do
  num := num * R           # repeated multiplication
  res := res ++ trunc(num) # truncation (concatenate to result)
end

In this example, we convert 0.3125 to base 2. The result should be (0.0101)2. You can check yourself that indeed (0.01012 = (0.3125)10.

R num Multiplication Truncation
2 0.3125 0.3125 × 2 = 0.625 ⌊0.625⌋ = 0 ← MSB
2 0.625 0.625 × 2 = 1.25 ⌊1.25⌋ = 1
2 0.25 0.25 × 2 = 0.5 ⌊0.5⌋ = 0
2 0.5 0.5 × 2 = 1.0 ⌊1.0⌋ = 1 ← LSB
2 0 STOP

The result can be obtained by reading from top-down (simulating moving right-to-left from dot): (0.0101)2.

Termination

Do we actually need to stop after we reach 0? Actually no! Let's look at what happens if we continue.

R num Multiplication Truncation
2 0.3125 0.3125 × 2 = 0.625 ⌊0.625⌋ = 0 ← MSB
2 0.625 0.625 × 2 = 1.25 ⌊1.25⌋ = 1
2 0.25 0.25 × 2 = 0.5 ⌊0.5⌋ = 0
2 0.5 0.5 × 2 = 1.0 ⌊1.0⌋ = 1 ← LSB
2 0
2 0
2 0
:
2 0

Notice how we get all zeroes on the right side. This means, insted of getting (0.0101)\(_{2}\), we get (0.010100...00)2. If we look at the conversion again, it does not change the value.

On the other hand, will it ever reach 0? Not necessarily. Try converting (0.1)10 to base 2. You will find that the value will repeat itself after some time1.

R num Multiplication Truncation
2 0.1 0.1 × 2 = 0.2 ⌊0.2⌋ = 0 ← MSB
2 0.2 0.2 × 2 = 0.4 ⌊0.4⌋ = 0
2 0.4 0.4 × 2 = 0.8 ⌊0.8⌋ = 0
2 0.8 0.8 × 2 = 1.6 ⌊1.6⌋ = 1
2 0.6 0.6 × 2 = 1.2 ⌊1.2⌋ = 1
2 0.2 we have seen this before

Can you see the cycle 0.2 ⇝ 0.4 ⇝ 0.8 ⇝ 0.6 ⇝ 0.2 in the column num? If you continue, due to the deterministic nature of the algorithm, you will never get any other values beside those. So, it is not guaranteed to terminate. But, luckily, we can be as close as we want to the actual value.

So, to ensure termination, we will limit this to at most 10 digits.

Exercises

Repeated Division by R

Convert 2100 to base 3.

(2212210)3

Steps
Base Value Remainder
3 2100 0
3 700 1
3 233 2
3 77 2
3 25 1
3 8 2
3 2 2
Repeated Multiplication by R

Convert 0.111111...111... to base 3. Note that this is value is infinitely long consisting of repeated 1. Can you still convert this?

(0.01)3

Steps

Here, we will simply look at the first 3 digits since they are repeated. We also use the fact that 0.999... with 9 repeated infinitely is equal to 1.

Base Value Remainder
3 0.111... × 3 = 0.333... ⌊0.333...⌋ = 0
3 0.333... × 3 = 0.999... ⌊0.999...⌋ = 1

We can prove that 0.999... = 1 as follows:

  • Let x = 0.999...
  • Let 10x = 9.999...
  • Then 10x - x = 9x = 9.999... - 0.999 = 9
    • Since 9x = 9, then x = 1

  1. If you try this on the tools above, the only reason why it terminates is due to "approximation" nature of floating point number. The value is not exact and this exactness is the one that saved us. ↩