The Power Tier Inverses: Roots, Logarithms, and Dynamic Convergence
In our last post, we explored how mercuryPow uses a binary squaring shortcut to rapidly calculate massive exponents, and how it relies on the square root operation to navigate fractional powers.
Because exponential growth is asymmetrical (the base and the exponent play completely different roles), deconstructing an exponent requires two completely different inverse operations:
In Mercury’s API terms, mercuryLog(a, b, val) computes val = log_b(a). In tier notation, this is the inverse route that solves for the exponent.
$$C = A^B \implies A = \sqrt[B]{C} \quad \text{and} \quad B = \log_A(C)$$
Today, we are going to look at how Mercury solves for both. We will start with the elegant simplicity of the Root, and then dive into the most complex convergence loop in the entire engine: the Logarithm.
The Root: The Elegant Inversion
When solving for a missing base, the strategy remains identical to how we handle division in the lower tiers.
In the Multiplicative Tier, division can always be rewritten as multiplication by a fractional inverse:
$$\frac{A}{B} = A \cdot \left(\frac{1}{B}\right)$$
In the Power Tier, finding a root can always be rewritten as exponentiation by a fractional inverse:
$$\sqrt[B]{A} = A^{\left(\frac{1}{B}\right)}$$
Because we already built mercuryPow to gracefully handle negative fractional bits, Mercury gets the highly complex root function almost for free. We don’t need a massive new algorithm to calculate a root; we simply flip the exponent into a fraction and route it right back through the engine we already built.
Here is the entirety of the mercuryRoot function. It is exactly eight lines of active math:
void mercuryRoot(void *stack, int Precision, uint *a, uint *b, uint *val) {
uint *p = (uint *) mercuryStackAlloc(stack, (Precision+2)*4);
uint *one = (uint *) mercuryStackAlloc(stack, (Precision+2)*4);
mercuryLoadUint(stack, Precision, one, 1);
// Step 1: Calculate the fractional inverse (1 / B)
mercuryDiv(stack, Precision, one, b, p);
mercuryStackFree(stack, (Precision+2)*4);
// Step 2: Pass the fractional inverse back into the positive variant
mercuryPow(stack, Precision, a, p, val);
mercuryStackFree(stack, (Precision+2)*4);
}
The Logarithm: Hunting for the Exponent
Solving for a missing base is straightforward. Solving for a missing exponent, however, is a completely different beast.
To compute $B = \log_A(C)$, we are asking the CPU: “To what power must I raise A to get C?” There is no simple fractional inversion for this. The engine must actively construct the exponent bit-by-bit. Mercury handles this through a highly optimized, automated two-phase search.
Phase 1: Finding the Ceiling
Before Mercury can test bits, it needs to know where to start. It does this by actively hunting for the highest necessary bit using two do-while loops.
It first checks if our target is larger or smaller than our base.
-
If the target is larger: The engine starts at bit
0and steps upward (bit++), squaring the base (mercurySqr) until it overshoots the target. This efficiently finds the highest whole-number bit. -
If the target is smaller: The engine starts at bit
0and steps downward (bit--), taking the square root of the base (mercurySqrt) until it drops below the target. This efficiently finds the highest fractional bit.
Once the overshoot happens, Mercury knows exactly where the ceiling is, and it proceeds to the convergence loop.
Phase 2: The Unified Descent
This is where the mathematical purity of the Power Tier shines. Once Mercury finds that starting bit, it iterates downward linearly across the specified precision.
It no longer cares if it is looking at a whole number or a fraction. Because the combinator of this tier is multiplicative, moving down one binary place always means halving the geometric magnitude of the step.
This unified descent is the absolute pinnacle of the Constructive Tiers working in harmony. Whether stepping from bit $2$ to $1$, or from bit $-1$ to $-2$, the engine simply calls mercurySqrt at the bottom of the loop to geometrically halve the step size for the next bit.
To find a logarithm, the engine must compare magnitudes (mercuryCmp), add candidate bits (mercuryAdd), combine running totals (mercuryMul), and dynamically halve its geometric steps (mercurySqrt). Every single operation we have built from the Additive Tier upward converges in this one loop to solve the hardest arbitrary-precision calculation in the library.
Why No Multi-Bit Stride?
If you read our previous post on Division, you might remember that Mercury used a 4-bit “nibble stride” to speed up calculations, pre-computing a table of chunks to subtract all at once.
You might wonder: Why not use a multi-bit stride for Logarithms?
The answer lies in the combinator. In division, scaling is linear—shifting our pre-computed table across the dividend only required cheap bit-shifts. But in the Power Tier, the combinator is multiplicative, and the scaling is geometric.
Every single fractional bit in an exponent represents a completely different geometric magnitude (e.g., $A^{1/2}$, then $A^{1/4}$, then $A^{1/8}$). You cannot mathematically bit-shift a square root. To discover the exact size of the next fractional bit’s contribution, the engine must actively execute a new square root on the previous step. Because every bit’s magnitude is geometrically dependent on the one before it, the clean nibble-table optimization used by division does not transfer directly. The log engine is naturally forced toward sequential refinement, evaluating and combining the candidate contributions one by one.
The Convergence Engine (mercuryLog)
Here is the core convergence loop where Mercury hunts down the bits:
// Step downward from our discovered ceiling
for (int i = 0; i <= bits; i++) {
// Test the current bit: Add it to our running exponent register
mercury_2Pow(stack, InnerPrecision, bit, _bit);
mercuryAdd(stack, InnerPrecision, reg, _bit, reg);
// Calculate the new power using our running root 'r' and 'p'
mercuryMul(stack, PowerPrecision, r, p, r);
// Compare our test power 'x' against our target 'A'
s = mercuryCmp(InnerPrecision, x, A) * c;
if (s > 0) {
// We overshot! Reject the bit and restore the previous state
mercuryLoadMercury(stack, InnerPrecision, last, reg);
mercuryLoadMercury(stack, PowerPrecision, lastR, r);
} else if (s == 0) {
// Perfect match! Clean exit.
mercuryLoadExtendMercury(stack, InnerPrecision, Precision, reg, val);
goto stackCleanup;
}
bit--; // Move down to the next smallest bit
if (i != bits - 1) {
// The Engine Drive: Halve the exponent step by taking the square root
mercurySqrt(stack, PowerPrecision, p, p);
}
}
This is the absolute pinnacle of the Constructive Tiers working in harmony. To find a logarithm, the engine must compare magnitudes (mercuryCmp), add candidate bits (mercuryAdd), combine running totals (mercuryMul), and dynamically halve its geometric steps (mercurySqrt).
Every single operation we have built from the Additive Tier upward converges in this one loop to solve the hardest arbitrary-precision calculation in the library.
Closing the Ladder
This completes the foundational Mercury arithmetic ladder. Addition taught us carry and borrow. Multiplication showed how places combine through additive geometry. Division reversed that geometry with pre-computed nibble tables. Power introduced binary squaring and the mirror of fractional exponents. Root revealed how an inverse can collapse into a call back through pow. Finally, logarithm brought the entire structure together as a constructive search for the missing exponent.
The lesson is that Mercury’s functions are not isolated tricks. They are a tiered family of operations. Each tier introduces a new kind of combination, and each inverse operation reveals what it means to solve for the missing relationship at that tier.