<story><title>Q (Number Format)</title><url>https://en.wikipedia.org/wiki/Q_(number_format)</url></story><parent_chain><item><author>vlovich123</author><text>Granted I haven’t played in space. Maybe text rendering is more complicated than indoor positioning. But there we simply made sure results were numerically deterministic on a given machine given a known seed. However, we would always run with a random seed to make sure we didn’t over tune to random initial parameters. And we did manage to make the system numerically stable (ie random perturbations still resulted in the expected value +&amp;#x2F;- some error). And yes, the system was highly non linear (lognormal probability calculations, Kalman filters, etc).&lt;p&gt;Do you have specific knowledge that it is actually difficult due to some nuance specific to  layout because you’ve spent time on the problem or is that an institution you have from first principles?</text></item><item><author>creato</author><text>TeX rendering (example from the parent of this thread) is highly non-linear though. Even a negligible difference in some computation can result in changes that cause an entire document to render completely differently. TeX layout is a global optimization problem, with a lot of big step functions in cost. If you want reproducible rendering in something like TeX, you need to use fixed point arithmetic.</text></item><item><author>vlovich123</author><text>The question though is whether you actually need bit identical or if you can just build a numerical model of your accuracy such that the result is +&amp;#x2F;- some bounded error.&lt;p&gt;Or you can just use infinite precision libraries at the cost of CPU.</text></item><item><author>kragen</author><text>Significant differences in FP calculations &lt;i&gt;still&lt;/i&gt; occur between different architectures, and sometimes even when code is compiled with different optimizations &lt;i&gt;on the same platform&lt;/i&gt;.  In particular, Intel Gen doesn&amp;#x27;t support denormalized floats and gradual underflow (and I think other GPUs are similar here); FMA (fused multiply-add) changes the results of most algorithms, though usually only in the least significant bit; and the IEEE standard doesn&amp;#x27;t require that operations beyond the basic ones (+, -, *, &amp;#x2F;, and square root) produce correctly-rounded results because that is deemed to be too difficult.&lt;p&gt;The FMA thing is the thing that made me realize that expecting identical output from FP algorithms is a lost cause.  Knuth&amp;#x27;s choice was the only reasonable choice if you&amp;#x27;re trying to define a deterministic platform that makes your results reproducible on future hardware.  We can expect with great confidence that 50 or 100 years from now, much less 1000 or 5000 years from now, there will be other optimizations like FMA that change the results of our programs, rendering their executions irreproducible.  But TeX will still produce the same page layout when run on the same input files.</text></item><item><author>dhosek</author><text>Last year I wrote some code in Rust to read GF files (the output from Metafont). Knuth was fond of these sorts of fixed-point representations of non-integers in his file formats and all of the binary formats he created around TeX and MF employ Q15.16 fixed-point numbers where integer values are not acceptable. Likewise, internally to TeX and MF, all non-integer calculations are done with Q15,16 fixed-point numbers since at the time that DEK was writing his programs, there was no standardized FP implementation and significant differences in FP calculations could occur between different architectures and he wanted to be able to guarantee identical output on all platforms.</text></item></parent_chain><comment><author>svat</author><text>It may be illustrative to discuss a concrete example from text layout: consider deciding whether to break before or after a certain word on a line.&lt;p&gt;• Suppose the width of each line is L, and the inter-word space is &amp;quot;S plus P minus M&amp;quot; in TeX notation (i.e. default S with stretchability of P and shrinkability of M), and that after N words with total width C, we encounter the next word of width W, which would have to either go on the next line, or be squeezed onto that line.&lt;p&gt;&lt;pre&gt;&lt;code&gt;    .....................|
    This is an example line
&lt;/code&gt;&lt;/pre&gt;
• If we break the line &lt;i&gt;before&lt;/i&gt; that word, we&amp;#x27;d have to stretch the default space of (C + (N-1)S) to L, so a stretch factor of (L - C - (N-1)S)&amp;#x2F;P.&lt;p&gt;• If we break the line &lt;i&gt;after&lt;/i&gt; that word, we&amp;#x27;d have to shrink the default space of (C + W + NS) to L, so a shrink factor of (C + W + NS - L)&amp;#x2F;M.&lt;p&gt;So we&amp;#x27;d pick one choice or the other depending on which of these two fractions is smaller.&lt;p&gt;(This is not exactly TeX&amp;#x27;s algorithm — the above is a greedy&amp;#x2F;local &amp;quot;best-fit&amp;quot; rather than TeX&amp;#x27;s &amp;quot;optimum fit&amp;quot; that considers the paragraph as a whole; see the paper at &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;www.eprg.org&amp;#x2F;G53DOC&amp;#x2F;pdfs&amp;#x2F;knuth-plass-breaking.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;www.eprg.org&amp;#x2F;G53DOC&amp;#x2F;pdfs&amp;#x2F;knuth-plass-breaking.pdf&lt;/a&gt; — but it&amp;#x27;s hopefully illustrative.)&lt;p&gt;Even in this simple case that just needs to compare two ratios (in practice we have to at least compare two sums of such fractions), if you compute these two fractions as real numbers, and you don&amp;#x27;t have any consistent floating-point arithmetic available across different machines and compilers (or across time), how would you ensure that the system would be deterministic &amp;#x2F; numerically stable as you said? (Would always make the same decision between the two choices?)&lt;p&gt;(And would that method have worked in 1980? The initial version of TeX, now called TeX78, was written in 1977–1978 in the SAIL language and only had to run on one computer&amp;#x2F;compiler (the ones at SAIL in Stanford), and it did use the &amp;quot;real&amp;quot; type. By 1980, already (programs based on) TeX had proliferated to various places—people were porting&amp;#x2F;rewriting TeX into their own OS&amp;#x2F;languages—and Knuth started the rewrite of TeX into the current TeX82 in WEB (based on Pascal), and that time both hardware and Pascal compilers varied widely in their support for and implementation of floating-point arithmetic, so Knuth pretty much &lt;i&gt;had&lt;/i&gt; to use fixed-point (i.e. only integer arithmetic staying within 2^31) to ensure that the same output would be produced everywhere. But I&amp;#x27;m curious how we could get numerical stability in the sense you mentioned even today, as the problem seems to inherently have the property that small perturbations can lead to different output.)</text></comment>
<story><title>Q (Number Format)</title><url>https://en.wikipedia.org/wiki/Q_(number_format)</url></story><parent_chain><item><author>vlovich123</author><text>Granted I haven’t played in space. Maybe text rendering is more complicated than indoor positioning. But there we simply made sure results were numerically deterministic on a given machine given a known seed. However, we would always run with a random seed to make sure we didn’t over tune to random initial parameters. And we did manage to make the system numerically stable (ie random perturbations still resulted in the expected value +&amp;#x2F;- some error). And yes, the system was highly non linear (lognormal probability calculations, Kalman filters, etc).&lt;p&gt;Do you have specific knowledge that it is actually difficult due to some nuance specific to  layout because you’ve spent time on the problem or is that an institution you have from first principles?</text></item><item><author>creato</author><text>TeX rendering (example from the parent of this thread) is highly non-linear though. Even a negligible difference in some computation can result in changes that cause an entire document to render completely differently. TeX layout is a global optimization problem, with a lot of big step functions in cost. If you want reproducible rendering in something like TeX, you need to use fixed point arithmetic.</text></item><item><author>vlovich123</author><text>The question though is whether you actually need bit identical or if you can just build a numerical model of your accuracy such that the result is +&amp;#x2F;- some bounded error.&lt;p&gt;Or you can just use infinite precision libraries at the cost of CPU.</text></item><item><author>kragen</author><text>Significant differences in FP calculations &lt;i&gt;still&lt;/i&gt; occur between different architectures, and sometimes even when code is compiled with different optimizations &lt;i&gt;on the same platform&lt;/i&gt;.  In particular, Intel Gen doesn&amp;#x27;t support denormalized floats and gradual underflow (and I think other GPUs are similar here); FMA (fused multiply-add) changes the results of most algorithms, though usually only in the least significant bit; and the IEEE standard doesn&amp;#x27;t require that operations beyond the basic ones (+, -, *, &amp;#x2F;, and square root) produce correctly-rounded results because that is deemed to be too difficult.&lt;p&gt;The FMA thing is the thing that made me realize that expecting identical output from FP algorithms is a lost cause.  Knuth&amp;#x27;s choice was the only reasonable choice if you&amp;#x27;re trying to define a deterministic platform that makes your results reproducible on future hardware.  We can expect with great confidence that 50 or 100 years from now, much less 1000 or 5000 years from now, there will be other optimizations like FMA that change the results of our programs, rendering their executions irreproducible.  But TeX will still produce the same page layout when run on the same input files.</text></item><item><author>dhosek</author><text>Last year I wrote some code in Rust to read GF files (the output from Metafont). Knuth was fond of these sorts of fixed-point representations of non-integers in his file formats and all of the binary formats he created around TeX and MF employ Q15.16 fixed-point numbers where integer values are not acceptable. Likewise, internally to TeX and MF, all non-integer calculations are done with Q15,16 fixed-point numbers since at the time that DEK was writing his programs, there was no standardized FP implementation and significant differences in FP calculations could occur between different architectures and he wanted to be able to guarantee identical output on all platforms.</text></item></parent_chain><comment><author>mkbosmans</author><text>Reasoning from first principles:&lt;p&gt;When a problem is linear, a small pertubation in your input will result in a similarly small difference in the results, bounded by some constant factor. When a problem is non-linear, there is no such constant upper bound to the output error.&lt;p&gt;There are differences in the amount of nonlinearity however. It seems that your algorithm was nonlinear, e.g. using log and exp functions, but otherwise pretty well behaved. So while the factor between input and output error might not be constant, but rather dependent on input values, it is still the case that in the limit of the input error to zero, the output error will also vanish. (obviously in the real domain, not considering floating point).&lt;p&gt;Contrast this with a problem that has discontinuities in it. In that case it might happen that however small you make your input error, any nonzero pertubation will cause a significant change in the solution. The TeX layout problem is an example of this, but also happens often enough in physical simulations.</text></comment>