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
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)
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 = floor(n / r^m)
and from this
b_m := n - a_m*r^m
Then we recursively proceed with
b_m in place of
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
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!