4 ms·

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

by creato 4y ago

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.

vlovich123 4y ago
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 +/- some error). And yes, the system was highly non linear (lognormal probability calculations, Kalman filters, etc). 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?
- samatman 4y ago
  The first release of TeX was in 1978. Dr. Knuth could have plausibly gotten results similar to yours by writing a 'classic' floating point algorithm: but IEEE 734 [sic: 754] wasn't even published until 1985, so relying on hardware, let alone stable results from hardware, was completely impossible. This would also have been very, very, very. Very slow. Adding a constant factor of 20-50X to TeX wouldn't have been fun at all. TeX is also a famous program, the algorithms involved are well-known to anyone with an interest. The statement that it uses an expensive global strategy for layout is accurate.
  - wruza 4y ago
    (For those also curious: I tried to look up IEEE 734 thinking it was a previous standard, but it seems there is none and the parent commenter meant IEEE 754-1985.)
    - samatman 4y ago
      Thank you, that was a typo, I've made a note in the original.
- mkbosmans 4y ago
  Reasoning from first principles: 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. 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). 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.
- Someone 4y ago
  It’s not necessarily more complicated, but it has a strict reproducibility requirement. If I render TeX today, it has to end up 100% identical to what you get when you render it on your machine tomorrow, or what I get ten years from now. If a single tiny rounding difference makes a letter even a millionth of its width wider, that may mean line breaks move to different locations, that the number of lines in the text changes, or even that the number of pages in the text changes.
- svat 4y ago
  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. • Suppose the width of each line is L, and the inter-word space is "S plus P minus M" 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. .....................| This is an example line • If we break the line before that word, we'd have to stretch the default space of (C + (N-1)S) to L, so a stretch factor of (L - C - (N-1)S)/P. • If we break the line after that word, we'd have to shrink the default space of (C + W + NS) to L, so a shrink factor of (C + W + NS - L)/M. So we'd pick one choice or the other depending on which of these two fractions is smaller. (This is not exactly TeX's algorithm — the above is a greedy/local "best-fit" rather than TeX's "optimum fit" that considers the paragraph as a whole; see the paper at http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf — but it's hopefully illustrative.) 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'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 / numerically stable as you said? (Would always make the same decision between the two choices?) (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/compiler (the ones at SAIL in Stanford), and it did use the "real" type. By 1980, already (programs based on) TeX had proliferated to various places—people were porting/rewriting TeX into their own OS/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 had 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'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.)
- kragen 4y ago
  Knuth has explained that he rewrote TeX with fixed point to get reproducibility; this is not a speculation from first principles, but a hard-won battle scar. But it's not specific to text layout either; almost any chaotic system has the same reproducibility problem if you rerun the same program with the same inputs (including seeds) on new hardware, or, often, even with a new version of the compiler or different compilation options. Of course the whole point of things like Kalman filters is that they are insensitive to small quantitative errors, and as you say you worked hard to ensure your programs as a whole were also insensitive; experience with things like that can lead your intuition astray.

by creato 4y ago

vlovich123 4y ago

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 +/- some error). And yes, the system was highly non linear (lognormal probability calculations, Kalman filters, etc). 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?

samatman 4y ago
The first release of TeX was in 1978. Dr. Knuth could have plausibly gotten results similar to yours by writing a 'classic' floating point algorithm: but IEEE 734 [sic: 754] wasn't even published until 1985, so relying on hardware, let alone stable results from hardware, was completely impossible. This would also have been very, very, very. Very slow. Adding a constant factor of 20-50X to TeX wouldn't have been fun at all. TeX is also a famous program, the algorithms involved are well-known to anyone with an interest. The statement that it uses an expensive global strategy for layout is accurate.
- wruza 4y ago
  (For those also curious: I tried to look up IEEE 734 thinking it was a previous standard, but it seems there is none and the parent commenter meant IEEE 754-1985.)
  - samatman 4y ago
    Thank you, that was a typo, I've made a note in the original.
mkbosmans 4y ago
Reasoning from first principles: 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. 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). 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.
Someone 4y ago
It’s not necessarily more complicated, but it has a strict reproducibility requirement. If I render TeX today, it has to end up 100% identical to what you get when you render it on your machine tomorrow, or what I get ten years from now. If a single tiny rounding difference makes a letter even a millionth of its width wider, that may mean line breaks move to different locations, that the number of lines in the text changes, or even that the number of pages in the text changes.
svat 4y ago
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. • Suppose the width of each line is L, and the inter-word space is "S plus P minus M" 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. .....................| This is an example line • If we break the line before that word, we'd have to stretch the default space of (C + (N-1)S) to L, so a stretch factor of (L - C - (N-1)S)/P. • If we break the line after that word, we'd have to shrink the default space of (C + W + NS) to L, so a shrink factor of (C + W + NS - L)/M. So we'd pick one choice or the other depending on which of these two fractions is smaller. (This is not exactly TeX's algorithm — the above is a greedy/local "best-fit" rather than TeX's "optimum fit" that considers the paragraph as a whole; see the paper at http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf — but it's hopefully illustrative.) 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'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 / numerically stable as you said? (Would always make the same decision between the two choices?) (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/compiler (the ones at SAIL in Stanford), and it did use the "real" type. By 1980, already (programs based on) TeX had proliferated to various places—people were porting/rewriting TeX into their own OS/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 had 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'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.)
kragen 4y ago
Knuth has explained that he rewrote TeX with fixed point to get reproducibility; this is not a speculation from first principles, but a hard-won battle scar. But it's not specific to text layout either; almost any chaotic system has the same reproducibility problem if you rerun the same program with the same inputs (including seeds) on new hardware, or, often, even with a new version of the compiler or different compilation options. Of course the whole point of things like Kalman filters is that they are insensitive to small quantitative errors, and as you say you worked hard to ensure your programs as a whole were also insensitive; experience with things like that can lead your intuition astray.