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: stackoverflow.com/questions/4429044/… — Gusman
– Gusman, Commented Apr 27, 2017 at 19:28
Math.Pow? I am a math failure, ironic considering my career, but I believe thats what you want? — Trey
– Trey, Commented Apr 27, 2017 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. — user555045
– user555045, Commented Apr 27, 2017 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
– Servy, Commented Apr 27, 2017 at 19:32

jimboweb · Accepted Answer · 2017-04-27 19:41:42Z

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, 2017 at 19:41

answered Apr 27, 2017 at 19:33

jimboweb

4,5623 gold badges28 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

Scott Chamberlain Over a year ago

Or to use the OP's function private static bool HasBase(int b, int n) { return Math.Log(b,n)%1 == 0; }

user555045 Over a year ago

Oh really? Math.Log(243, 3) % 1 = 0.99999999999999911 for example

Scott Chamberlain Over a year ago

True, you do need to be careful of floating point rounding errors

Novaterata Over a year ago

or use an epsilon like you should be using for all double comparisons

Michael Gunter Over a year ago

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 · Accepted Answer · 2017-04-27 20:44:13Z

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.

Xiaoy312 · Accepted Answer · 2017-04-27 19:58:44Z

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

Collectives™ on Stack Overflow

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

3 Answers 3

12 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

12 Comments

Comments

Comments

Linked

Related