How to find i-th root of n whose remainder is the smallest? Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively small number (e.g. the maximum number that can be represented by a unsigned int)?

I'm currently using gmp bignum library in C, and my algorithm is as follows:

It first finds the smallest possible base and the greatest possible base given the circunstances (binaries searches are performed) and then we know the range of i.

Then, for each possible i, we take the i-th root of n and the corresponding remainder. The smallest remainder is updated if the current remainder is smaller than it.

The algorithm does work, but it's far too slow (even using such a powerful library as gmp). For comparison, for a number with roughly 6 mega bits when expressed in binary the algorithm takes ~90 days to complete.

Intuitively, I think there is a better way to solve the problem (i.e. faster way, an algorithm with a smaller time complexity). What can be done to speed up this process?

Obs: Problem: Given n, find i such that the remainder, n - (floor(ithRootOf(n))^i, is the smallest possible. 2 &lt;= floor(ithRootOf(n)) &lt;= 2147483647
You want to write $n$ as $b^x + r$ with $x,r \ge 0$ and $b \in \{2, \dots, 2^{31} - 1\}$.

Since you're asking for the asymptotic complexity and the base $b$ is in a set of constant size, you can just focus on a single value of $b$. 
The exponent is then $x = \lfloor \log_b n \rfloor$ and can be found using $O(\log \log n)$ operations (search for the first $y$ such that $b^y &gt; n$ by trying $b, b^2, b^4, b^8, \dots$, where each term is the product of the previous term by itself, then binary search for the last $x \in \{y/2, \dots, y\}$ such that $b^x \le n $).

The above procedure already gives you $b^x$, from which you can compute $r = n - b^x$. Return the triple $(b, x, r)$ that minimizes $r$.

If the time of each arithmetic operation is constant, the above requires $O(\log \log n)$ time. If each arithmetic operation takes logarithmic time in the value of its operands, then the complexity is $O(\log n \cdot \log \log n)$.