5
$\begingroup$

Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root operations on real floating point values are correctly rounded, meaning that the result of each operation is as if the operation were computed to infinite precision and then subsequently rounded according to the specified rounding mode (most commonly round to nearest, ties to even). In other words, it is guaranteed for these operations that the final floating point number is as close as possible to the true value of the operation given the mathematical values of the input floating point numbers.

A number of programming languages also offer complex floating point arithmetic. Addition and subtraction of complex floating point numbers can obviously guarantee correct rounding (treating the rounding mode as applying to each component separately), since these operations can be computed componentwise. Surely then, I assumed, the correct rounding guarantee also applies to common language-provided implementations of complex multiplication, division, and square root?

So far, I have found no evidence that this is the case, and a fair amount of evidence to the contrary. For example, this recent paper provides examples of wildly incorrect results that can be obtained from naive attempts at computing complex multiplication via multiple floating point roundings, and describes an algorithm for complex multiplication that produces results accurate to within 2 ulps (but not guaranteed 100% correctly rounded as defined above).

Claude-Pierre Jeannerod, Christophe Monat, Laurent Thévenoux (2017). More accurate complex multiplication for embedded processors. SIES 2017.

This suggests that there is no standard/widely-used sequence of fused multiply-add tricks for doing complex multiplication with correct rounding. I've also found several references to the difficulty of computing complex division in a numerically-stable fashion.

Question 1: Given floating point inputs and outputs with $n$ exponent bits and $m$ significand bits, what is the best-known worst case time complexity for computing the correctly-rounded values of complex multiplication, division, and square root?

Question 2: Are any references available for methods for computing these complex operations with correct rounding using the real floating point operations available on a standard FPU?

Improve this question
$\endgroup$
13
  • $\begingroup$ Currently looking at Jean-Michel Muller et al's Handbook of Floating-Point Arithmetic, which appears to cover these issues in section 4.5. $\endgroup$ – Aaron Rotenberg Jan 18 '19 at 20:28
  • 2
    $\begingroup$ If you could add an answer summarizing what you find out, that would be awesome! $\endgroup$ – David Richerby Jan 18 '19 at 20:46
  • 1
    $\begingroup$ @DanielMcLaury If by 'for free' you mean 'losing the guarantees for addition/subtraction', sure. It's one or the other. $\endgroup$ – orlp Jan 18 '19 at 23:37
  • 1
    $\begingroup$ @Aaron Rotenberg Your findings and impressions are accurate, and to the best of my knowledge the answers to your questions are: (1) open research problem (2) no. There is very little work happening in this space, and I know of no library or paper that shows how to guarantee correctly rounded results. $\endgroup$ – njuffa Jan 18 '19 at 23:38
  • 3
    $\begingroup$ @AaronRotenberg Vincent Lefèvre and Jean-Michel Muller, "Accurate Complex Multiplication in Floating-Point Arithmetic", January 31, 2019 (online) "Abstract : We deal with accurate complex multiplication in binary floating-point arithmetic, with an emphasis on the case where one of the operands in a "double-word" number. We provide an algorithm that returns a complex product with normwise relative error bound close to the best possible one, i.e., the rounding unit u" $\endgroup$ – njuffa Feb 23 '19 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.