title: x86-64 Big Integer Representation?
body: <p>How do hig-performance native big-integer libraries on x86-64 represent a big integer in memory?  (or does it vary?  Is there a most common way?)</p>
  
  <p>Naively I was thinking about storing them as 0-terminated strings of numbers in base 2<sup>64</sup>.</p>
  
  <p>For example suppose <code>X</code> is in memory as:</p>
  
  <pre><code>[8 bytes] Dn
  .
  .
  [8 bytes] D2
  [8 bytes] D1
  [8 bytes] D0
  [8 bytes] 0
  </code></pre>
  
  <p>Let B = 2<sup>64</sup></p>
  
  <p>Then</p>
  
  <blockquote>
    <p>X = D<sub>n</sub> * B<sup>n</sup> + ... + D<sub>2</sub> * B<sup>2</sup> + D<sub>1</sub> * B<sup>1</sup> + D<sub>0</sub></p>
  </blockquote>
  
  <p>The empty string (i.e. 8 bytes of zero) means zero.</p>
  
  <p>Is this a reasonable way?  What are the pros and cons of this way?  Is there a better way?</p>
  
  <p>How would you handle signedness?  Does 2's complement work with this variable length value?</p>
  
  <p>(Found this: <a href="http://gmplib.org/manual/Integer-Internals.html" rel="nofollow noreferrer">http://gmplib.org/manual/Integer-Internals.html</a>  Whats a limb?)</p>