Sunday, November 22, 2026

Proof of correctness for the RussCox58Printer

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)

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
Shortest decimal only (#decompose:), ns per conversion
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.

Sunday, November 15, 2026

Fast Float printString in Squeak too

Squeak is using a variant of quite ancient Guy Steele Dragon4 algorithm for printing Float accurately.
Accurately means the shortest decimal representation that would round trip to the receiver when re-evaluated.
The implementation is quite easy thanks to LargeInteger arithmetic. But that's also a weakness.
LargeInteger arithmetic is slow. Unlike SmallInteger, it also puts lots of pressure on garbage collector.
Since that time, Float printing has made tremendous progress that Squeak/Smalltalk did not leverage yet.
Fortunately, Serge Stinckwich has recently published an awsome package for Pharo:

https://github.com/SergeStinckwich/pharo-ryu

That's fantastic, because on 64 bits images, with SmallInteger in the range $[-2ˆ61,2ˆ60-1]$, they run abysmally faster than Dragon4, particularly the DragonBox algorithm achieve up to 35x for large, tiny or random floats.
While the speed-up is less impressive for short Float entered by humans, it is enornous when serializing results of scientific computations.
We absolutely need that in Squeak. In any Smalltalk dialect in fact.

It's been an occasion to play with Squeak again. Asking Gemini, I discovered another interesting variant known as RussCox. There is an excellent publication explaining the algorithm in details:

https://research.swtch.com/fp

And also a proof of exactness https://research.swtch.com/fp-proof
The algorithm is very elegant and simple.
And it can be extended for printing a fixed number of decimal places too, which makes it a good candidate for more general purpose.

The algorithm is simple, but we do not have the fast 64 bits arithmetic used underneath available thru OpenSmalltalk VM.
For not spoiling efficiency, we need to split the integers into limbs and perform the arithmetic by ourself, this is a boring part that we are happy to delegate to a bot, so I tried to sketch an implementation quickly with help of Gemini web chat.
With the code sitting on github, simply giving the link to Gemini is enough for it to create a subclass of ShortFloatPrinter.
What I like in Gemini is its ability to cite sources. Apart from that, the number of errors in the code produced is rather high compared to Claude Sonnet.
It ranges from off-by-one errors in arithmetics - for example the shifts - to incorrect syntax at worse, like spitting condition ifTrue: ifFalse: without arguments.
But that's bearable, mostly errors that humans could as well produce, if I omit the later.

Gemini did propose a version with 28 bits limbs, with 5 limbs for storing each power of ten approximation with enough precision.
With some iterations to make the algorithm work, then my own optimizations, cherry picking Serge's (and probably Claude's) work, I could obtain a decent speed placing RussCox performance somewhere between Schubfach and DragonBox.
Gemini were not able to improve that speed, the answers overall fall apart and worsen the benchmarks.
So once again, I had to use my own brain and think, thanks to AI to let me do that...
Since the proof tells us that 114 bits of precision is enough for the powers of ten, and since we can use 29-bits limbs without fear of SmallInteger maxVal overflow in multiplications, this enables reducing the powers of ten to 4 limbs 4x29=116.
We can then transform the original 64-bit integer right padding of mantissa, to a more Squeakish friendly 58-bit integer right padding.
This way, we only have to handle a 2 limbs x 4 limbs product in the core uscale function, and with appropriate heuristics ignore the least significant limbs completely.
I again asked the AI to assit me on modifying the code, which it did with quite a lot of confusion mixing 58 and 59 bits everywhere. Deviating from a well known algorithm that certainly were fed into the AI learning phase makes the errors a bit more proeminent.
However, interaction by review and questioning makes the AI correct most of its errors, the rest of corrections is obtained by injecting failing examples: I executed those failures in Squeak debugger and checked in parallel the expectations given by the AI chat, and this revealed to be efficient enough.
Anyway, the debugger is a powerfull tool for diving into implementation details, it is too often underused in other languages. An area where 50 years later, Smalltalk still really shines!

With this variant on 58bits arithmetic that I named RussCox58Printer, the printer now beats DragonBox by about 10% in most areas, with the exception of Float with 2 fractional digits which is about 20% slower than DragonBox.
Well, those marginal costs do not really matter, because 80% of time spent now goes into streaming the outputs...
What is more interesting is simplicity and extensibility for printing with fixed precision as written above.
There is still quite some work before we integrate that in trunk, but we certainly will.

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 16511 1059 560 479 413 398 41.5x
uniform [0, 1) 615 943 433 408 345 320 1.9x
integral values 307 485 167 169 168 167 1.8x
two decimals 313 482 393 329 257 279 1.1x
large and tiny 16528 1069 673 464 401 385 42.9x
Shortest decimal only (#decompose:), ns per conversion
dataset Ryu Schubfach Dragonbox RussCox58 vs Ryu vs Schubfach vs Dragonbox
random bit patterns 255 170 106 93 2.7x 1.8x 1.1x
uniform [0, 1) 190 164 99 81 2.3x 2.0x 1.2x
integral values 22 24 23 23 1.0x 1.0x 1.0x
two decimals 248 178 112 138 1.8x 1.3x 0.8x
large and tiny 376 168 106 89 4.2x 1.9x 1.2x

I'm conscious that AI orientation of this blog may upset some members of our community, but I think that it illustrates how the outcomes could have been positive...
At least, the AI retro-contributed a tiny bit to the open source that nurtured it massively, something we might better profit by, before the industry makes the decision to kill the golden goose!
I've put the material on squeaksource for easier squeaking, it is at https://wwww.squeaksource.com/Ryu.html.
I'll try and retro-contribute to the source repository if I find time, but consider this post as a first step of retro-contribution.

Sunday, November 1, 2026

Resurrecting AlgebraicNumber in Squeak

What is an algebraic number? Any complex numbers which is root of a polynomial with integer coefficients $p(x) \in \mathbb{Z}[x]$, or in other words solution of $p(x)=0$
\[ a \in \bar{\mathbb{Q}} \Leftrightarrow \exists p \in \mathbb{Z}[x] \mid p(a)=0 \] Obviously, this set includes the set of relative integers $\mathbb{Z}$ since every integer $n \in \mathbb{Z}$ is solution of $x - n = 0$
Non less obviously, it includes the set of rationals $\mathbb{Q}$ since every fraction $p/q \in \mathbb{Q}$ is solution of $q x - p = 0$
It also includes some irrational numbers like $\sqrt{2}$ which is solution of $x^2 - 2 = 0$
But it also includes some complex numbers like $\imath$ which is solution of $x^2 + 1 = 0$
$\bar{\mathbb{Q}}$ has the structure of a field with + and * operations,
but more than that, it is an algebraic closure, which means that the roots of polynomials in $\bar{\mathbb{Q}}[x]$ are in $\bar{\mathbb{Q}}$
(the roots of polynomials whose coefficients are algebraic numbers are also algebraic numbers)
That make it a very important algebraic structure.

An algebraic number can be easily represented on computers by a polynomial of which it is a root and a region of the complex plane containing this root (and only this root).
For the subset of real algebraic numbers $\mathbb{R} \cap \bar{\mathbb{Q}}$, this region can be reduced as an interval $[a,b]$ of the real axis sufficiently narrow so as to contain a single real root of the polynomial.
We have just defined the AlgebraicNumber introduced in Squeak in MathMorphs by the team of Leandro Caniglia in the late 90s.
As we saw, it should better have been named RealAlgebraicNumber or maybe just AlgebraicReal

The fun with such numbers is that arithmetic operations are exact.
They can be defined by operations on their polynomials (and intervals).
Since I just introduced the polynomials in Squeak, we can revisit this nice piece of code from MathMorph.
We can manipulate numbers like $\sqrt{5}$ exactly, without having to resort to a floating point approximation like 5 sqrt.
Of course, if you are not interested in learning mathematics, not annoyed that 5 sqrt squared is slightly greater than 5, but just needing a fast square root, stick with Float.

The AlgebraicNumber package ugraded for Squeak trunk is available at https://squeaksource.com/STEM.html
It will require Polynomials and its prereq IntegerFactorization and CollectionArithmetic.
I didn't set up a Metacello nor a Monticello configuration yet, maybe I will.

The implementation rely on two essential features:

In details, there is a bit more, Sturm requires squareFree polynomials. Also AlgebraicNumber uses irreducible (minimal) polynomials, and thus factor, otherwise arithmetic operations result in a explosion of degree.

In the tradition of Smalltalk-80, AlgebraicNumber extends Fraction so an AlgebraicNumber whose value is rational is automatically reduced to its Fraction or Integer value.
It thus has to be able to perform mixed arithmetic in a natural way.
Mixed arithmetic with Float will cancel the exactness of operations though and convert results to limited precision.
Like with Fraction, such operations are subject to double rounding: the AlgebraicNumber is first converted asFloat, then operation is performed in floating point.

There are two practical utilities for creating an AlgebraicNumber:

  • taking the nth root of a fraction $\sqrt[n]{\frac{p}{q}}$,
    sqr3 := AlgebraicNumber nthRoot: 2 of: 3.
  • compute $sin(\pi \frac{p}{q})$ and $cos(\pi \frac{p}{q})$,
    sinPiOver3 := AlgebraicNumber sinpi: 1/3.

We can check $sin(\frac{\pi}{3}) = \frac{\sqrt{3}}{2}$,
sqr3 / 2 - sinPiOver3 = 0.
Or perform some more elementary checks:
sqr3 squared = 3.
sqr3 reciprocal = (sqr3 / 3).
(AlgebraicNumber nthRoot: 4 of: 3) = sqr3 sqrt.
Or we could play with the golden ratio:
phi := (AlgebraicNumber nthRoot: 2 of: 5) + 1 / 2.
(phi + 1) = phi squared.
(phi + 1) sqrt = phi.
(phi - 1) = phi reciprocal.
For example check the Binet formulation of fibonacci number $F_n$ :
fib := GeneratorTest new fibonacciSequence.
sqr5 := 2 * phi - 1.
binet := (1 to: 20) collect: [:n | (phi**n) - ((-1/phi)**n) / sqr5].
binet allSatisfy: [:bi | bi = fib next].
Or we could also check one of the Ramanujan expressions involving radicals like \[ \sqrt[3]{\frac{1}{9}}-\sqrt[3]{\frac{2}{9}}+\sqrt[3]{\frac{4}{9}} = \sqrt[3]{\sqrt[3]{2}-1} \] (#(1 -2 4) detectSum: [:i | AlgebraicNumber nthRoot: 3 of: i / 9]) = ((AlgebraicNumber nthRoot: 3 of: 2) - 1 nthRoot: 3).

Since not all algebraic number can be expressed by elementary operations +,-,*,/ and radicals,
the more general solution is to define them by a polynomial and the interval containing the root, like
x := Polynomial variableRank: 1.
nonRadical := AlgebraicNumber rootOfPolynomial: x squared squared - 4 * x - 2 between: 0 and: 2.
Galois fields theory make it possible to predict if such algebraic number can be printed or not with radicals.
And in this case, it is also possible to find such expressions, though generally awfully long.
This simple AlgebraicNumber package is not equipped to find them.
This is why it will just print an approximation in decimal notation, based on the more or less refined interval.
In the case of our nonRadical the approximation is very rough: (~1.00+/-1.0)
No surprise, it is somewhere between 0 and 2 exactly as we asked for...
It is possible to force the refinement of the approximation, like:
nonRadical approximationError: (10** -40).
and get (~1.5185121527849119038408961046906115287201916+/-9.183549615799121e-41)
That's how an AlgebraicNumber is printed now.

Final notice: like polynomials, the code has not been generated by AI, if that really matters.