Switching the Base of an Integer. With an Implementation in Rust.

Certainly most of you know, an integer can be presented w.r.t different bases. Usually they are presented in the decimal system that corresponds to a base of 10. Another presentation for instance is the hexadecimal system, that corresponds to a base of 16.

The aim of this small post is to give a wrap-up about this subject and to implement an algorithm that transforms a non-negative integer into another base.

Presentation of natural numbers:

Let us first look at some theoretic foundations.

(should the document not appear correctly, you can use this link)

Algorithm:

The proof of the above presentation theorem actually leads to an algorithm. In order to find for a given natural number n a presentation w.r.t to a base r, we can start by getting the maximal non-zero coefficient m like this:

m = floor(ln(n) / ln(r))

Having this, we can use Euclidean division to get the coefficient a_m:

a_m = floor(n / r^m)

and from this

b_m := n - a_m*r^m

Then we recursively proceed with b_m in place of n.

In Rust this looks like follows:

This function returns the above presentation in form of a vector of tuples (i, a_i) where a_i is the coefficient for the power r^i.

Formatting a number in a different base:

We can use the above algorithm to format a given integer w.r.t to a bases with r < 10:

Here, we are using the first entry of the coefficients vector to determine the length of the resulting string.

You can play with all that at the following playground.

Thanks for reading!