Exercices : Integer arithmetic

April, 2022 - François HU

Master of Science - EPITA

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

Table of contents

• Integer representation
  • Exercice 1: convert_base
• Integer addition
  • Exercice 2: addition_base
• Integer multiplication
  • Exercice 3: multiplication_base
  • Exercice 4: karatsuba
• Bitwise operations
  • Exercice 5
• Exercice 6

1. Integer representation

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).

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

1.1. Some useful commands

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

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:

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

type(0b11010001)

209
79
57871

int

Another way is using the command int:

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

type(int("11010001", 2))

209
79
57871

int

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

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

0b11010001
0o117
0xe20f

1.2. Conversion algorithm

Exercice 1: define a function convert_base(n, b) which returns a string that converts a decimal integer n in a b-radix integer.

2. Integer addition

Exercice 2: define a function addtion_base(A, B, b) which returns a string that contains the b-radix addition of A and B.

3. Integer multiplication

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

Exercice 3: define a function multiplication_base(A, B, b) which returns a string that contains the b-radix addition of A and B using the grade-school method (see lecture 1).

Exercice 4: define a function karatsuba(A, B, b) which returns a string that contains the b-radix multiplication of A and B using the karatsuba method (see lecture 1).

4. Bitwise operations

Exercice 5: What do these functions do?

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)

Exercice 6: we consider the following integers A and B:

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.