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.
import IPython
from IPython.display import HTML, display
import math
from decimal import Decimal
import tabulate # conda install tabulate
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:
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))
Integer divison: 2.0 , result type: <class 'float'> Integer divison: 1.3333333333333333 , result type: <class 'float'> Integer divison: 1.6666666666666667 , result type: <class 'float'> Integer divison: -1.3333333333333333 , result type: <class 'float'> Integer divison: -1.6666666666666667 , result type: <class 'float'> Integer divison: 1.108108108108108 , result type: <class 'float'>
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.
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))
Floor divison: 2 , result type: <class 'int'> Floor divison: 1 , result type: <class 'int'> Floor divison: 1 , result type: <class 'int'> Floor divison: -2 , result type: <class 'int'> Floor divison: -2 , result type: <class 'int'> Floor divison: 1.0 , result type: <class 'float'>
Now this is the tricky one. Inaccurately speaking, it is the remainder of the true division. Wikipedia has a better description, have fun ...
url = 'https://en.wikipedia.org/wiki/Modulo_operation'
iframe = '<iframe src=' + url + ' width=100% height=350></iframe>'
IPython.display.HTML(iframe)
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))
Modulo divison: 0 , result type: <class 'int'> Modulo divison: 1 , result type: <class 'int'> Modulo divison: 2 , result type: <class 'int'> Modulo divison: 2 , result type: <class 'int'> Modulo divison: 1 , result type: <class 'int'> Modulo divison: 0.39999999999999947 , result type: <class 'float'>
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)))
a=4 ,b=2 , divmod(a,b)=(2, 0) a=4 ,b=3 , divmod(a,b)=(1, 1) a=5 ,b=3 , divmod(a,b)=(1, 2) a=-4 ,b=3 , divmod(a,b)=(-2, 2) a=-5 ,b=3 , divmod(a,b)=(-2, 1) a=4.1 ,b=3.7 , divmod(a,b)=(1.0, 0.39999999999999947)
So it looks as if divmod sotres the float divison and modul division in a tuple.
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
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')))
a | b | a/b | a//b | a%b | divmod(a,b) |
4 | 2 | 2.0 | 2 | 0 | (2, 0) |
4 | 3 | 1.3333333333333333 | 1 | 1 | (1, 1) |
5 | 3 | 1.6666666666666667 | 1 | 2 | (1, 2) |
-4 | 3 | -1.3333333333333333 | -2 | 2 | (-2, 2) |
-5 | 3 | -1.6666666666666667 | -2 | 1 | (-2, 1) |
4.1 | 3.7 | 1.108108108108108 | 1.0 | 0.39999999999999947 | (1.0, 0.39999999999999947) |
This is actually more tricky than it sounds, as rounding errors and number finite number representaions start to play a role.
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')))
a | int(a) | round(a) | floor(a) | modf(a) | a%1 | Decimal Magic | String Conversion |
4 | 4 | 4 | 4 | (0.0, 4.0) | 0 | 0 | 0 |
4.1 | 4 | 4 | 4 | (0.09999999999999964, 4.0) | 0.09999999999999964 | 0.09999999999999964472863211995 | 09999999999999964 |
4.5 | 4 | 4 | 4 | (0.5, 4.0) | 0.5 | 0.5 | 5 |
4.6 | 4 | 5 | 4 | (0.5999999999999996, 4.0) | 0.5999999999999996 | 0.5999999999999996447286321199 | 5999999999999996 |
-4.1 | -4 | -4 | -5 | (-0.09999999999999964, -4.0) | 0.9000000000000004 | -0.09999999999999964472863211995 | 09999999999999964 |
-4.5 | -4 | -4 | -5 | (-0.5, -4.0) | 0.5 | -0.5 | 5 |
-4.6 | -4 | -5 | -5 | (-0.5999999999999996, -4.0) | 0.40000000000000036 | -0.5999999999999996447286321199 | 5999999999999996 |
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.
Straigth forward, based on the equation above.
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*}
\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$
\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.
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:
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')))
a | my converter (B=8) | oct(8) | my converter (B=16) | oct(16) |
12345 | [3, 0, 0, 7, 1] | 0o30071 | [3, 0, 3, 9] | 0x3039 |
-12345 | [-3, 0, 0, 7, 1] | -0o30071 | [-3, 0, 3, 9] | -0x3039 |
7 | [7] | 0o7 | [7] | 0x7 |
8 | [1, 0] | 0o10 | [8] | 0x8 |
15 | [1, 7] | 0o17 | [15] | 0xf |
16 | [2, 0] | 0o20 | [1, 0] | 0x10 |
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
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')))
a | my converter (B=8) | my converter (B=16) |
0.6789 | [5, 3, 3, 4, 6] | [10, 13, 12, 12, 6] |
-0.6789 | [-5, -3, -3, -4, -6] | [-10, -13, -12, -12, -6] |
0.0 | [] | [] |
0.1 | [0, 6, 3, 1, 4] | [1, 9, 9, 9, 9] |
0.2 | [1, 4, 6, 3, 1] | [3, 3, 3, 3, 3] |
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))
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')))
a | my converter (B=8) | my converter (B=16) |
12345 | ([3.0, 0, 0, 7, 1], []) | ([3.0, 0, 3, 9], []) |
0.6789 | ([0.0], [5, 3, 3, 4, 6]) | ([0.0], [10, 13, 12, 12, 6]) |
12345.6789 | ([3.0, 0, 0, 7, 1], [5, 3, 3, 4, 6]) | ([3.0, 0, 3, 9], [10, 13, 12, 12, 6]) |
-12345.6789 | ([-3.0, 0, 0, 7, 1], [5, 3, 3, 4, 6]) | ([-3.0, 0, 3, 9], [10, 13, 12, 12, 6]) |
The results of the oct conversion are identical to the textbook solution.