2
$\begingroup$

On a question on this site there is an explanation of the algorithm Knuth gives in The Art Of Computer Programming to compute an approximation of $y = \log_bx$.

Now, I understand why it works; anyway, the only question arising in my mind is: how can we pre-compute a table of logarithms with arguments of the type $\frac{2^k}{2^k-1}$? Or, generally speaking, is there an algorithm to compute a good approximation of $y = \log_b\frac{a^k}{a^k-1}$, considering such a logarithm as a special case?

I see that the simplest case is when $a = b$. So we can write $y = k - \log_b(b^k-1)$. But then? Of course we cannot execute the same algorithm to compute $y = \log_b(b^k-1)$, for, unless $k=1$, the argument $x = b^k-1$ won't respect the initial condition of $1 \leq x < a$

Probably a solution would be to factorize $x$ in prime numbers and then sum the logarithms of each one, since once I read that Henry Briggs (who derived the fundamental idea behind this algorithm) found a clever way to take logarithms of prime numbers (this is Chapter Nine of his Arithmetica Logarithmica: see here); but, you know, I had no more motivation to inform myself on that as I got to the first page of his book: "Logarithms are numbers which, adjoined to numbers in proportions, mantain equal differences".

I would rather like more "modern" explanations of the problem :)

$\endgroup$
3
$\begingroup$

If $k \gg 1$, $$\log_b\dfrac{a^k}{a^k-1}=\log_b\dfrac{1}{1-a^{-k}}=\dfrac{\ln_b(1+a^{-k}+a^{-2k}+...)}{\ln b}$$

Using Taylor expansion, we obtain

$$\dfrac{1}{\ln b}\sum_{n=0}^{\infty}(-1)^{n+1}\dfrac{(a^{-k}+a^{-2k}+...)^n}{n}=\dfrac{1}{\ln b}\sum_{n=0}^{\infty}(-1)^{n+1}\dfrac{a^{-nk}(1+a^{-k}+...)^n}{n}$$

Then we go back the process

$$\dfrac{1}{\ln b}\sum_{n=0}^{\infty}\dfrac{(-1)^{n+1}}{n}(\dfrac{a^{-k}}{1-a^{-k}})^n=\dfrac{1}{\ln b}\sum_{n=0}^{\infty}\dfrac{(-1)^{n+1}}{n(a^k-1)^n}$$

Just use first several terms to approximate the answer.

If $k \ll -1$, you can use a similar method. If $|k|$ isn't so large, direct calculation is the fastest way.

$\endgroup$
  • $\begingroup$ Ok, so it turns out that Taylor series rule in every case. However, I thought that $\log \frac{a^k}{a^k-1}$ was a special case of logarithm, computable without the need of Taylor series, as even Briggs uses them in his computations... Basically, I was not asking a "modern" method, but a "modern" explanation of some older methods $\endgroup$ – Riccardo Del Monte May 28 '14 at 13:03
  • $\begingroup$ I'm sorry, but I didn't know that Briggs was living in 16th century, and I mistakenly assumed that he was some 19th or 20th century mathematician. So, I didn't interpret the context properly. But I believe Taylor series is not a new concept which should be considered as "modern." It was invented in 1715 by Taylor and its prototype existed in the same age as Briggs. Unfortunately, I'm only familiar with problem-solving-like questions, so I unfortunately can't provide any explanation which you need. $\endgroup$ – Math.StackExchange May 28 '14 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.