We talked about binary numbers (with some theory) and base conversions and implemented an algorithm for base conversion (from decimal to 2<=b<=36). We examined Python's memory model and analyzed the efficiency of constructing a list using + or += operators.

- Make sure you understand binary numbers and base conversions (including the algorithms for conversion to and from a base b to decimal). It is a very useful tool in computer science.
- Elements of a list can be changed from inside a function, if this list is given as a parameter. Note that one should use dedicated list functions or the [] operator for mutating the list.
- Use Python tutor in order to understand what's going on in terms of memory. It can be very helpful.
- Try to analyze the number of operations your function does to see how will its runtime scale as a function of the input (we will elabore on this soon).

Before you click "Visualize Execution" button, you may want to use the following settings (can be adjusted via the drop boxes next to the textbox):

- Python 3.6
- Show exited frames (Python)
- Render all objects on the heap
- Draw pointers as arrows [default]

We use decimal numbers, that is, numbers in base 10. These numbers are represented using 10 digits (0-9). Binary numbers (in base 2) use two possible digits: 0-1. In general, a number in base $b$ will be represented using $b$ possible digits.

In [2]:

```
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
```

Using Python functions:

In [3]:

```
bin(10)
type(bin(10))
hex(161)
int("345")
int("1101", 2)
int("a1", 16)
int("a1", 2)
```

Out[3]:

Out[3]:

Out[3]:

Out[3]:

Out[3]:

Out[3]:

Let $x_{base 2} = a_{n-1} ... a_1 a_0$ be a binary number in base 2 with $n$ digits. The following formula returns its decimal representation: $$x_{base 10} = \sum_{0 \le k \le n-1} a_k \cdot 2^k$$

Converting from decimal to binary is done by integer division and modulo operations. Here is an implementation of the algorithm for conversion from decimal to a general base $b$.

In [6]:

```
def convert_base(n,b):
'''convert_base(int, int)->string
Returns the textual representation
of n(decimal) in base 2<=b<=10
'''
result = ""
while n != 0:
digit = n % b
n //= b
result = str(digit) + result
return result
```

In [7]:

```
convert_base(10,2)
```

Out[7]:

In [8]:

```
convert_base(0, 2)
```

Out[8]:

convert_base above mishandles n = 0

In [26]:

```
def convert_base(n,b):
'''convert_base(int, int)->string
Returns the textual representation
of n(decimal) in base 2<=b<=10
'''
if n == 0:
return "0"
result = ""
while n != 0:
digit = n % b
n //= b
result = str(digit) + result
return result
```

In [10]:

```
convert_base(0,2)
convert_base(12,3)
```

Out[10]:

Out[10]:

In [11]:

```
convert_base(161,16)
```

Out[11]:

The improved version above fails for 10<b (why ?) This issue is fixed in the final version below (improvement #2) (what happens when b = 1?)

In [ ]:

```
alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
```

In [ ]:

```
def convert_base(n,b):
'''convert_base(int, int)->string
Returns the textual representation
of n(decimal) in base 2<=b<=10
'''
assert 2 <= b <= 36
if n == 0:
return "0"
result = ""
alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
while n != 0:
digit = n % b
n //= b
result = alphabet[digit] + result
return result
```

In [13]:

```
convert_base(161, 16)
convert_base(10, 2)
convert_base(10, 80)
```

Out[13]:

Out[13]:

By understanding Python's memory model we

- can distinguish between objects that can be mutated and those that cannot. We can also understand how to mutate objects.
- can write a more efficient code.

In [14]:

```
def change_num(num):
num = 999
x = 30
change_num(x)
x
```

Out[14]:

In [15]:

```
def add_to_list(lst):
lst.append(999)
mylst = [1,2,3]
add_to_list(mylst)
mylst
```

Out[15]:

In [16]:

```
def change_lst(lst):
lst = []
mylst = [1,2,3]
change_lst(mylst)
mylst
```

Out[16]:

In [ ]:

```
#1 basics #####################################################
a = 1000 #1
b = "hello" #2
a += len(b) #3
c = 2*b[:2] #4
if b!=c: #5
c = b #6
del c #7
```

In [ ]:

```
#2 lists #####################################################
a = 1000 #1
d = [a,2] #2
d[1] = -1 #3
a = 1003 #4
for x in d: #5a
x = 7 #5b
```

In [ ]:

```
#3 funcs #####################################################
a = 1000 #1
b = "hello" #2
def is_palindrom(a): #3a
b = a[::-1] #3b
return a==b #3c
is_pal = is_palindrom #4
x = is_pal(b) #5
```

In [ ]:

```
#4 lists+funcs #####################################################
a = 1000 #1
d = [a,2] #2
def f(a,d): #3a
a = 2000 #3b
d[0] = a #3c
d = [] #3d
return d #3e
x = f(a,d) #4
```

Extend(), append(), sort(), and sorted():

In [28]:

```
#5 – lists operators and methods #####################################################
lst = [3,2,1]
id(lst)
lst
lst = lst+[0]
id(lst)
lst
lst.append(4)
id(lst)
lst
lst.insert(1,5)
id(lst)
lst
lst.extend([6,7])
id(lst)
lst
lst += [8]
id(lst)
lst
```

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

Out[28]:

In [29]:

```
lst
id(lst)
#sorted returns a sorted copy of the list, and does not change the original one
lst2 = sorted(lst)
id(lst)
lst
#list.sort() sorts in place, and does not return anything
lst.sort()
id(lst)
lst
```

Out[29]:

Out[29]:

Out[29]:

Out[29]:

Out[29]:

Out[29]:

We use + or += operators in order to construct the same list.

Using operator +: less efficient, since a new list is constructed every iteration the number of integers written to memory equals 1+2+ ... + n = (n+1)*n/2 (= asumptotically speaking, grows quadratically with n)

Using operator +=: more efficient, since the same list is extended again and again the number of integers written to memory equals n (= asumptotically speaking, grows linearly with n)

In [5]:

```
import time
```

In [12]:

```
n= 20000
lst = []
t0 = time.perf_counter()
for i in range(n):
lst = lst + [i]
t1 = time.perf_counter()
print("Extending a list n=", n, "times, using the + operator took",t1-t0, "seconds")
lst = []
t0 = time.perf_counter()
for i in range(n):
lst += [i]
t1 = time.perf_counter()
print("Extending a list n=", n, "times, using the += operator (extend()) took",t1-t0, "seconds")
```

We double the size of the input.

In [13]:

```
n= 40000
lst = []
t0 = time.perf_counter()
for i in range(n):
lst = lst + [i]
t1 = time.perf_counter()
print("Extending a list n=", n, "times, using the + operator took",t1-t0, "seconds")
lst = []
t0 = time.perf_counter()
for i in range(n):
lst += [i]
t1 = time.perf_counter()
print("Extending a list n=", n, "times, using the += operator (extend()) took",t1-t0, "seconds")
```

In accordance with the theory, the running time of the inefficient code increases by approximately 2**2 = 4 as n increases by 2, while the running time of the efficient code increases by approximately 2. Apparently n is large enough for the constants not to play a serious role, so that the measurements agree with the asymptotic analysis.