Finding the Exponent: Binary Construction in Mercury’s Square Roots and Logarithms

How knowing where to begin—and knowing how to refine—turns continuous mathematics into computational algorithms.

Mathematics gives us familiar relationships:

x² = a   and   b^x = a

But a computer must answer a more concrete question: How can we construct the unknown value from a finite sequence of operations?

Mercury, an arbitrary-precision floating-point arithmetic library, offers an interesting perspective. Its square-root and logarithm algorithms approach their answers through successive binary contributions. Each candidate is tested against the value being sought, and the construction becomes progressively finer.

The algorithms have something important in common. But their differences reveal why some inverse operations are easier to begin than others.

The Advantage of Knowing the First Bit

Consider the square root:

x = √a

If we know the leading binary position of a, we can determine the leading binary position of its positive square root.

For example:

2⁶ ≤ 100 < 2⁷

Since 2⁶ = 64 and 2⁸ = 256, the square root falls between 2³ and 2⁴:

2³ ≤ √100 < 2⁴

The answer begins at binary position 3.

This gives an algorithm a useful starting point. It can begin with the contribution 2³, then examine successively smaller powers of two.

Given a current approximation m, propose:

q = m + 2^k

If q² ≤ a, the contribution fits and can be retained. Otherwise, it is rejected.

The result is constructed one binary place at a time.

Notice what made the beginning convenient: squaring doubles the exponent of a power of two. The magnitude of the input therefore tells us where to begin constructing the root, even though the remaining bits still have to be tested.

But What If the Unknown Is the Exponent?

Now consider:

b^x = a

The logarithm asks for the missing exponent:

x = log_b(a)

For real logarithms, the target a must be positive and the base b must be positive and different from 1.

Unlike square-root extraction, we cannot generally read the leading position of x directly from the leading position of a. We must establish an appropriate exponent scale relative to the base.

Mercury’s logarithm implementation approaches this constructively. Repeated squaring or square rooting helps locate an initial power contribution. Once that scale is established, the algorithm can begin refining the unknown exponent.

For a positive exponent, think of candidate contributions in descending binary positions:

x ≈ b_k2^k + b_k-12^k-1 + b_k-22^k-2 + …

Here each binary choice b_j is either 0 or 1. Not every term is retained. Each candidate contribution is tested according to whether its corresponding power moves toward or beyond the target. For bases below 1, the comparisons reverse direction, but the construction principle remains.

When refinement reaches fractional binary positions, the mathematical relationship becomes particularly elegant.

Why Square Roots Return to the Story

Consider a nonnegative exponent with fractional binary contributions:

x = n + b₁/2 + b₂/4 + b₃/8 + …

where each b_i is either zero or one.

Exponentiation gives:

a^x = aⁿ × (a^1/2)^b₁ × (a^1/4)^b₂ × (a^1/8)^b₃ × …

But:

a^1/2 = √a

and:

a^1/4 = √(√a)

Each additional square root corresponds to a finer fractional binary contribution.

This is the connection that makes Mercury’s constructive logarithm algorithm so interesting: square roots are not merely related to logarithms mathematically; they can supply the successive power contributions used to recover the exponent.

Mercury’s optimized logarithm implementation also maintains an accumulated power, avoiding the need to recompute the entire exponentiation for each candidate contribution. Its slower counterpart provides a useful contrast by recomputing candidate powers more directly.

Why Binary?

Binary is not required by the continuity of logarithms. A real logarithm is continuous on its positive domain, but continuity alone does not dictate an algorithm.

Binary refinement is attractive because it transforms a search into successive two-way decisions.

Each step resolves another binary position. Each fractional exponent step can be generated through square rooting. And each candidate can be evaluated against the target.

There is a useful sense in which two is the natural minimal integer subdivision factor: it creates the smallest possible nontrivial choice.

It is not, however, a universal optimum for numerical computation. Other algorithms can compute logarithms through different approximations and convergence methods.

Mercury’s value as an educational implementation lies partly in how clearly its binary approach exposes the construction.

Where Continuous Mathematics Meets Finite Precision

Mathematically, successive refinement can continue indefinitely. A computer cannot.

Mercury represents a value using a configurable number of 32-bit mantissa words. Each additional word supplies 32 more bits of stored precision.

Eventually, a proposed correction becomes too small to change the representable result. The continuous mathematical process has encountered the finite resolution of its numerical representation.

This distinction matters. A converged finite-precision calculation is not the same thing as an exact mathematical limit. But a well-designed numerical algorithm can approach that limit systematically, with precision chosen by the caller.

The Larger Lesson

Square roots and logarithms are inverse operations of different relationships, yet both demonstrate a powerful approach to numerical computation:

Find the scale, propose a contribution, test it, and refine.

For square roots, the initial scale follows naturally from the leading binary position of the input. For logarithms, the exponent scale must first be established relative to the base and target.

From there, binary refinement turns the search into a sequence of increasingly fine decisions.

That is one of Mercury’s most interesting educational qualities. The implementation invites us to examine not only the answer, but how the answer is constructed.

The mathematics is continuous. The algorithm proceeds through discrete decisions. Precision determines how far the construction can go.

And the source code lets us follow those decisions all the way down.

Continue Exploring Mercury

Compare the algorithms directly in the Mercury C implementation, follow the canonical Mercury reference, or explore the Mercury learning hub.