Is there a method for computing logarithms similar to Square and Multiply for exponentiation?

Question

I used the Square and Multiply method and now I was wondering if there is a similar thing for the computation of logarithms. Shouldn't it be exactly the opposite of Square and Multiply? And if so where do you start?

Thanks in advance

Answer 1

You can use a similar technique to compute the integer part of $\log_b x$: Repeatedly square $b$ until you get something larger than $x$, then divide out the repeated squares starting with the largest one, unless that would get you below $1$.

One difference from exponentiation-by-squaring is that you need to store all the repeated squares because you need to use them in the opposite order they were produced in.

Instead of dividing (which is often expensive) you can start an accumulator at $1$ and keep multiplying in the repeated squares, discarding the product if it exceeds $x$.

In order to get at the fractional part of $\log_b x$ you can continue by taking repeated square roots of $b$, which is expensive. But if all your logs are to the same base (or you compute $\log_b x$ as $\frac{\log x}{\log b}$ for a common base), you can once and for all compute a table of repeated square roots of the base and use that for all of your logarithm calculations. A variation of this can yield a CORDIC-like algorithm for logarithms.

All this only works for numbers that you can compare. Logarithms groups or ring that doesn't have a well-behaved order is thought to be a hard problem. (And the hardness of this problem in particular settings is the basis of several cryptographic primitives).