# Problem 04

## Problem 04

Recent processors have instructions for multiplication and division of positive integers below 2^{64}. However, division is substantially slower than multiplication. You are given a large set S of integers between 0 and 2^{64}, all multiples of n, and you want to divide them all by n. How would you do this, using only multiplication and simple bit operations?

### Solution

We can write n = 2^{a} · b, with b an odd integer. Since gcd(b, 2^{64}) = 1, we can find c between 0 and 2^{64} with b · c ≡ 1 (mod 2^{64}). For each number in S, we divide it by 2^{a} (which is trivial in base 2) and we multiply it by c. Hence, if the number was previously k · n = k · 2^{a} · b, it is now k · b · c ≡ k (mod 2^{64}). Since k < 2^{64}, we have correctly performed the division.

This requires one modular inversion in total (which can be neglected in the total computation time), and per number it only requires one multiplication and a trivial operation (removing a zeros), which is a lot cheaper than division.

### Remarks

This problem is a nice example where the theory of modular arithmetic actually yields direct computational improvement in problems where it would seem unrelated at first, and without the need for deep theory or advanced preliminaries.