# coding: utf-8 #
#

# Conversion between numerical base systems

#

#

## Andreas Putz

#
# I created ths notebook after a tricky job interview question: # # "How would you convert a integer in the base 10 system to the hexadecimal system ?" # # So, my formal programming training has been a while, and while this is a textbook question, I have not pondered it for a decade or more. My answer was some tentative looping and some hint that the modulo operator might be helpful. So after wondering about this for a while, I decided to put some thought into it. And here it is. # # **Note:** This is not meant as a rigorous scientific acrticle, but a short treatise on the topic. Divison is a tricky IEEE operation for non-symbolic calculations. There are a lot of pitfalls for a naive implementation. # In[1]: import IPython from IPython.display import HTML, display import math from decimal import Decimal import tabulate # conda install tabulate # # Some Theory (Loosely based on "Springer, Mathematische Formeln") # # ## The position system # Each real number $x$ can be written in the following form: # # $$# x = x_m B^m + x_{m-1} B^{m-1} + x_0 B^0 + x_{-1} B^{-1} + \dots = (x_m x_{m-1}\dots x_1 x_0.x_{-1}\dots)_B #$$ # # where the integer $B>1$ is called the base and the digit $x_i \in \{0,\dots,B-1\}$. If $B>10$, the the decimal numbering is typically extended by adding alphabetic characters. # # Naming convention diverge from here on in the literature I have found, so for the sake of this work we will define the following: # * The **integer part** of $x$ is defined as $(x_m x_{m-1}\dots x_1 x_0)_B$ # * The **fractional part** of $x$ is defined as $(x_{-1}\dots)_B$ # ## Division operators in Python 3 # # ### Classic or True Division: x/y # Python 3 changed the definition of this operation. It now always returns a *float* and tries to approximate the true divison result according to IEEE specifications. # In[2]: tmp = 4/2;print('Integer divison:\t',tmp, ', result type: ', type(tmp)) tmp = 4/3;print('Integer divison:\t',tmp, ', result type: ', type(tmp)) tmp = 5/3;print('Integer divison:\t',tmp, ', result type: ', type(tmp)) tmp = -4/3;print('Integer divison:\t',tmp, ', result type: ', type(tmp)) tmp = -5/3;print('Integer divison:\t',tmp, ', result type: ', type(tmp)) tmp = 4.1/3.7;print('Integer divison:\t',tmp, ', result type: ', type(tmp)) # ### Floor Division: x//y # # Floor typically denotes a round down operation, i.e. it rounds to the biggest integer, which is smaller or equal than the number itself. Hence we get a different result for positive and neagite numbers as shown inthe example below. This will prove to be annoing for any conversion algorythm relying on this operation. # In[3]: tmp = 4//2;print('Floor divison:\t',tmp, ', result type: ', type(tmp)) tmp = 4//3;print('Floor divison:\t',tmp, ', result type: ', type(tmp)) tmp = 5//3;print('Floor divison:\t',tmp, ', result type: ', type(tmp)) tmp = -4//3;print('Floor divison:\t',tmp, ', result type: ', type(tmp)) tmp = -5//3;print('Floor divison:\t',tmp, ', result type: ', type(tmp)) tmp = 4.1//3.7;print('Floor divison:\t',tmp, ', result type: ', type(tmp)) # ### The modulo operation: x%y # # Now this is the tricky one. Inaccurately speaking, it is the remainder of the true division. Wikipedia has a better description, have fun ... # In[4]: url = 'https://en.wikipedia.org/wiki/Modulo_operation' iframe = '' IPython.display.HTML(iframe) # In[5]: tmp = 4%2;print('Modulo divison:\t',tmp, ', result type: ', type(tmp)) tmp = 4%3;print('Modulo divison:\t',tmp, ', result type: ', type(tmp)) tmp = 5%3;print('Modulo divison:\t',tmp, ', result type: ', type(tmp)) tmp = -4%3;print('Modulo divison:\t',tmp, ', result type: ', type(tmp)) tmp = -5%3;print('Modulo divison:\t',tmp, ', result type: ', type(tmp)) tmp = 4.1%3.7;print('Modulo divison:\t',tmp, ', result type: ', type(tmp)) # ### divmod # In[6]: for a,b in zip((4,4,5,-4,-5,4.1),(2,3,3,3,3,3.7)): print('a='+str(a),'\t,b='+str(b),',\tdivmod(a,b)='+str(divmod(a,b))) # So it looks as if divmod sotres the float divison and modul division in a tuple. # ### Summary # # And here we have it alltogether. I also got bored of the six lines, wo here is a little loop which does this a lot more elegantly # In[7]: mytable=[] mytable.append(('a','b','a/b','a//b','a%b','divmod(a,b)')) for a,b in zip((4,4,5,-4,-5,4.1),(2,3,3,3,3,3.7)): mytable.append((a,b,a/b,a//b,a%b,divmod(a,b))) display(HTML(tabulate.tabulate(mytable, tablefmt='html'))) # ## Operations on floats # This is actually more tricky than it sounds, as rounding errors and number finite number representaions start to play a role. # In[8]: mytable=[] mytable.append(('a','int(a)','round(a)','floor(a)','modf(a)','a%1','Decimal Magic','String Conversion')) for a in (4,4.1,4.5,4.6,-4.1,-4.5,-4.6): if "." in str(a): number_dec = str(a-int(a)).split('.')[1] else: number_dec = 0 mytable.append((a,int(a),round(a),math.floor(a),math.modf(a),a%1,Decimal.from_float(a)%1,number_dec)) display(HTML(tabulate.tabulate(mytable, tablefmt='html'))) # ## Translation Algorithms # # As the division and rounding algorithm behave slghtly differently for positive and negative numbers, we will treat only positive numbers. If we encounter a negative number, we will multiply by $-1$, apply the conversion algorithm, and then multiply by $-1$ again. # ### ($B\to 10$) # # Straigth forward, based on the equation above. # ### $(10\to B)$ # #
#

Algorithm (Base Conversion)

# Let $X=(y_m y_{m-1}\dots y_0.z_{-1}z_{-2}\dots)_{10}$ be a positive real number in the decimal system. We will treat the integer part $Y=(y_m y_{m-1}\dots y_0)$ and fractional part $Z=(z_{-1}z_{-2}\dots)$ individually. #

# Problem: Find # \begin{align*} # \tilde X=(\tilde y_n \tilde y_{n-1}\dots \tilde y_0.\tilde z_{-1} \tilde z_{-2}\dots)_{B} \text{ such that } X_{10}=X_B # \end{align*} #

# #
**Algorithm (Integer Part Y)**
#
# **Initialize**: $\tilde Y_0 = Y$ , $i=0$
# **repeat**
# # \begin{align*} # \tilde y_i &= \tilde Y_i \mod B \\ # \tilde Y_{i+1} &=\tilde Y_{i}/B - \tilde y_i/B \\ # i &=i+1 # \end{align*} # # **until** $\tilde Y_i=0$ #
# #
**Algorithm (Fractional Part Z)**
#
# **Initialize**: $\tilde Z_0 = Z$ , $i=0$
# **repeat**
# # \begin{align*} # \tilde z_i &= \text{integer}(\tilde Z_i * B) \\ # \tilde Z_{i+1} &=\tilde Z_{i}*B - \tilde y_i \\ # i &=i+1 # \end{align*} # # **until** $\tilde Z_i$ is whole or number of relevant digits is reached. #
# #
# # Implementation # ## Function to convert integer part # In[9]: def base10_to_newbase_integer(number=5326, base=16): ''' Converts a integer into a list of digits corresponding to a new base. Parameters ---------- number : int (5326) Base 10 input integer base : int (16) New base Yields ------ list List of digits in the new base. Notes ----- I did not add the usual convention to replace the digits above 9 with traditional alphabet notation. This is work for another day. ''' tmp = [] factor = 1 if number < 0: factor = -1 number = -number while True: if number < base: tmp.append(number) break else: number, remainder = divmod(number,base) tmp.append(int(remainder)) tmp.reverse() tmp[0] *= factor return tmp # A few testruns: # In[10]: mytable = [] mytable.append(('a','my converter (B=8)','oct(8)','my converter (B=16)','oct(16)')) for a in [12345,-12345,7,8,15,16]: mytable.append((a ,base10_to_newbase_integer(number=a,base=8),oct(a) ,base10_to_newbase_integer(number=a,base=16),hex(a))) display(HTML(tabulate.tabulate(mytable, tablefmt='html'))) # ## Function to convert fractional part # In[11]: def base10_to_newbase_fraction(number=0.6789, base=16,ndigits=5): ''' Converts the fractional part of a irrational number from base 10 to base B Parameters ---------- number : float (0.6789) Base 10 float 0<= number < 1 base : int (16) New base ndigits : int (5) Number of significant digits Yields ------ list List of digits in the new base. Notes ----- I did not add the usual convention to replace the digits above 9 with traditional alphabet notation. This is work for another day. I alos truncate at the maximum number of digits, not round. ''' tmp = [] digits = 0 while True: number, integer = math.modf(number*base) digits += 1 if number == 0 or digits > ndigits: break else: tmp.append(int(integer)) return tmp # In[12]: mytable = [] mytable.append(('a','my converter (B=8)','my converter (B=16)')) for a in [0.6789,-0.6789,0.,0.1,0.2]: mytable.append((a ,base10_to_newbase_fraction(number=a,base=8) ,base10_to_newbase_fraction(number=a,base=16))) display(HTML(tabulate.tabulate(mytable, tablefmt='html'))) # ## Now full float conversion: # In[13]: def base10_to_newbase(number=12345.6789, base=16,ndigits=5): ''' Converts the a float base 10 to base B Parameters ---------- number : float (12345.6789) Base 10 float base : int (16) New base ndigits : int (5) Number of significant fractional digits Yields ------ integer List of integer digits in the new base. fractional List of fractional digits in the new base. Notes ----- I did not add the usual convention to replace the digits above 9 with traditional alphabet notation. This is work for another day. I alos truncate at the maximum number of digits, not round. ''' fractional, integer = math.modf(number) return (base10_to_newbase_integer(number=integer,base=base), base10_to_newbase_fraction(abs(fractional),base=base,ndigits=ndigits)) # In[14]: mytable = [] mytable.append(('a','my converter (B=8)','my converter (B=16)')) for a in [12345,0.6789,12345.6789,-12345.6789,]: mytable.append((a ,base10_to_newbase(number=a,base=8) ,base10_to_newbase(number=a,base=16))) display(HTML(tabulate.tabulate(mytable, tablefmt='html'))) # The results of the oct conversion are identical to the textbook solution.