*April, 2022 - François HU*

*Master of Science - EPITA*

*This lecture is available here: https://curiousml.github.io/*

In Python, an integer is a element of $\mathbb{Z}$ which contains zero, positive and negative whole numbers without a fractional part. Python integers are interesting because they are not just, traditionally for programming languages such as C, 32-bit or 64-bit integers. Python integers are **arbitrary-precision integers**, also known as **bignums**. This means that they can be as large as we want (their sizes are only limited by the amount of available memory).

In [1]:

```
n1 = 0
n2 = 12
n3 = -121
n4 = 123456789
n5 = 500000000000000000000000000000000000000000000000000
```

You can **check the type** of an object with the command `type`

In [2]:

```
print(type(n1))
print(type(n2))
print(type(n3))
print(type(n4))
print(type(n5))
```

<class 'int'> <class 'int'> <class 'int'> <class 'int'> <class 'int'>

Integers are represented (by default) in decimal but they can be represented in other radix like **binary**, **octal** or **hexadecimal**:

In [3]:

```
print(0b11010001) # binary
print(0o117) # octal
print(0xE20F) # hexadecimal
type(0b11010001)
```

209 79 57871

Out[3]:

int

Another way is using the command `int`

:

In [4]:

```
print(int("11010001", 2)) # binary
print(int("117", 8)) # octal
print(int("E20F", 16)) # hexadecimal
type(int("11010001", 2))
```

209 79 57871

Out[4]:

int

We can convert an decimal integer easily in other radix representation:

In [5]:

```
print(bin(209))
print(oct(79))
print(hex(57871))
```

0b11010001 0o117 0xe20f

**Exercice 1:** define a function `convert_base(n, b)`

which returns a string that converts a decimal integer `n`

in a b-radix integer.

In [ ]:

```
```

**Exercice 2:** define a function `addtion_base(A, B, b)`

which returns a string that contains the b-radix addition of A and B.

In [ ]:

```
```

Python uses $O(k^2)$ grade-school multiplication algorithm for small numbers, but for big numbers it uses $O(k^{1.59})$ Karatsuba algorithm.

In [ ]:

```
```

In [ ]:

```
```

In [6]:

```
def secret_function1(n):
u = 0
while n:
n >>= 1
u += 1
return u
def secret_function2(n):
v = 0
z = 0
while n:
z += (n & 1)
v += 1
n >>= 1
return(v, z)
```

In [7]:

```
A = 340282366920938463463374607431768211456
B = 4096
```

Compare "numerically" the time complexity of `multiplication_base(A, B, 10)`

, `karatsuba(A, B, 10)`

and a bitwise multiplication strategy. Comment.

In [ ]:

```
```