Logarithms (Part I?)

January 3, 2017

The traditional—but certainly not the best—way to compute the value of the logarithm of some number x is to use a Taylor series, for example

\displaystyle \ln x = (x-1)-\frac{1}{2}(x-1)^2+\frac{1}{3}(x-1)^3-\frac{1}{4}(x-1)^4+\cdots

but that expansion is only valid for 0<x\leqslant{2}, or so, because it is the Taylor expansion of \ln x "around 1", and the convergence radius of this particular expression isn't very large. Furthermore, it needs a great deal of terms before converging.

Read the rest of this entry »

ln n!

February 23, 2016

In the course of analyzing an algorithm, I used the simplifying hypothesis that the cost function is

\displaystyle c(n)\approx\sum_{i_1}^n \lg i=\lg n!.

That expression is cumbersome but we can get a really good simplified function to use as a proxy. Let’s see how.

Read the rest of this entry »

Yet another Square Root Algorithm

April 29, 2014

Computing (integer) square root is usually done by using a float square root routine and casting it to an integer, possibly with rounding. What if, for some reason, we can’t use floats? What are the possibilities?


One possibility is to use binary search to find the square root of a number. It may be a good choice because it will only perform a number of iterations that is half of the (maximum) numbers of bits of the number (we will explain why in a moment). Another possibility is to use Newton’s method to find the square root. It does a bit better than binary search, but not exceedingly so: on very small integers, it may iterate a third as much iterations as binary search, but on large integers, it will do only a bit fewer iterations. Can we do better? Yes!

Read the rest of this entry »

Damn you, Napier!

January 15, 2013

Briggs‘ logarithms (often mistakenly understood to be Napier‘s logarithms) is such an useful function that most of us don’t really think about it, until we have to. Everyone’s familiar with its properties:

\displaystyle\log_b a = \frac{\log a}{\log b}

\log b^x = x \log b

\log a b = \log a + \log b (1)

\displaystyle\log \frac{a}{b} = \log a - \log b

but suddenly,

\log (a+b) = ?

What can we do with this last one?

Read the rest of this entry »