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

[DaviFN]

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

[Sensei]

2 hours ago, DaviFN said:

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

Can you show us your source code? It'll be easier to analyze..

If you open Task Manager how many CPUs/cores are used? If only one is used at a time, you can/should split to couple different threads, as many as cores and Hyper Threads. i.e. if 1st thread is working on n= 0,8,16,24,32 etc. 2nd thread should be working on n = 1,9,17,25,33 and so on (if you have 8 HT/cores). That will result in speed up equal to number of threads instantly.

ps. Also you can use profiler to identify which part of code is the most CPU time consuming, and try to fix it the first.

 

Edited June 30, 2019 by Sensei

[DaviFN]

This is the binary search to find the lower bound for i:

while(1)
  {
       if(executeBinarySearch==0)
       {
            break;
       }
       
       
       initialI = (rangeFinish+rangeStart)/2;
       
       
       
       mpz_rootrem(nthRoot,rem,n,initialI);
       int logic = mpz_cmp_ui(ithRoot,2147483647);
       
       if(mpz_cmp_ui(ithRoot,1)==0)
       { // i is too large and we got 1, let's pick a smaller i
            rangeFinish = initialI;
       }
       
       // logic > 0 means ithRoot is greater, logic == 0 means it's equal and logic < 0 means it's smaller.
       
       if(logic > 0)
       { //ith root is greater, so we have to pick a greater i
            rangeStart = initialI;
       }
       
       if(logic < 0)
       { //ith root is smaller, so we have to pick a smaller i
            rangeFinish = initialI;
       }
       
       if(rangeFinish<=rangeStart + 1)
       {
            break;
       }
       
       if(logic == 0)
       {
            break;
       }
       
       if(!mpz_cmp_ui(ithRoot,2147483647)>0)
       {
            break;
       }
       
  }

Similarly, this is the binary search to find the upper bound for i:

rangeStart = initialI;

while(1)
  {
       finalI = (rangeFinish+rangeStart)/2;
       
       mpz_rootrem(ithRoot,rem,n,finalI);
       int logic = mpz_cmp_ui(ithRoot,2147483647);
       
       if(rangeFinish<=rangeStart + 1)
       {
            break;
       }
       
       if(mpz_cmp_ui(ithRoot,1)==0)
       { // i is too large and we got 1, let's pick a smaller i
            rangeFinish = finalI;
       }
       
       if(mpz_cmp_ui(ithRoot,1)>0)
       { // we can pick a larger i
            rangeStart = finalI;
       }
       
  }

And this is the loop brute-forcing every i-th root possible, updating the smallest remainder when a smaller is found:

for(i=initialN;(i<=finalN && i>=initialN);i++)
  //for(i=finalN;i>=initialN;i--)
{
  

  mpz_rootrem(ithRoot,rem,n,i);
  
  
  if(mpz_cmp(rem,smallestRem)<0)
  { // new smallest remainder

       mpz_set(smallestRem,rem);
       smallestRemI = i;
  }

}

My CPU is single-core.

I've set the priority of the process to the highest one (not real-time), but it's still too slow.

Is there a non-brute force approach to the problem?

[Sensei]

       mpz_rootrem(nthRoot,rem,n,initialI);
       int logic = mpz_cmp_ui(ithRoot,2147483647);

In the first line you have variable "nthRoot", but later it is completely not used (you're comparing with ithRoot, not nthRoot).

On 6/30/2019 at 4:24 PM, DaviFN said:

My CPU is single-core. 

How is that possible? Computers with single core CPU are not produced and sold for maybe ~ 20 years.. Core 2 Duo had premiere in 2000 year.

Edited July 1, 2019 by Sensei