Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :)

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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 –  Riccardo Del Monte May 28 at 13:03
    
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. –  Aran Komatsuzaki May 28 at 18:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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