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