title: Fastest way to multiply two 64-bit ints to 128-bit then >> to 64-bit?
body: <p>I need to multiply two signed 64-bit integers <code>a</code> and <code>b</code> together, then shift the (128-bit) result to a signed 64-bit integer. What's the fastest way to do that?</p>
  
  <p>My 64-bit integers actually represent fixed-point numbers with <code>fmt</code> fractional bits. <code>fmt</code> is chosen so that <code>a * b &gt;&gt; fmt</code> should not overflow, for instance <code>abs(a) &lt; 64&lt;&lt;fmt</code> and <code>abs(b) &lt; 2&lt;&lt;fmt</code> with <code>fmt==56</code> would never overflow in 64-bits as the final result would be <code>&lt; 128&lt;&lt;fmt</code> and therefore fit in an int64.</p>
  
  <p>The reason I want to do that is to quickly and precisely evaluate quintic polynomials of the form <code>((((c5*x + c4)*x + c3)*x + c2)*x + c1)*x + c0</code> in fixed point format, with every number a signed 64-bit fixed-point number with <code>fmt</code> fractional bits. I'm looking for the most efficient way to achieve that.</p>