title: 64-bit fixed-point multiplication error
body: <p>I'm implementing a 64-bit fixed-point signed 31.32 numeric type in C#, based on <code>long</code>. So far so good for addition and substraction. Multiplication however has an annoying case I'm trying to solve.</p>
  
  <p>My current algorithm consist of splitting each operand into its most and least significant 32 bits, performing 4 multiplications into 4 longs and adding the relevant bits of these longs. Here it is in code:    </p>
  
  <pre><code>public static Fix64 operator *(Fix64 x, Fix64 y) {
  
      var xl = x.m_rawValue; // underlying long of x
      var yl = y.m_rawValue; // underlying long of y
  
      var xlow = xl &amp; 0x00000000FFFFFFFF; // take the 32 lowest bits of x
      var xhigh = xl &gt;&gt; 32; // take the 32 highest bits of x
      var ylow = yl &amp; 0x00000000FFFFFFFF; // take the 32 lowest bits of y
      var yhigh = yl &gt;&gt; 32; // take the 32 highest bits of y
  
      // perform multiplications
      var lowlow = xlow * ylow;
      var lowhigh = xlow * yhigh;
      var highlow = xhigh * ylow;
      var highhigh = xhigh * yhigh;
  
      // take the highest bits of lowlow and the lowest of highhigh
      var loResult = lowlow &gt;&gt; 32;
      var midResult1 = lowhigh;
      var midResult2 = highlow;
      var hiResult = highhigh &lt;&lt; 32;
  
      // add everything together and build result
      var finalResult = loResult + midResult1 + midResult2 + hiResult;
      return new Fix64(finalResult); // this constructor just copies the parameter into m_rawValue
  }
  </code></pre>
  
  <p>This works in the general case but fails in a number of scenarios. Namely, the result is off by 1.0 (decimal value), often for extremely small or large values of the operands. Here are some results from my unit tests (FromRaw() is a method that builds a Fix64 directly from a long value, without shifting it):</p>
  
  <pre><code>Failed for FromRaw(-1) * FromRaw(-1): expected 0 but got -1
  Failed for FromRaw(-4) * FromRaw(6791302811978701836): expected -1.4726290525868535041809082031 but got -2,4726290525868535041809082031
  Failed for FromRaw(2265950765) * FromRaw(17179869183): expected 2.1103311001788824796676635742 but got 1,1103311001788824796676635742
  </code></pre>
  
  <p>I'm trying to work out the logic of this on paper but I'm a bit stuck. How can I fix this?</p>