CODEWITHSUNDEEP
c#.netalgorithm
Ms Corlib
Ms Corlib

Reputation: 13

Does the standard library of C# have an easy way to check whether a number is a power of another number?

I'm trying to see if there is a good way to find whether, given ints b and n, there exists an int a such that a^n=b. In other words, something more efficient than the bad solution I wrote below 

private static bool HasBase(int b, int n)
{
    for(int a = 1; a <= int.MaxValue; ++a)
    {
        int pow = Power(a, n);
        if(pow == b)
            return true;
        else if(pow > b)
            return false;
    }
    return false;   
}

private static int Power(int a, int n) 
{
    return Enumerable.Range(a, n).Aggregate(1, (prev, cur) => prev * cur);
}

Upvotes: 0

Views: 157

Answers (3)

Michael Gunter
Michael Gunter

Reputation: 12811

The original question has a discrepancy between the title and text. Assuming the text is correct, OP wants to find X given a, b and X^a == b. Here's a rough algorithm that works to do this, but it isn't integer-perfect. The floating point error will always crop up when performing this sort of calculation using any built-in math functions. The only alternative is to perform some calculation-intensive loop.

// given
int value = ...;
int power = ...;

// calculate the [power]th root of [value]
var root = value >= 0
    ? Math.Pow(value, 1d / power)
    : Math.Abs(power % 2) == 1
        ? -Math.Pow(-value, 1d / power)
        : Double.NaN;

// determine if [root] is an int
var root_is_int = Math.Abs(root - Math.Round(root)) <= Double.Epsilon;

Note that, other than potential issues caused by rounding errors, this works for all values of value and power -- positives, negatives and zero.

Upvotes: 0

Xiaoy312
Xiaoy312

Reputation: 14477

You can find all the factors of b, and check if the same factor only repeats n or xn times. Because x^n*y^n = (xy)^n = a^n or x^(2n) = (xx)^n = a^n.

public static bool HasBase(int b, int n)
{
    // find all factors of b
    var factors = new List<int>();
    var dividers = Enumerable.Range(2, (int)Math.Round(Math.Sqrt(b) + 1)).GetEnumerator();
    dividers.MoveNext();
    while (true)
    {
        if (b % dividers.Current != 0)
        {
            if (dividers.MoveNext())
                continue;
            else
                break;
        }

        b /= dividers.Current;
        factors.Add(dividers.Current);
    }

    // if the base of each power can be divided by 3, a^n=b should be true.
    return multiples
        .GroupBy(x => x)
        .All(g => g.Count() % 3 == 0)
}

Upvotes: 0

jimboweb
jimboweb

Reputation: 4542

It has the Math.log(double, double) function, which finds the log of the first number in the base of the second number. If that comes out whole, then it's a power. So for example if I wanted to know if x is a power of 2 I could write:

bool isAPower = (Decimal)(Math.Log(x,2))%1==0;

In other words, take the log base 2 of x, and find the remainder if I divide it by one. If the mod is 0 it's true, if it's not 0 it will be false.

Upvotes: 3

Related Questions