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

Question

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);
}

Short answer, no. Here are some math examples with efficient algorithms to do this task: http://stackoverflow.com/questions/4429044/check-if-one-integer-is-an-integer-power-of-another — Gusman, Apr 27 '17 at 19:28
Math.Pow? I am a math failure, ironic considering my career, but I believe thats what you want? — Trey, Apr 27 '17 at 19:31
There isn't much like that in the standard library, but of course you don't have to brute-force it like this. Also you should be more careful, a lot of those powers will overflow and that may give you false positive. — harold, Apr 27 '17 at 19:31
@Trey This is calculating roots, not powers. The OP is looking to calculate `a` in the equation `a^n=b`, not `b`. — Servy, Apr 27 '17 at 19:32
OP: Either your title or your text are inaccurate. The title suggests you want to find `X` given `a`, `b` and `a^X == b`. However, the text suggests you want to find `X` given `a`, `b` and `X^a == b`. Which is it? — Michael Gunter, Apr 27 '17 at 19:56

jimboweb · Answer 1 · 2017-04-27T19:41:42.430

3

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.

edited Apr 27 '17 at 19:41

answered Apr 27 '17 at 19:33

jimboweb

4,362
3
22
45

Or to use the OP's function `private static bool HasBase(int b, int n) { return Math.Log(b,n)%1 == 0; }` – Scott Chamberlain Apr 27 '17 at 19:37
1

Oh really? `Math.Log(243, 3) % 1 = 0.99999999999999911` for example – harold Apr 27 '17 at 19:37
True, you do need to be careful of floating point rounding errors – Scott Chamberlain Apr 27 '17 at 19:39
Good point, harold, I was not thinking about that. It works if you type it to Decimal, however. I'll edit the answer to reflect that. – jimboweb Apr 27 '17 at 19:40
4

or use an epsilon like you should be using for all double comparisons – Novaterata Apr 27 '17 at 19:43
OK so why does this even work? Because it essentially shouldn't – harold Apr 27 '17 at 19:52
If you're using small integers it might actually be faster to use a for-next loop than to use this function, though, because Math.Log only works with doubles. – jimboweb Apr 27 '17 at 19:52
2

If OPs title is accurate, this answer is correct (although it has some possible issues with floating point errors that may invalidate the answer). However, OPs title doesn't match the posted question text. The title suggests they want to find `X` given `a`, `b` and `a^X == b`. However, the text suggests they want to find `X` given `a`, `b` and `X^a == b`. – Michael Gunter Apr 27 '17 at 19:54
According to c# docs: "The decimal keyword indicates a 128-bit data type. Compared to floating-point types, the decimal type has more precision and a smaller range..." In my experience typing doubles to decimals gets rid of double math wiggliness, but I can't prove it always works. Novaterata might be right that using an epsilon is better. – jimboweb Apr 27 '17 at 20:13
Well the thing is, the wiggliness is already there in the result from the `Log`, somehow it goes away during the cast but that's quite mysterious IMO - converting an inaccurate number to more precision doesn't give it more accuracy – harold Apr 27 '17 at 20:15
I get what you're saying harold; it doesn't seem like it should work but empirically it has for me. As I said, I can't prove it always works, since I don't even know why it does. – jimboweb Apr 27 '17 at 20:20
I should add that if you write the double in a variable and cast it to a decimal on the next line it does not get rid of the floating point error as it does when you cast it immediately. – jimboweb Apr 27 '17 at 20:53

Xiaoy312 · Answer 2 · 2017-04-27T19:58:44.593

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

Michael Gunter · Accepted Answer · 2017-04-27T20:44:13.003

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.

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

3 Answers3