*Challenge problems* Base conversion

posted Nov 1, 2012, 8:34 AM by Samuel Konstantinovich   [ updated Nov 16, 2012, 6:26 AM ]
;This page is under construction.

We write numbers in decimal (also known as base 10). Computers only store/process data using binary numbers (base 2). There are many other useful number bases that we use every day, base 60 is used in clocks, base 16 is used by many artists when naming colors on a computer. You should learn more about these bases, but the topic has been eliminated from school entirely. 

These problems require that you learn to convert numbers into different bases. You must understand the algorithms before you start writing the code. I don't expect you to come up with the algorithm on your own, but I do expect you to implement it yourself. You should wiki/google number base conversion to get an idea of how it works before attempting the examples. 

;;;PART A, basic conversion

1. Write a function binary to decimal:
;(btod x)    
;precondition:
;x must be an integer that consists of 1's and 0's
;that represents a binary number
;postcondition
;the value returned is the decimal equivalent of the 
;binary number x
(btod 1000) is 8
(btod 1001) is 9
(btod 10010) is 18
(btod 11110) is 30

2. Write a function to convert decimal to binary:
;(dtob x)
;precondition:
;x is any integer
;postcondition:
;the value returned is an integer that consits of 0's and 1's
;that represents a binary number equivalent to x
(dtob 10) is 1010
(dtob 8) is 1000
(dtob 13) is 1101
(dtob 50) is 110010

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;PART B, any base conversion
;You can easily convert your functions to work with any base 10 or lower:

3. Write a function base N to decimal
;(ntod x n)
;precondition:
;x must be an integer that consists of digits that are strictly less than n.
;the digits of x represent a base n number
;n <= 10
;postcondition
;the value returned is the decimal equivalent of the number x

base 3 examples:
(ntod 100 3) is 9
(ntod 101 3) is 10
(ntod 110 3) is 12

base 4 examples:
(ntod 100 4) is 16
(ntod 101 4) is 17
(ntod 212 4) is 38

4. Write a function decimal to base N
;(dton x n)
;precondition:
;x is any integer
;postcondition:
;the value returned is an integer that consits of digits strictly less than n
;that represents a base n equivalent to x

base 3 examples:
(dton 9 3) is 100
(dton 10 3) is 101
(dton 12 3) is 110

base 4 examples
(dton 16 4) is 100
(dton 17 4) is 101
(dton 36 4) is 210

5. Write a function that converts from base N to base M:
(ntom x n m)
example:
(ntom 1000 2 3)  is 22.
This means take the binary number 1000, and convert it to base 3. 
We need to use decimal as a middle step: 1000 is 8 in decimal, 8 in decimal is 22 in base 3.

How can you test this function? 
Come up with test cases that you know the answer to!


;;;PART C, advanced conversion
;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;How do we handle number bases higher than 10?!?!?
;We will use lists instead of integers to store the digits:
;in base 16, 13AF is a number, A stands for 10, F stands for 15... but we cannot write
;that way in an integer, instead we will write it as: '( 1 3 10 15)  

6. Improve your dton to give a list of digits as follows:
(dToAnyN x n)
;precondition:
;x must be an a list of numbers each strictly less than 10.
;postcondition
;the value returned is the base N equivalent of the number stored in list x.
(dToAnyN 13 2) -> ( 1  1  0  1)
(dToAnyN 36 4) -> ( 2  1  0 )
;now hex examples:
(dToAnyN 15 16) -> ( 15 )  
(dToAnyN 16 16) -> ( 1  0 )
(dToAnyN 33 16) -> ( 2  1 )
(dToAnyN 63 15) -> ( 3 15 )


7. improve your ntod to take a list of digits as follows:
(anyNtoD x n)
;precondition:
;x must be a list of integers each strictly less than n
;postcondition
;the value returned is the decimal equivalent of the number stored in list x. 
(anyNtoD '(1 1 0 1) 2) -> 13
(anyNtoD '(1 1 0 1) 3) -> 37 
(anyNtoD '(3 15) 16)  -> 63





Comments