5 ms·

> What's crazy about this is that we're limited to multiplying integers > of about 25 bits [...] > Why? Because the multiplier insists on rounding > its low

> What's crazy about this is that we're limited to multiplying integers > of about 25 bits [...] > Why? Because the multiplier insists on rounding > its low output bits rather than giving them back to the programmer. > Why? Because the multiplier is buried inside the floating-point unit. The reference to the 25-bit success makes it seem like the author is thinking of bits 53-105 of the 106-bit result of multiplying two 53-bit inputs. The multiplier is not going to “give them back” to the programmer because it never computed them in the first place. Floating-point 53x53->53 multiplication is implemented with a couple of guard bits, the last of which is “sticky”. The multiplier the author is asking for is not “buried”, it does not exist in the processor. I am not sure why integer multiplication is not preferred. It goes up to 64x64->128, if the author wants all the bits of the product. > A 53-bit multiplier producing a full 106-bit product won't be much larger than a 53-bit multiplier producing a correctly rounded 53-bit floating-point result. Yes, it will. It will have to be 106-bit wide instead of 56-bit wide.

nkurz 12y ago
I am not sure why integer multiplication is not preferred. It goes up to 64x64->128, if the author wants all the bits of the product. I'm a little confused by this also, but given the level of detail in the linked paper (http://eprint.iacr.org/2014/134.pdf http://eprint.iacr.org/2014/134.pdf) it's definitely not just an oversight. The issue may be that he's aiming for fastest possible performance on Sandy Bridge (AVX), and 256-bit integer vector multiplication wasn't added until Haswell (AVX2). And even then, 64-bit integer elements can only be done one at a time. But since he's suggesting instruction set changes, he's clearly not thinking only of backwards compatibility.
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]
makomk 12y ago
I think the design of his Curve25519 elliptic curve assumes 25-bit integers implemented using floating point arithmetic and requires them for maximum performance. I certainly haven't seen any fast integer-only implementations of it.
fdej 12y ago
Could you point to a paper that shows how to compute a correctly rounded 53-bit floating-point product without computing all 106 bits?

nkurz 12y ago

I am not sure why integer multiplication is not preferred. It goes up to 64x64->128, if the author wants all the bits of the product. I'm a little confused by this also, but given the level of detail in the linked paper (http://eprint.iacr.org/2014/134.pdf http://eprint.iacr.org/2014/134.pdf) it's definitely not just an oversight. The issue may be that he's aiming for fastest possible performance on Sandy Bridge (AVX), and 256-bit integer vector multiplication wasn't added until Haswell (AVX2). And even then, 64-bit integer elements can only be done one at a time. But since he's suggesting instruction set changes, he's clearly not thinking only of backwards compatibility.

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]

makomk 12y ago

I think the design of his Curve25519 elliptic curve assumes 25-bit integers implemented using floating point arithmetic and requires them for maximum performance. I certainly haven't seen any fast integer-only implementations of it.

fdej 12y ago

Could you point to a paper that shows how to compute a correctly rounded 53-bit floating-point product without computing all 106 bits?