I was very excited to publish the RussCox58Printer code and benchmarks. Supported by green tests, I did that early.
There are a bit less than $2^{64}$ finite Float values, so a very sparse sampling, with a few particular patterns completed by a few pseudo random ones is great for catching low hanging errors, but is in no way a proof of correctness.
The proof exists for original work, but shifting from 64-128 bits arithmetic to 58-116 bits and slightly deviating from implementation details does invalidate the proof, it needs to be redone.
Like the original work, the essential part requiring attention is the unrounded scale which multiplies two-limbs $x$ with four-limbs $pm$ then shift, and account for truncated bits so as to be sure to perform correct round-to-nearest-tie-to-even.
There is a slow path with the complete product, and a fast path omitting the contribution from least significant limbs.
We thus have to validate both paths and the switch condition
Let us start with the slow path. $pm$ is a limited precision approximation of $5^p \cdot 2^{pe}$ rounded up to nearest 116 bits integer, where $pe$ is the appropriate shift that ensure pm highBit=116
Thus, $pm = 5^p \cdot 2^{pe} + \delta$, with $0 \leq \delta \lt 1$ and $2^{115} \leq pm \lt 2^{116}$.
Note that (5**49) highBit=114 so for $0 \leq p \leq 49$, $pm$ is exact, $\delta = 0$.
$pm$ is decomposed into four 29-bits limbs, $p_3,p_2,p_1,p_0$
On the other side, we have $2^{57} \leq x \lt 2^{58}$, so the result is $2^{172} \leq x \cdot pm \lt 2^{174}$
$x$ is decomposed in two 29-bits limbs $x_1,x_0$ and the product fits on six 29-bits limbs, $l_5,l_4,l_3,l_2,l_1,l_0$.
For negative $p=-q$, $5^p = 1/5^q$ cannot be represented in base 2 with a finite sequence of bits.
However, if $x$ is a multiple of $5^q$, then the product $x \cdot 5^p$ can be represented with a finite sequence.
Since $x \lt 2^{58}$, the result fits on most significand limbs $l_5,l_4$ of the product.
However, (5**25) highBit=59, $x$ has at most 58 bits so it can never be a multiple of $5^{25}$. Hence we know for sure that $x \cdot 5^p$ is not representable with a finite sequence of bits for $p \leq -25$.
In the case of shortest decimal, the limit is $p \leq -24$ because x uses at most 55 bits:
- 53 bits for
Float precision - 1 bit for the upper bound of interval, half ulp away
- 1 more bit for lower bound of interval if $x$ is at a binade boundary (a normalized power of two), because the predecessor is half ulp lower, the separation bound is one quarter ulp below $x$
Note that denormals always have half ulp bounds on both side, $2^{-1075}$, whether a power of two or not.
Similarly, we know for sure that $x \cdot 5^p$ require at least 59 bits to be represented exactly for $p \ge 25$.
That is 61 bits for $p \ge 26$.
Note that 116-(5**24) highBit=60, $ctz(pm) \geq 58$ for $0 \leq p \lt 24$, which means that the $l_1,l_0$ limbs will be unconditionally null in this case.
When using shortest decimal representation, $ctz(x \cdot pm)=ctz(x) + ctz(pm) \geq 58$ for $0 \leq p \leq 26$ since 116-(5**24) highBit + 3=58
If ever we want to reuse unrounded scale for other purposes though, we should better avoid shortest decimal specifics.
In any case, for $p \lt -24$ and $p \gt 25$, we are sure that $x \cdot 5^p$ will set a bit beyond first 60 bits, which is more than required by the shortest decimal usage, so we know for sure that the exact product has truncated bits and that the result cannot be an exact tie. For such $p$, we can set the sticky bit to 1 unconditionally.
Let's now consider the potential problems that we could encounter: we are interested by $x \cdot 5^p \cdot 2^{pe}$.
We only keep the most significant bits of the result: $\lfloor x \cdot \cdot 5^p \cdot 2^{pe} / 2^{110 +s} \rfloor$
But we want to set a sticky bit if the division by $2^{110 +s}$ is not exact, that is if there are truncated bits
The significant bits that uscale does keep is $58-k$, where $k=6-s$, including the sticky bit.
Without the sticky bit, the significant part spans $58-k-1$ highest bits of the 174 bits.
With $k \gt -4$, the significant only spans limbs $l_5,l_4$ and sometimes head of $l_3$
With limited precision, we are computing $x \cdot (5^p \cdot 2^pe + \delta)$ instead, with $x \lt 2^{58}$ and $\delta \lt 1$, the pollution $x \cdot \delta \lt 2^{58}$ is limited to low limbs $l_1,l_0$. For this reason, uscale never search for the presence of sticky bit in those limbs, it might be false positive garbage. For correctness, we must prove that:
- the $\delta$ approximation will never propagate a carry up to the significant part
- it will always be possible to detect truncated bits in the remaining limbs tail of $l_3$ and $l_2$
There is a limited set of possible powers $p$ for the range of Float exponent, only a few hundreds, so the idea is to enumerate adverse situations for every possible value of $p$.
However, for $x$, the Float mantissa let $2^{53}$ possible values that we obviously cannot enumerate easily with our computers.
For having a carry propagating from low limbs error in $l_1,l_0$ up to significant bits, the exact result must have all the truncated bits in-between being 1. After the carry all these bit will become 0.
This is also the case when we will detect no truncated bit, while the exact result would have at least one. Though, for large magnitude of $p$ above 25, we have seen that the sticky bit can be set uncondtionnally and is not a problem.
For finding adverse situation, we thus have to search for cases where the truncated bits down to l2 are all zeros.
The bits in lowest limbs could be whatever.
Considering low bits is like taking remainder of division by $m=2^{110+s+1}$, IOW, considering modulo $m$.
Mathematically, this is equivalent to say that we search for some $x$ subject to $0 \leq x \cdot pm \bmod m \lt 2^{58}$
This is solvable in O(log m) time, exactly like in Cox's proof. With the help of Claude Sonnet, we can easily translate the search in Squeak Smalltalk, see RussCox58PrinterTest class>>firstY:mod:low:high: and its usages.
The strategy is thus to find every $\{x,s\}$ pair verifying this equation for each possible $p$, so finally every $\{x,s,p\}$ triplet, and check whether they are false positive or a true problem by comparing with exact arithmetic result obtained thru LargeInteger fractions.
For shortest decimal representation bounds, we found 28 potential problems overflowing the sticky bit, but none was a true problem overflowing the half bit.
Note that initial algorithm had a problem of false sticky bit for some large values of $p$. So the initial uscale implementation could answer incorrect results. This could even happen when $pm$ is exact at $p=32$, we can craft an $x$ such that all truncated bits in $l_2,l_3$ are truly zero, and a true 1 sits in $l_1$, but we do not detect it by fear of $\delta$ garbage... Fortunately, the false sticky bit did not change the final rounding direction, so the shortest decimal was still correct. However, with the remarks above, in order to have a more robust uscale, I have added the alwaysSticky instance variable for large $p$.
These are the elements of proof of correctness of slow path, we prove that we cannot construct an $x$ that defeats the algorithm.
For the fast path, the situation is different. The low limbs $l_1,l_0$ are not computed, so there is no excess in the computed limbs caused by $\delta$, on the contrary, those limbs are now underestimated. The question is still whether the carry coming from discarded low limbs computation could propagate up to the significant part. If $ctz(pm) \geq 58$, then $l_1,l_0$ are null, and the fast path is as exact as the slow path, problem solved for small positive $p$, so we have a first condition for taking the slow path canProduceLowLimbs.
If the first condition is true, the consideration is that the carry coming from $x_0 \cdot p_0 + 2^{29} (x_1 \cdot p_0 + x_0 \cdot p_1)$ can cause at most 2 carry up to limb $l_3$. Thus if truncated bits in tail of $l_3$ is less than binary mask $111\dots1101$ with appropriate number of bits in the mask, then the carry will change the truncated bits, but will not propagate up to significand. This gives a first condition truncatedBitsInL3 > (mask - 2) for which we are not sure of the fast path and should better revert to slow path.
The other condition is when truncated bits in tail of $l_3$ is zero. No carry can propagate up to significant in this case. For large $p$, we know for sure that there is a sticky bit (alwaysStick), but how to be sure if there are truncated bits or not in case of small negative $p$? Because carry from low limbs can completely change $l_2$, the bits in $l_2$ are complete garbage, we cannot trust them. When encountering condition truncatedBitsInL3 = 0 and: [alwaysSticky not] we'd better take the slow path.
In fact, this is not strictly necessary for shortest decimal printing, with a 2-d lattice, we can show that taking decision based on garbaged $l_2$ could work, but that makes uscale more fragile than necessary if wanting to reuse it for other purpose like parsing decimals.
So this time the elements of proof have been gathered for the whole algorithm. Utilities are published with the Ryu-Tests package on squeaksource.
This is better than handwaving arguments that I used in previous post (like the 114 bits limit for $pm$, which does not come from nowhere but would require carefull inspection of sources to verify that it is a sufficient condition).
The early heuristics used for switching from fast to slow path were also questionable. I had produced those with help of Gemini, and thought that I had understood them. But a more careful review revealed some false assumptions from my part, so my understanding was not rock solid. This is a common bias, because AI seems to know a lot more than us, it can become authoritative, and we can be convinced too easily. The green Unit tests were another confirmation bias.
My further questions to Gemini for sorting this out only brought more confusion, I could not understand the answers. Fortunately, we have more than one AI. I thus asked to Claude Sonnet if the heuristic were sound. It could not make more sense of it than I, other than politely qualifying the heuristic as probabilistic. From mathematical point of view, Claude Sonnet is much more solid. Amazingly solid. In doubt, it is verifying most assertions by executing python code.
So I massively used free version of Claude for getting a much deeper understanding of the algorithm, producing the proof, and robustifying the implementation. I have exhausted my free tokens several times before I could reach this state, which is an indication that the problem was not completely trivial. Note however that the alwaysSticky trick, the Pow116 architecture, and several other optimizations are my own production, human have their own value.
The 1 or 2 days initial work turned into more than a week, so the apparent efficiency dropped. Though, I think that understanding what the AI is producing, and using AI for accelerating such understanding is the usage that we should prioritize, at least this is my engineering bias. I couldn't decently publish the work in Squeak trunk without such mastering.
With all these modifications, along with a few traditional optimization in the streaming part, beneficial to other ShortestFloatPrinter variants, here are the new benchmarks which show that correctness did not downgrade performance:
Float to String (ns per conversion, best of 5 runs over 10,000 floats)
| dataset | printString | inexact | Ryu | Schubfach | Dragonbox | RussCox58 | Speedup vs printString |
|---|---|---|---|---|---|---|---|
| random bit patterns | 16458 | 1089 | 540 | 448 | 389 | 366 | 45.0x |
| uniform [0, 1) | 642 | 956 | 419 | 377 | 310 | 295 | 2.2x |
| integral values | 319 | 502 | 179 | 184 | 184 | 185 | 1.7x |
| two decimals | 321 | 493 | 410 | 347 | 260 | 254 | 1.3x |
| large and tiny | 16510 | 1101 | 665 | 450 | 388 | 374 | 44.1x |
| dataset | Ryu | Schubfach | Dragonbox | RussCox58 | vs Ryu | vs Schubfach | vs Dragonbox |
|---|---|---|---|---|---|---|---|
| random bit patterns | 266 | 181 | 112 | 102 | 2.6x | 1.8x | 1.1x |
| uniform [0, 1) | 200 | 174 | 102 | 89 | 2.2x | 2.0x | 1.1x |
| integral values | 22 | 23 | 23 | 23 | 1.0x | 1.0x | 1.0x |
| two decimals | 259 | 189 | 114 | 109 | 2.4x | 1.7x | 1.0x |
| large and tiny | 384 | 178 | 109 | 99 | 3.9x | 1.8x | 1.1x |
What's next? The nice thing is that uscale can be used both for reading and parsing decimals. For printing with fixed number of significant digits and for parsing decimals, the proof has to be extended with the correct $\{x,s,p\}$ range, but now we have a solid base to do so.
For example (10**17-1) highBit=57, so parsing a 17 digits can use up to 57 bits of x. Fortunately, there is no interest in outputting more than 17 digits, so the algorithm will be able to parse most printed Floats. Similarly, printing with fixed precision should better stop at 17 significand digits. We would see that 18 digits reveal the limits imposed by the reduction from 128 to 116 bits. Anyway, (10**18-1) highBit=60, with half bit and sticky bit required by unrounded scale, we already enter the land of LargeInteger.
Last, we could also extend Pow116 to other bases than 10 as the comment suggests. But each new base would require both precomputed power tables and proof of correctness. While the former could be automated on the fly, the later would be much more challenging, which severely limits the applicability.