What is the most effective way to calculate the exponent in $x^y = z$?

Question

I was recently watching a video on Karatsuba's fast multiplication algorithm and the narrator stated something that intrigued me:

$2^{1.6} \approx 3 $

Specifically, I wondered what power $2$ would need to be raised to in order to be equal to $3$:

$2^p = 3$

Since my knowledge in the field of mathematics is rather lacking, I attempted to brute force the answer in the C# programming language:

double p = 1.5;
for (; Math.Pow(2, p) != 3;)
    p += 0.00000000000000000000000000000000000000000000000000000000000001;

Console.WriteLine(p);

_{Note: This snippet is intended for creating a CodeGolf.SE challenge, so please disregard the abuse of the for iterator here. It's abused for the sake of brevity.}

However, as the incremental value increases in precision, the time it takes to reach an answer, also increases (likely by orders of magnitude), so this is a very inefficient way to determine the value needed for $p$.

---

What is the most effective way to determine the exponent needed in order for the following to be a true statement when $x$ and $z$ are known:

$$x^y = z$$

Answer 1

In general for positive reals $a$ and $b$ the value $x$ such that $b^x=a$ is known as $\log_b(a)$ and is called "the logarithm base $b$ of $a$" . In our case we have $b=2,a=3$.

The rule for converting logarithms with a special base to something with normal natural logarithm is $\log_b(a) = \log(a)/\log(b)$.

This is because we need $b^x=a$, and we have $b^x=(e^{\log(b)})^x = e^{\log(b)x}$ so we need $\log(b)x = \log(a)$.

In conclusion $\log_2(3) = \log(3)/\log(2) \approx 1.58496250072$

Answer 2

If you don't want to use logarithms:

2^x = 3. x is obviously at least 1 but less than 2. So we create a sum starting with 1, and divide by 2^1: 2^y = 1.5. Square both sides, getting 2^(2y) = 2.25.

Obviously 1 <= 2y < 2. Add 0.5 to the sum, divide by 2, getting 2^(2z) = 1.125. Square to get 2^(4z) = 1.265625, square again to get 2^(8z) = 1.6018, square again to get 2^(16z) = 2.5658. So add 1/16 to the sum, divide by 2 getting 2^(16u) = 1.2829. And so on.

Answer 3

One approach is to write $\log_2{3}$ as a continued fraction. You can do all these steps strictly in integer arithmetic, although quickly they become very large integers.

$$\begin{align} \log_{2}3&=1+\log_{2}(3/2)=1+\frac{1}{\log_{3/2}2}\\ \log_{3/2}2&=1+\log_{3/2}(4/3)=1+\frac1{\log_{4/3}(3/2)}\\ \log_{4/3}(3/2)&=1+\log_{4/3}(9/8)\\ \log_{9/8}(4/3)&=2+\log_{9/8}(2^8/3^5)\\ \log_{2^8/3^5}(9/8)&=2+\log_{2^8/3^5}(3^{12}/2^{19})\\&\vdots \end{align}$$

On the next step, you’d want to find the largest $n$ such that $$3^{12n+5}<2^{19n+8}$$ As you can see, just integer arithmetic, but we’re talking big integers. Indeed, the exponents grow exponentially.

This gives a sequence of approximations: $$1,2,\frac32,\frac85,\frac{19}{12},\frac{65}{41},\frac{84}{53},\frac{485}{306},\dots$$

---

Aside: The continued fractions for $\log_23$ are related to music. The pentatonic scale and the $12$-note scale sound good to our ears because $5$ and $12$ are denominators for good approximations for $\log_23,$ which means the scales can divide an octave into $5$ or $12$ roughly even intervals and still get almost perfect “fifths.”