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