float-significand-investigation.md (10090B)
Binary64 significand investigation — shift, rounding, normalization
This follows the layout-access screen. It is
still an investigation: no public arithmetic or value encoding has changed.
The workers in bench/float-significands.tri execute entirely in Tree Calculus;
Python is only the input generator and external correctness oracle.
Questions and representations
Compare:
- LSB-first: existing canonical naturals, with a high 1 and empty zero.
- MSB-first: canonical Boolean bit lists, with a leading 1 and empty zero.
- Cached variants:
(width, bits)with trusted, accurate bit length.
These are working significands, not complete float values. They have no sign, exponent, NaN, or infinity handling. Widths of 53 and 106 model binary64 precision and an exact product's maximum width. Tests also include shorter values and zero.
Kernels:
- Right shift returning
(quotient, discardedNonzero). - Round
n / 2^kto nearest integer, ties to even, returning(rounded, inexact). - Exact odd-significand normalization, returning
(removedPowersOfTwo, bits). - Three successive rounded shifts, with each operation rounded separately.
- Conversion and bit-length-only controls.
The shift result retains the sticky flag separately; it is not a jammed integer with sticky ORed into its low bit. Rounding increment carry is preserved (including a result wider than the retained prefix). This is a primitive for a float implementation, not yet final rounding into binary64's exponent range.
Algorithms and cache accounting
LSB shifts/rounding consume discarded low bits and can reuse the untouched high suffix. Rounding consults the guard bit, accumulated sticky flag, and retained low-bit parity. Increment uses the existing natural successor.
MSB operations determine the retained prefix from width and shift count. They copy that prefix, inspect the discarded suffix for guard/sticky, and propagate rounding carry back toward the most significant bit. A separate conversion is not included in these measurements; output remains in the input layout.
Uncached MSB operations compute width. Cached operations receive it as an input invariant. Separate build-cache controls charge width computation. The maintained MSB variant returns a new cache calculated from retained width and carry; it does not walk the output to discover its length. Chains compare rebuilding versus maintaining that cache. The ordinary cached single-operation variants return bits, not an updated cache; do not interpret their times as complete cache maintenance costs.
Cached LSB variants cap work when the shift exceeds the known width. This
avoids scanning a whole significand when the answer can be determined from
metadata. The uncached LSB variant still terminates at the end of the input:
a count of 2^128 never causes that many recursive steps. Trusted cache inputs
are not a proposed unchecked public API for arbitrary trees.
Both directions have costs beyond list length: LSB operations can share a suffix, whereas MSB operations rebuild a prefix. Full-result observation retains this real distinction rather than forcing both implementations into a common output layout and silently charging conversion to one side.
Correctness and methodology
test/float_significands.py checks 819 deterministic cases against exact Python
integer arithmetic for each of 18 workers, plus five demand/huge-count probes.
Coverage includes:
- all values 0..63 and shifts 0..9;
- widths 1, 2, 8, 24, 53, 54, and 106;
- exact powers of two, powers plus one, and all-one significands;
- below-half, exact-half, and above-half residues;
- even/odd retained quotients and carry growth;
- shifts zero, near width, beyond width, 2046, and
2^128; - cache accuracy in maintained outputs and in chains;
- zero-shift demand which must not force an unused significand.
The Python rounding oracle is separately cross-checked by
test/float_significands_oracle_test.py: 2,560 small cases use exact Fraction
distance and even-result tie breaking rather than the guard/sticky algorithm.
It also checks huge counts and a concrete double-rounding counterexample. A
chain of rounded operations is intentionally not equated to one final rounding.
The recorded run has 500 measured invocations, all checked against full expected trees. Each batch contains 96 values. There are 100 workload groups, five fresh-process repetitions, and four retained timing samples per group. The whole-run time and process heap are bounded. As in the first screen, compilation/loading are outside the measured invocation-through-full-force interval, rendering follows it, and profiling collection overhead is included. Allocation means cumulative allocated bytes, not peak memory.
Randomized job ordering, initial-repetition exclusion, raw samples, min/max and
medians follow the first screen. Results and artifact/source hashes are recorded
in bench/float-significand-results.json. Raw logs and staged source/input/output
snapshots remain in /tmp/tricu-float-significands-final for this run.
Results: workload matters
Below are batch medians for 96 53-bit significands, in milliseconds and allocated decimal MB. MSB cached here means preexisting width and bits-only output. Short timings are noisy; allocation differences and large timing gaps are stronger evidence than close rankings.
| Round workload | LSB ms / MB | Cached LSB ms / MB | Cached MSB ms / MB |
|---|---|---|---|
| Small shifts: 1, 2, 3, 7; random bits | 5.41 / 21.29 | 6.08 / 24.55 | 41.74 / 277.58 |
| Small shifts; all-one bits (long carries) | 7.95 / 46.59 | 9.12 / 49.85 | 37.67 / 288.33 |
| Near width: 52, 53, 54; random bits | 44.80 / 284.15 | 26.73 / 201.05 | 6.01 / 38.17 |
| Near width; powers of two / powers plus one | 44.38 / 284.14 | 28.32 / 200.99 | 10.17 / 59.08 |
Far shifts: 2046 and 2^128 |
37.93 / 283.20 | 1.70 / 7.94 | 1.98 / 8.92 |
The sparse near-width control matters: random MSB suffixes usually reveal a sticky 1 quickly. Sparse suffixes can require much more traversal. It narrows the advantage without reversing it in this implementation. Long carry chains also increase LSB costs but do not reverse the small-shift result.
Cache construction is not free
On the mixed 53-bit batch:
| Round strategy | ms | Allocated MB |
|---|---|---|
| LSB without metadata | 22.37 | 135.76 |
| LSB with supplied width | 14.70 | 71.16 |
| LSB computing width for this operation | 20.83 | 128.31 |
| MSB without metadata | 26.48 | 202.10 |
| MSB with supplied width | 23.39 | 146.05 |
Computing a cache just to throw it away is not the same proposition as carrying metadata that arithmetic can maintain cheaply. The synthetic mix gives equal frequency to very different shifts; it is not an application workload model.
Chains reward maintained metadata, but not enough to decide the layout
Three rounded shifts on the mixed 53-bit batch:
| Chain | ms | Allocated MB |
|---|---|---|
| LSB | 28.46 | 160.18 |
| MSB, recompute width | 66.86 | 452.30 |
| MSB, supplied initial width then rebuild | 63.30 | 396.02 |
| MSB, maintain width from carries/counts | 45.03 | 324.32 |
At 106 bits, LSB versus maintained MSB was 43.38 ms / 277.40 MB versus 97.21 ms / 714.00 MB. Zero and large-shift cases can collapse a chain early; these are complete chain workloads, not three independent scalar timings.
Odd normalization favors the existing direction
For mixed random 53-bit inputs, exact odd normalization cost 3.80 ms / 6.68 MB LSB-first versus 19.47 ms / 102.25 MB MSB-first. In the sparse powers-of-two control, it was 8.37 ms / 54.34 MB versus 19.01 ms / 123.32 MB.
This supports the claim that removing low zero bits is convenient in the existing representation. It does not prove that always normalizing floats to odd significands is desirable: restoring implicit width and managing exponents may outweigh that convenience. The public representation remains undecided.
Current interpretation
- LSB-first remains a strong working-significand candidate. Its small-shift, normalization, and measured-chain behavior withstands adversarial controls.
- MSB-first has a real advantage for some near-total discards; dismissing it based only on small shifts would be wrong.
- Width/exponent-derived bounds can matter more than bit direction for far alignment gaps. We should exploit known binary64 precision where possible rather than automatically storing or recomputing redundant metadata.
- A single direction need not serve every stage, but conversion has real cost: LSB-to-MSB for a mixed 53-bit batch cost 7.29 ms / 27.58 MB. A hybrid needs to amortize that cost, not assume reversal is free.
Still required before selection
The next blocked-significand and arithmetic-pipeline screen is now available. It covers radix-256 arithmetic and bounded aligned pipelines; full binary64 semantics and division remain open.
Blocked/limb candidates have not yet been compared on these kernels. Neither have complete aligned addition/subtraction (especially cancellation), exact products plus final rounding, correctly rounded division, or retained-heap behavior. The 106-bit inputs here model size, not the distribution of products. There is no binary64 arithmetic conformance claim yet.
Next, compare blocked bit operations and use these primitives in equivalent addition/subtraction and multiplication pipelines. Include subnormal transitions, rounding overflow, and exponent metadata maintenance. Only then compare whole operation and chain costs to choose public and working representations.
Reproduce
HOST=$(nix build .# --no-link --print-out-paths)/bin/tricu
python3 test/float_significands_oracle_test.py
python3 test/float_significands.py "$HOST" \
--directory /tmp/float-significands-new --size 96 --repeats 5
Use a fresh directory and normal Python assertion settings (not python -O).
Failed runs leave complete: false and retain diagnostic files.