12 ms·

Q (Number Format)

106 points by brudgers 4y ago

dhosek 4y ago
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.
- kragen 4y ago
  Significant differences in FP calculations still occur between different architectures, and sometimes even when code is compiled with different optimizations on the same platform. In particular, Intel Gen doesn'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't require that operations beyond the basic ones (+, -, *, /, and square root) produce correctly-rounded results because that is deemed to be too difficult. The FMA thing is the thing that made me realize that expecting identical output from FP algorithms is a lost cause. Knuth's choice was the only reasonable choice if you'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.
  - vlovich123 4y ago
    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 +/- some bounded error. Or you can just use infinite precision libraries at the cost of CPU.
    - 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.)
  - adgjlsfhk1 4y ago
    Note that not all languages semantically allow combining a+b*c into fma. This isn't a floating point problem, but a language problem.
    - tsimionescu 4y ago
      If you're doing long FP calculations, you can allow FMA, or have poor results. Sure, some languages think it's worth it for the determinism, but rounding after every operation can completely destroy your precision. Even more so for something like x87, where internal registers are higher precision, not that too many people use it anymore.
      - adgjlsfhk1 4y ago
        There's a 3rd option. Allow fma, but only where the programmer explicitly puts an `fma` (or specifically allows reordering). This does sacrifice a little bit of ease of use to get optimal performance, but allows for reproducibility and high performance. It is a shame x87 was so poorly thought out. If it had a better defined programming model, it would be incredibly useful.
  - mochomocha 4y ago
    Subnormals in particular I think are a pretty big failure of the IEEE standard, in the sense that because their implementation is very slow & varies across architectures, the only time most people learn about them is when they're hitting FP perf issues & want to disable their support.
    - adgjlsfhk1 4y ago
      yeah. the ieee standard was way better than not having it, but I think that for a lot of cases, posits are much better thought out now. hopefully they'll start to gain broader hardware support.
      - Aardwolf 4y ago
        What makes posits so good for hardware? Does the fact that they have variable sized exponent not cause similar difficulty as the subnormals in floats?
        adgjlsfhk1 4y ago
        The main difference of posits (the variable sized exponent) is slightly worse for hardware (but not much). Posits, however win back a lot of points because they remove a lot of special cases. FP hardware generally needs special checks for NaNs, Infs, -0 and subnormals. Posits only have 2 "special" numbers 0 and NaR. The problem with subnormal floats isn't that they are inherently slow, it's that they are different and rare which means they aren't well optimized for. With Posits, everything is the same, which reduces the number of branches in hardware.
      - adrian_b 4y ago
        Posits have advantages for low-precision numbers, e.g. up to 32 bits. For high-precision numbers, e.g. for 64 bits, the standard double-precision floating-point numbers are the best. Any number format using a given number of bits has the same number of values that can be represented. The only difference between various formats, e.g. integers, fixed-point numbers, floating-point numbers or posits, is how the same number of points is distributed over the line of the real numbers, being more dense in some parts and more rare in other parts. For scientific computation, the optimal distribution of the representable numbers is when the relative error is constant. The ideal number format would be logarithmic, but it is too difficult to add and subtract logarithmic numbers, so the second best format is used, i.e. floating-point numbers, which allow fast implementations for all important arithmetic operations. Posits have a non-uniform relative error, low close too 1 and high for large and small numbers, so they are unsuitable for complex physics modelling, which needs more computations with large numbers and small numbers than with numbers close to 1. On the other hand, for the applications where low-precision numbers are suitable, e.g. machine learning, graphics or some kinds of DSP, posits could be better than floating-point numbers.
  - TazeTSchnitzel 4y ago
    > Intel Gen doesn't support denormalized floats and gradual underflow (and I think other GPUs are similar here) It differs from vendor to vendor. I know at least one major GPU vendor that has full denormal support, at least for normal arithmetic (not sure about transcendentals etc). In Vulkan, it's possible to ask the GPU to either always flush denormals to zero, or (if the HW supports it) to never do so, but I think nobody uses this, and there may be a (huge) performance penalty from requesting either of these!
- tantalor 4y ago
  > where integer values are not acceptable Er why not
  - vlovich123 4y ago
    Are you asking why there’s floating point in general? Or why Tex needed floating point to represent layout? For the latter likely because you have to do layout. You could try defining a fundamental page unit but some layout decisions will likely still put you into fractional space where you need to preserve the fractions to get a correct result.
    - tantalor 4y ago
      Ah I misunderstood. Thought it was "integers not allowed" which would be strange. Actually it is "integers not sufficient"
    - proto_lambda 4y ago
      Qm.n notation is for fixed point numbers, not floating point. As OP said, floating point was not a viable option at the time.
    - zelphirkalt 4y ago
      So why not work with fractions instead? Then be problem becomes to store big or arbitrary sized integers.
      - projektfu 4y ago
        They are effectively fractions. Everything is represented to the nearest 1/65536. This is equivalent to arbitrary fractions with 16-bit numerators and denominators.
        zelphirkalt 4y ago
        I think my question is rather, "Why not use a representation as a fraction?" then. Technically every number inside a computer, which is not merely symbols interpreted outside of the computer, is a fraction, because of limited precision of finite memory. I guess it is all about the representation then. So the question becomes one of why one representation is better and why not use a fraction representation of 2 integers instead.
stefanpie 4y ago
Fixed point is a super fun rabbit hole into quantization and numerical representations. I work with them all the time for FPGA hardware design and HLS to build deep learning models and HLS is our bread and butter.
infogulch 4y ago
I recently discovered 'posits' which are clearly the best number format for representing rationals (don't say 'real', we can exactly represent approximately 0% of the reals).
- zelphirkalt 4y ago
  So what makes posits so great?
  - infogulch 4y ago
    No infinities, it saturates instead. Only one bit pattern for 'NaR'. Only one bit pattern for 0. No subnormals. No overflow or underflow. Highest resolution around 0. Natural graceful degredation in resolution for larger numbers. A much higher percentage of hitting an exactly representable result over all operations. Equality and ordinal comparison is the same as for integers. Much simpler addition and multiplication. -1/x is just twos complement. Perfect reciprocals of powers of 2. 1 clock sigmoid function. A very clean conceptual design. https://youtu.be/JJgT-YphE1Y https://youtu.be/JJgT-YphE1Y
    - wruza 4y ago
      Also prohibits nan-boxing, afaiu, which may be a big loss for dynamic languages.
      - nerdponx 4y ago
        What does NaN-boxing mean in this context?
        wruza 4y ago
        https://softwareengineering.stackexchange.com/a/185431 https://softwareengineering.stackexchange.com/a/185431 Basically it is a way to push primitive values of any type and pointers into a 64-bit double, to reduce memory/cache footprint in dynamic languages.
xolve 4y ago
Learned about these from Rust In Action book. Seems like programmers keep rediscovering stuff now and then.
astrobe_ 4y ago
It seems to be a complicated way to explain that, if you need decimal values, you can just multiply then by a power of two internally. e.g. if you just need a resolution of 1/256 (a case that comes to mind are measures coming from a analog-to-digital converter), you just multiply everything by 256 and do your arithmetic as usual. Or actually you don't have to do anything except remember to scale your constants the same way and do the conversion for I/Os where needed. Might be wise to protect those values with a dedicated type to prevent mistakes. The "saturation" thing in the article is a joke; no way you can get correct results at the end if you cap the result of computations on overflow. That's slightly better than letting the overflow happen, but the right thing to do is to throw an error, not silently min/max the result.
- adhesive_wombat 4y ago
  Saturation is a real thing: lots of DSPs use Q-format fixed-point integer maths with saturation. It's not designed to not have errors, it's a way to detect overflows without floating point capability. You can't always just throw an error in some hard real time systems (though you obviously need to take care of saturated results "carefully", which depends on what you're up to).
fsckboy 4y ago
imho it's unmoored to think of two's complement as having a sign bit. Two's complement was invented to escape from the sign bit and it works by adding/subtracting the bits as if there is no sign (careful defending the sign bit unless you believe zero to be a positive number)
- layer8 4y ago
  The sign bit in two’s complement is still called the sign bit.
  - fsckboy 4y ago
    not in the sense where you would always keep in mind "there is one bit of sign and 7 bits of value", and not in the sense that you "can run the sign bit through an ALU adder as data, don't worry, it'll work". It's just a confusing way to think about it. one place where "the sign bit interpretation" shows up, is still not a slam dunk for sign bits. Using C as the example, when casting a signed char to a signed word, you do have to take the "sign bit" and extend it: but you don't just move it to the new sign bit, you extended it through all those other "data/value" bits.
    - layer8 4y ago
      The representation sure works differently from one’s complement, but it is still called the sign bit, because the number is negative if and only if that bit is set.
      - fsckboy 4y ago
        yes, but my original comment did say don't "think" of it as a sign bit rather than don't call it that. and one's complement is a complement, but two's complement isn't really. It does turn out that if you take the complement and add one you get the right value, but a better way to think of it (on byte scale e.g.) is "take a modulo-256 dial, now change the labeling counter clockwise from the top to negative numbers because you note that 255+1 is 0 just like -1+1 is 0". I just think this explanation serves beginning C or ASM programmers better because it's more mentally agile. I learned it what I would call "the dumb way", but since I was amazed that it worked I studied it to convince myself it was true and then I realized what was actually going on.

106 points by brudgers 4y ago

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.

kragen 4y ago
Significant differences in FP calculations still occur between different architectures, and sometimes even when code is compiled with different optimizations on the same platform. In particular, Intel Gen doesn'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't require that operations beyond the basic ones (+, -, *, /, and square root) produce correctly-rounded results because that is deemed to be too difficult. The FMA thing is the thing that made me realize that expecting identical output from FP algorithms is a lost cause. Knuth's choice was the only reasonable choice if you'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.
- vlovich123 4y ago
  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 +/- some bounded error. Or you can just use infinite precision libraries at the cost of CPU.
  - 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.)
- adgjlsfhk1 4y ago
  Note that not all languages semantically allow combining a+b*c into fma. This isn't a floating point problem, but a language problem.
  - tsimionescu 4y ago
    If you're doing long FP calculations, you can allow FMA, or have poor results. Sure, some languages think it's worth it for the determinism, but rounding after every operation can completely destroy your precision. Even more so for something like x87, where internal registers are higher precision, not that too many people use it anymore.
    - adgjlsfhk1 4y ago
      There's a 3rd option. Allow fma, but only where the programmer explicitly puts an `fma` (or specifically allows reordering). This does sacrifice a little bit of ease of use to get optimal performance, but allows for reproducibility and high performance. It is a shame x87 was so poorly thought out. If it had a better defined programming model, it would be incredibly useful.
- mochomocha 4y ago
  Subnormals in particular I think are a pretty big failure of the IEEE standard, in the sense that because their implementation is very slow & varies across architectures, the only time most people learn about them is when they're hitting FP perf issues & want to disable their support.
  - adgjlsfhk1 4y ago
    yeah. the ieee standard was way better than not having it, but I think that for a lot of cases, posits are much better thought out now. hopefully they'll start to gain broader hardware support.
    - Aardwolf 4y ago
      What makes posits so good for hardware? Does the fact that they have variable sized exponent not cause similar difficulty as the subnormals in floats?
      - adgjlsfhk1 4y ago
        The main difference of posits (the variable sized exponent) is slightly worse for hardware (but not much). Posits, however win back a lot of points because they remove a lot of special cases. FP hardware generally needs special checks for NaNs, Infs, -0 and subnormals. Posits only have 2 "special" numbers 0 and NaR. The problem with subnormal floats isn't that they are inherently slow, it's that they are different and rare which means they aren't well optimized for. With Posits, everything is the same, which reduces the number of branches in hardware.
    - adrian_b 4y ago
      Posits have advantages for low-precision numbers, e.g. up to 32 bits. For high-precision numbers, e.g. for 64 bits, the standard double-precision floating-point numbers are the best. Any number format using a given number of bits has the same number of values that can be represented. The only difference between various formats, e.g. integers, fixed-point numbers, floating-point numbers or posits, is how the same number of points is distributed over the line of the real numbers, being more dense in some parts and more rare in other parts. For scientific computation, the optimal distribution of the representable numbers is when the relative error is constant. The ideal number format would be logarithmic, but it is too difficult to add and subtract logarithmic numbers, so the second best format is used, i.e. floating-point numbers, which allow fast implementations for all important arithmetic operations. Posits have a non-uniform relative error, low close too 1 and high for large and small numbers, so they are unsuitable for complex physics modelling, which needs more computations with large numbers and small numbers than with numbers close to 1. On the other hand, for the applications where low-precision numbers are suitable, e.g. machine learning, graphics or some kinds of DSP, posits could be better than floating-point numbers.
- TazeTSchnitzel 4y ago
  > Intel Gen doesn't support denormalized floats and gradual underflow (and I think other GPUs are similar here) It differs from vendor to vendor. I know at least one major GPU vendor that has full denormal support, at least for normal arithmetic (not sure about transcendentals etc). In Vulkan, it's possible to ask the GPU to either always flush denormals to zero, or (if the HW supports it) to never do so, but I think nobody uses this, and there may be a (huge) performance penalty from requesting either of these!
tantalor 4y ago
> where integer values are not acceptable Er why not
- vlovich123 4y ago
  Are you asking why there’s floating point in general? Or why Tex needed floating point to represent layout? For the latter likely because you have to do layout. You could try defining a fundamental page unit but some layout decisions will likely still put you into fractional space where you need to preserve the fractions to get a correct result.
  - tantalor 4y ago
    Ah I misunderstood. Thought it was "integers not allowed" which would be strange. Actually it is "integers not sufficient"
  - proto_lambda 4y ago
    Qm.n notation is for fixed point numbers, not floating point. As OP said, floating point was not a viable option at the time.
  - zelphirkalt 4y ago
    So why not work with fractions instead? Then be problem becomes to store big or arbitrary sized integers.
    - projektfu 4y ago
      They are effectively fractions. Everything is represented to the nearest 1/65536. This is equivalent to arbitrary fractions with 16-bit numerators and denominators.
      - zelphirkalt 4y ago
        I think my question is rather, "Why not use a representation as a fraction?" then. Technically every number inside a computer, which is not merely symbols interpreted outside of the computer, is a fraction, because of limited precision of finite memory. I guess it is all about the representation then. So the question becomes one of why one representation is better and why not use a fraction representation of 2 integers instead.

stefanpie 4y ago

Fixed point is a super fun rabbit hole into quantization and numerical representations. I work with them all the time for FPGA hardware design and HLS to build deep learning models and HLS is our bread and butter.

infogulch 4y ago

I recently discovered 'posits' which are clearly the best number format for representing rationals (don't say 'real', we can exactly represent approximately 0% of the reals).

zelphirkalt 4y ago
So what makes posits so great?
- infogulch 4y ago
  No infinities, it saturates instead. Only one bit pattern for 'NaR'. Only one bit pattern for 0. No subnormals. No overflow or underflow. Highest resolution around 0. Natural graceful degredation in resolution for larger numbers. A much higher percentage of hitting an exactly representable result over all operations. Equality and ordinal comparison is the same as for integers. Much simpler addition and multiplication. -1/x is just twos complement. Perfect reciprocals of powers of 2. 1 clock sigmoid function. A very clean conceptual design. https://youtu.be/JJgT-YphE1Y https://youtu.be/JJgT-YphE1Y
  - wruza 4y ago
    Also prohibits nan-boxing, afaiu, which may be a big loss for dynamic languages.
    - nerdponx 4y ago
      What does NaN-boxing mean in this context?
      - wruza 4y ago
        https://softwareengineering.stackexchange.com/a/185431 https://softwareengineering.stackexchange.com/a/185431 Basically it is a way to push primitive values of any type and pointers into a 64-bit double, to reduce memory/cache footprint in dynamic languages.

xolve 4y ago

Learned about these from Rust In Action book. Seems like programmers keep rediscovering stuff now and then.

astrobe_ 4y ago

It seems to be a complicated way to explain that, if you need decimal values, you can just multiply then by a power of two internally. e.g. if you just need a resolution of 1/256 (a case that comes to mind are measures coming from a analog-to-digital converter), you just multiply everything by 256 and do your arithmetic as usual. Or actually you don't have to do anything except remember to scale your constants the same way and do the conversion for I/Os where needed. Might be wise to protect those values with a dedicated type to prevent mistakes. The "saturation" thing in the article is a joke; no way you can get correct results at the end if you cap the result of computations on overflow. That's slightly better than letting the overflow happen, but the right thing to do is to throw an error, not silently min/max the result.

adhesive_wombat 4y ago
Saturation is a real thing: lots of DSPs use Q-format fixed-point integer maths with saturation. It's not designed to not have errors, it's a way to detect overflows without floating point capability. You can't always just throw an error in some hard real time systems (though you obviously need to take care of saturated results "carefully", which depends on what you're up to).

fsckboy 4y ago

imho it's unmoored to think of two's complement as having a sign bit. Two's complement was invented to escape from the sign bit and it works by adding/subtracting the bits as if there is no sign (careful defending the sign bit unless you believe zero to be a positive number)

layer8 4y ago
The sign bit in two’s complement is still called the sign bit.
- fsckboy 4y ago
  not in the sense where you would always keep in mind "there is one bit of sign and 7 bits of value", and not in the sense that you "can run the sign bit through an ALU adder as data, don't worry, it'll work". It's just a confusing way to think about it. one place where "the sign bit interpretation" shows up, is still not a slam dunk for sign bits. Using C as the example, when casting a signed char to a signed word, you do have to take the "sign bit" and extend it: but you don't just move it to the new sign bit, you extended it through all those other "data/value" bits.
  - layer8 4y ago
    The representation sure works differently from one’s complement, but it is still called the sign bit, because the number is negative if and only if that bit is set.
    - fsckboy 4y ago
      yes, but my original comment did say don't "think" of it as a sign bit rather than don't call it that. and one's complement is a complement, but two's complement isn't really. It does turn out that if you take the complement and add one you get the right value, but a better way to think of it (on byte scale e.g.) is "take a modulo-256 dial, now change the labeling counter clockwise from the top to negative numbers because you note that 255+1 is 0 just like -1+1 is 0". I just think this explanation serves beginning C or ASM programmers better because it's more mentally agile. I learned it what I would call "the dumb way", but since I was amazed that it worked I studied it to convince myself it was true and then I realized what was actually going on.