Exercices : Integer arithmetic

April, 2022 - François HU

Master of Science - EPITA

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

image-2.png

Table of contents

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

1.1. Some useful commands

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

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

Another way is using the command int:

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

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?

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

Compare "numerically" the time complexity of multiplication_base(A, B, 10), karatsuba(A, B, 10) and a bitwise multiplication strategy. Comment.