colinrmitchell.com

Blog

Base Conversion in Haskell

Posted Monday, February 23rd 2015 in Programming - Permalink

Converting a number from one base to another is quite easy to do in Haskell. To convert a number from base 10 to another base, we must first know what the value of each digit in the new base is. These values are all powers of the base. For base 10, the first digit is the ones digit, or 100. The tens digit is 101, the hundreds digit is 102, and so forth. This also applies for every other base.

Once we know the value for each digit for the new base, we can convert a base 10 number to this base as follows:

1. Divide the number by the largest place value that is less than or equal to the number.
2. The digit will be the quotient of the division in step 1.
3. Continue at step 1. with the remainder of the quotient in step 1. If the power of the
   base for this digit is zero, stop.

As an example, we will convert 19 base 10 to base 3:

1. 19 / (3^2) = 19 / 9 = 2 R 1
   First digit is 2.
2. 1 / (3^1) = 1 / 3 = 0 R 1
   The second digit is 0.
3. 1 / (3^0) = 1 / 1 = 1 R 0
   The last digit is 1.

In Haskell, we can first get all of the powers of a number with the following list comprehension:

[base ^ y | y <- [0,1..]]

Now, we need a recursive function to define our algorithm above. We can define it as such:

dig _ [] = []
dig n (z:zs) = (quot n z) : (dig (rem n z) zs)

This functions takes a number and returns a list of digits. We have one end case: if we run out of digit places, we stop. The second line is the body of the function. It says to take the quotient of the number n and the largest digit place. It adds this to the digits that result from recursing this function with the remainder of the number divided by the largest digit place.

Now we can build our function to convert a base 10 number to an arbitrary base. The first consideration we will take is that we will not convert below base 2. Also, commonly, bases with more digits than base 10 use roman alphabet characters for digits larger than 9. We will also want to do this so that we can convert to, for example, hexidecimal, which uses digits zero through nine and ‘A’ through ‘F’. Each digit we calculate will now come from the list

['0'..'9'] ++ ['A'..'Z']

instead of just [0,1..9]. We can piece together out total function as

toBase :: Int -> Int -> String
toBase base x
   | (base < 2) || (base > 36)
      = ""
   | otherwise
      = dig x . reverse $ takeWhile ((>=) x) [base ^ y | y <- [0,1..]]
   where
      dig _ [] = []
      dig n (z:zs) = (digits !! (quot n z)) : (dig (rem n z) zs)

      digits = ['0'..'9'] ++ ['A'..'Z']

This function takes a base from 2 to 36, and a number in base 10, and converts it to the base. It begins by calculating all of the powers of the base that are equal to or less than the number,

reverse $ takeWhile ((>=) x) [base ^ y | y <- [0,1..]]

For example,

ghci> let x = 29
ghci> let base = 3
ghci> reverse $ takeWhile ((>=) x) [base ^ y | y <- [0,1..]]
[27,9,3,1]

It then applies the recursive function dig to calculate each digit using our algorithm from above. We can now convert to many bases!

ghci> toBase 3 19
"201"
ghci> toBase 2 127                                           
"1111111"                                      
ghci> toBase 16 27384                                   
"6AF8"         


List Posts Newest Posts Page 1Next Page