4 ms·

How do you correctly round, say, 6172293634027511 * 7059478094414279 / 2^53 = 4837593847918366.50000000000000011102 without essentially computing the full 106-b

by stromgo 12y ago

How do you correctly round, say, 6172293634027511 * 7059478094414279 / 2^53 = 4837593847918366.50000000000000011102 without essentially computing the full 106-bit product?

dragontamer 12y ago
IEEE Floating point rounds numbers in binary, not in decimal. So it is trivial by simply having a 54-bit register to hold the 53-bit mantissa. So the answer to your question is... Floating Point numbers "don't round correctly". They're actually quite complicated, and require careful study.
- stromgo 12y ago
  My example has nothing to do with decimal rounding. It's an example of a product (6172293634027511 * 7059478094414279) whose result is extremely close to the fence between two representable numbers (4837593847918366.5 * 2^53). If the 106-bit product happened to be 2 units smaller, then the rounded result would change.
  - dragontamer 12y ago
    As stated before, Floating Point numbers "don't round correctly" according to IEEE Floating Point arithmetic. There are very simple rules on how to round. This makes calculation of errors a bit complicated. http://en.wikipedia.org/wiki/IEEE_floating_point#Rounding_rules http://en.wikipedia.org/wiki/IEEE_floating_point#Rounding_ru... At best, Intel at one point provided 80-bit rounding (ie: 68-bit mantissa). That is, if you use the x87 floating-point coprocessor. But these technically do not match IEEE specifications for rounding.
    - fdej 12y ago
      Er, what? Floating point numbers do "round correctly" (in binary) -- that's pretty much the whole point of the IEEE standard. In particular, to compute a product of two 53-bit floating-point numbers with correct rounding (as the standard mandates), it is certainly not sufficient in general to compute just a 54-bit approximation and round that.
      - deleted 12y ago
        [deleted]
nwhitehead 12y ago
The idea is that you can use guard digits instead of full products and get correct rounding (as if to infinite precision). For IEEE-754 math you need 3 guard digits, typically named Guard, Round, and Sticky. The trick at the hardware level is that Sticky represents the OR of a bunch of bits. Instead of keeping the full 106 bit partial product at each step you only need to keep the 53+3 bit product. As you shift+add the partial products you use special rules to keep track of the Sticky bit and you will still get the right answer.
- fdej 12y ago
  I'm aware of the 53+3 bit algorithm for addition and subtraction, but I don't see how this could possibly work for multiplication. Could you please point me to a paper that explains how to compute a correctly rounded 53-bit product without computing the full 106-bit product?
  - pascal_cuoq 12y ago
    I can't find a handy reference, but here is a 5x5 multiplication: 1XXXX * 1XXXX _________ XXXXX XXXXX XXXXX XXXXX 1XXXX Using a sticky bit means computing the logical-or of all the bits that are sufficiently far to the right in all these partial results, instead of computing them individually and summing them. Like for addition, the idea is that the result you obtain is different from the exact result, but rounds the same. The sticky bit only serves to round (midpoint + a small quantity) correctly up.
    - stromgo 12y ago
      Let's say that the full product in your example is 1XXXXYZZZZ To round it we need: (1) the X bits for our answer (2) the Y bit for rounding (3) the logical-or of the Z bits for rounding Ok so there might be a trick to compute (3) without computing ZZZZ, but we still want to know how to compute 1XXXXY without computing ZZZZ.
      - pascal_cuoq 12y ago
pascal_cuoq 12y ago
I see what you mean now. I agree that each of the low-order bits of the 106-bit product is available at some point. Not necessarily simultaneously, but yes, it seems like little additional effort for processor designers to keep these somewhere and assemble them in another register or something. For some reason (maximum depth reached?) there is no “reply” link at the bottom of the post of yours at which I understood, so I am replying here.

by stromgo 12y ago

How do you correctly round, say, 6172293634027511 * 7059478094414279 / 2^53 = 4837593847918366.50000000000000011102 without essentially computing the full 106-bit product?

dragontamer 12y ago

IEEE Floating point rounds numbers in binary, not in decimal. So it is trivial by simply having a 54-bit register to hold the 53-bit mantissa. So the answer to your question is... Floating Point numbers "don't round correctly". They're actually quite complicated, and require careful study.

stromgo 12y ago
My example has nothing to do with decimal rounding. It's an example of a product (6172293634027511 * 7059478094414279) whose result is extremely close to the fence between two representable numbers (4837593847918366.5 * 2^53). If the 106-bit product happened to be 2 units smaller, then the rounded result would change.
- dragontamer 12y ago
  As stated before, Floating Point numbers "don't round correctly" according to IEEE Floating Point arithmetic. There are very simple rules on how to round. This makes calculation of errors a bit complicated. http://en.wikipedia.org/wiki/IEEE_floating_point#Rounding_rules http://en.wikipedia.org/wiki/IEEE_floating_point#Rounding_ru... At best, Intel at one point provided 80-bit rounding (ie: 68-bit mantissa). That is, if you use the x87 floating-point coprocessor. But these technically do not match IEEE specifications for rounding.
  - fdej 12y ago
    Er, what? Floating point numbers do "round correctly" (in binary) -- that's pretty much the whole point of the IEEE standard. In particular, to compute a product of two 53-bit floating-point numbers with correct rounding (as the standard mandates), it is certainly not sufficient in general to compute just a 54-bit approximation and round that.
    - deleted 12y ago
      [deleted]

nwhitehead 12y ago

The idea is that you can use guard digits instead of full products and get correct rounding (as if to infinite precision). For IEEE-754 math you need 3 guard digits, typically named Guard, Round, and Sticky. The trick at the hardware level is that Sticky represents the OR of a bunch of bits. Instead of keeping the full 106 bit partial product at each step you only need to keep the 53+3 bit product. As you shift+add the partial products you use special rules to keep track of the Sticky bit and you will still get the right answer.

fdej 12y ago
I'm aware of the 53+3 bit algorithm for addition and subtraction, but I don't see how this could possibly work for multiplication. Could you please point me to a paper that explains how to compute a correctly rounded 53-bit product without computing the full 106-bit product?
- pascal_cuoq 12y ago
  I can't find a handy reference, but here is a 5x5 multiplication: 1XXXX * 1XXXX _________ XXXXX XXXXX XXXXX XXXXX 1XXXX Using a sticky bit means computing the logical-or of all the bits that are sufficiently far to the right in all these partial results, instead of computing them individually and summing them. Like for addition, the idea is that the result you obtain is different from the exact result, but rounds the same. The sticky bit only serves to round (midpoint + a small quantity) correctly up.
  - stromgo 12y ago
    Let's say that the full product in your example is 1XXXXYZZZZ To round it we need: (1) the X bits for our answer (2) the Y bit for rounding (3) the logical-or of the Z bits for rounding Ok so there might be a trick to compute (3) without computing ZZZZ, but we still want to know how to compute 1XXXXY without computing ZZZZ.
    - pascal_cuoq 12y ago

pascal_cuoq 12y ago

I see what you mean now. I agree that each of the low-order bits of the 106-bit product is available at some point. Not necessarily simultaneously, but yes, it seems like little additional effort for processor designers to keep these somewhere and assemble them in another register or something. For some reason (maximum depth reached?) there is no “reply” link at the bottom of the post of yours at which I understood, so I am replying here.