How to find i-th root of n whose remainder is the smallest?

Question

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 <= floor(ithRootOf(n)) <= 2147483647

Answer 1

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 > 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)$.

Answer 2

You say you have a number of 6 Megabits, that is $n < 2^{6,000,000}$.

We want to find numbers $b^k$ where b and k are integers, $2 ≤ b < 2^{31}$, k as large as possible such that $b^k ≤ n$, we you want to find the pair b, k that makes $n-b^k$ as small as possible. Since n is fixed, this is equivalent to making $n / b^k$ as small as possible, or making $\log n - k \cdot \log b$ as small as possible.

We find potential candidates by calculating k using double precision floating-point arithmetic. We calculate x = $\log n \div \log b$, and k = $\lfloor x \rfloor$. Then we calculate $\log n - k \cdot \log b$, and pick the b, k where this is smallest.

We need to be careful because of rounding errors in floating point arithmetic: So we can't just choose b, k which make $\log n - k \cdot \log b$ according to our calculation. We also need to consider all b', k' which may give the same or worse results due to rounding errors, but in reality might be better.

We also need to be careful if $x = \log n - k \cdot \log b$ is so close to the nearest integer that we can't determine $k = \lfloor x \rfloor$ for sure. In these cases, let k' = x rounded to the nearest integer and k = k' - 1 (these are the two possible values); we process (b, k) like every other pair, but must consider (b, k') to be a candidate as well.

If b is large then we can save more time: For example, if n is a 6 million bit number, then for b ≥ 70,000 there will always be two or more consecutive values b with the same k. If b is close to $2^{31}$, we find that over 200,000 consecutive values b have the same k. So for large b, we instead find the largest b for a fixed k: b = $\lfloor \exp (\log n \div (k + 1)) \rfloor$; this substantially reduces the amount of work.

Once we have a small number of candidates, to avoid having to figure out whether say $2^{1,234,568}$ or $4^{617,284}$ are closer to n, we exclude values b which are powers of some smaller number.

Then we first examine all the pairs (b, k') where the calculated x was very close to an integer: We have to calculate $b^{k'}$ exactly, reject it if it is greater than n, otherwise keep the smallest one. If none of these were accepted, we examine all the other candidates that might be optimal.

For a 6 million bit number n, if we examine individual b's up to about 50,000 and then switch to examining individual k, we have about 250,000 values to examine. With a bit of luck there is only one pair (b, k) that could be the best, so we only have a few million floating point operations, which should run in a few milliseconds.

(What is the problem with x close to an integer? Say we have $n = 7^{1,000,000} - 1$ and $n' = 7^{1,000,000} + 1$. With b = 7, we will get x = 1,000,000 or something very close, but in both cases we don't actually know whether k should be 999,999 or 1,000,000. So we have to try 1,000,000 separately. $7^{1,000,000} then turns out to be too large in the first case).

If you only want to find the best b, k and not the actual remainder, you may be able to do without high-precision arithmetic altogether.