How to check if a ^ b == c ^ d. The problem I'm running into is speed with loops. I've already optimized the part to find exponents
Here are the functions. Basically I loop from 1 to n and check if a ^ b == c ^ d. I was wondering if there is a faster way to do this.
int power(int x, int n) {
if (n < 0)
return this->power(1/x, -1*n);
else if (n == 0)
return 1;
else if (n == 1)
return x;
else if (n % 2 == 0)
return this->power(x * x, n / 2);
else if (n % 2 != 0)
return x * (this->power(x * x, (n - 1)/2));
}
int count(int n) {
int count = 0;
n = n + 1;
for(int a = n; a >= 1; --a) {
for(int b = n; b >= 1; --b) {
for(int c = n; c >= 1; --c) {
for(int d = n; d >= 1; --d) {
if (this->power(a,b) == this->power(c,d))
count = count + 1;
}
}
}
}
return count % (this->power(10, 9) + 7);
}
source to share
Why recursively and repeatedly compute powers over and over in nested loops when you can compute them once and use them forever? (Well, for the rest of the function.)
The way you recursively calculate each cardinality a
and c
, did the same job over and over. I improved the function so it calculates all possible results for the value n
and caches them in vector
of vector
(temporary matrix):
unsigned long long count(unsigned n) {
// Indexed as results[a-1][b-1]
std::vector<std::vector<unsigned long long>> results;
for (std::size_t i = 0; i < n; ++i) {
results.emplace_back(n); // Emplace a vector with n slots
}
// Calcuate all the possible results for a^b, 1<=a<=n and 1<=b<=n
// 1^n is always 1
for (std::size_t b = 1; b <= n; ++b) {
results[0][b-1] = 1;
}
// Manually calculate the rest
for (std::size_t a = 2; a <= n; ++a) {
unsigned long long value = 1;
for (std::size_t b = 1; b <= n; ++b) {
value *= a;
results[a-1][b-1] = value;
}
}
// Compare all the things
unsigned long long count = 0;
// I'd change this because 1^m == 1^n for any values of m and n,
// but I didn't make up the problem
for (std::size_t a = 1; a <= n; ++a) {
for (std::size_t b = 1; b <= n; ++b) {
for (std::size_t c = 1; c <= n; ++c) {
for (std::size_t d = 1; d <= n; ++d) {
if (results[a-1][b-1] == results[c-1][d-1]) {
// std::cout << a << "^" << b << " = " << c << "^" << d << "\n";
++count;
}
}
}
}
}
return count;
}
There are several potential problems with this problem:
- 15 is the highest number for
n
that can be transmitted because 16 16 is greater than the minimum maximum value forunsigned long long
(2 64 - 1). - This takes into account cases such as (1 m = 1 n ), which is always true and does not need a computer check.
- This also allows for cases that could be considered duplicate. (2 4 = 4 2 ) and (4 2 = 2 4 ) are considered two cases.
- This also takes into account the cases where (a = c) and (b = d), which means it looks exactly the same on the left and right side of the expression (of course, 2 4 = 2 4 )
If you want to do higher precision than 64 bits, you will most likely need to find an arbitrary precision math library.
source to share