title: How do modern processors carry out integer arithmetic operations?
body: <p><a href="https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations" rel="nofollow noreferrer">This</a> Wikipedia page mentions computation complexity of different mathematical operations, including addition, subtraction, multiplication and division. I'd like to focus on these four.</p>
  
  <p>First of all, every of the mentioned operations has its complexity specified as a function of number of digits. Does that mean that on real hardware adding any two <code>int64_t</code>s will take the same amount of time?</p>
  
  <p>This is an important aspect, since it would allow an attacker to gain some information about e.g. cryptographic keys from sheer observing the encrypting/decrypting party.</p>
  
  <p>Will adding two <code>int32_t</code>s take twice shorter than adding two <code>int64_t</code>s?</p>
  
  <p>Moreover, there are multiple algorithms specified for the multiplication and division operations. Which of these is used in real life processors? We know the asymptotic complexity, but there's the constant too, which is of a big importance.</p>
  
  <p>The Intel Software Developer manual for the <code>IMUL</code> instruction doesn't mention the actual algorithm used, simply states:</p>
  
  <pre><code>TMP_XP ← DEST ∗ SRC
  </code></pre>
  
  <p>The whole question pertained the x86_64 architecture at the beginning, but I'd be interesting if any other architectures (ARM, Aarch64, POWER) use some different techniques than x86.</p>