Square Numbers and more General Powers

[Menag]

Somehow the latex formulars aren't shown correctly, hence i added links.

Hey guys,
I'll just state my problem. I have a natural number n and I want to know if there exists a natural number m such that m^2 = n. Or in general, I have two natural numbers n, k and I want to know if there exists a natural numbers m such that m^k = n. The best would be if I could also obtain this natural number m. The most naive way would be just to try out the numbers. So we would have something like

for (int i = 0; x = pow(i,k) < n; ++i) {
    if (x == n) {
        return true;
    }
}
return false;

Since the power can be calculated in logarithmic time and the loop goes till k-root(n) we have log(k) * k-root(n) operations. But these are multiplications hence a bit slower anyway. So i came up with another idea. For square numbers we have a cool formular! The sum of the first n odd numbers is n^2, hence

LaTeX1

Therefore we could just add them up and only have additions (except the one multiplication with 2). Hence the code would be something like

int res = 0;
for (int i = 1; res < n; i +=2) {
    res = res + i - 1;
    if (res == n) {
        return true;
    }
}
return false;

Here we have only 2 * sqrt(n) additions. In comparison, we had sqrt(n) * log(2) multiplications before.
So I tryed generalizing this and found the following formular:

LaTeX2

Note that the proof shouldn't be that hard with induction and using the binomial theorem.

Well, as you can see, this needs fucking lots of operations.
While the inner power can be calculated quite fast by remembering the calculations, the binomial coefficient is slow. Anyway, these could just be calculated once and saved into an array. The (-1)^j could be exchanged by cases with calculating modulo, hence does not need log(j) time. Hence we come up with 2k multiplications and k additions/subtractions in the inner sum. Therefore we have 3k * k-root(n) + O(binomial coefficients) operations.
So it seems like this isn't the right way to look for a better algorithm or I just missed something.
So my question is: Do you know a better algorithm then just trying out the numbers from 1 to k-root(n) or do you have any ideas about my formulars?

That's all for now, thanks in advance!

 

[Dr Super Good]

On processors with a floating point unit you could convert the number to a floating point and then perform n^(1/k) and then check if the number is very close to a whole number. This however suffers from accuracy limitations and so will not be suited for very large numbers as it might get an incorrect results. This however will probably need the fewest operations. Also needs a floating point unit otherwise it will likely be a ton slower than your current suggestion.

I will think about the problem further.

The big question is not "is the an answer?", but "is there not an answer?". An obvious one would be when the power, k, exceeds the input, n since it is impossible for there to be a natural number such that m^k = n. That test alone would mean all such tests with k>n will return in order 1. Obviously this condition is un ideal, you could probably find a considerably wider condition for which k>x where x is based on n so there cannot be a solution. This is just a test for the maximum value of k, there are others as well.

One could try and find the minimum value of n such that is required for a certain k to generate a natural number. One could possibly find a general rule with respects to both k and n that is needed for a natural number to be found. This might not solve your complexity problem when actually solving it, but it could potentially save a lot of operations if the function is subject to inputs that continuously fail.

As for speeding up the algorithm itself. I am confused what you got as the output as I thought you wanted m = n^(1/k) where n and k are inputs and m is the output.

 

[Menag]

On processors with a floating point unit you could convert the number to a floating point and then perform n^(1/k) and then check if the number is very close to a whole number. This however suffers from accuracy limitations and so will not be suited for very large numbers as it might get an incorrect results. This however will probably need the fewest operations. Also needs a floating point unit otherwise it will likely be a ton slower than your current suggestion.

I need exact operations and even VERY big numbers. Otherwise i would've done this already!

The big question is not "is the an answer?", but "is there not an answer?". An obvious one would be when the power, k, exceeds the input, n since it is impossible for there to be a natural number such that m^k = n. That test alone would mean all such tests with k>n will return in order 1. Obviously this condition is un ideal, you could probably find a considerably wider condition for which k>x where x is based on n so there cannot be a solution. This is just a test for the maximum value of k, there are others as well.

If we have k >= n we have no problem with the current algorithm. Since k-root(n) < 2 in this case it interupts after the first loop. Of course we would still have to calculate the power 2^k once but this is only a small optimization. I actually want to have a more intelligent algorithm if there is one.

One could try and find the minimum value of n such that is required for a certain k to generate a natural number. One could possibly find a general rule with respects to both k and n that is needed for a natural number to be found. This might not solve your complexity problem when actually solving it, but it could potentially save a lot of operations if the function is subject to inputs that continuously fail.

Since we have 1^k = 1, we can't find such a n,k every time, but yes, for all other n > 1 with k >= n this does not have a solution. But still, the worst case is the same :/.

As for speeding up the algorithm itself. I am confused what you got as the output as I thought you wanted m = n^(1/k) where n and k are inputs and m is the output.

What exactly are you confused about? In the first place I want to have a boolean if it is a square or not. If it's possible I'd like to have the root too. But all my ideas give me the possibility to return the root!

Anyway, thanks for the ideas!

PS: the actual problem is for n >>> k.

 

[peq]

How big are your numbers?

Using Newtons method (https://en.wikipedia.org/wiki/Nth_root_algorithm):

def rootIterative(k: Int, n: BigInt): Option[BigInt] = {
    var x = n
    while (true) {
      val delta = (n / x.pow(k - 1) - x) / k
      if (delta == 0) {
        // fixpoint
        if (x.pow(k) == n)
          return Some(x)
        else
          return None
      }
      x += delta
    }
    return None
  }

or recursively:

  def root(k: Int, n: BigInt): Option[BigInt] = {
    @tailrec
    def root(k: Int, n: BigInt, guess: BigInt): Option[BigInt] = {
      val delta = (n / guess.pow(k - 1) - guess) / k
      if (delta == 0) {
        if (guess.pow(k) == n)
          Some(guess)
        else
          None
      } else {
        root(k, n, guess + delta)
      }
    }
    
    root(k, n, n);
  }

I tested it by taking the 3. root of 3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609^3 and it took 238ms.

EDIT: should have done more tests. Actually the method does not work with integer division, but I think some small modifications should make it work:

  def root(k: Int, n: BigInt): Option[BigInt] = {
    @tailrec
    def root(k: Int, n: BigInt, guess: BigInt): Option[BigInt] = {
      val kdelta = (n / guess.pow(k - 1) - guess)
      if (kdelta > 0)
        return None
      else if (kdelta == 0)
        if (guess.pow(k) == n) Some(guess) else None
      else
        root(k, n, guess + (kdelta / k).min(-1))
    }

    root(k, n, n);
  }

Another alternative would be binary search, but I think that would be slower:

def binarySearchRoot(k: Int, n: BigInt): Option[BigInt] = {
    var lowerBound: BigInt = 0
    var upperBound: BigInt = n
    while (lowerBound < upperBound) {
      val test = (lowerBound + upperBound) / 2
      val pow = test pow k

      if (pow == n)
        return Some(test)
      else if (pow < n)
        lowerBound = test + 1
      else
        upperBound = test - 1
    }
    if ((lowerBound pow k) == n)
      return Some(lowerBound)
    else
      return None
  }

 

[Dr Super Good]

If n is a prime number you can instantly return false. If you can check that quickly is another problem altogether though.

Are you sure it will not be faster to use some sort of optimized fixed point calculation for n^1/k and checking if it contains meaningful fractional parts? I believe these scale in time based on the number of words used for n and k. It would be far better to have something that works in reliable time even if for small values it is slower.

 

[Menag]

If n is a prime number you can instantly return false. If you can check that quickly is another problem altogether though.

Are you sure it will not be faster to use some sort of optimized fixed point calculation for n^1/k and checking if it contains meaningful fractional parts? I believe these scale in time based on the number of words used for n and k. It would be far better to have something that works in reliable time even if for small values it is slower.

Yeah I talked to peq. I think I'm going to make a fast numerical root implementation and then i look in a neighborhood for integers. Hence I would need the time for calculating the root and then a few exponentiations to test if an integer is near it. I was curious anyway if there is a faster algorithm.