How to compute logarithms (without log function)

This article is a condensed version of the original, where the musical roots of the algorithm and its ancient origins are explored, making it less straightforward to follow. Here’s a clear explanation of how it works, think of it as a tutorial on “how to calculate logarithms in Python/JavaScript without the log function.”

The two Python implementations below are similar, except the second handles arguments in the 0–1 range. To make the logic explicit, both provide the list of consecutive convergents found, excluding the first one if integer.

def mla(a, b, max_q):

    if b <= 1 or a < 1:

        return []

    if a == 1:

        return ["0/1"]  # log_b(1) = 0

    if a == b:

        return ["1/1"]  # log_b(b) = 1

 for p in results]

    results = []

    link, lower, upper = a, 1, b

    p, q = 1, 1

    while q < max_q:

        while link < 1:

            link *= b; p += 1

        while link > b:

            link /= b; p += 1

        if q == 1:

            H = b / link; p += p - 1

        q += 1

        if link == b:

            results.append(f"{p-1}/1"); break

        if lower < link < upper:

            commas = [link/lower, upper/link]

            if (max(commas) - 1) / (min(commas) - 1) <= 2:

                results.append(f"{p}/{q}")

            lower, upper = (link, upper) if link < H else (lower, link)

        link *= a

    return results

The three gap theorem says that for any irrational number \(\alpha\) and any positive integer \(n\), the set of fractional parts \(\{k\alpha\}\) (that is, \(k\alpha \bmod 1\)) for \(k = 1, 2, ..., n\), when arranged on the unit interval \([0,1)\), divides it into at most three distinct gap sizes. It also connects \(\alpha\) and the k values where gap changes relates to its continued fraction expansion. This algorithm uses a logarithmic isomorphism instead of \(k\alpha \bmod 1\); for instance, with \(\log_b(a)\), it looks at the modular remainders of exponential sequences \(a^x \cdot b^{y_x} \in (1, b]\), effectively rotating the \(a^x\) sequence within a modular space of \(b^{y_x}\). It detects when gaps change, marking that a convergent of the continued fraction expansion has been found. As the location of the change narrows, it focuses on comparing only the most recent gaps in that area.

This live demo calculates a few example convergents and renders one of the earlier ones. By default, it’s set to log2(3), showing a list of 10 convergents up to 1054/665, with the graphic displaying 19/12.

For more on the music theory behind it, see (link), and for the theoretical basis (group theory, continued fractions, three gap theorem), see (link).