Remember your basic algebra!
To find p such that
x^p = y, take the natural logarithm:
x^p = y ⇒ log(x^p) = log(y) ⇒ log(x)p = log(y) ⇒
p = log(y) / log(x)
The natural logarithm yields a real result in this case, so take the least-trailing-integer of the result.
In C++:
1 2 3
|
# include <cmath>
...
std::floor(std::log(y) / std::log(x))
|
To follow through on your algorithm:
I don't think this problem is a good fit for a recursive solution, but we'll do it anyways for the sake of demonstration.
Given that the goal of recursion is to to break the problem down into something smaller, you're going to need some extra state besides the base, x and the maximum, y. You can avoid adding an extra parameter by manipulating the result and exponent,
but that requires manipulating logarithms which defeats the point. (Edit: actually, you can divide.)
It looks like you're getting confused about what y is in your attempt. It is the result of the exponentation x^p; you're looking for the greatest exponent p which doesn't exceed y. Here is one way to do this in an accumulative-recursive style:
1 2 3 4 5 6 7 8 9 10 11 12
|
int ilogx_impl(int const x, int const y, int const acc) {
if ((acc * x) > y) return 0;
else return ilogx_impl(x, y, acc * x) + 1;
}
int ilogx(int const x, int const y) {
return ilogx_impl(x, y, 1);
}
# include <iostream>
int main() {
std::cout << "as integers, the greatest power that 2 can be raised to "
<< "without exceeding 1023 is " << ilogx(2, 1023) << ".\n";
}
|